【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)

文章目录

  • 从零实现 `list` 容器:细粒度剖析与代码实现
    • 前言
      • 1. `list` 的核心数据结构
        • 1.1节点结构分析:
      • 2. 迭代器设计与实现
        • 2.1 为什么 `list` 需要迭代器?
        • 2.2 实现一个简单的迭代器
          • 2.2.1 迭代器代码实现:
          • 2.2.2 解释:
        • 2.3 测试简单迭代器
          • 2.3.1 测试代码:
          • 2.3.2 输出:
          • 2.3.3 解释:
        • 2.4 增加后向移动和 `->` 运算符
          • 2.4.1关键点:
          • 2.4.2 增加后向移动和 `->` 运算符的实现代码:
        • 2.5 测试前后移动和 `->` 运算符
          • 2.5.1 目的:
          • 2.5.2 测试代码:
          • 2.5.3 输出:
          • 2.5.4 解释:
        • 2.6 为什么不能简单使用 `const` 修饰?
          • 2.6.1 问题解释:
          • 2.6.2 为什么不能简单使用 `const` 修饰?
          • 2.6.3 错误示例:直接使用 `const` 修饰
          • 2.6.4 错误代码:
          • 2.6.5 错误分析:
        • 2.7 正确的解决方案:使用模板参数区分 `const` 和 `non-const`
          • 2.7.1 使用模板参数的好处:
          • 2.7.2 实现代码:
        • 2.8 测试模板泛化后的迭代器
          • 2.8.1 测试代码:
          • 2.8.2 输出结果:
          • 2.8.3 解释:
      • 3. `list` 容器的基本操作
        • 3.1 构造函数
        • 3.2 构造函数分析:
      • 4. 插入与删除操作
        • 4.1 插入操作
          • 4.1.1 插入操作分析:
        • 4.2 删除操作
          • 4.2.1 删除操作分析:
      • 5. 反向迭代器的设计
        • 5.1 反向迭代器分析:
      • 6. 迭代器失效问题
        • 6.1 删除操作中的迭代器失效
        • 6.2 错误使用示例
        • 6.3 解决方案
      • 7. 总结与展望
    • 完整的 `list` 容器实现代码

从零实现 list 容器:细粒度剖析与代码实现

接上篇【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器

💬 欢迎讨论:学习过程中有问题吗?随时在评论区与我交流。你们的互动是我创作的动力!

👍 支持我:如果你觉得这篇文章对你有帮助,请点赞、收藏并分享给更多朋友吧!
🚀 一起成长:欢迎分享给更多对计算机视觉和图像处理感兴趣的小伙伴,让我们共同进步!

本文详细介绍如何从零开始实现一个 C++ list 容器,帮助读者深入理解 list 的底层实现,包括核心数据结构、迭代器的设计、以及常见的插入、删除等操作。从初学者到进阶开发者都能从中受益。


前言

在 C++ 标准模板库 (STL) 中,list 是一种双向链表容器,适合频繁的插入和删除操作。它与 vector 的主要区别在于 list 不支持随机访问,并且在进行插入、删除操作时无需移动其他元素。这使得 list 在某些需要大量动态修改元素的场景下具有独特优势,例如链表的插入删除操作具有 O(1) 的时间复杂度。

为了更好地理解 list 的工作原理,本文将从零开始实现一个简化版的 list,并详细分析每个步骤背后的实现原理及其易错点。


1. 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.1节点结构分析:
  1. _val:存储节点的数据。
  2. _prev 和 _next:分别指向前一个节点和后一个节点,便于实现双向链表的遍历、插入和删除操作。

该结构简单明了,双向链表的节点可以方便地进行前向和后向操作。接下来我们将实现如何使用该结构构建一个完整的 list 容器。


2. 迭代器设计与实现

2.1 为什么 list 需要迭代器?

在 C++ 中,vector 是一种动态数组,元素在内存中是连续存储的,因此我们可以使用下标快速访问元素,例如 vec[0] 可以直接访问 vector 的第一个元素。而 list 底层是通过链表结构实现的,每个节点在内存中的位置并不连续。因此,链表无法像数组一样通过下标随机访问元素。每个节点都通过指针链接到前一个节点(_prev)和后一个节点(_next)。为了遍历链表,我们需要使用迭代器。

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


