0


深度剖析C++STL:手持list利剑,破除编程重重难题(下)

前言:

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

一. list的底层结构

  1. list

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

具体代码示例如下:

  1. namespace W {
  2. // 定义链表节点
  3. template<class T>
  4. struct ListNode {
  5. T _val; // 节点存储的值
  6. ListNode* _prev; // 指向前一个节点
  7. ListNode* _next; // 指向后一个节点
  8. ListNode(const T& val = T()) : _val(val), _prev(nullptr), _next(nullptr) {}
  9. };
  10. }

分析:

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

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

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

二. list的迭代器

2.1 迭代器的概念与实现

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

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

接下来,我们将实现

  1. ListIterator

,它内部保存一个指向

  1. ListNode

的指针

  1. _node

,并支持以下基本操作:

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

具体代码示例如下:

  1. namespace W {
  2. template<class T>
  3. class ListIterator {
  4. typedef ListNode<T> Node; // 使用 Node 表示链表节点类型
  5. public:
  6. // 构造函数,接受一个指向链表节点的指针
  7. ListIterator(Node* node = nullptr) : _node(node) {}
  8. // 解引用操作,返回节点的值
  9. T& operator*() { return _node->_val; }
  10. // 前向移动操作,指向下一个节点
  11. ListIterator& operator++() {
  12. _node = _node->_next; // 将当前节点移动到下一个节点
  13. return *this; // 返回自身以支持链式调用
  14. }
  15. // 比较操作,判断两个迭代器是否相等
  16. bool operator!=(const ListIterator& other) const { return _node != other._node; }
  17. private:
  18. Node* _node; // 迭代器指向的链表节点
  19. };
  20. }
  1. 构造函数:初始化一个指向链表节点的指针 _node,用于遍历链表。
  2. **operator***:返回节点存储的值 _val
  3. **operator++**:将迭代器移动到链表中的下一个节点。
  4. **operator!=**:用于判断两个迭代器是否相等。

2.2 迭代器拼接为list的测试

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

代码示例如下:

  1. #include <iostream>
  2. int main() {
  3. // 创建三个节点,分别存储值 1、2、3
  4. W::ListNode<int> node1(1);
  5. W::ListNode<int> node2(2);
  6. W::ListNode<int> node3(3);
  7. // 链接节点形成链表
  8. node1._next = &node2; // node1 的下一个节点是 node2
  9. node2._prev = &node1; // node2 的前一个节点是 node1
  10. node2._next = &node3; // node2 的下一个节点是 node3
  11. node3._prev = &node2; // node3 的前一个节点是 node2
  12. // 创建迭代器,指向第一个节点
  13. W::ListIterator<int> it(&node1);
  14. // 使用迭代器遍历链表并输出每个节点的值
  15. while (it != nullptr) {
  16. std::cout << *it << std::endl; // 输出当前节点的值
  17. ++it; // 前向移动到下一个节点
  18. }
  19. return 0;
  20. }

输出:

1
2
3

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

代码示例如下:

  1. namespace W {
  2. template<class T>
  3. class ListIterator {
  4. typedef ListNode<T> Node;
  5. public:
  6. ListIterator(Node* node = nullptr) : _node(node) {}
  7. // 解引用操作,返回节点的值
  8. T& operator*() { return _node->_val; }
  9. // 指针操作,返回节点的指针
  10. T* operator->() { return &(_node->_val); }
  11. // 前向移动
  12. ListIterator& operator++() {
  13. _node = _node->_next;
  14. return *this;
  15. }
  16. // 后向移动
  17. ListIterator& operator--() {
  18. _node = _node->_prev;
  19. return *this;
  20. }
  21. // 比较操作
  22. bool operator!=(const ListIterator& other) const { return _node != other._node; }
  23. private:
  24. Node* _node;
  25. };
  26. }

我们通过一个测试程序验证迭代器的前向后向移动功能,同时通过

  1. ->

