深度剖析C++STL：手持list利剑，破除编程重重难题（下）

前言：

上篇我们提到STL中list的相关接口及用法，本篇将从list的底层逻辑出发，手动实现一个建议的list容器。

一. list的底层结构

在 list 的实现中，底层是通过双向链表结构来存储数据。双向链表中的每个节点不仅包含数据，还包含指向前一个节点和后一个节点的两个指针。以下是节点结构的定义：

具体代码示例如下：

namespace W {// 定义链表节点template<class T>struct ListNode {T _val;               // 节点存储的值ListNode* _prev;      // 指向前一个节点ListNode* _next;      // 指向后一个节点ListNode(const T& val = T()) : _val(val), _prev(nullptr), _next(nullptr) {}};
}

 分析：

1. _val表示节点所存储的数据

2. _prev和_next分别表示前驱与后驱指针，方便后续的遍历和对元素的相关操作。

3. 采用模板，有效解决数据类型不同时的代码冗余。

二. list的迭代器

2.1 迭代器的概念与实现

迭代器的作用类似于一个指针，它指向链表中的某个节点，允许我们通过类似指针的方式来访问和操作链表节点。与普通指针不同，迭代器提供了更高级的功能，并且能够保持接口的一致性，因此它成为了 STL 容器中访问元素的核心工具。

为了实现最基本的链表迭代器，首先我们需要定义链表节点的结构。该结构已经在上文定义了。

接下来，我们将实现 ListIterator，它内部保存一个指向 ListNode 的指针 _node，并支持以下基本操作：

1. 解引用操作：通过 *it 访问链表节点中的值。
2. 前向移动操作：通过 ++it 访问链表中的下一个节点。
3. 比较操作：通过 it != end() 判断两个迭代器是否相等。

具体代码示例如下：

namespace W {template<class T>class ListIterator {typedef ListNode<T> Node;  // 使用 Node 表示链表节点类型public:// 构造函数，接受一个指向链表节点的指针ListIterator(Node* node = nullptr) : _node(node) {}// 解引用操作，返回节点的值T& operator*() { return _node->_val; }// 前向移动操作，指向下一个节点ListIterator& operator++() {_node = _node->_next;  // 将当前节点移动到下一个节点return *this;  // 返回自身以支持链式调用}// 比较操作，判断两个迭代器是否相等bool operator!=(const ListIterator& other) const { return _node != other._node; }private:Node* _node;  // 迭代器指向的链表节点};
}

1. 构造函数：初始化一个指向链表节点的指针 _node，用于遍历链表。
2. operator*：返回节点存储的值 _val。
3. operator++：将迭代器移动到链表中的下一个节点。
4. operator!=：用于判断两个迭代器是否相等。

2.2 迭代器拼接为list的测试

为了验证我们刚刚实现的迭代器功能，先创建一些链表节点，并将它们链接成一个链表。然后我们使用迭代器遍历链表并输出每个节点的值。 

代码示例如下：

#include <iostream>int main() {// 创建三个节点，分别存储值 1、2、3W::ListNode<int> node1(1);      W::ListNode<int> node2(2);      W::ListNode<int> node3(3);      // 链接节点形成链表node1._next = &node2;  // node1 的下一个节点是 node2node2._prev = &node1;  // node2 的前一个节点是 node1node2._next = &node3;  // node2 的下一个节点是 node3node3._prev = &node2;  // node3 的前一个节点是 node2// 创建迭代器，指向第一个节点W::ListIterator<int> it(&node1);// 使用迭代器遍历链表并输出每个节点的值while (it != nullptr) {std::cout << *it << std::endl;  // 输出当前节点的值++it;  // 前向移动到下一个节点}return 0;
}

输出：

1
2
3

2.3 后置++与->运算符的重载 

代码示例如下：

