【C++篇】深度解析 C++ List 容器：底层设计与实现揭秘

ops/2024/11/26 20:36:40/

文章目录

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！

 1.背景

1.1 C++List容器简介

 在 C++ 标准模板库（STL）中，std::list 是一种基于双向链表的数据结构容器，提供高效的动态内存管理和插入、删除操作。由于其底层实现特点，它在以下场景中尤为适合：

  • 频繁插入和删除操作：双向链表的插入和删除时间复杂度为 O(1)，而动态数组（如 std::vector）在中间插入或删除可能需要移动大量元素，时间复杂度为 O(n)。
  • 内存分散存储：链表无需连续存储空间，适合大规模动态数据管理，避免数组因空间不足频繁扩展的问题。
  • 迭代器的稳定性：链表的节点操作不会使迭代器失效（除非删除当前节点）。

1.2 为什么要手动实现List容器 

手动实现 std::list 容器主要有以下几个目的：

  1. 深入理解 STL 原理
    学习 STL 的使用很常见，但深入理解其背后的设计思想和实现细节却能显著提高编程能力。例如，手动实现 std::list 能帮助理解：

    • 数据结构（双向链表）的工作机制。
    • 指针操作的应用场景及其陷阱（如野指针、内存泄漏等）。
    • 算法的复杂度优化。

  2. 学习数据结构与算法
    手动实现 std::list 是学习和巩固链表数据结构的最佳方式。通过构造、插入、删除、遍历等操作的实现，可以更深入理解链表这种经典数据结构及其适用场景。

  3. 掌握 C++ 编程核心技能
    手动实现过程中会接触到许多 C++ 的核心特性：

    • 模板（实现泛型 List 容器）。
    • RAII 和智能指针（处理内存管理）。
    • 异常安全和边界情况处理。

  4. 灵活性与定制化需求
    std::list 适用于一般场景，但在特殊需求下可能需要自定义实现。例如：

    • 提供专门优化的操作接口。
    • 定制内存分配策略（如减少内存碎片）。
    • 引入多线程支持或锁机制。

  5. 增强调试与优化能力
    自己实现容器能够提高调试复杂数据结构的能力，同时通过分析 STL 实现与自己的差异，进一步理解容器的性能优化策略。

 1.3 特点

  • 底层实现：双向链表

    • 每个节点包含三个部分：数据域（data）、前向指针（prev） 和 后向指针（next）。
    • 节点之间通过指针相连，形成链式存储结构。

  • 动态内存分配

    • 插入或删除节点时，只需调整指针，无需像数组那样移动大量元素。

  • 高效的插入和删除

    • 插入和删除操作的时间复杂度为 O(1)（只需调整指针）。

  • 双向访问

    • 可以从任意节点向前或向后遍历，灵活性更高。

  • 缺点

    • 额外的内存开销：每个节点需要额外存储两个指针，占用更多空间。
    • 随机访问性能较差：链表不支持直接索引访问，定位元素需要从头或尾逐步遍历，时间复杂度为 O(n)。

 C++ 中的 List 容器是一个基于双向链表的容器，它在插入和删除操作上性能优越，适用于需要频繁动态调整数据的场景。在这篇文章中，我们将从零开始模拟实现一个简化版的 List 容器，深度剖析其底层原理。

 2. C++List核心概念

2.1 核心概念

双向链表（Doubly Linked List）

  • 结构特点：
    双向链表是由一系列独立的节点组成，每个节点包含三部分：

    • 数据域：存储实际数据。
    • 前向指针（prev）：指向前一个节点。
    • 后向指针（next）：指向后一个节点。

    节点之间通过指针连接，形成链式结构，既可以向前遍历，也可以向后遍历。

template<typename T>
struct Node {
    T data;        // 节点数据
    Node* prev;    // 指向前一个节点
    Node* next;    // 指向后一个节点
};

  • 起点和终点：

    • 双向链表通常有两个特殊节点：头节点（head） 和 尾节点（tail）：

    • 尾节点：链表的终点，next 指针指向 NULL。
    • 头节点：链表的起点，prev 指针指向 NULL。
    • 动态内存管理
      • 链表的每个节点在需要时动态分配内存。链表的容量只受限于系统内存，而不像数组需要提前分配固定大小的空间。
      • 使用动态分配的方式，每个节点在内存中分散存储，无需连续内存空间。
    • 迭代器支持 
  • std::list 提供了双向迭代器（Bidirectional Iterator），支持从头到尾的顺序遍历，也支持从尾到头的逆向遍历。
  • 由于链表不支持随机访问，std::list 的迭代器无法像 std::vector 那样直接通过索引定位元素。

3.C++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插入与删除

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.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()); }};
}

5. 迭代器设计思路与实现

5.1 迭代器设计思路

迭代器的核心思想是对容器的内部结构提供抽象访问，同时保持与容器一致的操作方式。对于 list 容器来说：

  • 迭代器内部保存一个指向链表节点的指针，通过该指针对链表进行遍历和访问。
  • 重载操作符，如 *、++、--，使迭代器的使用更像指针操作。

 5.2 简单版迭代器

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;  // 迭代器指向的链表节点};
}
5.2.1  解释：
  1. 构造函数：初始化一个指向链表节点的指针 _node，用于遍历链表。
  2. operator*：返回节点存储的值 _val。
  3. operator++：将迭代器移动到链表中的下一个节点。
  4. operator!=：用于判断两个迭代器是否相等。
5.2.2 测试链表的准确性

创建新的节点，使用模拟实现的迭代器输出节点的值。测试