运算符访问链表节点的值。我们会分别测试基本数据类型

  1. int

和自定义类型

  1. CustomType

的场景,展示迭代器在不同数据类型下的使用方式。

  1. 对于 int 类型,我们可以通过 *it 来访问节点的值,而不需要使用 *(it->),虽然 *(it->) 也是合法的,但没有必要。
  2. **对于自定义类型 CustomType**,可以通过 it->x 来访问自定义类型 CustomType 中的成员变量 x

测试代码示例如下:

  1. #include <iostream>
  2. struct CustomType {
  3. int x;
  4. };
  5. int main() {
  6. // 创建三个 int 类型的节点,分别存储值 1、2、3
  7. W::ListNode<int> node1(1);
  8. W::ListNode<int> node2(2);
  9. W::ListNode<int> node3(3);
  10. // 链接节点形成链表
  11. node1._next = &node2;
  12. node2._prev = &node1;
  13. node2._next = &node3;
  14. node3._prev = &node2;
  15. // 创建迭代器,初始指向第二个节点
  16. W::ListIterator<int> it(&node2);
  17. // 对于 int 类型,使用 *it 访问节点的值
  18. std::cout << *it << std::endl; // 输出 2
  19. // 后向移动,指向第一个节点
  20. --it;
  21. std::cout << *it << std::endl; // 输出 1
  22. // 前向移动,指向第三个节点
  23. ++it;
  24. ++it;
  25. std::cout << *it << std::endl; // 输出 3
  26. // 创建自定义类型 CustomType 的节点
  27. W::ListNode<CustomType> customNode1({1});
  28. W::ListNode<CustomType> customNode2({2});
  29. customNode1._next = &customNode2;
  30. customNode2._prev = &customNode1;
  31. // 创建自定义类型 CustomType 的迭代器
  32. W::ListIterator<CustomType> customIt(&customNode1);
  33. // 使用 it-> 访问 CustomType 的成员变量 x
  34. std::cout << customIt->x << std::endl; // 输出 1
  35. return 0;
  36. }

输出:

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的其他元素。

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

  1. #include <iostream>
  2. template<class T>
  3. struct ListNode {
  4. T _val;
  5. ListNode* _prev;
  6. ListNode* _next;
  7. ListNode(T val) : _val(val), _prev(nullptr), _next(nullptr) {}
  8. };
  9. template<class T>
  10. class ListIterator {
  11. typedef ListNode<T> Node;
  12. public:
  13. ListIterator(Node* node = nullptr) : _node(node) {}
  14. // 解引用操作,返回节点的值
  15. T& operator*() { return _node->_val; }
  16. // 前向移动
  17. ListIterator& operator++() {
  18. _node = _node->_next;
  19. return *this;
  20. }
  21. // 后向移动
  22. ListIterator& operator--() {
  23. _node = _node->_prev;
  24. return *this;
  25. }
  26. private:
  27. Node* _node;
  28. };
  29. int main() {
  30. // 创建三个节点,分别存储值 1、2、3
  31. ListNode<int> node1(1), node2(2), node3(3);
  32. // 链接节点形成链表
  33. node1._next = &node2;
  34. node2._prev = &node1;
  35. node2._next = &node3;
  36. node3._prev = &node2;
  37. // 尝试创建一个 const 迭代器
  38. const ListIterator<int> constIt(&node1);
  39. // 错误1:前向移动时,编译器报错,因为 ++ 操作符不能对 const 迭代器操作
  40. ++constIt; // 编译错误
  41. // 错误2:解引用操作也无法进行修改
  42. *constIt = 5; // 编译错误
  43. }

错误分析:

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

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

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

为了处理上述问题,我们可以使用模板参数来区分

  1. const

  1. non-const

的情况。通过模板参数

  1. Ref

  1. Ptr

,我们可以控制迭代器的行为,使得它在常量链表和非常量链表中都能正常工作。

