前言
这个是C语言中的带头双向循环链表，这么设计更方便头插尾插，end()迭代器指向头部，既然是带头双向循环链表，意味着每个结点都存放一个next和prev指针，通过头结点可以快速找到尾结点，任意位置插入都在常数时间内(得益于迭代器)。
如果熟悉C语言模拟的带头双向循环链表，list就会熟悉，list真正比较难的点在于迭代器和const迭代器，因为内部空间物理上不连续，逻辑上连续，无法像vector和string那样typedef T* iterator;这里留个悬念，后面讲。
一、list类以及常用接口和函数
构造函数
和vector对比一下发现基本上一样，也没啥可说的了。
迭代器
既然是双向,就和vector的一样，普通，const，反向，const反向。
容量
和vector差别很大了，因为他是链表，无法提前扩容，也没有capacity一说。
重要函数
也和vector类似，vector没实现头插和头删因为效率太低（可以insert(begin())来哦头插），但是list的头插，头删，尾插，尾删效率非常高，其余接口没啥可说的。
操作
演示：
void Test_splice(list<int> lt,list<int> lt1)
{
lt.splice(lt.begin(),lt1);
cout << "splice后:";
for (auto e : lt) {
cout << e << ' ';
}
cout << endl;
}
void Test_remove(list<int> lt)
{
lt.remove(2);
lt.remove(4);
cout << "remove后:";
for (auto e : lt) {
cout << e << ' ';
}
cout << endl;
}
void Test_remove_if(list<int> lt)
{
lt.remove_if([](int a) {return a % 2 == 0; });
cout << "remove偶数后:";
for (auto e : lt) {
cout << e << ' ';
}
cout << endl;
}
void Test_unique(list<int> lt)
{
lt.unique();
cout << "unique后:";
for (auto e : lt) {
cout << e << ' ';
}
cout << endl;
}
void Test_merge(list<int> lt,list<int> lt1)
{
lt.sort(), lt1.sort();
lt.merge(lt1);
cout << "merge后:";
for (auto e : lt) {
cout << e << ' ';
}
cout << endl;
}
void Test_sort(list<int> lt)
{
lt.sort();
cout << "sort后:";
for (auto e : lt) {
cout << e << ' ';
}
cout << endl;
}
void Test_reverse(list<int> lt)
{
lt.reverse();
cout << "reverse后:";
for (auto e : lt) {
cout << e << ' ';
}
cout << endl;
}
int main()
{
list<int> lt{5,3,1,2,2,5,4,6};
list<int> lt1{ 7,8,9,10,11 };
cout << "原lt为{5,3,1,2,2,5,4,6}" << endl;
cout << "原lt1为{ 7,8,9,10,11 }" << endl;
Test_splice(lt, lt1);
Test_remove(lt);
Test_remove_if(lt);
Test_unique(lt);
Test_merge(lt, lt1);
Test_sort(lt);
Test_reverse(lt);
return 0;
}
用法用几次基本就会了，但是有几个需要注意的点：
1.splice
注意，如果传的是右值属性，或者传的拷贝，此时splice后，右值x被悬空，不能使用x。
2.merge
要求合并前两个list均有序。
3，sort
我问你，库里有一个sort，那这个sort还有用吗？当然，因为库里要求的是随机迭代器，list是双向迭代器。但是sort的意义不大，因为如果想要有序用list本身就不是一个明智的选择，list排序很麻烦，不如vector / set。
二、迭代器失效问题
insert
insert会失效吗？不会，因为insert不会涉及到开空间，只是把结点连接起来就可以，但是为了保持一致性，库里的insert同样返回的是新插入元素位置的迭代器。
erase
erase会失效吗？包的，你那个位置都没了当然失效了，所以erase会导致当然位置的迭代器失效，解决方法：返回值给原迭代器下一个迭代器的位置
三、list的模拟实现
list除了迭代器还是比较简单的，把_prev和_next链接好就可以，注意控制好_head
结点：
template<class T>
struct list_node
{
T _val;
list_node<T>* _next;
list_node<T>* _prev;
list_node(const T&x)
:_val(x),
_next(nullptr)
,_prev(nullptr)
{}
};
list基本框架
还是加一个_sz来存储数据，这样求size()就可以快速拿到，否则还要遍历。
namespace myspace {
template<class T>
class list {
typedef list_node<T> Node;
public:
list()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
_sz = 0;
}
void push_back(const T& x)
{
Node* newnode = new Node(x);
Node* _tail = _head->_prev;
_head->_prev = newnode;
newnode->_next = _head;
_tail->_next = newnode;
newnode->_prev = _tail;
_sz++;
}
private:
Node* _head;
size_t sz;
};
}
当然，库里push_back还是复用的insert,所以我们来讲迭代器的实现。
普通迭代器
list的迭代器库里设计的很有意思，让我们一点一点讲下去。
首先想普通迭代器怎么设计？ 直接使用T*一定不行，内存上不连续，使用不了，这里C++类里可以重载++，–，*的优势就来了，我们可以定义一个类，只分装一个结点指针，++就是让这个指针往next走，解引用就是拿到_node里的值，相等就是判断_node相不相等，begin就是iterator(_head->next)来构造。
大致写一个就是：
template<class T>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T> Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_val;
}
Self& operator++()//前置加加
{
_node = _node->_next;
return *this;
}
Self operator++(int)//后置加加
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& x)const
{
return _node != x._node;
}
bool operator==(const Self& x)const
{
return _node == x._node;
}
T* operator->()
{
return &(operator*());
}
};
//list类里
typedef list_iterator<T> iterator;
//迭代器
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
这里operator->的实现很有意思，当然可以直接对val取地址，这两个结果一样。
设一个Self是因为名字过长，这样比较方便。
这样遍历的代码就能跑起来了。
const迭代器
下一步：const迭代器怎么设计？先想一个问题，const迭代器是什么变成const属性？其实也就是operator* 和 operator->拿到的内容不能改变，有一种比较明显的思路，就是再分装一个类叫const_list_iterator去控制，当然这样是可以的，但是库里很杜绝这种非常冗余的行为，就是两份非常相似的代码不写一份而写两份，这块我们在set和map还会充分提现这个思想，库里怎么设计的呢？只能说真的很牛这个设计，它额外控制了两个模板参数来控制operator* 和operator->的返回值，在list里通过传const类型就是const迭代器，非const就是普通迭代器，
//list迭代器
template<class T,class Ref,class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_val;
}
Self& operator++()//前置加加
{
_node = _node->_next;
return *this;
}
Self operator++(int)//后置加加
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& x)const
{
return _node != x._node;
}
bool operator==(const Self& x)const
{
return _node == x._node;
}
Ptr operator->()
{
return &(operator*());
}
};
list类内部：
typedef list_iterator<T, T&,T*> iterator;
typedef list_iterator<T, const T&,const T*> const_iterator;
这样设计就可以只用一份代码来实现const和非const迭代器，但是这里实际上还是两份代码，因为模板会编译出两份。
有了迭代器插入和删除就好写了，这也是为什么可以O(1)插入的原因。
insert
iterator insert(iterator pos, const T& x)
{
Node* _node = pos._node;
Node* _prev = pos._node->_prev;
Node* newnode = new Node(x);
_prev->_next = newnode;
newnode->_prev = _prev;
_node->_prev = newnode;
newnode->_next = _node;
_sz++;
return iterator(newnode);
}
erase
iterator erase(iterator pos)
{
assert(pos != end());
Node* _prev = pos._node->_prev;
Node* _next = pos._node->_next;
_prev->_next = _next;
_next->_prev = _prev;
delete pos._node;
_sz--;
return iterator(_next);
}
其余头插头删和尾插尾删均可以复用erase和insert。
完善一下其他函数
构造
list(const initializer_list<T>& x)
{
empty_init();
auto it = x.begin();
while (it != x.end())
{
push_back(*it);
it++;
}
}
list(const myspace::list<T>& x)
{
empty_init();
auto it = x.begin();
while (it != x.end())
{
push_back(*it);
++it;
}
}
private:
void empty_init()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
_sz = 0;
}
重载operator=
void swap(list<T>& x)
{
std::swap(_head, x._head);
std::swap(_sz, x._sz);
}
myspace::list<T>& operator=(const myspace::list<T>& x)
{
list<T> tmp(x);
swap(tmp);
return *this;
}
myspace::list<T>& operator=(myspace::list<T>&& x)
{
swap(x);
return *this;
}
析构
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
it++;
}
_sz = 0;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
写clear和empty_init主要是为了方便，不写也可以。
完整模拟
四、list的优缺点
和vector相对：
优点就是插入和删除效率很高，适合频繁插入和删除的场景，也不涉及扩容问题
缺点：1.不支持随机访问，访问元素是O(n)
2.底层空间不连续，缓存效率低，空间利用率低
五、总结
list的迭代器需要掌握，后面的map和set还会用到类似的思想。
还需要掌握vector和list的区别，可以从底层，随机访问，插入删除，空间，迭代器等场景来做对比。