2.2 实现一个简单的迭代器

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

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

  1. 解引用操作:通过 *it 访问链表节点中的值。
  2. 前向移动操作:通过 ++it 访问链表中的下一个节点。
  3. 比较操作:通过 it != end() 判断两个迭代器是否相等。
2.2.1 迭代器代码实现:
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;  // 迭代器指向的链表节点};
}
2.2.2 解释:
  1. 构造函数:初始化一个指向链表节点的指针 _node,用于遍历链表。
  2. operator*:返回节点存储的值 _val
  3. operator++:将迭代器移动到链表中的下一个节点。
  4. operator!=:用于判断两个迭代器是否相等。

2.3 测试简单迭代器

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

2.3.1 测试代码:
#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;
}
2.3.2 输出:
1
2
3
2.3.3 解释:
  1. 迭代器 it 初始指向第一个节点 node1
  2. 通过 *it 获取节点的值,并通过 ++it 将迭代器移动到下一个节点,直到链表末尾。

2.4 增加后向移动和 -> 运算符

目前的迭代器只能进行前向移动,而 list双向链表,因此我们还需要增加后向移动 (--) 的功能,使迭代器可以从链表末尾向前遍历。同时,为了让迭代器像指针一样操作,我们还需要重载 -> 运算符,以便可以通过 -> 访问链表节点的成员。

2.4.1关键点:
  1. _val 是基本数据类型(如 int)时,可以直接通过 *it 来获取节点的值,而不需要使用 *(it->)。虽然 *(it->) 语法上是正确的,但显得繁琐且不必要。

    为什么 *(it->) 是正确的?
    因为 it-> 是在调用 operator->(),返回 _val 的指针,然后 *(it->) 解引用该指针。语法上是没有问题的,但通常我们直接使用 *it 更简洁。

  2. _val 是自定义类型时,可以使用 it->x 直接访问自定义类型的成员变量 x。编译器会将 it->x 优化为 it.operator->()->x,让访问更加方便。

2.4.2 增加后向移动和 -> 运算符的实现代码:
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;};
}

2.5 测试前后移动和 -> 运算符
2.5.1 目的:

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

2.5.2 测试代码:
  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.5.3 输出:
2
1
3
1
2.5.4 解释:
  1. 对于 int 类型的节点,我们通过 *it 访问节点的值,++it--it 分别实现了前向和后向移动。
  2. 对于自定义类型 CustomType 的节点,通过 it->x 可以访问自定义类型成员变量 x。编译器会将 it->x 优化为 it.operator->()->x,使得操作简化。

2.6 为什么不能简单使用 const 修饰?
2.6.1 问题解释:

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

2.6.2 为什么不能简单使用 const 修饰?
  • const 修饰的迭代器会限制所有成员的修改,包括迭代器内部的 _node 指针。如果我们对 const 迭代器执行 ++-- 操作,这些操作会修改 _node,而 const 禁止这种修改。
2.6.3 错误示例:直接使用 const 修饰

下面是一个简单的错误示例,展示了为什么简单地使用 const 修饰符会导致问题:

2.6.4 错误代码:
#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;  // 编译错误
}
2.6.5 错误分析:
  1. 无法执行前向移动 (++constIt):由于 const 修饰符限制了修改成员变量 _node,因此 ++ 操作无法执行,因为该操作会修改迭代器的内部指针。

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


2.7 正确的解决方案:使用模板参数区分 constnon-const

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

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

2.8 测试模板泛化后的迭代器

现在我们通过测试来验证模板参数 RefPtr 的设计是否能够正确处理常量链表和非常量链表的迭代器情况。以下场景将会被测试:

  1. 非常量链表:迭代器允许修改节点的值。
  2. 常量链表const 迭代器只能读取节点值,不能修改。
2.8.1 测试代码:
#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;
}
2.8.2 输出结果:
1
2
20
1
2.8.3 解释:
  1. 非常量链表
    • 使用 it 迭代器遍历链表,前向移动并修改节点的值。*it = 20 修改了第二个节点的值。
  2. 常量链表
    • 使用 constIt 迭代器只能读取节点的值,无法修改。如果尝试 *constIt = 10,编译器会报错,禁止修改。