namespace W {template<class T>class ListIterator {typedef ListNode<T> Node;public:ListIterator(Node* node = nullptr) : _node(node) {}// 解引用操作，返回节点的值T& operator*() { return _node->_val; }// 指针操作，返回节点的指针T* operator->() { return &(_node->_val); }// 前向移动ListIterator& operator++() {_node = _node->_next;return *this;}// 后向移动ListIterator& operator--() {_node = _node->_prev;return *this;}// 比较操作bool operator!=(const ListIterator& other) const { return _node != other._node; }private:Node* _node;};
}

我们通过一个测试程序验证迭代器的前向和后向移动功能，同时通过 -> 运算符访问链表节点的值。我们会分别测试基本数据类型 int 和自定义类型 CustomType 的场景，展示迭代器在不同数据类型下的使用方式。

1. 对于 int 类型，我们可以通过 *it 来访问节点的值，而不需要使用 *(it->)，虽然 *(it->) 也是合法的，但没有必要。

2. 对于自定义类型 CustomType，可以通过 it->x 来访问自定义类型 CustomType 中的成员变量 x

测试代码示例如下：

#include <iostream>struct CustomType {int x;
};int main() {// 创建三个 int 类型的节点，分别存储值 1、2、3W::ListNode<int> node1(1);      W::ListNode<int> node2(2);      W::ListNode<int> node3(3);      // 链接节点形成链表node1._next = &node2;node2._prev = &node1;node2._next = &node3;node3._prev = &node2;// 创建迭代器，初始指向第二个节点W::ListIterator<int> it(&node2);// 对于 int 类型，使用 *it 访问节点的值std::cout << *it << std::endl;  // 输出 2// 后向移动，指向第一个节点--it;std::cout << *it << std::endl;  // 输出 1// 前向移动，指向第三个节点++it;++it;std::cout << *it << std::endl;  // 输出 3// 创建自定义类型 CustomType 的节点W::ListNode<CustomType> customNode1({1});W::ListNode<CustomType> customNode2({2});customNode1._next = &customNode2;customNode2._prev = &customNode1;// 创建自定义类型 CustomType 的迭代器W::ListIterator<CustomType> customIt(&customNode1);// 使用 it-> 访问 CustomType 的成员变量 xstd::cout << customIt->x << std::endl;  // 输出 1return 0;
}

输出：

2
1
3
1

分析：

1. 对于 int 类型的节点，我们通过 *it 访问节点的值，++it 和 --it 分别实现了前向和后向移动。
2. 对于自定义类型 CustomType 的节点比如说结构体，通过 it->x 可以访问自定义类型成员变量 x。需要注意 it->x 是被编译器优化后的代码，其原本类型为 it.operator->()->x。

2.4 常见误区const分析

问题：当模板参数类型被const修饰时，是否可以通过直接在相关接口内添加const修饰的方式进行匹配？

答案是不行！！！

分析：

1. 在 vector 中，const_iterator 通过 const 修饰符即可实现不可修改的迭代器，这是因为 vector 的底层存储是连续的内存块，通过 const 限制访问的值即可。而 list 的底层是双向链表，迭代器不仅需要访问链表节点的值，还需要操作链表的前驱和后继节点（即 _prev 和 _next 指针）。直接使用 const 修饰迭代器无法满足这些需求，因为 const 限制了对链表结构的必要修改。

2. const修饰之后会限制成员内所有变量的修改操作，无法进行++，--等操作，也就无法获取list的其他元素。

 以下是一个错误代码示例：

#include <iostream>template<class T>
struct ListNode {T _val;ListNode* _prev;ListNode* _next;ListNode(T val) : _val(val), _prev(nullptr), _next(nullptr) {}
};template<class T>
class ListIterator {typedef ListNode<T> Node;public:ListIterator(Node* node = nullptr) : _node(node) {}// 解引用操作，返回节点的值T& operator*() { return _node->_val; }// 前向移动ListIterator& operator++() {_node = _node->_next;return *this;}// 后向移动ListIterator& operator--() {_node = _node->_prev;return *this;}private:Node* _node;
};int main() {// 创建三个节点，分别存储值 1、2、3ListNode<int> node1(1), node2(2), node3(3);// 链接节点形成链表node1._next = &node2;node2._prev = &node1;node2._next = &node3;node3._prev = &node2;// 尝试创建一个 const 迭代器const ListIterator<int> constIt(&node1);// 错误1：前向移动时，编译器报错，因为 ++ 操作符不能对 const 迭代器操作++constIt;  // 编译错误// 错误2：解引用操作也无法进行修改*constIt = 5;  // 编译错误
}

错误分析：

1. 无法执行前向移动 (++constIt)：由于 const 修饰符限制了修改成员变量 _node，因此 ++ 操作无法执行，因为该操作会修改迭代器的内部指针。

