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

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

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

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

前言

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

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

1. `list` 的核心数据结构

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

代码语言：javascript复制

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节点结构分析：

_val：存储节点的数据。
_prev 和 _next：分别指向前一个节点和后一个节点，便于实现双向链表的遍历、插入和删除操作。

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

2. 迭代器设计与实现

2.1 为什么 `list` 需要迭代器？

在 C 中，vector 是一种动态数组，元素在内存中是连续存储的，因此我们可以使用下标快速访问元素，例如 vec[0] 可以直接访问 vector 的第一个元素。而 list 底层是通过链表结构实现的，每个节点在内存中的位置并不连续。因此，链表无法像数组一样通过下标随机访问元素。每个节点都通过指针链接到前一个节点（_prev）和后一个节点（_next）。为了遍历链表，我们需要使用迭代器。
迭代器的作用类似于一个指针，它指向链表中的某个节点，允许我们通过类似指针的方式来访问和操作链表节点。与普通指针不同，迭代器提供了更高级的功能，并且能够保持接口的一致性，因此它成为了 STL 容器中访问元素的核心工具。

2.2 实现一个简单的迭代器

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

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

解引用操作：通过 *it 访问链表节点中的值。
前向移动操作：通过 it 访问链表中的下一个节点。
比较操作：通过 it != end() 判断两个迭代器是否相等。

2.2.1 迭代器代码实现：

代码语言：javascript复制

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 解释：

构造函数：初始化一个指向链表节点的指针 _node，用于遍历链表。
operator*：返回节点存储的值 _val。
operator ：将迭代器移动到链表中的下一个节点。
operator!=：用于判断两个迭代器是否相等。

2.3 测试简单迭代器

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

2.3.1 测试代码：

代码语言：javascript复制

#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;
}

2.3.2 输出：

代码语言：javascript复制

1
2
3

2.3.3 解释：

迭代器 it 初始指向第一个节点 node1。
通过 *it 获取节点的值，并通过 it 将迭代器移动到下一个节点，直到链表末尾。

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

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

2.4.1关键点：

当 _val 是基本数据类型（如 int）时，可以直接通过 *it 来获取节点的值，而不需要使用 *(it->)。虽然 *(it->) 语法上是正确的，但显得繁琐且不必要。 为什么 *(it->) 是正确的？ 因为 it-> 是在调用 operator->()，返回 _val 的指针，然后 *(it->) 解引用该指针。语法上是没有问题的，但通常我们直接使用 *it 更简洁。
当 _val 是自定义类型时，可以使用 it->x 直接访问自定义类型的成员变量 x。编译器会将 it->x 优化为 it.operator->()->x，让访问更加方便。

2.4.2 增加后向移动和 `->` 运算符的实现代码：

代码语言：javascript复制

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 测试代码：

对于 int 类型，我们可以通过 *it 来访问节点的值，而不需要使用 *(it->)，虽然 *(it->) 也是合法的，但没有必要。
对于自定义类型 CustomType，可以通过 it->x 来访问自定义类型 CustomType 中的成员变量 x。

代码语言：javascript复制

#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;
}

2.5.3 输出：

代码语言：javascript复制

2.5.4 解释：

对于 int 类型的节点，我们通过 *it 访问节点的值， it 和 --it 分别实现了前向和后向移动。
对于自定义类型 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 错误代码：

代码语言：javascript复制

#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、3
    ListNode<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 错误分析：

无法执行前向移动 ( constIt)：由于 const 修饰符限制了修改成员变量 _node，因此操作无法执行，因为该操作会修改迭代器的内部指针。
无法修改节点的值 (*constIt = 5)：由于迭代器是 const 的，解引用操作也不能用于修改节点的值，因此编译器会报错。

2.7 正确的解决方案：使用模板参数区分 `const` 和 `non-const`

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

2.7.1 使用模板参数的好处：

灵活性：可以根据需要处理 const 和 non-const 的迭代器场景。
安全性：对于常量链表，保证不能修改节点的值；对于非常量链表，允许修改。
代码复用：通过模板参数，既可以编写一套代码，处理 const 和 non-const 两种情况。

2.7.2 实现代码：

代码语言：javascript复制

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 测试模板泛化后的迭代器

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

非常量链表：迭代器允许修改节点的值。
常量链表：const 迭代器只能读取节点值，不能修改。

2.8.1 测试代码：

代码语言：javascript复制

#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;
}

2.8.2 输出结果：

代码语言：javascript复制

2.8.3 解释：

非常量链表：
- 使用 it 迭代器遍历链表，前向移动并修改节点的值。*it = 20 修改了第二个节点的值。
常量链表：
- 使用 constIt 迭代器只能读取节点的值，无法修改。如果尝试 *constIt = 10，编译器会报错，禁止修改。

3. `list` 容器的基本操作

3.1 构造函数

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

代码语言：javascript复制

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 构造函数分析：

默认构造函数：创建一个空链表，并初始化头节点。
指定大小构造函数：使用 push_back 向链表中插入 n 个值为 val 的节点。
迭代器区间构造函数：通过一对迭代器 [first, last) 形成的区间构造链表。

4. 插入与删除操作

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

4.1 插入操作

代码语言：javascript复制

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_back 和 push_front 可以方便地在链表的头部和尾部插入新节点。

4.2 删除操作

代码语言：javascript复制

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_front 和 pop_back 实现头部和尾部节点的删除。

5. 反向迭代器的设计

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

代码语言：javascript复制

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

代码语言：javascript复制

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 错误使用示例

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

代码语言：javascript复制

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 返回的新迭代器，确保迭代器指向的内存有效。

代码语言：javascript复制

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

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

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

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

完整的 `list` 容器实现代码

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

代码语言：javascript复制

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 容器的神秘面纱：从底层设计到高效应用的全景解析的内容啦，各位大佬有什么问题欢迎在评论区指正，或者私信我也是可以的啦，您的支持是我创作的最大动力！❤️

stl 设计源码 c++ 容器

0 人点赞

【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` 容器：细粒度剖析与代码实现

1. `list` 的核心数据结构

2.1 为什么 `list` 需要迭代器？

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

2.4.2 增加后向移动和 `->` 运算符的实现代码：

2.5 测试前后移动和 `->` 运算符

2.6 为什么不能简单使用 `const` 修饰？

2.6.2 为什么不能简单使用 `const` 修饰？

2.6.3 错误示例：直接使用 `const` 修饰

2.7 正确的解决方案：使用模板参数区分 `const` 和 `non-const`

3. `list` 容器的基本操作

完整的 `list` 容器实现代码