阅读量:0
list就是我们之前学过的链表，我们都知道链表和string、vector不一样，链表自身是不连续的一段内存，而string和vector是连续的。并且这里的list是双向带头的链表。因此我们先来看链表的节点：
template<class T> struct list_node { list_node(const T& val = T()) :next(nullptr) ,prev(nullptr) ,data(val) {} list_node<T>* next; list_node<T>* prev; T data; };我们使用模板来表示链表的一个节点，这一个节点里面有一个T类型的数据，并且有两个方向next和prev，两个节点的指针来存储另外两个节点的信息。
对于容器，我们都需要有迭代器，像我们使用过的string 和 vector 都有迭代器，我们在模拟基础实现的时候，直接使用了原生指针typedef成了迭代器，但是对于链表来说，它的内存是不连续的，因此不能进行随机访问，也就是不能进行+，+=这些操作，因此我们必须封装一个迭代器：
template<class T,class Ref, class Ptr> struct list_iterator { typedef list_node<T> node; typedef list_iterator<T,Ref,Ptr> self; list_iterator(node* val) :_node(val) {} Ref operator*() { return _node->data; } Ptr operator->() { return &_node->data; } 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& val) const { return _node != val._node; } bool operator==(const self& val) const { return _node == val._node; } node* _node; };这里我们使用了模板来完成链表的迭代器，对于iterator 和 const_iterator，区别就是能不能对此处位置值的修改，因此我们完全可以使用模板来完成两个迭代器。
T这个参数就是数据类型，也就是我们链表里面存的是什么类型的数据。对于Ref和Ptr，其实就是在迭代器那里，如果我们传入的是const_iterator，那么Ref，Ptr也就会被编译器推断成相应正确的类型。
Ref operator*() { return _node->data; } Ptr operator->() { return &_node->data; }迭代器的本质其实也就是一个节点，只不过是对这个节点进行了封装，我们在使用迭代器时，就可以通过迭代器来操作相应的节点位置。并且我们对迭代器也进行了相应的运算符重载，例如前置、后置++(--)，!= 和 ==，解引用* ，->等操作，这些操作都比较简单，返回对应的结果即可，唯一要注意的是，->运算符重载时，是返回节点数据的地址。
下面我们来看看list类的实现：
class list { public: typedef list_node<T> node; typedef list_iterator<T,T&,T*> iterator; typedef list_iterator<T, const T&, const T*> const_iterator; private: node* _head; size_t _size; };我们先来看看三个typedef：
- typedef list_node<T> node;这个比较好理解，我们在创建一个节点时，需要使用到 list_node<T>，因为太长所以直接定义为node。
- typedef list_iterator<T,T&,T*> iterator;
- typedef list_iterator<T, const T&, const T*> const_iterator;
这里就能明白，为什么我们在封装迭代器的时候需要传入三个模板参数，当我们使用不同的迭代器时，传入的参数就不一样，就可以满足普通迭代器和const迭代器的区别了。
list内部成员就只有一个头节点和 _size实时记录list的大小。
我们先来看list的一些构造函数：
void Init_Empty() { _head = new node; _head->next = _head; _head->prev = _head; _size = 0; } list() { Init_Empty(); } list(size_t n, const T& val = T()) { Init_Empty(); for (size_t i = 0; i < n; ++i) { push_back(val); } } list(int n, const T& val = T()) { Init_Empty(); for (int i = 0; i < n; ++i) { push_back(val); } } template <class Iterator> list(Iterator first, Iterator last) { Init_Empty(); while (first != last) { push_back(*first); ++first; } } list(const list<T>& lt) { Init_Empty(); for (auto e : lt) push_back(e); } void swap(list<T> lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } list<T>& operator=(const list<T> lt) { swap(lt); return *this; } ~list() { clear(); delete _head; _head = nullptr; } void clear() { auto it = begin(); while (it != end()) { it = erase(it); } }我们先实现了一个Init_Empty函数，这个函数就是帮助我们先构造处一个头节点，因此list无参构造就可以直接调用这个函数。
接下来是用n个val值初始化list：
list(size_t n, const T& val = T()) { Init_Empty(); for (size_t i = 0; i < n; ++i) { push_back(val); } } list(int n, const T& val = T()) { Init_Empty(); for (int i = 0; i < n; ++i) { push_back(val); } }因为我们的头节点是不算在链表数据之内的，它只是一个帮助我们找到其他节点的一个工具。所以我们先调用 Init_Empty，完成头节点的构造，再向头节点后面不断插入即可。
template <class Iterator> list(Iterator first, Iterator last) { Init_Empty(); while (first != last) { push_back(*first); ++first; } } list(const list<T>& lt) { Init_Empty(); for (auto e : lt) push_back(e); }迭代器区间构造和拷贝构造函数也比较简单，思想和n个val初始化类似，这里不做过多解释。
void swap(list<T> lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } list<T>& operator=(const list<T> lt) { swap(lt); return *this; } ~list() { clear(); delete _head; _head = nullptr; } void clear() { auto it = begin(); while (it != end()) { it = erase(it); } }最后是赋值重载和析构，对于赋值重载，我们只需要交换对应list的成员变量即可，和前面的string vector思想一致。对于析构函数，我们直接调用了clear(),因为clear的功能就是从begin()开始，一直删除直到剩下头节点，然后再delete头节点即可。
接下来是迭代器，这里比较简单，也就不解释了：
iterator begin() { return _head->next; } iterator end() { return _head; } const_iterator begin()const { return _head->next; } const_iterator end()const { return _head; }接下来是insert和erase函数使用：
iterator insert(iterator pos, const T& val) { node* tmp = new node; node* cur = pos._node; node* prev = cur->prev; tmp->data = val; prev->next = tmp; tmp->prev = prev; tmp->next = cur; cur->prev = tmp; _size++; return tmp; } iterator erase(iterator pos) { assert(pos != end()); node* cur = pos._node; node* prev = cur->prev; node* next = cur->next; delete[] cur; cur = nullptr; prev->next = next; next->prev = prev; _size--; return next; }我们之前学习链表的时候，对于增删已经非常熟悉，无非就是增加或者删除节点，然后将对应的节点的next与prev调整好指向方向。这里对于insert，因为我们要在pos位置增加一个节点，我们只需要找到pos位置之前的节点prev，然后将新开出来的节点插入到pos和 prev之间即可。
对于erase，我们需要找到pos位置的prev和next，然后delete[ ]掉pos位置的节点，然后将prev和next链接起来就行了，需要注意的只是删除的时候pos位置不能等于end()，因为我们不能删除头节点。
然后是头插尾插和头删尾删：
void push_back(const T& val) { insert(end(), val); } void push_front(const T& val) { insert(begin(), val); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); }这里就是insert和erase的复用，找好对应的pos位置即可。
最后就是几个简单的函数功能：
//链表的长度 size_t size() { return _size; } //是否为空 bool empty() { return _size == 0; } //返回链表第一个数据 T& front() { iterator it = begin(); return it._node->data; } //返回链表第一个数据 const T& front()const { const_iterator it = begin(); return it._node->data; } //返回链表最后一个数据 T& back() { iterator it = end(); return it._node->prev->data; } //返回链表最后一个数据 const T& back()const { const_iterator it = end(); return it._node->prev->data; }上面的函数功能都比较好理解，大家知道是干什么的就行，实现起来肯定没问题。
以上内容就是对list的基础功能实现，如有错误，欢迎批评指正！！！