3. list 容器的基本操作

3.1 构造函数

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

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;  // 指向头节点的指针};
}
3.2 构造函数分析:
  1. 默认构造函数:创建一个空链表,并初始化头节点。
  2. 指定大小构造函数:使用 push_back 向链表中插入 n 个值为 val 的节点。
  3. 迭代器区间构造函数:通过一对迭代器 [first, last) 形成的区间构造链表。

4. 插入与删除操作

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

4.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);}// 在链表末尾插入新节点void push_back(const T& val) { insert(end(), val); }// 在链表头部插入新节点void push_front(const T& val) { insert(begin(), val); }};
}
4.1.1 插入操作分析:
  • 插入效率:由于链表的结构,插入操作只需调整节点的指针,不涉及大规模的内存移动,时间复杂度为 O(1)。
  • 头尾插入:通过 push_backpush_front 可以方便地在链表的头部和尾部插入新节点。

4.2 删除操作
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()); }};
}
4.2.1 删除操作分析:
  • 删除效率:删除节点同样是通过调整指针实现,时间复杂度为 O(1)。
  • 头尾删除:通过 pop_frontpop_back 实现头部和尾部节点的删除。

5. 反向迭代器的设计

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

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); }};
}
5.1 反向迭代器分析:
  • 解引用和指针操作:反向迭代器的 operator*operator-> 实际上是操作前一个节点。
  • 前向和后向移动:反向迭代器的 ++ 操作是通过调用普通迭代器的 -- 来实现的。

6. 迭代器失效问题

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

6.1 删除操作中的迭代器失效

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

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

下面的示例展示了错误的迭代器使用方式,迭代器在删除操作后没有更新,导致其指向了已被释放的内存。

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

为了解决迭代器失效问题,每次删除节点后都要使用 erase 返回的新迭代器,确保迭代器指向的内存有效。

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

7. 总结与展望

通过这篇文章,我们从零开始模拟实现了一个 list 容器,并深入剖析了以下几个方面:

  • 双向链表的核心数据结构:理解链表节点的 _prev_next 指针,以及如何通过它们实现双向遍历。
  • 迭代器的设计:实现了 list 的正向和反向迭代器,支持前向移动、后向移动和解引用操作。
  • 模板参数解决 constnon-const 场景:通过模板参数 RefPtr,灵活应对 const 链表和非常量链表的不同需求,保证代码的安全性和灵活性。
  • 插入与删除操作:高效的插入和删除操作,时间复杂度均为 O(1),体现了链表结构的优势。
  • 反向迭代器的实现:通过包装普通迭代器,设计了一个反向迭代器,方便反向遍历链表。
  • 迭代器失效问题:讲解了迭代器失效的原因及其解决方法,避免了未定义行为。

今后,读者您可以尝试进一步扩展这篇文章中的 list 容器,例如:

  • 实现更多的容器操作:如 findsort 等高级操作。
  • 实现与 STL 接口兼容的完整 list 容器:包括迭代器失效的处理、异常安全的插入与删除操作。
  • 性能优化与内存管理:如使用自定义的内存池优化链表的节点分配和释放。

通过持续的实践和优化,我们能够更深入地理解 C++ 标准库的实现细节,并在开发过程中提高代码的效率和健壮性。


完整的 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) {}};// 正向迭代器template<class T, class Ref, class Ptr>class ListIterator {typedef ListNode<T> 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;};// 反向迭代器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); }};// list 容器实现template<class T>class list {typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;public:list() { CreateHead(); }list(size_t n, const T& val = T()) {CreateHead();for (size_t i = 0; i < n; ++i)push_back(val);}~list() {clear();delete _head;}iterator begin() { return iterator(_head->_next); }iterator end() { return iterator(_head); }void push_back(const T& val) { insert(end(), val); }void push_front(const T& val) { insert(begin(), val); }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);}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()); }void clear() {Node* cur = _head->_next;while (cur != _head) {Node* next = cur->_next;delete cur;cur = next;}_head->_next = _head;_head->_prev = _head;}private:void CreateHead() {_head = new Node();_head->_next = _head;_head->_prev = _head;}Node* _head;};
}

