当前位置： 首页 > article >正文

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

article 2024/11/26 16:24:27

文章目录

须知

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

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对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、3
    W::ListNode<int> node1(1);      
    W::ListNode<int> node2(2);      
    W::ListNode<int> node3(3);      

    // 链接节点形成链表
    node1._next = &node2;  // node1 的下一个节点是 node2
    node2._prev = &node1;  // node2 的前一个节点是 node1
    node2._next = &node3;  // node2 的下一个节点是 node3
    node3._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、3
    W::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 的成员变量 x
    std::cout << customIt->x << std::endl;  // 输出 1

    return 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、3
    W::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.kler.cn/a/410171.html

相关文章：

  • [每日一氵] 拆分 pip install git+https://github.com/xxx/xx.git@bece3d4
  • webrtc音频模块介绍(二) ADM
  • GitLab 备份与恢复
  • [极客大挑战 2019]BabySQL--详细解析
  • 802.11协议
  • Flutter：SlideTransition位移动画，Interval动画延迟
  • 类和对象plus版
  • 量化交易系统开发-实时行情自动化交易-4.4.做市策略
  • 蓝桥杯每日真题 - 第22天
  • Wireshark抓取HTTPS流量技巧
  • 量子生成对抗网络
  • docker镜像、容器、仓库介绍
  • Flutter：启动屏逻辑处理01：修改默认APP启动图标
  • 大数据实战——MapReduce案例实践
  • Node.js的http模块：创建HTTP服务器、客户端示例
  • uniapp+vue2重新进入小程序就清除缓存，设备需要重新扫码
  • 实现飞2米高的框架(c语言版)
  • 网络渗透测试工具推荐与简介
  • MySQL获取数据库内所有表格数据总数
  • 解决getSubject is supported only if a security manager is allowed
  • HarmonyOS NEXT应用元服务开发Intents Kit（意图框架服务）习惯推荐方案开发者测试
  • 计算机网络——第3章 数据链路层（自学笔记）
  • 机器学习中数据集Upsampling和Downsampling是什么意思？中英文介绍
  • Spring Boot 实战：基于 Validation 注解实现分层数据校验与校验异常拦截器统一返回处理
  • IDEA 2024安装指南（含安装包以及使用说明 cannot collect jvm options 问题一）
  • PostgreSQL 中约束Constraints