0
0

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

文章目录

从零实现

  1. list

容器：细粒度剖析与代码实现

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

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

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

本文详细介绍如何从零开始实现一个 C++ 

  1. list

容器，帮助读者深入理解 

  1. list

的底层实现，包括核心数据结构、迭代器的设计、以及常见的插入、删除等操作。从初学者到进阶开发者都能从中受益。

前言

在 C++ 标准模板库 (STL) 中，

  1. list

是一种双向链表容器，适合频繁的插入和删除操作。它与 

  1. vector

的主要区别在于 

  1. list

不支持随机访问，并且在进行插入、删除操作时无需移动其他元素。这使得 

  1. list

在某些需要大量动态修改元素的场景下具有独特优势，例如链表的插入删除操作具有 O(1) 的时间复杂度。

为了更好地理解 

  1. list

的工作原理，本文将从零开始实现一个简化版的 

  1. list

，并详细分析每个步骤背后的实现原理及其易错点。

1.

  1. list

的核心数据结构

在 

  1. list

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

  1. namespace W {// 定义链表节点template<classT>structListNode{
  2.         T _val;// 节点存储的值
  3.         ListNode* _prev;// 指向前一个节点
  4.         ListNode* _next;// 指向后一个节点ListNode(const T& val =T()):_val(val),_prev(nullptr),_next(nullptr){}};}
1.1节点结构分析：
  1. _val：存储节点的数据。
  2. _prev 和 _next：分别指向前一个节点和后一个节点，便于实现双向链表的遍历、插入和删除操作。

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

  1. list

容器。

2. 迭代器设计与实现

2.1 为什么
  1. list

需要迭代器？

在 C++ 中，

  1. vector

是一种动态数组，元素在内存中是连续存储的，因此我们可以使用下标快速访问元素，例如 

  1. vec[0]

可以直接访问 

  1. vector

的第一个元素。而 

  1. list

底层是通过链表结构实现的，每个节点在内存中的位置并不连续。因此，链表无法像数组一样通过下标随机访问元素。每个节点都通过指针链接到前一个节点（

  1. _prev

）和后一个节点（

  1. _next

）。为了遍历链表，我们需要使用迭代器。

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

2.2 实现一个简单的迭代器

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

接下来，我们将实现 

  1. ListIterator

，它内部保存一个指向 

  1. ListNode

的指针 

  1. _node

，并支持以下基本操作：

  1. 解引用操作：通过 *it 访问链表节点中的值。
  2. 前向移动操作：通过 ++it 访问链表中的下一个节点。
  3. 比较操作：通过 it != end() 判断两个迭代器是否相等。
2.2.1 迭代器代码实现：
  1. namespace W {template<classT>classListIterator{typedef ListNode<T> Node;// 使用 Node 表示链表节点类型public:// 构造函数，接受一个指向链表节点的指针ListIterator(Node* node =nullptr):_node(node){}// 解引用操作，返回节点的值
  2.         T&operator*(){return _node->_val;}// 前向移动操作，指向下一个节点
  3.         ListIterator&operator++(){
  4.             _node = _node->_next;// 将当前节点移动到下一个节点return*this;// 返回自身以支持链式调用}// 比较操作，判断两个迭代器是否相等booloperator!=(const ListIterator& other)const{return _node != other._node;}private:
  5.         Node* _node;// 迭代器指向的链表节点};}
2.2.2 解释：
  1. 构造函数：初始化一个指向链表节点的指针 _node，用于遍历链表。
  2. **operator***：返回节点存储的值 _val。
  3. **operator++**：将迭代器移动到链表中的下一个节点。
  4. **operator!=**：用于判断两个迭代器是否相等。
2.3 测试简单迭代器

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

2.3.1 测试代码：
  1. #include<iostream>intmain(){// 创建三个节点，分别存储值 1、2、3
  2.     W::ListNode<int>node1(1);      
  3.     W::ListNode<int>node2(2);      
  4.     W::ListNode<int>node3(3);// 链接节点形成链表
  5.     node1._next =&node2;// node1 的下一个节点是 node2
  6.     node2._prev =&node1;// node2 的前一个节点是 node1
  7.     node2._next =&node3;// node2 的下一个节点是 node3
  8.     node3._prev =&node2;// node3 的前一个节点是 node2// 创建迭代器，指向第一个节点
  9.     W::ListIterator<int>it(&node1);// 使用迭代器遍历链表并输出每个节点的值while(it !=nullptr){
  10.         std::cout <<*it << std::endl;// 输出当前节点的值++it;// 前向移动到下一个节点}return0;}
2.3.2 输出：
  1. 123
2.3.3 解释：
  1. 迭代器 it 初始指向第一个节点 node1。
  2. 通过 *it 获取节点的值，并通过 ++it 将迭代器移动到下一个节点，直到链表末尾。
2.4 增加后向移动和
  1. ->

运算符

目前的迭代器只能进行前向移动，而 

  1. list

是双向链表，因此我们还需要增加后向移动 (

  1. --

) 的功能，使迭代器可以从链表末尾向前遍历。同时，为了让迭代器像指针一样操作，我们还需要重载 

  1. ->

运算符，以便可以通过 

  1. ->

访问链表节点的成员。

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 增加后向移动和
  1. ->

运算符的实现代码：

  1. namespace W {template<classT>classListIterator{typedef ListNode<T> Node;public:ListIterator(Node* node =nullptr):_node(node){}// 解引用操作，返回节点的值
  2.         T&operator*(){return _node->_val;}// 指针操作，返回节点的指针
  3.         T*operator->(){return&(_node->_val);}// 前向移动
  4.         ListIterator&operator++(){
  5.             _node = _node->_next;return*this;}// 后向移动
  6.         ListIterator&operator--(){
  7.             _node = _node->_prev;return*this;}// 比较操作booloperator!=(const ListIterator& other)const{return _node != other._node;}private:
  8.         Node* _node;};}
2.5 测试前后移动和
  1. ->

运算符

2.5.1 目的：

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

  1. ->

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

  1. int

和自定义类型 

  1. CustomType

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

2.5.2 测试代码：
  1. 对于 int 类型，我们可以通过 *it 来访问节点的值，而不需要使用 *(it->)，虽然 *(it->) 也是合法的，但没有必要。
  2. **对于自定义类型 CustomType**，可以通过 it->x 来访问自定义类型 CustomType 中的成员变量 x。
  1. #include<iostream>structCustomType{int x;};intmain(){// 创建三个 int 类型的节点，分别存储值 1、2、3
  2.     W::ListNode<int>node1(1);      
  3.     W::ListNode<int>node2(2);      
  4.     W::ListNode<int>node3(3);// 链接节点形成链表
  5.     node1._next =&node2;
  6.     node2._prev =&node1;
  7.     node2._next =&node3;
  8.     node3._prev =&node2;// 创建迭代器，初始指向第二个节点
  9.     W::ListIterator<int>it(&node2);// 对于 int 类型，使用 *it 访问节点的值
  10.     std::cout <<*it << std::endl;// 输出 2// 后向移动，指向第一个节点--it;
  11.     std::cout <<*it << std::endl;// 输出 1// 前向移动，指向第三个节点++it;++it;
  12.     std::cout <<*it << std::endl;// 输出 3// 创建自定义类型 CustomType 的节点
  13.     W::ListNode<CustomType>customNode1({1});
  14.     W::ListNode<CustomType>customNode2({2});
  15.     customNode1._next =&customNode2;
  16.     customNode2._prev =&customNode1;// 创建自定义类型 CustomType 的迭代器
  17.     W::ListIterator<CustomType>customIt(&customNode1);// 使用 it-> 访问 CustomType 的成员变量 x
  18.     std::cout << customIt->x << std::endl;// 输出 1return0;}
2.5.3 输出：
  1. 2131
2.5.4 解释：
  1. 对于 int 类型的节点，我们通过 *it 访问节点的值，++it 和 --it 分别实现了前向和后向移动。
  2. 对于自定义类型 CustomType 的节点，通过 it->x 可以访问自定义类型成员变量 x。编译器会将 it->x 优化为 it.operator->()->x，使得操作简化。
2.6 为什么不能简单使用
  1. const

修饰？

2.6.1 问题解释：

在 

  1. vector

中，

  1. const_iterator

通过 

  1. const

修饰符即可实现不可修改的迭代器，这是因为 

  1. vector

的底层存储是连续的内存块，通过 

  1. const

限制访问的值即可。而 

  1. list

的底层是双向链表，迭代器不仅需要访问链表节点的值，还需要操作链表的前驱和后继节点（即 

  1. _prev

和 

  1. _next

指针）。**直接使用 

  1. const

修饰迭代器无法满足这些需求**，因为 

  1. const

限制了对链表结构的必要修改。

2.6.2 为什么不能简单使用
  1. const

修饰？

  • const 修饰的迭代器会限制所有成员的修改，包括迭代器内部的 _node 指针。如果我们对 const 迭代器执行 ++ 或 -- 操作，这些操作会修改 _node，而 const 禁止这种修改。
2.6.3 错误示例：直接使用
  1. const

修饰

下面是一个简单的错误示例，展示了为什么简单地使用 

  1. const

修饰符会导致问题：

2.6.4 错误代码：
  1. #include<iostream>template<classT>structListNode{
  2.     T _val;
  3.     ListNode* _prev;
  4.     ListNode* _next;ListNode(T val):_val(val),_prev(nullptr),_next(nullptr){}};template<classT>classListIterator{typedef ListNode<T> Node;public:ListIterator(Node* node =nullptr):_node(node){}// 解引用操作，返回节点的值
  5.     T&operator*(){return _node->_val;}// 前向移动
  6.     ListIterator&operator++(){
  7.         _node = _node->_next;return*this;}// 后向移动
  8.     ListIterator&operator--(){
  9.         _node = _node->_prev;return*this;}private:
  10.     Node* _node;};intmain(){// 创建三个节点，分别存储值 1、2、3
  11.     ListNode<int>node1(1),node2(2),node3(3);// 链接节点形成链表
  12.     node1._next =&node2;
  13.     node2._prev =&node1;
  14.     node2._next =&node3;
  15.     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 正确的解决方案：使用模板参数区分
  1. const

和 

  1. non-const

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

  1. const

和 

  1. non-const

的情况。通过模板参数 

  1. Ref

和 

  1. Ptr

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

2.7.1 使用模板参数的好处：
  • 灵活性：可以根据需要处理 const 和 non-const 的迭代器场景。
  • 安全性：对于常量链表，保证不能修改节点的值；对于非常量链表，允许修改。
  • 代码复用：通过模板参数，既可以编写一套代码，处理 const 和 non-const 两种情况。
2.7.2 实现代码：
  1. namespace W {template<classT,classRef,classPtr>classListIterator{typedef ListNode<T> Node;// 使用 Node 表示链表节点类型public:ListIterator(Node* node =nullptr):_node(node){}// 解引用操作，返回节点的值
  2.         Ref operator*()const{return _node->_val;}// 指针操作，返回节点的值的指针
  3.         Ptr operator->()const{return&_node->_val;}// 前向移动
  4.         ListIterator&operator++(){
  5.             _node = _node->_next;return*this;}// 后向移动
  6.         ListIterator&operator--(){
  7.             _node = _node->_prev;return*this;}// 比较操作，判断两个迭代器是否相等booloperator!=(const ListIterator& other)const{return _node != other._node;}private:
  8.         Node* _node;};}
2.8 测试模板泛化后的迭代器

现在我们通过测试来验证模板参数 

  1. Ref

和 

  1. Ptr

的设计是否能够正确处理常量链表和非常量链表的迭代器情况。以下场景将会被测试：

  1. 非常量链表：迭代器允许修改节点的值。
  2. 常量链表：const 迭代器只能读取节点值，不能修改。
2.8.1 测试代码：
  1. #include<iostream>structCustomType{int x;};intmain(){// 创建三个 int 类型的节点，分别存储值 1、2、3
  2.     W::ListNode<int>node1(1);      
  3.     W::ListNode<int>node2(2);      
  4.     W::ListNode<int>node3(3);// 链接节点形成链表
  5.     node1._next =&node2;
  6.     node2._prev =&node1;
  7.     node2._next =&node3;
  8.     node3._prev =&node2;// 创建一个非常量迭代器
  9.     W::ListIterator<int,int&,int*>it(&node1);
  10.     std::cout <<*it << std::endl;// 输出 1++it;// 前向移动
  11.     std::cout <<*it << std::endl;// 输出 2// 修改节点的值*it =20;
  12.     std::cout <<*it << std::endl;// 输出 20// 创建一个常量链表节点const W::ListNode<int>constNode1(1);const W::ListNode<int>constNode2(2);
  13.     constNode1._next =&constNode2;// 创建一个常量迭代器
  14.     W::ListIterator<int,constint&,constint*>constIt(&constNode1);
  15.     std::cout <<*constIt << std::endl;// 输出 1// 常量迭代器不允许修改值// *constIt = 10;  // 错误：无法修改常量链表节点的值return0;}
2.8.2 输出结果：
  1. 12201
2.8.3 解释：
  1. 非常量链表： - 使用 it 迭代器遍历链表，前向移动并修改节点的值。*it = 20 修改了第二个节点的值。
  2. 常量链表： - 使用 constIt 迭代器只能读取节点的值，无法修改。如果尝试 *constIt = 10，编译器会报错，禁止修改。

3.

  1. list

容器的基本操作

3.1 构造函数

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

  1. namespace W {template<classT>classlist{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<classIterator>list(Iterator first, Iterator last){CreateHead();while(first != last){push_back(*first);++first;}}// 析构函数~list(){clear();delete _head;}// 头节点初始化voidCreateHead(){
  2.             _head =newNode();
  3.             _head->_next = _head;
  4.             _head->_prev = _head;}// 清空链表voidclear(){
  5.             Node* cur = _head->_next;while(cur != _head){
  6.                 Node* next = cur->_next;delete cur;
  7.                 cur = next;}
  8.             _head->_next = _head;
  9.             _head->_prev = _head;}private:
  10.         Node* _head;// 指向头节点的指针};}
3.2 构造函数分析：
  1. 默认构造函数：创建一个空链表，并初始化头节点。
  2. 指定大小构造函数：使用 push_back 向链表中插入 n 个值为 val 的节点。
  3. 迭代器区间构造函数：通过一对迭代器 [first, last) 形成的区间构造链表。

4. 插入与删除操作

  1. list

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

4.1 插入操作
  1. namespace W {template<classT>classlist{typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;public:// 在指定位置前插入新节点
  2.         iterator insert(iterator pos,const T& val){
  3.             Node* newNode =newNode(val);
  4.             Node* cur = pos._node;
  6.             newNode->_next = cur;
  7.             newNode->_prev = cur->_prev;
  8.             cur->_prev->_next = newNode;
  9.             cur->_prev = newNode;returniterator(newNode);}// 在链表末尾插入新节点voidpush_back(const T& val){insert(end(), val);}// 在链表头部插入新节点voidpush_front(const T& val){insert(begin(), val);}};}
4.1.1 插入操作分析：
  • 插入效率：由于链表的结构，插入操作只需调整节点的指针，不涉及大规模的内存移动，时间复杂度为 O(1)。
  • 头尾插入：通过 push_back 和 push_front 可以方便地在链表的头部和尾部插入新节点。
4.2 删除操作
  1. namespace W {template<classT>classlist{typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;public:// 删除指定位置的节点
  2.         iterator erase(iterator pos){
  3.             Node* cur = pos._node;
  4.             Node* nextNode = cur->_next;
  6.             cur->_prev->_next = cur->_next;
  7.             cur->_next->_prev = cur->_prev;delete cur;returniterator(nextNode);}// 删除链表头部节点voidpop_front(){erase(begin());}// 删除链表尾部节点voidpop_back(){erase(--end());}};}
4.2.1 删除操作分析：
  • 删除效率：删除节点同样是通过调整指针实现，时间复杂度为 O(1)。
  • 头尾删除：通过 pop_front 和 pop_back 实现头部和尾部节点的删除。

5. 反向迭代器的设计

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

  1. ++

对应正向迭代器的 

  1. --

，反之亦然。

  1. namespace W {template<classIterator>classReverseListIterator{
  2.         Iterator _it;public:ReverseListIterator(Iterator it):_it(it){}autooperator*(){ Iterator temp = _it;--temp;return*temp;}autooperator->(){return&(operator*());}
  4.         ReverseListIterator&operator++(){--_it;return*this;}
  5.         ReverseListIterator operator++(int){ ReverseListIterator temp =*this;--_it;return temp;}
  6.         ReverseListIterator&operator--(){++_it;return*this;}
  7.         ReverseListIterator operator--(int){ ReverseListIterator temp =*this;++_it;return temp;}booloperator==(const ReverseListIterator& other)const{return _it == other._it;}booloperator!=(const ReverseListIterator& other)const{return!(*this== other);}};}
5.1 反向迭代器分析：
  • 解引用和指针操作：反向迭代器的 operator* 和 operator-> 实际上是操作前一个节点。
  • 前向和后向移动：反向迭代器的 ++ 操作是通过调用普通迭代器的 -- 来实现的。

6. 迭代器失效问题

在操作 

  1. list

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

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

假设我们使用 

  1. erase

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

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

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

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

为了解决迭代器失效问题，每次删除节点后都要使用 

  1. erase

返回的新迭代器，确保迭代器指向的内存有效。

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

7. 总结与展望

通过这篇文章，我们从零开始模拟实现了一个 

  1. list

容器，并深入剖析了以下几个方面：

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

今后，读者您可以尝试进一步扩展这篇文章中的 

  1. list

容器，例如：

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

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

完整的

  1. list

容器实现代码

最后，附上完整的代码实现，包括链表节点结构、迭代器、插入删除操作等。

  1. namespace W {// 链表节点结构template<classT>structListNode{
  2.         T _val;
  3.         ListNode* _prev;
  4.         ListNode* _next;ListNode(const T& val =T()):_val(val),_prev(nullptr),_next(nullptr){}};// 正向迭代器template<classT,classRef,classPtr>classListIterator{typedef ListNode<T> Node;public:ListIterator(Node* node =nullptr):_node(node){}
  6.         Ref operator*()const{return _node->_val;}
  7.         Ptr operator->()const{return&_node->_val;}
  9.         ListIterator&operator++(){
  10.             _node = _node->_next;return*this;}
  12.         ListIterator&operator--(){
  13.             _node = _node->_prev;return*this;}booloperator!=(const ListIterator& other)const{return _node != other._node;}private:
  14.         Node* _node;};// 反向迭代器template<classIterator>classReverseListIterator{
  15.         Iterator _it;public:ReverseListIterator(Iterator it):_it(it){}autooperator*(){ Iterator temp = _it;--temp;return*temp;}autooperator->(){return&(operator*());}
  17.         ReverseListIterator&operator++(){--_it;return*this;}
  18.         ReverseListIterator operator++(int){ ReverseListIterator temp =*this;--_it;return temp;}
  19.         ReverseListIterator&operator--(){++_it;return*this;}
  20.         ReverseListIterator operator--(int){ ReverseListIterator temp =*this;++_it;return temp;}booloperator==(const ReverseListIterator& other)const{return _it == other._it;}booloperator!=(const ReverseListIterator& other)const{return!(*this== other);}};// list 容器实现template<classT>classlist{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;}
  22.         iterator begin(){returniterator(_head->_next);}
  23.         iterator end(){returniterator(_head);}voidpush_back(const T& val){insert(end(), val);}voidpush_front(const T& val){insert(begin(), val);}
  25.         iterator insert(iterator pos,const T& val){
  26.             Node* newNode =newNode(val);
  27.             Node* cur = pos._node;
  29.             newNode->_next = cur;
  30.             newNode->_prev = cur->_prev;
  31.             cur->_prev->_next = newNode;
  32.             cur->_prev = newNode;returniterator(newNode);}
  34.         iterator erase(iterator pos){
  35.             Node* cur = pos._node;
  36.             Node* nextNode = cur->_next;
  38.             cur->_prev->_next = cur->_next;
  39.             cur->_next->_prev = cur->_prev;delete cur;returniterator(nextNode);}voidpop_front(){erase(begin());}voidpop_back(){erase(--end());}voidclear(){
  40.             Node* cur = _head->_next;while(cur != _head){
  41.                 Node* next = cur->_next;delete cur;
  42.                 cur = next;}
  43.             _head->_next = _head;
  44.             _head->_prev = _head;}private:voidCreateHead(){
  45.             _head =newNode();
  46.             _head->_next = _head;
  47.             _head->_prev = _head;}
  49.         Node* _head;};}

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

在这里插入图片描述

标签： c++ list windows
本文转载自: https://blog.csdn.net/2301_79849925/article/details/142532087
版权归原作者 Hoshiᅟᅠ      所有， 如有侵权，请联系我们删除。
登录后发布评论

“【C++篇】揭开 C++ STL list 容器的神秘面纱：从底层设计到高效应用的全景解析（附源码）”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航
从零实现