以上就是关于【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析的内容啦,各位大佬有什么问题欢迎在评论区指正,或者私信我也是可以的啦,您的支持是我创作的最大动力!❤️

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/434109.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

设置VsCode搜索时排除文件,文件列表中隐藏文件

按照《VsCode gdb gdbserver远程调试C程序》中介绍的方法&#xff0c;配置好VsCode后&#xff0c;打开一个C/C工程&#xff0c;发现左侧的面板会显示编译时生成的中间文件&#xff08;比如.d和.o文件&#xff09;。我们可以通过设置隐藏掉一些我们不需要打开的文件以简洁面板…

如何使用 DomCrawler 进行复杂的网页数据抓取?

在互联网时代&#xff0c;数据是宝贵的资源。无论是市场分析、客户洞察还是内容聚合&#xff0c;从网页中抓取数据都是一项关键技能。Symfony 的 DomCrawler 是一个强大的工具&#xff0c;可以帮助开发者从复杂的网页中提取所需的数据。本文将详细介绍如何使用 DomCrawler 进行…

SO-ELM预测 | MATLAB实现SO-ELM蛇群算法优化极限学习机多输入单输出

回归预测 | MATLAB实现SO-ELM蛇群算法优化极限学习机多输入单输出 目录 回归预测 | MATLAB实现SO-ELM蛇群算法优化极限学习机多输入单输出效果一览基本介绍程序设计效果一览 基本介绍 Matlab实现SO-ELM蛇群算法优化极限学习机多变量回归预测 1.data为数据集,7个输入特征,1个输…

C#和数据库高级:密封类和方法覆盖

文章目录 一、密封类关键字&#xff1a;sealed方法覆盖 面向对象三大特性总结 一、密封类 关键字&#xff1a;sealed 方法覆盖 面向对象三大特性总结

Java项目实战II基于Java+Spring Boot+MySQL的厨艺交流平台设计与实现(源码+数据库+文档)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。获取源码联系方式请查看文末 一、前言 在美食文化…

记一次停车场后台管理系统漏洞挖掘

漏洞描述 停车场后台管理系统是一种专为停车场管理者设计的综合管理平台&#xff0c;旨在提供全面、高效、智能的停车场运营管理解决方案&#xff0c;系统利用现代信息技术&#xff0c;如物联网、大数据、云计算等&#xff0c;实现对停车场内车辆进出、车位管理、费用结算、安…

多模态——基于XrayGLM的X光片诊断的多模态大模型

0.引言 近年来&#xff0c;通用领域的大型语言模型&#xff08;LLM&#xff09;&#xff0c;如ChatGPT&#xff0c;已在遵循指令和生成类似人类的响应方面取得了显著成就。这些成就不仅推动了多模态大模型研究的热潮&#xff0c;也催生了如MiniGPT-4、mPLUG-Owl、Multimodal-G…

【工具分享】DoNex勒索病毒解密工具

前言 DoNex勒索软件首次被发现于2024年3月&#xff0c;是由一系列早期勒索软件演变而来&#xff0c;包括2022年4月首次出现的Muse、2022年11月的假冒LockBit 3.0&#xff0c;以及2023年5月的DarkRace。这款勒索软件主要针对美国、意大利和荷兰的企业&#xff0c;使用复杂的加密…

日本IT-正社员、契约社员、个人事业主该如何选?

正社員&#xff1a;就是「正规社员」的意思&#xff0c;按照公司的规定而直接雇用&#xff0c;而且没有制定雇用期间&#xff0c;基本上是以终身雇用至退休年龄&#xff08;70岁&#xff09;为前提。而被雇用的一方需要听从公司的业务命令&#xff0c;包括职位或职场的调迁&…

AI名词扫盲

本篇章主要介绍一些AI研究方向的名词以及解释&#xff0c;后续会持续补充&#xff0c;名词解释与时间顺序无关&#xff0c;欢迎各位大佬们在评论区查漏补缺。 目录 AI&#xff08;Artificial Intelligence&#xff0c;人工智能&#xff09;卷积神经网络&#xff08;CNN&#xf…

