引言
因为list结构的特殊性，所以拆分为结点、迭代器和list本身进行学习。
一、结点
细节：
- 使用struct，标明公有属性（这样从外部调用比较方便）
- list是带头双向循环链表
- 提供全缺省的默认构造函数
template<class T> struct __list_node { __list_node<T>* _prev; __list_node<T>* _next; T _data; __list_node(const T& x = T()) : _prev(nullptr) , _next(nullptr) , _data(x) {} };
二、迭代器
由于list的每个结点物理空间不连续，导致迭代器不能像之前string、vector那样简单的设计为指针，而是设计为一个类（进行封装），以此完成*、->、++、–等一系列操作。
2.1 成员变量与默认成员函数
细节：
- 仍然使用struct，标明公有属性
- 成员变量是一个结点的指针
- 提供带参构造函数（其余的默认成员函数不用显式定义，浅拷贝即可）
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* n) : _node(n) {} };
此时的迭代器设计，可以说是list乃至STL的精华，天才般地运用了类的优势。
2.2 operator*
细节：
- 返回引用，为了区别普通迭代器和const迭代器
Ref operator*() { return _node->_data; }
2.3 operator->
细节：
- 返回指针，为了区别普通迭代器和const迭代器
Ptr operator->() { return &_node->_data; }
2.4 operator++
细节：
- 为了区分前置和后置，后置参数加上int（无实际意义，以示区分）
- 前置传引用返回，后置传值返回
self& operator++()//前置++ { _node = _node->_next; return *this; } self operator++(int)//后置++ { self tmp(*this); _node = _node->_next; return tmp; }
2.5 operator- -
细节：同上
self& operator--()//前置-- { _node = _node->_prev; return *this; } self operator--(int)//后置-- { self tmp(*this); _node = _node->_prev; return tmp; }
2.6 relational operators
bool operator!=(const self& s) { return _node != s._node; } bool operator==(const self& s) { return _node == s._node; }
三、list
3.1 成员变量
list类包含了
- _head（指向哨兵位）
template<class T> class list { public: typedef __list_node<T> node; private: node* _head; };
3.2 迭代器
typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator;
3.2.1 begin
细节：
- begin()在_head->next
- 使用匿名对象
iterator begin() { return iterator(_head->_next); } const_iterator begin() const { return const_iterator(_head->_next); }
3.2.2 end
细节：
- end()在_head
- 使用匿名对象
iterator end() { return iterator(_head); } const_iterator end() const { return const_iterator(_head); }
3.3 默认成员函数
3.3.1 constructor
空初始化：创建哨兵位
void empty_init() { _head = new node; _head->_prev = _head; _head->_next = _head; }
无参构造
list() { empty_init(); }
迭代器区间构造
细节：使用类模板，可以传任意类型的迭代器
template <class InputIterator> list(InputIterator first, InputIterator last) { empty_init(); while (first != last) { push_back(*first); ++first; } }
3.3.2 destructor
~list() { clear(); delete _head; _head = nullptr; }
3.3.3 copy constructor
现代写法
细节：
- 用迭代器区间构造，构造出临时对象
- 再使用list中的swap，交换*this和tmp的值，完成拷贝构造
list(const list<T>& lt) { empty_init(); list<T> tmp(lt.begin(), lt.end()); swap(tmp); }
3.3.4 operator=
现代写法
细节：
- 传参变成传值，这样就会拷贝构造出一个临时对象
- 再使用list中的swap，交换*this和tmp的值，完成赋值重载
list<T>& operator=(list<T> lt) { swap(lt); return *this; }
3.4 修改
3.4.1 insert
指定位置插入
细节：
- 在pos之前插入
- 迭代器不会失效
void insert(iterator pos, const T& x) { node* cur = pos._node; node* prev = cur->_prev; node* new_node = new node(x); prev->_next = new_node; new_node->_prev = prev; cur->_prev = new_node; new_node->_next = cur; }
3.4.2 push_front
头插
void push_front(const T& x) { insert(begin(), x); }
3.4.3 push_back
尾插
void push_back(const T& x) { insert(end(), x); }
3.4.4 erase
指定位置删除
细节：
- assert断言，防止删除哨兵位
- 返回删除节点的下一位，防止迭代器失效
iterator erase(iterator pos) { assert(pos != end()); node* cur = pos._node; node* prev = cur->_prev; node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; return iterator(next); }
3.4.5 pop_front
void pop_front() { erase(begin()); }
3.4.6 pop_back
void pop_back() { erase(--end()); }
3.4.7 clear
清除所有结点（除哨兵位以外）
void clear() { iterator it = begin(); while (it != end()) { erase(it++); } }
3.4.8 swap
交换两个list类的值
细节：使用std库中的swap函数，交换各个成员变量的值
void swap(list<T>& lt) { std::swap(_head, lt._head); }
总结
学习完list类，对于STL中的精华——迭代器设计，有了更深一步的了解。同时，了解多参数模板的用途和方法，极大提高代码复用程度。
真诚点赞，手有余香
