一、list的介绍
list是可以在常数范围内在任意位置进行效率为O(1)的插入和删除的序列式容器，并且该容器可以前后双向迭代。
list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素，关于双向链表的细节可以移步数据结构（二）：链表。
二、list的使用
1.构造函数
常用的构造函数有如下四种：
代码如下：
int main()
{
list<int> lt1;//空的链表
list<int> lt2(4, 100);//链表有4个值为100的结点
list<int> lt3(lt2);//用lt2拷贝构造出lt3
list<int> lt4(lt2.begin(), lt2.end());//用lt2的迭代器区间构造lt4
return 0;
}
调试如下：
2.遍历
由于链表底层的地址不连续，所以不再支持下标+[]的遍历方式，但之前提到过迭代器是所有容器统一的遍历方式，所以仍可用迭代器来遍历链表。由于范围for会被编译器替换成迭代器，所以也可用范围for遍历。
代码如下：
int main()
{
list<int> lt1;//空的链表
list<int> lt2(4, 100);//链表有4个值为100的结点
list<int> lt3(lt2);//用lt2拷贝构造出lt3
list<int> lt4(lt2.begin(), lt2.end());//用lt2的迭代器区间构造lt4
//迭代器遍历
list<int>::iterator it1 = lt2.begin();
while (it1 != lt2.end())
{
cout << *it1 << " ";
it1++;
}
cout << endl;
//范围for遍历
for (auto& e : lt4)
cout << e << " ";
cout << endl;
return 0;
}
运行结果如下：
3.数据的插入与删除
（1）尾部的插入与删除
代码如下：
//打印list内容的函数
template<class T>
void print(const list<T>& lt)
{
list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
int main()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
print(lt);//1 2 3 4 5
lt.pop_back();//删掉尾部的5
print(lt);//1 2 3 4
return 0;
}
运行结果如下：
（2）头部的插入与删除
之前的string和vector两个容器不支持头部插入与删除是因为它们的底层结构是数组，在头部插入、删除时需要挪动数据，消耗较大，所以不支持这两个操作。
但链表底层不连续，任意位置插入删除的效率为O(1)，不用担心挪动数据引起的消耗，所以提供了这两个函数。
代码如下：
int main()
{
list<int> lt;
lt.push_front(1);
lt.push_front(2);
lt.push_front(3);
lt.push_front(4);
lt.push_front(5);
print(lt);//5 4 3 2 1
lt.pop_front();//删掉头部的1
print(lt);//5 4 3 2
return 0;
}
运行结果如下：
（3）任意位置插入与删除
代码如下：
int main()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
print(lt);
auto pos = ++lt.begin();//pos指向lt中的2
lt.insert(pos, -100);//在pos位置前插入-100
print(lt);
lt.insert(pos, 3, 60);//在pos位置前插入3个60
print(lt);
lt.erase(pos);//删除pos位置的数据
print(lt);
return 0;
}
运行结果如下：
4.一些简单的操作函数
（1）clear
清空链表中的数据。
代码如下：
int main()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
print(lt);
lt.clear();//清空
print(lt);
return 0;
}
运行结果如下：
（2）swap
注意list类内部的swap和全局的swap不同，list类内部的swap执行时效率更高，这一点可以在下面模拟实现的时候看到。
代码如下：
int main()
{
vector<int> v = { 1, 2, 3, 4, 5 };
list<int> lt1(v.begin(), v.end() - 3);
list<int> lt2(v.begin(), v.end());
cout << "lt1:";
print(lt1);
cout << "lt2:";
print(lt2);
lt1.swap(lt2);
cout << "lt1:";
print(lt1);
cout << "lt2:";
print(lt2);
return 0;
}
运行结果如下：
三、list的模拟实现
1.结点结构
之前提到STL中的list是用双链表实现的，所以不难得出下面的结构。
代码如下：
template<class T>
struct _list_node//用struct，成员默认为public
{
T _val;
_list_node<T>* _prev;//指向前一个结点
_list_node<T>* _next;//指向后一个结点
};
把默认构造函数加入到_list_node结构体中。
代码如下：
template<class T>
struct _list_node
{
_list_node(const T& val = T())
:_val(val)
, _prev(nullptr)
, _next(nullptr)
{}
T _val;
_list_node<T>* _prev;
_list_node<T>* _next;
};
2.迭代器
list底层是不连续的一个个结点，结构与vector和string有很大差别，所以list的迭代器也与vector和string的迭代器差别很大。在list的模拟实现中，迭代器是很重要的一部分。
（1）初步实现
1）结构
首先这里的迭代器还是结点的一个指针，只不过在解引用、++、!=等行为上与原生指针不同，需要封装，在下面封装的过程中也可以看到C++的优越之处。
代码如下：
template<class T>
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T> self;//typedef来简化代码
node* _pnode;
_list_iterator(node* pnode)
:_pnode(_pnode)
{}
};
2）opearator*
迭代器是结点的指针，如果直接解引用得到是这个结点的地址，但实际希望的是得到结点内的数据(_val)，所以这里需要重载opearator*
代码如下：
template<class T>
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T> self;
node* _pnode;
T& operator*()
{
return _pnode->_val;//得到结点内的数据(_val)并返回
}
};
3）opearator!=
迭代器比较大小时，比较的不是迭代器本身，而应该是其中_pnode是否相等，所以这里要重载opearator!=
代码如下：
template<class T>
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T> self;
node* _pnode;
bool operator!=(const self& s)
{
return _pnode != s._pnode;
}
};
4）operator++
迭代器++也不能直接让_pnode++，因为链表底层的地址不是连续的，直接++可能会造成非法访问，实际想要的++是去访问下一个结点，这里通过重载来实现。（这里是后置++）
代码如下：
template<class T>
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T> self;
node* _pnode;
self& operator++()
{
_pnode = _pnode->_next;
return _pnode;
}
};
5）构造函数
不写构造函数时，编译器会自动进行浅拷贝。具体到这里，希望的就是产生的迭代器内的_pnode直接和传入的结点指针相同，所以不需要自己实现。
6）析构函数
如果要写析构函数，最多也只是把_pnode释放并置空，但是迭代器只是访问链表中的一个结点，这个结点释放与否是整张链表才可以处理的，所以这里析构函数也不需要写。
7）其它操作
下面的操作重载比较简单，这里不多赘述。
代码如下：
template<class T>
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T> self;
node* _pnode;
self operator++(int)//前置++
{
self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
self operator--(int)//前置--
{
self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
bool operator==(const self& s)
{
return _pnode == s._pnode;
}
};
（2）问题
上面的迭代器看起来没有问题，但在遇到const类型时会出现迭代器修改了const修饰的变量的内容。
代码如下：
template<class T>
void func(const List<T>& lt)
{
List<T>::const_Iterator it = lt.begin();
while (it != lt.end())
{
*it += 2;//虽然it是const类型的迭代器，但是这里对*it修改编译器并不会报错
cout << *it << " ";
it++;
}
cout << endl;
}
所以上面的实现的迭代器是有问题的，它无法处理const类型的迭代器修改值的问题，所以需要如下修改即可。
（由于代码重复性太高且上面已给出，这里只截图）
截图如下：
可以看到，两份代码、逻辑都几乎完全一样，重复性太高，所以这样的代码很差。
（3）修正
STL库中的list的模板参数有三个，数据类型T，T的引用Ref，T的指针Ref，加上后面两个参数后即可用一份代码完成普通迭代器和const迭代器的功能。
（代码与上面大同小异，只是修改了返回值的类型）
代码如下：
// 数据类型T T& T*
template<class T, class Ref, class Ptr>
struct _list_iterator
{
//拷贝构造、赋值重载、析构不需要写
//数据类型为T的一个结点
typedef _list_node<T> node;
//数据类型为T的迭代器
typedef _list_iterator<T, Ref, Ptr> self;
//构造函数
_list_iterator(node* pnode)
:_pnode(pnode)
{}
Ref operator*()
{
return _pnode->_val;
}
Ptr operator->()
{
return &_pnode->_val;//返回值的地址
}
bool operator!=(const self& s) const
{
return _pnode != s._pnode;
}
bool operator==(const self& it) const
{
return _pnode == s._pnode;
}
//前置++
self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
//后置++
self operator++(int)
{
self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
self operator--(int)
{
self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
//成员变量：指向某一个结点的指针
node* _pnode;
};
同时在list类中typedef一下两种迭代器。
代码如下：
template<class T>
class List
{
public:
//数据类型为T的普通迭代器
typedef _list_iterator<T, T&, T*> Iterator;
//数据类型为T的const迭代器
typedef _list_iterator<T, const T&, const T*> const_Iterator;
private:
node* _head;
};
3.成员函数的实现
注意链表中的成员变量是需要一个头结点即可，根据头结点的prev、next指针及迭代遍历即可访问到链表中所有的结点。
头结点的作用只是标示链表的开始，并用它的prev和next指针访问整个链表，本身是不存数据的（就算存了也不会访问到）。
链表的头（第一个存放有效数据的结点）是头结点的next指向的结点，尾（最后一个存放有效数据的结点的前一个结点）是头结点。
（1）默认构造函数
默认构造函数在实现时注意将_head->_next、_head->_prev都初始化为_head自己，这样在后续函数的实现时会方便很多，如果设为nullptr，后面的处理中可能会需要多次解决空指针访问的问题。
代码如下：
template<class T>
class List
{
//数据类型为T的一个结点
typedef _list_node<T> node;
public:
List()
{
//注意虽然头结点的值不重要，但也不能给0，应为T的类型不一定是int
//这里给T()
_head = new node(T());
//头结点的prev和next都指向头结点
_head->_next = _head;
_head->_prev = _head;
}
private:
node* _head;//只需要一个头结点，根据它即可找到链表中所有的结点
};
（2）拷贝构造
拷贝构造就是先生成一个头结点，然后依次把结点连接到头结点后面。
代码如下：
template<class T>
class List
{
//数据类型为T的一个结点
typedef _list_node<T> node;
public:
List(const List<T>& lt)
{
//生成一个新的头结点
_head = new node(T());
_head->_next = _head;
_head->_prev = _head;
//依次连接后面的结点
for (const auto& e : lt)
push_back(e);//这个函数在后面会实现
}
private:
node* _head;//只需要一个头结点，根据它即可找到链表中所有的结点
};
（3）赋值运算符重载
实现方法一：先清空当前链表，然后依次把数据连接到当前链表内。
代码如下：
template<class T>
class List
{
//数据类型为T的一个结点
typedef _list_node<T> node;
public:
List<T>& operator=(const List<T>& lt)
{
if (this != <)
{
//先清空链表
this->clear();
//然后把数据依次连接到*this的头后面
for (const auto& e : lt)
push_back(e);
}
return *this;
}
private:
node* _head;//只需要一个头结点，根据它即可找到链表中所有的结点
};
实现方法二：传参时生成一个临时拷贝，把这个临时拷贝的头结点和*this的头结点交换，因为头结点后面连接着一个链表所有的数据，所以交换头结点即交换了所有的数据。
代码如下：
template<class T>
class List
{
//数据类型为T的一个结点
typedef _list_node<T> node;
public:
// 注意传参时不传引用，编译器就会自动生成临时拷贝
List<T>& operator=(List<T> lt)
{
swap(_head, lt._head);
return *this;
}
private:
node* _head;//只需要一个头结点，根据它即可找到链表中所有的结点
};
（4）析构函数
用clear函数（之后会实现）清空链表中的数据后释放头结点即可。
代码如下：
template<class T>
class List
{
public:
~List()
{
clear();
delete _head;
_head = nullptr;
}
private:
node* _head;//只需要一个头结点，根据它即可找到链表中所有的结点
};
（5）一些简单函数的实现
下面实现的函数较为简单，需要注意的地方都已用注释标出，这里不再赘述。
代码如下：
template<class T>
class List
{
//数据类型为T的一个结点
typedef _list_node<T> node;
public:
//数据类型为T的迭代器
typedef _list_iterator<T, T&, T*> Iterator;
typedef _list_iterator<T, const T&, const T*> const_Iterator;
Iterator begin()
{
//_head->_next为链表实际的头（存有效数据的第一个结点）
//_head->_next类型为node*，前面的Iterator在这里可以理解为类型强转
return Iterator(_head->_next);
}
const_Iterator begin() const
{
return Iterator(_head->_next);
}
Iterator end()
{
//尾是头结点
return Iterator(_head);
}
const_Iterator end() const
{
return Iterator(_head);
}
bool empty()
{
return begin() == end();
}
//遍历得到链表的数据个数
size_t size()
{
size_t sz = 0;
Iterator it = begin();
while (it != end())
{
sz++;
it++;
}
return sz;
}
//遍历清除链表中的所有结点
void clear()
{
Iterator it = begin();
while (it != end())
it = erase(it);
}
private:
node* _head;//只需要一个头结点，根据它即可找到链表中所有的结点
};
（6）数据的插入与删除
1）insert
在某一位置前插入一个元素。
代码如下：
template<class T>
class List
{
public:
//在pos前插入val
void insert(Iterator pos, const T& val)
{
assert(pos._pnode != nullptr);
//找到前后的结点
node* cur = pos._pnode;
node* prev = cur->_prev;
node* newnode = new node(val);
//连接前后的结点
cur->_prev = newnode;
newnode->_next = cur;
newnode->_prev = prev;
prev->_next = newnode;
}
private:
node* _head;//只需要一个头结点，根据它即可找到链表中所有的结点
};
2）erase
删除某一位置的元素。注意这里为了防止迭代器失效要返回下一个结点的迭代器。
代码如下：
template<class T>
class List
{
public:
//删除pos位置的数据
Iterator erase(Iterator pos)
{
assert(pos._pnode != nullptr);
assert(pos != end());
//找到前后的数据
node* prev = pos._pnode->_prev;
node* next = pos._pnode->_next;
//删掉当前位置的结点
delete pos._pnode;
//连接
prev->_next = next;
next->_prev = prev;
return Iterator(next);
}
private:
node* _head;//只需要一个头结点，根据它即可找到链表中所有的结点
};
3）链表头尾数据的插入与删除
这里可以复用insert和erase的代码，但是要注意传参时参数的位置，详见注释。
代码如下：
template<class T>
class List
{
public:
void push_back(const T& val)
{
//在end()前插入val（也即头结点的前面），变成新的尾
insert(end(), val);
}
void push_front(const T& val)
{
//在begin()前插入val（也即头结点的后面），变成新的头
insert(begin(), val);
}
void pop_back()
{
//--end()挪到头结点的前面（也即最后一个结点）
erase(--end());
}
void pop_front()
{
erase(begin());
}
private:
node* _head;//只需要一个头结点，根据它即可找到链表中所有的结点
};