使用模板参数的好处:

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

代码示例如下:

  1. namespace W {
  2. template<class T, class Ref, class Ptr>
  3. class ListIterator {
  4. typedef ListNode<T> Node; // 使用 Node 表示链表节点类型
  5. public:
  6. ListIterator(Node* node = nullptr) : _node(node) {}
  7. // 解引用操作,返回节点的值
  8. Ref operator*() const { return _node->_val; }
  9. // 指针操作,返回节点的值的指针
  10. Ptr operator->() const { return &_node->_val; }
  11. // 前向移动
  12. ListIterator& operator++() {
  13. _node = _node->_next;
  14. return *this;
  15. }
  16. // 后向移动
  17. ListIterator& operator--() {
  18. _node = _node->_prev;
  19. return *this;
  20. }
  21. // 比较操作,判断两个迭代器是否相等
  22. bool operator!=(const ListIterator& other) const { return _node != other._node; }
  23. private:
  24. Node* _node;
  25. };
  26. }

** 注意:此处Ref代表T&,Ptr代表T*

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

代码示例如下:

  1. #include <iostream>
  2. struct CustomType {
  3. int x;
  4. };
  5. int main() {
  6. // 创建三个 int 类型的节点,分别存储值 1、2、3
  7. W::ListNode<int> node1(1);
  8. W::ListNode<int> node2(2);
  9. W::ListNode<int> node3(3);
  10. // 链接节点形成链表
  11. node1._next = &node2;
  12. node2._prev = &node1;
  13. node2._next = &node3;
  14. node3._prev = &node2;
  15. // 创建一个非常量迭代器
  16. W::ListIterator<int, int&, int*> it(&node1);
  17. std::cout << *it << std::endl; // 输出 1
  18. ++it; // 前向移动
  19. std::cout << *it << std::endl; // 输出 2
  20. // 修改节点的值
  21. *it = 20;
  22. std::cout << *it << std::endl; // 输出 20
  23. // 创建一个常量链表节点
  24. const W::ListNode<int> constNode1(1);
  25. const W::ListNode<int> constNode2(2);
  26. constNode1._next = &constNode2;
  27. // 创建一个常量迭代器
  28. W::ListIterator<int, const int&, const int*> constIt(&constNode1);
  29. std::cout << *constIt << std::endl; // 输出 1
  30. // 常量迭代器不允许修改值
  31. // *constIt = 10; // 错误:无法修改常量链表节点的值
  32. return 0;
  33. }

输出:

1
2
20
1

分析:

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

三. list的相关操作

3.1 list的构造函数

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

  1. namespace W {
  2. template<class T>
  3. class list {
  4. typedef ListNode<T> Node;
  5. public:
  6. typedef ListIterator<T, T&, T*> iterator;
  7. // 默认构造函数
  8. list() { CreateHead(); }
  9. // 指定大小的构造函数
  10. list(size_t n, const T& val = T()) {
  11. CreateHead();
  12. for (size_t i = 0; i < n; ++i)
  13. push_back(val);
  14. }
  15. // 迭代器区间构造函数
  16. template<class Iterator>
  17. list(Iterator first, Iterator last) {
  18. CreateHead();
  19. while (first != last) {
  20. push_back(*first);
  21. ++first;
  22. }
  23. }
  24. // 析构函数
  25. ~list() {
  26. clear();
  27. delete _head;
  28. }
  29. // 头节点初始化
  30. void CreateHead() {
  31. _head = new Node();
  32. _head->_next = _head;
  33. _head->_prev = _head;
  34. }
  35. // 清空链表
  36. void clear() {
  37. Node* cur = _head->_next;
  38. while (cur != _head) {
  39. Node* next = cur->_next;
  40. delete cur;
  41. cur = next;
  42. }
  43. _head->_next = _head;
  44. _head->_prev = _head;
  45. }
  46. private:
  47. Node* _head; // 指向头节点的指针
  48. };
  49. }
