【C++】List -- 详解（上）https://developer.aliyun.com/article/1514686?spm=a2c6h.13148508.setting.25.4b904f0ejdbHoA
二、STL_list 源码剖析
1、list 的底层结构
SGI 版本 STL 中 list 部分源码：
// 链表节点结构 template <class T> struct __list_node { typedef void* void_pointer; void_pointer next; void_pointer prev; T data; }; // 迭代器 -- 一个类封装了节点指针 template<class T, class Ref, class Ptr> struct __list_iterator { typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; typedef __list_iterator<T, Ref, Ptr> self; // ... typedef Ptr pointer; typedef Ref reference; // ... typedef __list_node<T>* link_type; link_type node; // 节点指针 // ... }; // 带头双向循环链表结构 template <class T, class Alloc = alloc> class list { protected: typedef __list_node<T> list_node; // 节点 // ... public: typedef T value_type; typedef list_node* link_type; // 节点指针 // ... public: // 迭代器(这里的iterator和const_iterator是定义在list类域中的内嵌类型) typedef __list_iterator<T, T&, T*> iterator; // 传了T，T&，T*模板参数 typedef __list_iterator<T, const T&, const T*> const_iterator; // 传了T，const T&，const T*模板参数 // ... protected: link_type node; // 成员变量，节点指针 // ... };
三、list的模拟实现
1、list 的节点结构
双向循环链表节点结构：一个数据域，两个指针。
namespace xyl { // List的节点类 template<class T> struct list_node { T _data; // 数据域 list_node<T>* _prev; // 前驱指针 list_node<T>* _next; // 后继指针 // 默认构造函数，T()是缺省值(T类型的默认构造函数) list_node(const T& x= T()) :_data(x) ,_prev(nullptr) ,_next(nullptr) {} }; }
2、 list 的迭代器
前面学习的 string 和 vector 容器的正向迭代器其实就是原生指针，++ 可以直接走到下一个元素，而 list 的正向迭代器是用一个类，把节点指针封装起来，然后通过实现运算符重载函数，让迭代器具有像指针一样的行为，比如：重载了 * 运算符，实现了 *it 解引用返回节点中的存储的数据的引用，重载了 ++ 运算符，实现了 it++ 直接走到下一个元素。
list 正向迭代器的结构：
namespace xyl { // T:节点中数据的类型 Ref:节点中数据的引用 Ptr:节点中数据的指针(地址) 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*() // *it 本质是：it.operator*() { return _node->_val; // 返回节点中数据(对象)的引用/const常引用，具体返回什么取决于在list类域中定义迭代器时传给Ref的参数是什么 // 我们想要得到的是节点中存储的数据(对象)，而不是整个节点(节点中包含数据和2个指针) } Ptr operator->() // it-> 本质是：it.operator->() { return &(operator*()); // 返回节点中数据(对象)的指针/const常指针，具体返回什么取决于在list类域中定义迭代器时传给Ptr的参数是什么 } // 让迭代器可以移动（双向） // ++it 本质是：it.operator++() Self& operator++() { _node = _node->_next; return *this; } // it++ 本质是：it.operator++(0) Self operator++(int) // 不能用引用返回 { Self tmp(*this); _node = _node->_next; return tmp; } // --it 本质是：it.operator--() Self& operator--() { _node = _node->_prev; return *this; } // it-- 本质是：it.operator--(0) Self operator--(int) // 不能用引用返回 { Self tmp(*this); _node = _node->_prev; return tmp; } // 让两个迭代器可以进行比较，判断两个迭代器是否相等，其实判断的是节点指针是否相等 bool operator!=(const Self& l)const { return _node != l._node; } bool operator==(const Self& l)const { return _node != l._node; } }; }
迭代器有两种实现方式，具体应根据容器底层数据结构实现：
- 原生态指针，比如：vector。
- 将原生态指针进行封装，因迭代器使用形式与指针完全相同。
因此在自定义的类中必须实现以下方法：
- 指针可以解引用，迭代器的类中必须重载 operator*() 。
- 指针可以通过 -> 访问其所指空间成员，迭代器类中必须重载 oprator->() 。
- 指针可以 ++ 向后移动，迭代器类中必须重载 operator++() 与 operator++(int) 。
- 至于operator--() / operator--(int) 释放需要重载，根据具体的结构来抉择，双向链表可以向前移动，所以需要重载，如果是 forward_list 就不需要重载 -- 。
- 迭代器需要进行是否相等的比较，因此还需要重载 operator==() 与 operator!=() 。
（1）如何实现 const 迭代器？
string 和 vector 的迭代器就是一个原生指针，我们给原生指针加上 const 就可以变成 const 迭代器，比如：
// T: 容器中存储的数据的类型 typedef T* iterator; typedef const T* const_iterator;
但 list 的迭代器不是一个原生指针，而是一个类里面封装了原生指针，那如何实现 list 的 const 迭代器呢？
const 迭代器，顾名思义，就是不能改变的迭代器，是不能通过 * 和 -> 修改指向成员的，所以我们把 operator*() 和 operator->() 函数的返回值改成常引用即可。比如：
const T& operator*() ; // 返回节点中数据(对象)的const常引用
那我们需要实现一个 __list_const_iterator 的类吗？在类中重载一个返回值为常引用的 operator*() 函数。
普通写法需要这样，因为 T& operator*(); 和 const T& operator*(); 这两个函数只是返回值不同，无法放在一个类里面构成重载。
SGI 版本 stl_list 源码中是怎么样实现的：
通过增加模板参数来控制，普通迭代器传过来的参数就是 T&，const 迭代器传过来的参数就是 const T&。
（2）迭代器遍历 list 中节点的方式是什么？
如果迭代器管理的节点中的数据是内置类型：
void test() { int arr[] = { 1, 2, 3, 4, 5 }; list<int> lt(arr, arr + sizeof(arr) / sizeof(int)); list<int>::iterator it = lt.begin(); while (it != lt.end()) { // 对指向当前节点的迭代器解引用 *it 可以得到当前节点中存储的数据 cout << *it << " "; // it.operator*() ++it; } }
如果迭代器管理的节点中的数据是自定义类型 / 结构体：
struct TreeNode { int _val; struct TreeNode* _left; struct TreeNode* _right; TreeNode(int val = -1) :_val(val) ,_left(nullptr) ,_right(nullptr) {} }; void test() { list<TreeNode> lt; lt.push_back(TreeNode(1)); lt.push_back(TreeNode(2)); lt.push_back(TreeNode(3)); list<TreeNode>::iterator it = lt.begin(); while (it != lt.end()) { /* 错误写法： * 对指向当前节点的迭代器解引用*it可以得到当前节点中存储的TreeNode结构体 * TreeNode结构体中存储的数据_val是不能直接输出出来的 * 除非重载了专门针对输出TreeNode结构体中数据的流插入运算符，比如：ostream& operator<<(ostream& out, const TreeNode node); */ // cout << *it << " "; // error!!! /* 正确写法1： * 对指向当前节点的迭代器解引用*it得到当前节点中存储的TreeNode结构体 * 然后用'.'再去访问 TreeNode 结构体中存储的数据_val */ cout << (*it)._val << " "; /* 正确写法2： * 调用 operator->() 函数 * 迭代器->，返回迭代器指向节点中存储的TreeNode结构体的地址(指针)：TreeNode* * 然后该指针再使用'->'访问结构体中存储的数据_val * 代码为：it->->_val，但可读性太差，编译器进行了特殊处理，省略掉了一个箭头，保持了程序的可读性 */ // 注意：一般结构体的指针才会使用'->'来访问成员 // 当迭代器管理的节点中的数据是结构体的时候，就可以用'->' cout << it->_val << " "; // 这种写法常用 it++; } }
（3）迭代器（ __list_iterator 类）中需要写拷贝构造、赋值重载、析构函数吗？
不需要，默认生成的就可以，而且也不需要我们去实现。虽然迭代器中封装了节点指针，但节点是归链表管理的，链表 list 中的节点也不需要迭代器去释放，list 自己会去释放。
（4） vector 和 list 的迭代器哪个更复杂呢？有什么区别呢？
它们的大小都是一样的（32 位下），vector 的迭代器是一个原生指针，大小为 4 字节；list 的迭代器是一个类封装了一个节点指针，大小也是 4 字节，物理上没什么区别。
list 的迭代器之所以要定义成自定义类型，是因为原生指针无法直接做到像指针一样的行为，所以需要用自定义的类把原生指针封装起来，然后在类中定义一些运算符重载函数，使得这个自定义类型的对象通过调用这些函数，从而可以做到像指针一样的行为。
我们在物理上可以看到，都是存了一个指针，但在运行逻辑上完全不同。
- vector 迭代器 ++，是一个指针直接 ++ 到下一个位置；
- list 迭代器 ++，是一个自定义类型的对象调用了 operator++() 函数，在函数内算出下一个位置。
3、list 的底层结构
带头双向循环链表结构：
// 带头双向循环链表结构 namespace xyl { template<class T> // T: 节点中数据的类型 class list { public: typedef __list_node<T> Node; // 节点 public: // 迭代器 // iterator是内嵌类型，在list类域里面定义的类型(类中类) // 为啥要typedef呢？为了统一规范名称，所有容器迭代器都叫iterator，用起来更方便 // 普通迭代器，指明模板参数为 T, T&, T* typedef __list_iterator<T, T&, T*> iterator; // const迭代器，指明模板参数为 T, const T&, const T* typedef __list_iterator<T, const T&, const T*> const_iterator; iterator begin(); // 返回指向第一个有效节点的迭代器 iterator end(); // 返回指向头节点的迭代器 const_iterator begin() const; const_iterator end() const; private: Node* _head; // 头节点指针 public: // 默认成员函数 list(); // 默认构造函数 template<class InputIterator> list(InputIterator first, InputIterator last); // 带参构造函数 list(const list<T>& lt); // 拷贝构造函数（深拷贝） list<T>& operator=(list<T> lt) // 赋值运算符重载函数（深拷贝） ~list(); // 析构函数 // 容量操作 size_t size(); // 有效元素个数 bool empty(); // 判空 // 修改操作 iterator insert(iterator pos, const T& data); // 指定迭代器位置之前插入元素 iterator erase(iterator pos); // 删除指定迭代器位置的元素 void push_back(const T& data); // 尾插 void push_front(const T& data); // 头插 void pop_back(); // 尾删 void pop_front(); // 头删 void clear(); // 清空有效元素 }; }
注意：list 类域中的 __list_iterator 和 __list_iterator 是定义在类内部的类（嵌套类型）。
用 typedef 重命名为 iterator 和 const_iterator ，目的是为了统一规范迭代器的名称，所有容器的迭代器都叫 iterator 等，用起来更方便。否则每个容器都定义迭代器，如果每个容器迭代器的名字都不一样，那用户的使用成本就太高了。
// 普通迭代器，指明模板参数为 T, T&, T* typedef __list_iterator<T, T&, T*> iterator; // const迭代器，指明模板参数为 T, const T&, const T* typedef __list_iterator<T, const T&, const T*> const_iterator;
其中 T 、 T& 、 T* 都是类型参数。当 list 的类型确定了，T 、 T& 、 T* 的类型自动确定，那么 iterator 的类型同时也自动确定了，这看起来就像 iterator 和 list 是共生的一样。有什么样的螺丝就需要什么样的螺丝刀，否则螺丝刀再漂亮，没有对号的螺丝也是没用的。
4、list 的一些成员函数
（1）默认成员函数
a. 构造函数
// 默认构造函数 list() { // 构造头节点，自己指向自己 _head = new Node; _head->_prev = _head; _head->_next = _head; } // 用迭代器区间初始化[first,last) template<class InputIterator> list(InputIterator first, InputIterator last) :_head(new Node) // 当前对象是一个正在构造的对象，成员变量是随机值，需要进行初始化 { // 建立头节点自身的链接 _head->_prev = _head; _head->_next = _head; // 用迭代器遍历元素，尾插到新容器中 while (first != last) { push_back(*first); first++; } }
b. 拷贝构造函数（传统写法和现代写法都可以）
//拷贝构造函数(深拷贝--传统写法) // lt2(lt1) list(const list<T>& lt) :_head(new Node) // 当前对象是一个正在构造的对象，成员变量是随机值，需要进行初始化 { // 建立头节点自身的链接 _head->_prev = _head; _head->_next = _head; // 把lt中所有节点拷贝插入到新容器中 for (const auto& e : lt) { push_back(e); } } // 拷贝构造函数(深拷贝--现代写法) // lt2(lt1) list(const list<T>& lt) :_head(new Node) // 当前对象是一个正在构造的对象，成员变量是随机值，需要进行初始化 { // 建立头节点自身的链接 _head->_prev = _head; _head->_next = _head; list<T> tmp(lt.begin(), lt.end()); std::swap(_head, tmp._head); // 交换两个容器的内容 }
c. 赋值运算符重载函数（深拷贝——传统写法）
list<T>& operator=(const list<T>& lt) { if (this != <) // 防止自己给自己赋值 { // 清除当前容器所有有效元素 clear(); // 把lt中所有节点拷贝插入到当前容器中 for (const auto& e : lt) { push_back(e); } } return *this; // 返回当前容器 }
d. 赋值运算符重载函数（深拷贝——现代写法）
list<T>& operator=(list<T> lt) // 传值传参，拷贝构造出临时对象 { std::swap(_head, lt._head); // 交换两个容器的内容 return *this; // 返回当前容器 }
e. 析构函数
~list() { /* Node* cur = _head->_next; // 从第一个有效节点开始删除 while (cur != _head) { Node* next = cur->_next; // 先记录下一个节点 delete cur; // 释放当前节点 cur = next; // 遍历下一个节点 } delete _head; // 释放头节点 _head = nullptr; */ clear(); delete _head; _head = nullptr; }
（2）容量操作
a. size
// O(N) size_t size() { size_t n = 0; // 遍历整个链表，统计有效元素个数 iterator it = begin(); while (it != end()) { n++; it++; } return n; }
b. empty
bool empty() { return begin() == end(); }
（3）修改操作
a. insert
iterator insert(iterator pos, const T& data) { Node* cur = pos._node; // 当前节点（pos中封装了节点的指针） Node* prev = cur->_prev; // 前驱节点 Node* newnode = new Node(data); // 新节点 // 建立前驱节点和新节点的链接 prev->_next = newnode; newnode->_prev = prev; // 建立新节点与当前节点的链接 newnode->_next = cur; cur->_prev = newnode; // 返回指向第一个新插入元素的迭代器 return iterator(newnode); // 注意：此处调用iterator的构造函数构造出一个匿名对象 // return newnode; // 也可以这样写，因为单参数的构造函数支持隐式类型的转换 }
b. erase
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); // 注意：此处调用iterator的构造函数构造出一个匿名对象 }
c. push_back 和 push_front
void push_back(const T& data) // 尾插 { /* Node* newNode = new Node(data); // 构造新节点 Node* tail = _head->_prev; // 尾节点 // 建立尾节点和新节点的链接 tail->_next = newNode; newNode->_prev = tail; // 建立新节点和头节点的链接 newNode->_next = _head; _head->_prev = newNode; */ insert(end(), data); // 在头节点的前面插入，相当于是尾插 } void push_front(const T& data) // 头插 { insert(begin(), data); // 在第一个有效节点前面插入，相当于是头插 }
d. pop_back 和 pop_front
void pop_back() // 尾删 { erase(--end()); } void pop_front() // 头删 { erase(begin()); }
e. clear
void clear() { /* iterator it = begin(); while (it != end()) { Node* cur = it._node; // 记录当前节点 it++; // 遍历下一个节点 delete cur; // 删除当前节点 } // 建立头节点自身的链接 _head->_next = _head; _head->_prev = _head; */ iterator it = begin(); while (it != end()) { it = erase(it); // 删除当前节点，返回指向下一个节点的迭代器 } }
【补充】 类模板成员函数的实例化
编译器进行类模板推演，实例化出一个 list 类，然后再实例化出这个 lt 对象。
- 类模板中的成员函数都是函数模板。
- 类模板成员函数的实例化，是按需实例化，只有当程序用到它时才进行实例化。
- 一个模板，如果没有实例化，编译器是不会去检查它内部的语法的，也不会报错。
void test() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.clear(); }
四、list与vector的对比
vector 与 list 都是 STL 中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：