#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

 5.3 强化版迭代器

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

 注意：

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

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;};
}
5.3.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> 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;
}

 5.4 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;};
}
5.4.1 测试const迭代器
#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;
}

5.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); }};
}

6. 迭代器失效问题

6.1 erase行为导致迭代器失效

6.1.1 正确示例：
std::list<int> myList = {10, 20, 30, 40};
for (auto it = myList.begin(); it != myList.end(); ) {if (*it == 20) {it = myList.erase(it); // 返回删除元素后下一个有效迭代器} else {++it;}
}

6.1.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.1.3 解决方案

更新迭代器或者从新获取迭代器

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

 最后

在完成对 C++ list 容器的模拟实现后，我们回顾了整个实现的核心要点：

  1. 数据结构设计
    使用双向链表作为底层存储结构，为 list 的高效插入和删除操作奠定了基础。

  2. 迭代器机制
    实现了仿 STL 的双向迭代器，使我们可以方便地遍历和操作链表，进一步贴近 STL 的使用体验。

  3. 功能扩展
    模拟实现了 push_back、push_front、erase 等基本操作，并通过合理的设计，保证了性能和稳定性。

  4. 潜在问题处理
    我们分析了迭代器失效等潜在问题，并提供了解决方案，确保代码的可靠性和可维护性。

学习与实践的收获

通过手动实现 list 容器，不仅加深了对 STL 容器工作原理的理解，也提升了设计数据结构与操作接口的能力。这种动手实践的过程，是巩固 C++ 编程基础、深入学习 STL 的重要一步。

下一步建议：可以尝试实现其他 STL 容器（如 vector 或 map），并对比其性能和使用场景的差异。同时，将模拟实现的 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;};
}

下一篇文章再会！！！


http://www.ppmy.cn/ops/136920.html

相关文章

可视化建模与UML《活动图实验报告》

可视化建模与UML《活动图实验报告》

你当像鸟飞往你的山。 一、实验目的&#xff1a; 1、熟悉活动图的基本功能和使用方法。 2、掌握使用建模工具软件绘制协作图的方法 二、实验环境&#xff1a; window7 | 10 | 11 EA15 三、实验内容&#xff1a; <1>绘制学生选课系统中添加课程(Add Course)用例的活动图…
阅读更多...
es写入磁盘的过程以及相关优化

es写入磁盘的过程以及相关优化

数据写入到内存buffer同时写入到数据到translog buffer，这是为了防止数据不会丢失每隔1s数据从buffer中refresh到FileSystemCache中，生成segment文件，这是因为写入磁盘的过程相对耗时，借助FileSystemCache，一旦生成segment文件，就能通过索引查询到了refresh完，memory bu…
阅读更多...
STM32端口模拟编码器输入

STM32端口模拟编码器输入

文章目录 前言一、正交编码器是什么&#xff1f;二、使用步骤2.1开启时钟2.2配置编码器引脚 TIM3 CH1(PA6) CH2 (PA7)上拉输入2.3.初始化编码器时基2.4 初始化编码器输入2.5 配置编码器接口2.6 开启定时器2.7获取编码器数据 三、参考程序四、测试结果4.1测试方法4.2串口输出结果…
阅读更多...
PD虚拟机启动后 Mac主机无法上网解决教程

PD虚拟机启动后 Mac主机无法上网解决教程

部分用户在运行Parallels Desktop的Windows 11打开后&#xff0c;Windows上网没有问题 &#xff0c;但是Mac主机不能访问带域名的网站&#xff0c;而访问带ip的网站没问题&#xff0c;退出parallels虚拟机以后&#xff0c;mac网络恢复正常。 解决&#xff1a; 退出 Parallels D…
阅读更多...
Pytorch使用手册-Build the Neural Network（专题五）

Pytorch使用手册-Build the Neural Network（专题五）

在 PyTorch 中如何构建一个用于 FashionMNIST 数据集分类的神经网络模型，并解析了 PyTorch 的核心模块 torch.nn 的使用方法。以下是具体内容的讲解： 构建神经网络 在 PyTorch 中，神经网络的核心在于 torch.nn 模块，它提供了构建神经网络所需的所有工具。关键点如下： nn.…
阅读更多...
redis模糊匹配key内存分析的脚本

redis模糊匹配key内存分析的脚本

效果&#xff1a; 脚本 与 redis-cli 命令放在同一路径下执行脚本 注意&#xff1a; 1、SCAN 命令仅扫描当前节点的键&#xff0c;若要扫描整个集群中的所有节点&#xff0c;建议在各个从节点上分别执行&#xff1b; 2、为避免扫描对业务产生影响&#xff1a; 可以在从节点或…
阅读更多...
利用DeepFlow解决APISIX故障诊断中的方向偏差问题

利用DeepFlow解决APISIX故障诊断中的方向偏差问题

概要&#xff1a;随着APISIX作为IT应用系统入口的普及&#xff0c;其故障定位能力的不足导致了在业务故障诊断中&#xff0c;APISIX常常成为首要的“嫌疑对象”。这不仅导致了“兴师动众”式的资源投入&#xff0c;还可能使诊断方向“背道而驰”&#xff0c;从而导致业务故障“…
阅读更多...
SpringBoot线程池的使用

SpringBoot线程池的使用

SpringBoot线程池的使用 在现代Web应用开发中&#xff0c;特别是在使用Spring Boot框架时&#xff0c;合理使用线程池可以显著提高应用的性能和响应速度。线程池不仅能够减少线程创建和销毁的开销&#xff0c;还能有效地控制并发任务的数量&#xff0c;避免因线程过多而导致的…
阅读更多...
最新文章

Copyright @ 2022~2023