C++ STL list 模拟实现：双向链表与迭代器封装

一、List 的介绍

list 是 STL 中支持在任意位置高效（常数时间）插入、删除的双向迭代序列式容器，底层基于带头双向链表实现 —— 每个元素存于独立节点，通过指针连接前后元素；它和 forward_list 类似但后者是单链表、仅支持前向迭代；和 array、vector、deque 相比，list 的插入删除效率更优，但缺点是不支持随机访问（访问第 n 个元素需线性遍历），且每个节点的指针会占用额外空间（对存储小元素的大 list 影响较明显）。

二、默认成员函数

1、List 的节点结构、容器结构

节点结构

namespace ljh {
    template<class T> struct list_node {
        list_node(const T& val) : _next(nullptr), _prev(nullptr), _val(val) {}
        T _val;
        list_node<T>* _next;
        list_node<T>* _prev;
    };
}

成员变量设为公有，是为了让后续写 list 容器 / 迭代器时，能直接操作节点的 _next/_prev/_val，省写 get/set，简化代码。

迭代器结构

namespace ljh {
    template<class T> struct _list_iterator {
        typedef list_node<T> Node;
        _list_iterator(Node* node) :_node(node) {}
        Node* _node;
    };
}

链表的迭代器为啥不能直接用原生指针？

因为链表的原生指针只能访问节点本身，而迭代器需要模拟'像普通指针一样解引用取数据、++/-- 遍历'的行为。原生指针解引用得到的是整个节点，不是数据；且链表的'下一个元素'需要通过 _next 指针跳转，原生指针的 ++ 是地址 +1，不符合链表的节点连接逻辑，所以得封装迭代器类来重载 *、++ 等运算符。

迭代器结构为啥用 struct？

迭代器结构体用 struct，是因为迭代器只是遍历容器的工具，不用刻意封装成私有，用 struct 让成员直接暴露，能简化后续迭代器功能的实现。

迭代器为啥不能写析构函数？

不能为迭代器编写析构函数，因为节点的内存是由容器管理的，迭代器只是'借用节点指针来访问元素'，本身并不持有节点的所有权。若在迭代器析构时释放节点，会导致容器内的节点被非法销毁。

链表结构

namespace ljh {
    template<class T> class list {
        typedef list_node<T> Node;
    private:
        Node* _head;
        size_t _size;
    };
}

2、List 构造函数

void empty_init() {
    _head = new Node(-1);
    _head->_prev = _head;
    _head->_next = _head;
    _size = 0;
}
list() { empty_init(); }

3、List 拷贝构造函数

list(const list<T>& lt) {
    empty_init();
    for (auto& e : lt) {
        push_back(e);
    }
}

4、List 赋值运算符重载

void swap(list<T>& lt) {
    std::swap(_head, lt._head);
    std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt) {
    swap(lt);
    return *this;
}

利用拷贝构造 + 交换实现赋值运算符重载，高效且安全。

5、List 析构函数

void clear() {
    iterator it = begin();
    while (it != end()) {
        it = erase(it);
    }
    _size = 0;
}
~list() {
    clear();
    delete _head;
    _head = nullptr;
}

三、迭代器

1、begin/end

typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
iterator begin() { return iterator(_head->_next); }
iterator end() { return iterator(_head); }
const_iterator begin() const { return const_iterator(_head->_next); }
const_iterator end() const { return const_iterator(_head); }

目前我们先不写反向迭代器，等学到后面的容器适配器部分时再讲解它的实现方式。

2、迭代器的运算符重载

