list
1. list介绍
- list文档（非官方）
官方文档- list是双向带头循环链表，它可以在常数范围内的任意位置进行插入和删除操作。
- list的迭代器是双向迭代器(bidirectional iterator)，它可以前后双向迭代。
由容器的底层结构决定，STL迭代器有不同的种类：
- list的底层空间如下图所示：
- 正因list的底层空间如此，它相比其他容器：
优点：在任意位置插入、删除元素的执行效率更高（相比vector、deque等）；
缺点：不支持位置的随机访问，要访问某个节点，需要迭代器迭代；需要开辟额外的空间来储存下一个节点、上一个节点的地址；缓存命中率低。
2. list的常用接口
- 与vector一样，list的许多接口中有很多别名：
-
构造函数(constructor)
(constructor) 功能 explicit list (const allocator_type& alloc = allocator_type());默认构造函数 explicit list (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type());用n个val值初始化 template <class InputIterator>list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());用迭代器初始化（可以允许其他类型作为参数初始化） list (const list& x);拷贝构造函数 list<int> lt1; list<int> lt2(3, 2); int nums[] = { 1,2,3 }; list<int> lt3(arr, arr + 3); list<int> lt4(v3); -
容量操作
函数 功能 size_type size(); const 返回有效元素个数 bool empty(); const 判断是否为空 void resize (size_type n, value_type val = value_type()); 改变有效元素个数 -
迭代器
函数 功能 iterator begin();const_iterator begin() const; 返回容器开头的位置的迭代器 iterator end();const_iterator end() const; 返回容器最后一个有效元素的下一个位置的迭代器 reverse_iterator rbegin();const_reverse_iterator rbegin() const; 返回容器最后一个有效元素的位置的迭代器 reverse_iterator rend();const_reverse_iterator rend() const; 返回容器开头的前一个位置的迭代器 关于list的迭代器：
-
迭代器一般是指针，在string和vector中，因为底层空间是连续的，所以它们的迭代器可以直接使用指针；但是list不行，因为它的空间不是连续的，是多块由指针连接的小空间。因此list的迭代器必须做出改变，即重新封装。
-
list的迭代器如下：
list迭代器被重新封装成为一个类，它的成员变量是一个节点的类型的指针，指向节点；另外在迭代器类中，还实现了一系列运算符重载，如*/->/!=/==/++/--，使得其与别的容器的迭代器功能一致。 -
关于迭代器内运算符
->的重载：
重载operator->，编译器进行了特殊处理。
struct A { A(int a1 = 0, int a2 = 0) : _a1(a1) , _a2(a2) { } int _a1; int _a2; }; void Test() { list<A> la; A aa(1, 2); la.push_back(aa); list<A>::iterator it = la.begin(); cout << it->_a1 << endl; }operator->返回的是
A*，it->_a1就等价于A * _ a1，这不合语法，正确写法应该是it->->_a1，但是这么写很难看，于是编译器做了优化，自动替我们加上了一个->，于是我们只需写成这样即可：it->_ val- 迭代器提供了一种不暴露容器底层设计的方法来访问容器内容。
-
-
访问元素
函数 功能 reference front();const_reference front() const; 访问链表开头一个元素 reference back();const_reference back() const; 访问链表最后一个元素 int nums[] = { 1,2,3 }; list<int> lt(arr, arr + 3); cout << lt.front() << endl; cout << lt.back() << endl; -
修改操作
函数 功能 void push_back (const value_type& val); 尾插一个值 void pop_back(); 尾删一个值 void push_front (const value_type& val); 头插一个值 void pop_front(); 头删一个值 insert 在某个位置插入元素 erase 删除某个位置的元素 void swap (list& x); 交换两个list对象 void clear(); 清空有效元素 -
链表操作
STL还提供了一些链表操作，如sort、reverse等，但是不常使用，这里就不多介绍了，若要查看，请移步官方文档。
3. 模拟实现list（部分接口）
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace Myspace
{
template <class T>
struct list_node
{
list_node(const T& value = T())
: _next(nullptr)
, _pre(nullptr)
, _val(value)
{ }
list_node<T>* _next;
list_node<T>* _pre;
T _val;
};
// 正向迭代器
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef __list_iterator<T, Ref, Ptr> Self; // Self表示自己
typedef list_node<T> Node;
__list_iterator(Node* node = nullptr)
: _node(node)
{ }
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self operator++(int)
{
Self tmp = *this;
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_pre;
return *this;
}
Self operator--(int)
{
Self tmp = *this;
_node = _node->_pre;
return tmp;
}
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &(_node->_val);
}
bool operator!=(const Self& it) const
{
return it._node != _node;
}
bool operator==(const Self& it) const
{
return it._node == _node;
}
Node* _node; // 当前迭代器所指向的节点的指针
};
template <class T>
class list
{
typedef list_node<T> Node;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
///
// <构造>
void CreatHead()
{
_head = new Node;
_head->_next = _head->_pre = _head;
}
list()
{
CreatHead();
}
list(int n, const T& _value = T())
{
CreatHead();
while (n--)
{
push_back(_value);
}
}
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
CreatHead();
while (first != last)
{
push_back(*first);
++first;
}
}
list(const list<T>& lt)
{
CreatHead();
//for (auto e : lt)
//{
// push_back(e);
//}
list<T> temp(lt.begin(), lt.end());
this->swap(temp);
}
list<T> operator=(list<T> lt)
{
if (lt._head != _head)
{
swap(lt);
}
return *this;
}
///
// <迭代器>
iterator begin()
{
return _head->_next; // 单参数的构造函数，可以进行整型提升，Node* 提升为iterator
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next; // 单参数的构造函数，可以进行整型提升，Node* 提升为iterator
}
const_iterator end() const
{
return _head;
}
///
// <容量>
size_t size()
{
size_t sz = 0;
Node* cur = _head->_next;
while (cur != _head)
{
sz++;
++cur;
}
return sz;
}
bool empty()
{
return _head == _head->_pre;
}
void resize(size_t n, const T& value = T())
{
size_t sz = size();
if (n < sz)
{
while (n < sz)
{
pop_back();
sz--;
}
}
else
{
while (sz < n)
{
push_back(value);
sz++;
}
}
}
///
// <访问>
T& front()
{
return _head->_next->_val;
}
const T& front() const
{
return _head->_next->_val;
}
T& back()
{
return _head->_pre->_val;
}
const T& back() const
{
return _head->_pre->_val;
}
///
// <删除、插入>
void push_back(const T& value)
{
insert(end(), value);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& value = T())
{
insert(begin(), value);
}
void pop_front()
{
erase(begin());
}
iterator insert(iterator pos, const T& value = T())
{
Node* newnode = new Node(value); // 待插入的新节点
Node* cur = pos._node; // 取出pos迭代器的节点
newnode->_pre = cur->_pre;
newnode->_next = cur;
cur->_pre->_next = newnode;
cur->_pre = newnode;
return newnode;
}
iterator erase(iterator pos)
{
assert(pos._node != _head);
Node* cur = pos._node;
Node* ret = cur->_next; // 保留一下返回值
cur->_pre->_next = cur->_next;
cur->_next->_pre = cur->_pre;
delete cur;
return ret;
}
void clear()
{
Node* cur = _head->_next;
while (cur != _head)
{
_head->_next = cur->_next;
delete cur;
cur = _head->_next;
}
_head->_next = _head->_pre = _head;
}
void swap(list<T>& lt)
{
std::swap(lt._head, _head);
}
private:
Node* _head;
};
}
注意：
- 构造函数
vector(int n, const T& value = T())接口需要重载多个（int/size_t/long），以防止创建对象时（vector<int> v(2,3);）编译器自动匹配到vector(InputIterator first, InputIterator last)这个接口。
原因：编译器总会选择最匹配的接口。 - 在扩容时拷贝数据的时候，不要使用memcpy（上述代码的第151行），原因如下：
如果模板实例化为string，那么此时就相当于memcpy(string1, string2, size)，将两个string类memcpy，一定是浅拷贝，因为string类本身有个char*的指针，需要动态开辟空间，memcpy仅仅是将两个指针指向了同一块空间，并没有开辟新的空间。
直接赋值即可，赋值会调用string自己的赋值运算符重载，它自己会实现深拷贝。
不止是string，其他任何动态管理空间的类都是如此。
4. 迭代器失效
list的结构是链状表，正因为它不是一块连续的空间，它的迭代器失效问题没有string和vector多。
只有在删除数据的时候，才可能引起迭代器失效。
-
链表的
insert没有迭代器失效的问题！
因为没有扩容，不需要挪动数据，位置没有改变，迭代器还是指向那个节点。 -
但是
earse有迭代器失效的问题！
因为节点释放了，迭代器却依旧指向那个位置。
STL为erase增添了返回值，我们用完erase后要接收它的返回值，它返回的是删除的节点的下一个节点。
`，将两个string类memcpy，一定是浅拷贝，因为string类本身有个char*的指针，需要动态开辟空间，memcpy仅仅是将两个指针指向了同一块空间，并没有开辟新的空间。
直接赋值即可，赋值会调用string自己的赋值运算符重载，它自己会实现深拷贝。
不止是string，其他任何动态管理空间的类都是如此。
4. 迭代器失效
list的结构是链状表，正因为它不是一块连续的空间，它的迭代器失效问题没有string和vector多。
只有在删除数据的时候，才可能引起迭代器失效。
-
链表的
insert没有迭代器失效的问题！
因为没有扩容，不需要挪动数据，位置没有改变，迭代器还是指向那个节点。 -
但是
earse有迭代器失效的问题！
因为节点释放了，迭代器却依旧指向那个位置。
STL为erase增添了返回值，我们用完erase后要接收它的返回值，它返回的是删除的节点的下一个节点。