简介
STL中的List与顺序表vector类似，同样是一种序列式容器，其原型是带头节点的双向循环链表。
List的使用
list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。
List的构造
构造的使用
list<int> l1; 无参构造
list<int> l2(5, 10);//放5个值为10的数据
list<int> l3(l2.begin(), l2.end()); 迭代器构造
list<int> l4(l3); 拷贝构造构造的实现
无参构造
template<class T>
struct list_node
{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& data = T()):_data(data), _next(nullptr), _prev(nullptr){}
};template<class T>
typedef list_node<T> Node;
typedef list_iterator<T> Self;
Node* _node;list()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}private:Node* _head;size_t _size;迭代器iterator
概念
此处我们可以将iterator理解为指针，指向list中的某一个节点。
以图示为例，list头节点的begin()迭代器扮演了指针的角色指向了下一个节点，依次往后。
注意
1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
iterator的使用
由于链表节点之间不连续的性质，我们对其进行遍历时也必须使用迭代器或范围for.
我们以链表的遍历打印（顺序和倒序）为例，代码如下：
正序
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array[0]));
// 使用正向迭代器正向list中的元素
// list<int>::iterator it = l.begin(); // C++98中语法
auto it = l.begin(); // C++11之后推荐写法
while (it != l.end())
{cout << *it << " ";++it;
}
cout << endl;倒序
// 使用反向迭代器逆向打印list中的元素// list<int>::reverse_iterator rit = l.rbegin();
auto rit = l.rbegin();//此句是现代写法，C++11后才支持while (rit != l.rend())
{cout << *rit << " ";++rit;
}
cout << endl;iterator的实现
begin() 与 end()
iterator begin()
{/* iterator it(_head->_next);return it;*///return iterator(_head->_next);return _head->_next; 最直接的写法
}iterator end()
{return _head;
}list接口
list capacity（容量）
目录
empty判空
bool empty() const
{return _size == 0;
}size
size_t size() const
{return _size;
}list element access（成员访问）
目录
front
void pop_front()
{erase(begin());
}back
void pop_back()
{erase(--end());
}list modifiers（链表调整）
目录
insert
void insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);// prev newnode curnewnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;++_size;
}接下来的插入复用insert代码即可。
push_front
void push_front(const T& x)
{insert(begin(), x);
}push_back
void push_back(const T& x)
{insert(end(), x);
}erase
void 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;--_size;
}同理，头删尾删代码复用删除代码即可。
pop_front
void pop_front()
{erase(begin());
}pop_back
void pop_back()
{erase(--end());
}clear
void clear()
{auto it = begin();while (it != end()){it = erase(it);}
}swap
void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}使用
插入和删除
void TestList3()
{int array[] = { 1, 2, 3 };list<int> L(array, array + sizeof(array) / sizeof(array[0]));// 在list的尾部插入4，头部插入0L.push_back(4);L.push_front(0);PrintList(L);// 删除list尾部节点和头部节点L.pop_back();L.pop_front();PrintList(L);
}clear
~list()
{clear();delete _head;_head = nullptr;
}swap
list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}list迭代器失效
与顺序表类似，list的迭代器失效也是由于iterator指向的节点发生了变化，可能不是我们想要的节点。迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
在这里，我们仍然举个例子：
void TestListIterator1()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给//其赋值l.erase(it);++it;}
}同样地，我们只要将l.erase(it)前加上“it = ”即可：
void TestListIterator1()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给//其赋值it = l.erase(it);++it;}
}
list与vector的对比
vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：
List实现总代码
#pragma once
#include <iostream>
#include <list>
#include <assert.h>
using namespace std;namespace Frenemy
{template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& data = T()):_data(data), _next(nullptr), _prev(nullptr){}};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->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};template<class T>class list{typedef list_node<T> Node;public:/*typedef list_iterator<T> iterator;typedef list_const_iterator<T> const_iterator;*/typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){/* iterator it(_head->_next);return it;*///return iterator(_head->_next);return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}list(initializer_list<T> il){empty_init();for (auto& e : il){push_back(e);}}// lt2(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}// lt1 = lt3list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}// 16:18继续void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);// prev newnode curnewnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;++_size;return newnode;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}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;--_size;return next;}size_t size() const{return _size;}bool empty() const{return _size == 0;}private:Node* _head;size_t _size;};struct AA{int _a1 = 1;int _a2 = 1;};// 按需实例化// T* const ptr1// const T* ptr2template<class Container>void print_container(const Container& con){// const iterator -> 迭代器本身不能修改// const_iterator -> 指向内容不能修改,不能进行权限放大，只能进行权限缩小typename Container::const_iterator it = con.begin();//auto it = con.begin();while (it != con.end()){//*it += 10;cout << *it << " ";++it;}cout << endl;for (auto e : con){cout << e << " ";}cout << endl;}void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){*it += 10;cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;print_container(lt);list<AA> lta;lta.push_back(AA());lta.push_back(AA());lta.push_back(AA());lta.push_back(AA());list<AA>::iterator ita = lta.begin();while (ita != lta.end()){//cout << (*ita)._a1 << ":" << (*ita)._a2 << endl;// 特殊处理，本来应该是两个->才合理，为了可读性，省略了一个->cout << ita->_a1 << ":" << ita->_a2 << endl;cout << ita.operator->()->_a1 << ":" << ita.operator->()->_a2 << endl;++ita;}cout << endl;}void test_list2(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int> lt2(lt1);print_container(lt1);print_container(lt2);list<int> lt3;lt3.push_back(10);lt3.push_back(20);lt3.push_back(30);lt3.push_back(40);lt1 = lt3;print_container(lt1);print_container(lt3);}void func(const list<int>& lt){print_container(lt);}void test_list3(){// 直接构造list<int> lt0({ 1,2,3,4,5,6 });// 隐式类型转换list<int> lt1 = { 1,2,3,4,5,6,7,8 };const list<int>& lt3 = { 1,2,3,4,5,6,7,8 };func(lt0);func({ 1,2,3,4,5,6 });print_container(lt1); }
}