template<class T, class Ref, class Ptr >
struct _list_iterator {
    typedef list_node<T> Node;
    typedef _list_iterator<T, Ref, Ptr> self;
    Node* _node;
    _list_iterator(Node* node) :_node(node) { }
    Ref operator*() { return _node->_val; }
    Ptr operator->() { return &this->_node->_val; }
    self& operator++() { _node = _node->_next; return *this; }
    self operator++(int) {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    self& operator--() { _node = _node->_prev; return *this; }
    self operator--(int) {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    bool operator!=(const self& it) const { return _node != it._node; }
    bool operator==(const self& it) { return _node == it._node; }
};

2.1 operator*

这里返回的是 _node 节点存储的数据，返回类型用 T&，目的是避免传递自定义类型时产生不必要的拷贝开销。

Ref 参数的作用？

用 Ref 替代具体的返回值类型，是为了通过这个模板参数适配 const 迭代器：当第二个模板参数传入的是 const T& 时，就代表这是一个 const 迭代器（此时解引用返回的是只读引用）。

2.2 operator->

重载这个运算符，是为了应对数据是结构体的场景。为了让迭代器的用法和原生指针一致，C++ 编译器对迭代器的 operator-> 做了'语法糖'优化，允许省略一次 ->，让 it->_a2 等价于 (it.operator->())->_a2。

ptr 模版参数的作用？

Ptr 的作用在此体现：区分普通迭代器返回的 T*（可读写结构体成员）和 const 迭代器返回的 const T*（只读），实现一套模板复用，保证 const 迭代器的安全性。

2.3 operator 前置++/--

前置 ++ 和 -- 的逻辑很相似：都是直接修改当前迭代器的节点指针，然后返回自身的引用。返回自身引用的好处是支持链式操作，而且没有临时对象的开销，效率更高。

2.4 operator 后置++/--

后置 ++ 和 -- 的核心是'先返回原状态，再移动'。函数参数里的 int 是个占位符，实现时会先创建一个临时迭代器保存当前状态，然后移动 _node，最后返回这个临时迭代器。因为会创建临时对象，它的效率比前置版本略低。

2.5 operator!=/==

这两个运算符的逻辑很直接：判断两个迭代器的 _node 指针是否指向同一个节点。其中 operator!= 后面加了 const，是为了保证调用这个函数时不会修改当前迭代器的状态。

2.6 迭代器拷贝构造问题？

lt.begin() 返回临时迭代器，it 是用它拷贝构造而来的。编译器默认生成的拷贝构造是浅拷贝，只会复制内部节点指针，让 it 和原临时迭代器指向链表中同一个节点。这刚好满足需求，深拷贝不仅多此一举，还会带来巨大开销，因此迭代器不用写拷贝构造。

四、list 增删查改

1、push_back

void push_back(const T& x) {
    Node* tail = _head->_prev;
    Node* newnode = new Node(x);
    tail->_next = newnode;
    newnode->_prev = tail;
    newnode->_next = _head;
    _head->_prev = newnode;
    ++_size;
}

先找到链表的尾节点，再创建新节点；接着把 tail 的 next 指向新节点、新节点的 prev 指向 tail，完成新节点和原尾节点的连接；最后让新节点的 next 指向头节点、头节点的 prev 指向新节点，维持链表的循环结构。

2、insert

iterator insert(iterator pos, const T& x) {
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* newnode = new Node(x);
    prev->_next = newnode;
    newnode->_next = cur;
    cur->_prev = newnode;
    newnode->_prev = prev;
    ++_size;
    return newnode;
}

先从迭代器 pos 里拿到它指向的节点 cur，再找到 cur 的前驱节点 prev，同时创建新节点 newnode；把 prev 的 next 指向新节点、新节点的 next 指向 cur，再让 cur 的 prev 指向新节点、新节点的 prev 指向 prev—— 这样就把新节点'夹'在了 prev 和 cur 之间。

3、push_front

void push_front(const T& x) {
    insert(begin(), x);
}

直接复用 insert，在 begin() 前插入元素 x，既简化代码又保证逻辑一致。

4、pop_back

void pop_back() {
    assert(_head->_next != _head);
    Node* del = _head->_prev;
    Node* tail = del->_prev;
    tail->_next = _head;
    _head->_prev = tail;
    delete del;
    _size--;
}

先断言链表非空，找到尾节点和它的前驱节点，重新建立前驱节点与头节点的循环连接，释放原尾节点内存，最后更新链表长度。

5、erase

iterator erase(iterator pos) {
    assert(pos != end());
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    prev->_next = next;
    next->_prev = prev;
    delete cur;
    --_size;
    return next;
}

先断言避免删除无效节点，找到待删节点的前后节点并重新建立连接，释放待删节点内存，更新链表长度后返回后继节点迭代器防止失效。

6、pop_front

void pop_front() {
    erase(begin());
}

直接复用 erase 函数，删除 begin() 对应的头节点，既简化代码又保证逻辑一致。

7、list 迭代器失效问题

insert 操作：list 节点物理离散，插入仅新增节点、不改变原有节点地址，因此原迭代器不会失效；返回新节点迭代器，可按需更新使用。 erase 操作：仅被删除节点的迭代器失效（节点内存被释放），其他迭代器仍有效；返回被删节点的后继节点迭代器，需用它更新原迭代器，避免访问失效节点。

五、其他接口

1、swap

void swap(list<T>& lt) {
    std::swap(_head, lt._head);
    std::swap(_size, lt._size);
}

通过 std::swap 分别交换两个链表的头节点指针和元素个数，实现两个链表数据的高效交换（无需拷贝 / 移动节点，仅交换两个核心成员，时间复杂度 O(1)）。

2、clear

void clear() {
    iterator it = begin();
    while (it != end()) {
        it = erase(it);
    }
    _size = 0;
}

通过遍历 + 复用 erase 删除所有节点，利用 erase 返回的后继迭代器避免失效，最后重置 _size 完成清空。

3、迭代器性质方面分类

单向迭代器：仅支持 ++（向后移动），对应底层是单向链表 / 哈希结构的容器（如 forward_list、unordered_map）； 双向迭代器：支持 ++/--（前后移动），对应底层是双向链表 / 树形结构的容器（如 list、map、set）； 随机迭代器：支持 ++/--/+/-（任意位置跳转），对应底层是连续存储的容器（如 vector、string、deque）。

4、sort

问题 1：list 不能用 std::sort 的原因

std::sort 算法要求迭代器是随机迭代器（支持 +/- 等随机跳转操作），但 list 的迭代器是双向迭代器（仅支持 ++/--），不满足 std::sort 的要求，因此 list 无法直接使用全局的 std::sort。

问题 2：list 的内置 sort 成员函数

list 提供了自己的 sort 成员函数，但它的效率存在局限性：因为链表是离散存储的，元素不连续，缓存利用率低，所以 list::sort 的效率比 std::sort 要差；仅在数据量较小时，list::sort 的效率尚可；数据量较大时，和 std::sort 的效率差异会非常明显。

std::sort 和 list::sort 效率对比

void test_op() {
    srand((unsigned)time(NULL));
    const int N = 5000000;
    vector<int> v;
    v.reserve(N);
    list<int> lt1;
    for (int i = 0; i < N; ++i) {
        auto e = rand();
        v.push_back(e);
        lt1.push_back(e);
    }
    int begin1 = clock();
    sort(v.begin(), v.end());
    int end1 = clock();
    int begin2 = clock();
    lt1.sort();
    int end2 = clock();
    printf("vector sort:%d\n", end1 - begin1);
    printf("list sort:%d\n", end2 - begin2);
}

数据量越小，差异越小：当数据量仅 5 万时，两者效率接近； 数据量越大，差异越悬殊：数据量到 500 万时，vector sort 耗时远低于 list sort； 核心原因：vector 是连续存储，std::sort 能利用缓存高效排序；而 list 是离散节点，list::sort 缓存利用率低，数据量放大后效率劣势会被急剧放大。

优化方案

1、拷贝数据：把 std::list 中的元素拷贝到 std::vector 中； 2、高效排序：用 std::sort 对 vector 中的数据排序； 3、拷贝回写：将排序后的 vector 数据再拷贝回 std::list。 借助 vector 的连续存储 + 缓存友好，结合 std::sort 的高效实现，能大幅提升 list 数据的排序性能。

void test_op() {
    srand((unsigned)time(NULL));
    const int N = 5000000;
    list<int> lt1;
    list<int> lt2;
    for (int i = 0; i < N; ++i) {
        auto e = rand();
        lt1.push_back(e);
        lt2.push_back(e);
    }
    int begin1 = clock();
    vector<int> v;
    v.reserve(N);
    for (auto& e : lt1) {
        v.push_back(e);
    }
    sort(v.begin(), v.end());
    int i = 0;
    for (auto& e : lt1) {
        e = v[i++];
    }
    int end1 = clock();
    int begin2 = clock();
    lt2.sort();
    int end2 = clock();
    printf("list→vector→std::sort 耗时：%d\n", end1 - begin1);
    printf("list::sort 直接排序 耗时：%d\n", end2 - begin2);
}

从运行结果能明显看到：'list→vector→std::sort' 效率远高于 'list::sort 直接排序'，充分体现了借助 vector+std::sort 优化 list 排序的显著优势。