2. 无法修改节点的值 (*constIt = 5)：由于迭代器是 const 的，解引用操作也不能用于修改节点的值，因此编译器会报错。

 2.6 使用模板参数实现const与non-const

为了处理上述问题，我们可以使用模板参数来区分 const 和 non-const 的情况。通过模板参数 Ref 和 Ptr，我们可以控制迭代器的行为，使得它在常量链表和非常量链表中都能正常工作。

使用模板参数的好处：

• 灵活性：可以根据需要处理 const 和 non-const 的迭代器场景。
• 安全性：对于常量链表，保证不能修改节点的值；对于非常量链表，允许修改。
• 代码复用：通过模板参数，既可以编写一套代码，处理 const 和 non-const 两种情况。

代码示例如下：

namespace W {template<class T, class Ref, class Ptr>class ListIterator {typedef ListNode<T> Node;  // 使用 Node 表示链表节点类型public:ListIterator(Node* node = nullptr) : _node(node) {}// 解引用操作，返回节点的值Ref operator*() const { return _node->_val; }// 指针操作，返回节点的值的指针Ptr operator->() const { return &_node->_val; }// 前向移动ListIterator& operator++() {_node = _node->_next;return *this;}// 后向移动ListIterator& operator--() {_node = _node->_prev;return *this;}// 比较操作，判断两个迭代器是否相等bool operator!=(const ListIterator& other) const { return _node != other._node; }private:Node* _node;};
}

 注意：此处Ref代表T&，Ptr代表T*。

下面我们将对上述代码进行测试，以检验在常量链表和非常量链表下是否能正常应用。

代码示例如下：

#include <iostream>struct CustomType {int x;
};int main() {// 创建三个 int 类型的节点，分别存储值 1、2、3W::ListNode<int> node1(1);      W::ListNode<int> node2(2);      W::ListNode<int> node3(3);      // 链接节点形成链表node1._next = &node2;node2._prev = &node1;node2._next = &node3;node3._prev = &node2;// 创建一个非常量迭代器W::ListIterator<int, int&, int*> it(&node1);std::cout << *it << std::endl;  // 输出 1++it;  // 前向移动std::cout << *it << std::endl;  // 输出 2// 修改节点的值*it = 20;std::cout << *it << std::endl;  // 输出 20// 创建一个常量链表节点const W::ListNode<int> constNode1(1);const W::ListNode<int> constNode2(2);constNode1._next = &constNode2;// 创建一个常量迭代器W::ListIterator<int, const int&, const int*> constIt(&constNode1);std::cout << *constIt << std::endl;  // 输出 1// 常量迭代器不允许修改值// *constIt = 10;  // 错误：无法修改常量链表节点的值return 0;
}

输出：

1
2
20
1 

分析：

1. 非常量链表：
   • 使用 it 迭代器遍历链表，前向移动并修改节点的值。*it = 20 修改了第二个节点的值。
2. 常量链表：
   • 使用 constIt 迭代器只能读取节点的值，无法修改。如果尝试 *constIt = 10，编译器会报错，禁止修改。

三. list的相关操作

3.1 list的构造函数

我们将实现多种构造函数，允许用户创建空链表、指定大小的链表，以及从迭代器区间构造链表。

namespace W {template<class T>class list {typedef ListNode<T> Node;public:typedef ListIterator<T, T&, T*> iterator;// 默认构造函数list() { CreateHead(); }// 指定大小的构造函数list(size_t n, const T& val = T()) {CreateHead();for (size_t i = 0; i < n; ++i)push_back(val);}// 迭代器区间构造函数template<class Iterator>list(Iterator first, Iterator last) {CreateHead();while (first != last) {push_back(*first);++first;}}// 析构函数~list() {clear();delete _head;}// 头节点初始化void CreateHead() {_head = new Node();_head->_next = _head;_head->_prev = _head;}// 清空链表void clear() {Node* cur = _head->_next;while (cur != _head) {Node* next = cur->_next;delete cur;cur = next;}_head->_next = _head;_head->_prev = _head;}private:Node* _head;  // 指向头节点的指针};
}

构造函数分析：

1. 默认构造函数：创建一个空链表，并初始化头节点。
2. 指定大小构造函数：使用 push_back 向链表中插入 n 个值为 val 的节点。
3. 迭代器区间构造函数：通过一对迭代器 [first, last) 形成的区间构造链表。

3.2 插入与删除

list 容器的优势在于高效的插入与删除操作。我们将在指定位置插入节点，或删除指定节点，插入和删除的时间复杂度均为 O(1)。 

插入操作

namespace W {template<class T>class list {typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;public:// 在指定位置前插入新节点iterator insert(iterator pos, const T& val) {Node* newNode = new Node(val);Node* cur = pos._node;newNode->_next = cur;newNode->_prev = cur->_prev;cur->_prev->_next = newNode;cur->_prev = newNode;return iterator(newNode);//将Node*强制转换为iterator}// 在链表末尾插入新节点void push_back(const T& val) { insert(end(), val); }// 在链表头部插入新节点void push_front(const T& val) { insert(begin(), val); }};
}