巧用枚举消除条件判断

shigen坚持更新文章的博客写手&#xff0c;记录成长&#xff0c;分享认知&#xff0c;留住感动。个人IP&#xff1a;shigen 在上一篇的文章结合HashMap与Java 8的Function和Optional消除ifelse判断中有讲到如何结合HashMap与Java 8的Function和Optional消除ifelse判断&#xff…

Linux进程切换以及调度算法

目录 Linux进程切换以及调度算法 Linux进程切换介绍 前置知识 进程切换过程分析 调度算法 补充知识 Linux进程切换以及调度算法 Linux进程切换介绍 前面提到&#xff0c;分时操作系统下&#xff0c;CPU会在多个进程中做高速切换以实现多个进程看似同时执行的&#xff0…

open-resty 服务安装redis插件

从github下载 作者&#xff1a;程序那点事儿 日期&#xff1a;2023/11/16 22:04 lua-resty-redis-cluster cd /usr/local/openresty/modules #进入到modules目录git clone https://github.com/cuiweixie/lua-resty-redis-cluster.git #下载插件mv lua-resty-redis-cluster/ …

字节跳动青训营x豆包Marscode 技术训练营报名啦!

最近字节跳动青训营又开营了&#xff0c;作为第二次参加的我来给没有了解过的同学从几个方面简单介绍一下。 青训营是什么 青训营是字节跳动 稀土掘金 社区发起的技术系列培训 & 人才选拔项目&#xff0c;面向在校大学生&#xff0c; 课程全程免费&#xff0c;包含前端、…

git小乌龟

下载git小乌龟 官方地址 Download – TortoiseGit – Windows Shell Interface to Git git小乌龟下载 选择自己对应的版本进行下载 安装完成后我们会发现是英文&#xff0c;这对我们这些英语不好的很不友好&#xff0c;所以就需要下载语言包 下载对应语言包 安装完成后我们…

Java Web —— 第十天(SpringBoot原理)

SpringBoot框架之所以使用起来更简单更快捷&#xff0c;是因为SpringBoot框架底层提供了两个非常重要的 功能&#xff1a;一个是起步依赖&#xff0c;一个是自动配置。 通过SpringBoot所提供的起步依赖&#xff0c;就可以大大的简化pom文件当中依赖的配置&#xff0c;从而解决…

React学习笔记(四)——React 组件生命周期

目录 1. 生命周期-概览 2. 生命周期-挂载阶段 3. 生命周期-更新阶段 4. 生命周期-卸载阶段 5. setState扩展-发现问题 6. setState扩展-更多用法 7. setState扩展-异步 1. 生命周期-概览 了解react类组件生命周期整体情况 大致步骤&#xff1a; 什么是生命周期React类组…

CentOS 修改服务器登录密码的完整指南

个人名片 &#x1f393;作者简介&#xff1a;java领域优质创作者 &#x1f310;个人主页&#xff1a;码农阿豪 &#x1f4de;工作室&#xff1a;新空间代码工作室&#xff08;提供各种软件服务&#xff09; &#x1f48c;个人邮箱&#xff1a;[2435024119qq.com] &#x1f4f1…

【Linux】ubuntu 16.04 搭建jdk 11 环境(亲测可用)

目录 0.环境 1.题外话 2.详细 0.环境 windows11 主机 Virtual Box 7.0 ubuntu 16.04系统 想搭建个 jdk11的环境&#xff0c;用于项目 1.题外话 因为虚拟机与主机传输文件不方便&#xff0c;所以可以尝试用共享文件夹的方式传输&#xff0c;亲测可用&#xff0c;参考以下博…

2024-09-27 buildroot C和语言将 中文的GBK编码转换为 UTF-8 的代码, printf 显示出来,使用 iconv 库去实现。

一、GBK 的英文全称是 "Guobiao Kuozhan"&#xff0c;意为 "National Standard Extended"。它是对 GB2312 编码的扩展&#xff0c;用于表示更多汉字和符号 GBK&#xff08;国标扩展汉字编码&#xff09;是一种用于简体中文和繁体中文字符的编码方式&#x…