构造函数分析:
  1. 默认构造函数:创建一个空链表,并初始化头节点。
  2. 指定大小构造函数:使用 push_back 向链表中插入 n 个值为 val 的节点。
  3. 迭代器区间构造函数:通过一对迭代器 [first, last) 形成的区间构造链表。

3.2 插入与删除

  1. list

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

插入操作

  1. namespace W {
  2. template<class T>
  3. class list {
  4. typedef ListNode<T> Node;
  5. typedef ListIterator<T, T&, T*> iterator;
  6. public:
  7. // 在指定位置前插入新节点
  8. iterator insert(iterator pos, const T& val) {
  9. Node* newNode = new Node(val);
  10. Node* cur = pos._node;
  11. newNode->_next = cur;
  12. newNode->_prev = cur->_prev;
  13. cur->_prev->_next = newNode;
  14. cur->_prev = newNode;
  15. return iterator(newNode);//将Node*强制转换为iterator
  16. }
  17. // 在链表末尾插入新节点
  18. void push_back(const T& val) { insert(end(), val); }
  19. // 在链表头部插入新节点
  20. void push_front(const T& val) { insert(begin(), val); }
  21. };
  22. }

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

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

删除操作

代码示例如下:

  1. namespace W {
  2. template<class T>
  3. class list {
  4. typedef ListNode<T> Node;
  5. typedef ListIterator<T, T&, T*> iterator;
  6. public:
  7. // 删除指定位置的节点
  8. iterator erase(iterator pos) {
  9. Node* cur = pos._node;
  10. Node* nextNode = cur->_next;
  11. cur->_prev->_next = cur->_next;
  12. cur->_next->_prev = cur->_prev;
  13. delete cur;
  14. return iterator(nextNode);
  15. }
  16. // 删除链表头部节点
  17. void pop_front() { erase(begin()); }
  18. // 删除链表尾部节点
  19. void pop_back() { erase(--end()); }
  20. };
  21. }

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

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

四. 反向迭代器的设计

在双向链表中,反向迭代器可以通过包装普通迭代器实现。反向迭代器的

  1. ++

对应正向迭代器的

  1. --

,反之亦然。

代码示例如下:

  1. namespace W {
  2. template<class Iterator>
  3. class ReverseListIterator {
  4. Iterator _it;
  5. public:
  6. ReverseListIterator(Iterator it) : _it(it) {}
  7. auto operator*() { Iterator temp = _it; --temp; return *temp; }
  8. auto operator->() { return &(operator*()); }
  9. ReverseListIterator& operator++() { --_it; return *this; }
  10. ReverseListIterator operator++(int) { ReverseListIterator temp = *this; --_it; return temp; }
  11. ReverseListIterator& operator--() { ++_it; return *this; }
  12. ReverseListIterator operator--(int) { ReverseListIterator temp = *this; ++_it; return temp; }
  13. bool operator==(const ReverseListIterator& other) const { return _it == other._it; }
  14. bool operator!=(const ReverseListIterator& other) const { return !(*this == other); }
  15. };
  16. }
  • 解引用和指针操作:反向迭代器的 operator*operator-> 实际上是操作前一个节点。
  • 前向和后向移动:反向迭代器的 ++ 操作是通过调用普通迭代器的 -- 来实现的。

五. 迭代器的失效问题

**在操作

  1. list

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

**假设我们使用

  1. erase

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

注意:erase返回的是删除元素的下一个!!!

常见错误示例如下:

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

改正代码示例如下:

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

** 小结:**

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

** **



标签: c++ list 开发语言

本文转载自: https://blog.csdn.net/2303_81060385/article/details/143895671
版权归原作者 诚丞成 所有, 如有侵权,请联系我们删除。

“深度剖析C++STL:手持list利剑,破除编程重重难题(下)”的评论:

还没有评论