这篇文章主要为大家详细介绍了C++如何模拟实现STL容器list，文中的示例代码讲解详细，对我们学习C++有一定帮助，需要的可以参考一下
list 概述
相比于 vector 的连续线性空间，list 采用的是零散的空间，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。
list 是支持常数时间从容器任何位置插入和移除元素容器，但不支持快速随机访问。list 通常实现为双向链表，与 forward_list 相比，list 的迭代器可以向前移动，但也因此需要在节点中多开辟一个指针变量，在空间上效率稍低。
接口总览
namespace qgw { /// @brief list 中每个节点 /// @tparam T 节点存储的数据的类型 template struct _list_node { _list_node(const T& data = val()); // 节点类的构造函数 _list_node* _prev; // 指向前一节点 _list_node* _next; // 指向后一节点 T _data; // 存储节点数据 }; /// @brief list 的迭代器 /// @tparam T list 数据的类型 /// @tparam Ref 数据的引用类型 /// @tparam Ptr 数据的指针类型 template struct _list_iterator { typedef _list_iterator iterator; typedef _list_iterator self; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef _list_node list_node; // 构造函数 _list_iterator(list_node* node = nullptr); // 各种运算符重载 bool operator==(const self& x) const; bool operator!=(const self& x) const; reference operator*() const; pointer operator->() const; self& operator++(); self operator++(int); self& operator--(); self operator++(int); list_node* _node; // 指向对应的 list 节点 }; template class list { public: typedef T value_type; typedef T* pointer; typedef T& reference; typedef _list_node list_node; typedef _list_iterator iterator; typedef _list_iterator const_iterator; public: // 默认成员函数 list(); list(const list& other); list& operator=(const list& other); ~list(); // 元素访问 reference front(); reference back(); // 迭代器 iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; // 容量 bool empty() const; size_t size() const; // 修改器 void clear(); iterator insert(iterator pos, const T& val); void push_front(const T& val); void push_back(const T& val); iterator erase(iterator pos); void pop_front(); void pop_back(); void swap(list& other); // 操作 void splice(iterator pos, list& other); void splice(iterator pos, list& other, iterator it); void splice(iterator pos, list& other, iterator first, iterator last); void merge(list& other); void remove(const T& value); void reverse(); void unique(); private: list_node* _node; // 指向链表头节点 }; } list 的节点
list 的节点我们设计成一个 _list_node 类，里面有三个成员变量，分别为前后指针和数据。
它的构造函数将数据初始化为给定数据，再将前后指针初始化为空即可。
/// @brief 节点类的构造函数 /// @param data 用来构造节点的初值 _list_node(const T& data = T()) : _data(data) { _prev = nullptr; _next = nullptr; }
默认成员函数
默认构造函数
SGI list 不仅是一个双向链表，还是一个带头的循环链表。
/// @brief 构造一个空链表 list() { _node = new list_node; // 创建一个头节点 _node->_prev = _node; // 前面指向自己 _node->_next = _node; // 后面指向自己 }
析构函数
list 的析构函数，先调用 clear 释放数据资源，再 delete 掉头节点即可。
/// @brief 释放资源 ~list() { clear(); delete _node; _node = nullptr; } 拷贝构造函数
用另一容器创建新对象。
先申请一个头节点，然后遍历 other 容器，将 other 中的数据逐一尾插到 *this 中。
/// @brief 用给定容器初始化 /// @param other 用来初始化的容器 list(const list& other) { _node = new list_node; _node->_next = _node; _node->_prev = _node; for (const auto& e : other) { push_back(e); } }
复制赋值函数
先创建给定容器的拷贝 tmp，然后交换 *this 和 tmp，最后返回 *this。
/// @brief 替换容器内容 /// @param other 用作数据源的另一容器 /// @return *this list& operator=(const list & other) { // tmp 出了作用域就销毁了 list tmp(other); swap(tmp); // 返回引用可以连续赋值 return *this; }
list 的迭代器
list 的节点在内存中不是连续存储的，因此不能使用原生指针作为 list 的迭代器。list 的迭代器必须有能力指向 list 的节点，并能够正确的递增、递减、取值、成员存取等操作。正确的操作是指：递增时指向下一节点，递减时指向上一节点，取值时取的是节点的数据值，成员取用的是节点的成员。
由于 STL list 是一个双向链表（double linked-list），迭代器必须具备前移、后移的能力，所以 list 提供的是 Bidirectional Iterators。
构造函数
list 的迭代器中成员变量只有一个节点指针，将其指向给定节点即可。
/// @brief list 迭代器的构造函数 /// @param node 用来构造的节点 _list_iterator(list_node* node = nullptr) { _node = node; } operator==
判断两迭代器指向的节点是否为同一个，直接比较迭代器中节点的指针即可。切记不能比较指针中的值，因为不同节点的值可能相同。
/// @brief 判断两迭代器指向的节点是否相同 /// @param x 用来比较的迭代器 /// @return 相同返回 true，不同返回 false bool operator==(const self& x) const { return _node == x._node; } operator!=
!= 的比较方法和 == 一样。
/// @brief 判断两迭代器指向的节点是否不同 /// @param x 用来比较的迭代器 /// @return 不同返回 true，相同返回 false bool operator!=(const self& x) const { return _node != x._node; } operator*
迭代器是模仿指针的，让我们可以像使用指针一样。因此可以对迭代器进行解引用操作，该操作得到的是迭代器中节点指针指向的数据，并且返回引用，因为有可能修改该数据。
/// @brief 获取指向节点中的数据值 /// @return 返回指向节点数据的引用 reference operator*() const { return _node->_data; } operator->
-> 运算符的重载稍显复杂，让我们先看下面这个场景。
也就是 list 中存储的是自定义类型，自定义类型中又有多个成员变量，我们想取出指定的成员变量，当然这里用 . 也可以做到。
// 有一个学生类，里面有姓名和学号两个成员 struct Stu { string name; string id; }; list s; Stu s1 = { "qgw", "001" }; Stu s2 = { "wlr", "002" }; s.push_back(s1); s.push_back(s2); list::iterator ptr = s.begin(); // 输出第一个学生的姓名和学号 cout << (*ptr).name << endl; cout << s.begin()->id << endl; /// @brief 获取节点中数据的地址 /// @return 返回节点指向的数据的地址 pointer operator->() const { return &(operator*()); } 看到这你可能会疑惑，operator-> 返回的是节点的数据的地址，也是说上面 s.begin()-> 得到的是一个地址，那这条语句是怎么执行的？
实际上这里确实应该有两个箭头像这样 s.begin()->->id，但这种方式的可读性太差了，所以编译器对此做了优化，在编译为我们添加一个箭头。
operator++
operator++ 运算符的作用十分清晰，就是让迭代器指向链表中下一节点。
前置实现的思路是：通过迭代器中的节点指针找到下一节点，然后赋值给迭代器中的节点指针。
后置实现的思路是：先保存当前位置迭代器，然后调用前置 ++，最后返回临时变量。
需要注意的是：前置 ++ 返回的是前进后迭代器的引用，后置 ++ 返回的是一个临时变量。
/// @brief 前置++ /// @return 返回前进一步后的迭代器 self& operator++() { _node = _node->_next; return *this; } /// @brief 后置++ /// @param 无作用，只是为了与前置 ++ 进行区分，形成重载 /// @return 返回当前的迭代器 self operator++(int) { self tmp = *this; // 直接调用前置 ++ ++(*this); return tmp; } operator--
前置实现的思路是：通过迭代器中的节点指针找到前一节点，然后赋值给迭代器中的节点指针。
后置实现的思路是：先保存当前位置迭代器，然后调用前置 --，最后返回临时变量。
/// @brief 前置 -- /// @return 返回后退一步后的迭代器 self& operator--() { _node = _node->_prev; return *this; } /// @brief 后置 -- /// @param 无作用，只是为了与前置 -- 进行区分，形成重载 /// @return 返回当前的迭代器 self operator--(int) { self tmp = *this; --(*this); return tmp; } 元素访问
front
front 获取第一个元素的引用，直接用 begin 获取指向第一个元素的迭代器，再解引用即可。
/// @brief 返回容器首元素的引用 /// @return 首元素的引用 reference front() { return *begin(); } back
end 获取最后一个元素的引用，先用 end 获取最后一个元素下一位置的迭代器，再回退一步，然后解引用就可以了。
/// @brief 返回容器中最后一个元素的引用 /// @return 最后元素的引用 reference back() { return *(--end()); } 迭代器
在 begin 和 end 实现之前，我们先来看下 list 的示意图，下图为有 3 个元素的链表：
begin
begin 获取的是首元素的迭代器，根据上图，begin 的实现也就非常清晰了，直接返回头节点的下一位置即可。
/// @brief 返回指向 list 首元素的迭代器 /// @return 指向首元素的迭代器 iterator begin() { // 根据节点指针构造迭代器 return iterator(_node->_next); } // const 版本供 const 容器使用 const_iterator begin() const { return const_iterator(_node->_next); } end
end 获取的是最后一个元素下一个位置的迭代器，根据上图就是 _node 所指向的节点。
/// @brief 返回指向 list 末元素后一元素的迭代器 /// @return 指向最后元素下一位置的迭代器 iterator end() { // 调用 iterator 构造函数 return iterator(_node); } const_iterator end() const { return const_iterator(_node); } 容量
empty
begin 和 end 指向相同，说明链表此时只有一个头节点，链表为空。
/// @brief 检查容器是否无元素 /// @return 若容器为空则为 true，否则为 false bool empty() const { return begin() == end(); } size
size 函数的作用是返回容器中元素的数量。
在 C++ 11 前，该函数的复杂度可能是常数的，也可能是线性的。从 C++ 11 起该函数的复杂度为常数。
下面代码的时间复杂度是线性的，要想改成常数也很简单，只需要在 list 中开辟一个成员变量记录个数即可。
/// @brief 返回容器中的元素数 /// @return 容器中的元素数量 size_t size() const { size_t sz = 0; auto it = begin(); while (it != end()) { ++it; ++sz; } return sz; } 修改器
insert
下图为：只有 0、1 两个元素的链表，在 1 之前插入元素值为 2 的节点的示意图。
插入的思路比较清晰：
1.插入节点的 _next 指向 pos 位置的节点
2.插入节点的 _prev 指向 pos 前一位置的节点
3.pos 前一位置的节点的 _next 指向插入的节点
4.pos 位置节点的 _prev 指向插入的节点
/// @brief 插入元素到容器中的指定位置 /// @param pos 将内容插入到 pos 之前 /// @param val 要插入的元素值 /// @return 指向被 插入 val 的迭代器 iterator insert(iterator pos, const T& val) { list_node* tmp = new list_node(val); // 创建要插入的节点 tmp->_next = pos._node; // (1) tmp->_prev = pos._node->_prev; // (2) (pos._node->_prev)->_next = tmp; // (3) pos._node->_prev = tmp; // (4) return tmp; } push_front
push_front 的作用是在第一个元素之前插入一个节点，直接调用 insert 在 begin 之前插入就行。
/// @brief 添加给定元素 val 到容器起始 /// @param val 要添加的元素值 void push_front(const T& val) { insert(begin(), val); } push_back
push_back 的作用是在容器的最后添加一个节点，直接调用 insert 在 end 之前插入就行。
/// @brief 添加给定元素 val 到容器尾 /// @param val 要添加的元素值 void push_back(const T& val) { insert(end(), val); } erase
下图为：有三个元素 0、1、2 的链表，删除 pos 指向节点（值为 1）的示意图。
删除的思路也很清晰：
1.将 pos 前一节点的 _next 指针指向 pos 的下一节点
2.将 pos 下一节点的 _prev 指针指向 pos 的前一节点
3.delete 释放掉 pos 所指向的节点
/// @brief 从容器擦除指定的元素 /// @param pos 指向要移除的元素的迭代器 /// @return 最后移除元素之后的迭代器 iterator erase(iterator pos) { list_node* nextNode = pos._node->_next; // 记录 pos 指向节点的下一节点 list_node* prevNode = pos._node->_prev; // 记录 pos 指向节点的前一节点 prevNode->_next = nextNode; // (1) nextNode->_prev = prevNode; // (2) delete (pos._node); return (iterator)nextNode; } pop_front
pop_front 移除容器第一个元素，也就是 begin 指向的节点。
/// @brief 移除容器首元素 void pop_front() { erase(begin()); } pop_back
pop_back 移除容器最后一个节点，也就是 end 指向的前一个节点。
/// @brief 移除容器的末元素 void pop_back() { erase(--end()); } clear
clear 用于清空容器所有数据，不清理头节点。
采用遍历的方式调用 erase 删除每一个节点。
/// @brief 从容器擦除所有元素 void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } swap
swap 用来交换两个 list 容器，不用 list 中每个元素的值，直接交换 _node 指针即可。
/// @brief 将内容与 other 的交换 /// @param other 要与之交换内容的容器 void swap(list& other) { std::swap(_node, other._node); } 操作
splice
在实现该函数之前，先来看下 list 内部的一个函数 transfer。
list 内部提供一个迁移操作（transfer）：将某连续范围的元素迁移都某个特定位置之前。
这个函数比上面所写的要复杂的多，要对着图仔细思考。
/// @brief 将 [first, last) 范围的所有元素移动到 pos 之前 /// @param pos 将内容移动到 pos 之前 /// @param first 范围起始位置 /// @param last 范围结束位置 void transfer(iterator pos, iterator first, iterator last) { if (pos != last) { last._node->_prev->_next = pos._node; // (1) first._node->_prev->_next = last._node; // (2) pos._node->_prev->_next = first._node; // (3) list_node* tmp = pos._node->_prev; // (4) pos._node->_prev = last._node->_prev; // (5) last._node->_prev = first._node->_prev; // (6) first._node->_prev = tmp; // (7) } }
有了上面的函数，splice 的实现也就非常简单了，下面共有三个重载实现：
根据要转移的元素选择调用不同的函数。
/// @brief 将 other 接合于 pos 所指位置之前，两者不能是同一 list /// @param pos 将内容插入到它之前 /// @param other 要从它转移内容的另一容器 void splice(iterator pos, list& other) { if (!other.empty()) { transfer(pos, other.begin(), other.end()); } } /// @brief 将 it 所指元素接合到 pos 所指位置之前 /// @param pos 将内容插入到它之前 /// @param other 要从它转移内容的另一容器 /// @param it 从 other 转移到 *this 的元素 void splice(iterator pos, list& other, iterator it) { // 取得一个 [i, j) 的范围，使得能调用 transfer iterator j = it; ++j; // 检查是否有必要执行 // pos == it 时说明 pos 和 it 指向的是同一节点 // pos == j 时说明，it 刚好在 pos 之前 if (pos == it || pos == j) { return; } transfer(pos, it, j); } /// @brief 将 [first, last) 内的所有元素接合于 pos 所指位置之前 /// @param pos 将内容插入到它之前 /// @param first 起始位置 /// @param last 结束位置 void splice(iterator pos, list& other, iterator first, iterator last) { if (first != last) { transfer(pos, first, last); } } merge
merge 函数和归并排序中的合并操作类似，该函数的作用是：合并两个已递增排序的链表。
/// @brief 合并两个递增链表，合并到 *this 上 /// @param other 要合并的另一容器 void merge(list& other) { iterator first1 = begin(); iterator end1 = end(); iterator first2 = other.begin(); iterator end2 = other.end(); while (first1 != end1 && first2 != end2) { if (*first2 <*first1) { iterator next = first2; transfer(first1, first2, ++next); first2 = next; } else { ++first1; } } if (first2 != end2) { // 将 other 链表剩余元素合并到 *this 中 transfer(first1, first2, end2); } } remove
remove 用来删除 list 中值等于 val 的元素，直接遍历链表，找到就删除。
/// @brief 移除等于 val 元素 /// @param val 要移除的元素的值 void remove(const T& val) { iterator first = begin(); iterator last = end(); while (first != last) { iterator next = first; ++next; if (*first == val) { erase(first); } first = next; } } reverse
reverse 的作用是逆转容器中的元素顺序。
该函数的思路简单，从第 2 个元素开始，以次头插到链表头部。
/// @brief 将 *this 的内容逆置 void reverse() { // 空链表或只有一个元素直接返回 if (_node->_next == _node || _node->_next->_next == _node) { return; } iterator first = begin(); ++first; while (first != end()) { iterator old = first; // 第一次循环时指向第 2 个元素 ++first; // 第一次循环时指向第 3 个元素 transfer(begin(), old, first); } } unique
unique 用来移除数值相同的连续元素，只保留一个。
该函数利用的是双指针的思想，first 和 next 分别指向前后两个元素，相同就删除后一个。
/// @brief 移除数值相同的连续元素 void unique() { iterator first = begin(); iterator last = end(); if (first == last) { return; } iterator next = first; while (++next != last) { // 此时 next 指向 first 下一个节点 if (*first == *next) { // 连续的相同，就删除后一个 erase(next); } else { // 不相同 first 向 end 移动 first = next; } // 使 next 再次指向 first // 这样再进 while 时，++next 又使 next 指向 first 下一个 next = first; } } 以上就是详解C++ STL模拟实现list的详细内容，更多关于C++ STL list的资料请关注0133技术站其它相关文章！
以上就是详解C++ STL模拟实现list的详细内容，更多请关注0133技术站其它相关文章！