 注意：在返回值处如果已经完成了iterator用Node*类型数据的构造函数，则会进行隐式类型转换，无需强制转换。

• 插入效率：由于链表的结构，插入操作只需调整节点的指针，不涉及大规模的内存移动，时间复杂度为 O(1)。
• 头尾插入：通过 push_back 和 push_front 可以方便地在链表的头部和尾部插入新节点。

 删除操作

代码示例如下：

namespace W {template<class T>class list {typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;public:// 删除指定位置的节点iterator erase(iterator pos) {Node* cur = pos._node;Node* nextNode = cur->_next;cur->_prev->_next = cur->_next;cur->_next->_prev = cur->_prev;delete cur;return iterator(nextNode);}// 删除链表头部节点void pop_front() { erase(begin()); }// 删除链表尾部节点void pop_back() { erase(--end()); }};
}

 注意：在返回值处如果已经完成了iterator用Node*类型数据的构造函数，则会进行隐式类型转换，无需强制转换。

• 删除效率：删除节点同样是通过调整指针实现，时间复杂度为 O(1)。
• 头尾删除：通过 pop_front 和 pop_back 实现头部和尾部节点的删除。

四. 反向迭代器的设计

在双向链表中，反向迭代器可以通过包装普通迭代器实现。反向迭代器的 ++ 对应正向迭代器的 --，反之亦然。

代码示例如下：

namespace W {template<class Iterator>class ReverseListIterator {Iterator _it;public:ReverseListIterator(Iterator it) : _it(it) {}auto operator*() { Iterator temp = _it; --temp; return *temp; }auto operator->() { return &(operator*()); }ReverseListIterator& operator++() { --_it; return *this; }ReverseListIterator operator++(int) { ReverseListIterator temp = *this; --_it; return temp; }ReverseListIterator& operator--() { ++_it; return *this; }ReverseListIterator operator--(int) { ReverseListIterator temp = *this; ++_it; return temp; }bool operator==(const ReverseListIterator& other) const { return _it == other._it; }bool operator!=(const ReverseListIterator& other) const { return !(*this == other); }};
}

• 解引用和指针操作：反向迭代器的 operator* 和 operator-> 实际上是操作前一个节点。
• 前向和后向移动：反向迭代器的 ++ 操作是通过调用普通迭代器的 -- 来实现的。

五. 迭代器的失效问题

在操作 list 容器时，特别是在删除节点的过程中，可能会出现迭代器失效问题。迭代器失效是指当某个节点被删除后，指向该节点的迭代器变得无效，继续使用这个迭代器将导致未定义行为。因此，在删除节点后，必须使用返回的迭代器进行下一步操作，以避免迭代器失

假设我们使用 erase 函数删除链表中的节点。如果我们继续使用之前的迭代器而不更新它，程序将会崩溃，因为该迭代器指向的内存已经被释放。 

注意：erase返回的是删除元素的下一个！！！

 常见错误示例如下：

void WrongIteratorUsage() {W::list<int> lst = {1, 2, 3, 4, 5};auto it = lst.begin();while (it != lst.end()) {lst.erase(it);  // 错误：删除后 it 失效++it;  // 未更新的迭代器继续操作，导致崩溃}
}

 改正代码示例如下：

void TestIteratorInvalidation() {W::list<int> lst = {1, 2, 3, 4, 5};auto it = lst.begin();while (it != lst.end()) {it = lst.erase(it);  // 正确：使用 erase 返回的新迭代器}
}

 小结：

本篇模拟实现了list的底层结构，迭代器，一系列构造函数，运算符重载和相关接口，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！