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

news/2024/11/27 1:32:25/

文章目录

须知

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

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对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/news/1550201.html

相关文章

嵌入式Linux移植cJSON库

嵌入式Linux移植cJSON库

嵌入式Linux移植cJSON库 一、前言二、移植三、常用函数四、代码案例五、注意事项一、前言 在使用嵌入式系统做项目时，碰见了使用JSON格式数据的需求，所以需要移植cJSON库进行组织和解析数据。 二、移植 cJSON的github地址：https://github.com/DaveGamble/cJSON，可以在git仓…
阅读更多...
僵尸毁灭工程 服务搭建 联机教程 无需公网IP、服务器

僵尸毁灭工程 服务搭建 联机教程 无需公网IP、服务器

主要内容 什么是僵尸毁灭工程 搭建该服务&#xff0c;需要准备什么 详细步骤 1.下载并运行 SteamCMD 2.下载僵尸毁灭服务端 3.运行 MoleSDN 进行异地联机 4.小伙伴皮蛋加入鼠鼠服务器 完成联机 什么是僵尸毁灭工程 一款由The Indie Stone开发的开放世界生存模拟游戏。游…
阅读更多...
WebRTC音视频同步原理与实现详解（上）

WebRTC音视频同步原理与实现详解（上）

第一章、RTP时间戳与NTP时间戳 1.1 RTP时间戳 时间戳&#xff0c;用来定义媒体负载数据的采样时刻&#xff0c;从单调线性递增的时钟中获取&#xff0c;时钟的精度由 RTP 负载数据的采样频率决定。 音频和视频的采样频率是不一样的&#xff0c;一般音频的采样频率有 8KHz、…
阅读更多...
【linux】插入新硬盘如何配置：格式化、分区、自动挂载（Ubuntu）

【linux】插入新硬盘如何配置：格式化、分区、自动挂载（Ubuntu）

文章目录 具体方法GPT分区表&#xff08;GUID Partition Table&#xff09;&#xff08;建议都用这种分区方法&#xff09;MBR分区表方法&#xff08;最大支持2TB分区&#xff09;&#xff08;Master Boot Record&#xff09; 附加&#xff1a;如何查看硬盘的型号另外&#xff…
阅读更多...
如何使用 Python 开发一个简单的文本数据转换为 Excel 工具

如何使用 Python 开发一个简单的文本数据转换为 Excel 工具

目录 一、准备工作 二、理解文本数据格式 三、开发文本数据转换为Excel工具 读取CSV文件 将DataFrame写入Excel文件 处理其他格式的文本数据 读取纯文本文件： 读取TSV文件： 四、完整代码与工具封装 五、使用工具 六、总结 在数据分析和处理的日常工作中，我们经常…
阅读更多...
spark 3.4.4 利用Spark ML中的交叉验证、管道流实现鸢尾花分类预测案例选取最优模型

spark 3.4.4 利用Spark ML中的交叉验证、管道流实现鸢尾花分类预测案例选取最优模型

前情回顾 前面的案例中&#xff0c;介绍了怎么基于管道流实现啊鸢尾花案例&#xff0c;利用逻辑斯蒂回归模型预测。详细内容步骤可以参照相应的博客内容 本案例内容 在 Spark 中使用交叉验证结合逻辑回归&#xff08;Logistic Regression&#xff09;以及管道流&#xff08;P…
阅读更多...
Sickos1.1 详细靶机思路 实操笔记

Sickos1.1 详细靶机思路 实操笔记

Sickos1.1 详细靶机思路 实操笔记 免责声明 本博客提供的所有信息仅供学习和研究目的&#xff0c;旨在提高读者的网络安全意识和技术能力。请在合法合规的前提下使用本文中提供的任何技术、方法或工具。如果您选择使用本博客中的任何信息进行非法活动&#xff0c;您将独自承担…
阅读更多...
业务架构、数据架构、应用架构和技术架构

业务架构、数据架构、应用架构和技术架构

TOGAF(The Open Group Architecture Framework)是一个广泛应用的企业架构框架&#xff0c;旨在帮助组织高效地进行架构设计和管理。 TOGAF 的核心就是由我们熟知的四大架构领域组成:业务架构、数据架构、应用架构和技术架构。 企业数字化架构设计中的最常见要素是4A 架构。 4…
阅读更多...
最新文章

Copyright @ 2022~2023