深入解析 C++ STL list：双向链表原理与迭代器实战

// 迭代器遍历
auto it = V.begin();
while (it != V.end()) {
    cout << *it << " ";
    it++;
}
cout << endl;

// 范围 for 循环（推荐）
for (const auto& e : V) {
    cout << e << " ";
}
cout << endl;

为什么非连续空间可以使用 ++？

首先 ++ 是在迭代器内部使用了运算符重载（因此只支持在迭代器对象上使用）。对于 list，++ 的本质是移动到下一个节点的地址（即 ->next），而不是简单的内存地址加一。

核心操作接口

指定位置前插入

使用 insert 接口，参数为迭代器位置和待插入值。

// 在 begin 位置插入 5
V.insert(V.begin(), 5);

注意： list 的内存是不连续的，不能直接使用 + 进行指针运算，必须使用迭代器。

此外，insert 之后对于 list 的迭代器是不会失效的，这是 list 相比 vector 的一大优势。

指定位置删除

使用 erase 接口。

// 删除 begin 位置的元素
V.erase(V.begin());

注意： 使用 erase 后，如果不接收返回值，那么被删除元素的迭代器就会失效。如果后续还需要使用该位置，建议保存 erase 返回的新迭代器。

排序与去重

list 的排序属于稳定排序（时间复杂度 n log n），且直接在容器内部完成，无需额外算法调用。

// 升序排序
v.sort();

// 降序排序
V.sort(greater<int>());

// 去重（前提是元素已经有序）
V2.unique();

拼接与反转

splice 支持整体拼接、单个元素拼接、范围拼接。这在合成多个链表时非常有用，比如先拼接多个链表再用排序，这样就实现了整体有序。

// 整体拼接：将 V2 的所有元素拼接到 V1 的末尾
V1.splice(V1.end(), V2);

// 单个元素拼接：将 V2 中 it2 指向的元素拼接到 V1 的 it1 前面
V1.splice(it1, V2, it2);

// 反转
V2.reverse();

注意： reverse 翻转的是整个链表顺序，而非特定区间。

模拟实现：理解底层结构

为了深入理解 list，我们尝试手动实现一个简化版的双向链表。这有助于理解哨兵头节点、节点结构以及迭代器的设计。

节点结构设计

list 属于不连续的存储，通过指针来连接每个空间。我们需要一个节点结构：节点包含 prev、next、val。

template<class T>
struct list_node {
public:
    // 构造函数
    list_node(const T& date = T()) 
        : next(nullptr), prev(nullptr), val(date) {}

    // 节点成员
    list_node<T>* next;
    list_node<T>* prev;
    T val;
};

头节点与类封装

除了节点结构外，我们需要一个指针去指向这个节点，这里采用哨兵头节点（Sentinel Node）的设计，这样头尾操作可以统一处理。

template<class T>
class list {
    typedef list_node<T> Node;
public:
    list() : Head(nullptr) {
        // 开辟头节点
        Head = new Node;
        Head->next = Head; // 形成环
        Head->prev = Head;
    }

private:
    Node* Head;
};

核心功能实现

尾插

双向链表的尾插很简单，头节点的前一个就是尾节点。

void push_back(const T& date) {
    // 先开辟空间
    Node* tmp = new Node(date);
    
    // 确认关系：tmp 插在 Head 之前
    Node* pc = Head->prev;
    pc->next = tmp;
    tmp->prev = pc;
    tmp->next = Head;
    Head->prev = tmp;
}

尾删

尾删需要注意边界情况：如果只有一个头结点的情况下，是不能删除的。

void pop_back() {
    if (Head->next == Head) return; // 空表保护
    
    // 找尾节点 cur
    Node* cur = Head->prev;
    // 标记尾的前一个节点 pc
    Node* pc = cur->prev;
    
    // 重新连接 pc 和头节点
    pc->next = Head;
    Head->prev = pc;
    
    // 释放
    delete cur;
    cur = nullptr;
}

头插与头删

头插需要找到头结点的下一个节点，然后连接即可。头删同理，但要注意更新迭代器（如果在外部持有迭代器的话）。

// 头插
void push_front(const T& date) {
    Node* cur = new Node(date);
    Node* pc = Head->next;
    
    Head->next = cur;
    cur->prev = Head;
    cur->next = pc;
    pc->prev = cur;
}

// 头删
void pop_front() {
    if (Head->next == Head) return;
    
    Node* cur = Head->next;
    Node* pc = cur->next;
    
    Head->next = pc;
    pc->prev = Head;
    
    delete cur;
    cur = nullptr;
}

拷贝构造与赋值

这里需要注意深浅拷贝的问题。对于内置类型，字节拷贝即可；对于自定义类型，需确保资源正确管理。我们采用'拷贝构造临时对象 + 交换'的方法来实现赋值运算符重载，避免重复分配内存。

// 拷贝构造
list(const list<T>& V) {
    Head = new Node;
    Head->next = Head;
    Head->prev = Head;
    
    auto it = V.begin();
    while (it != V.end()) {
        push_back(*it);
        it++;
    }
}

// 赋值运算符重载
list<T>& operator=(const list<T>& V) {
    list<T> temp(V); // 拷贝构造临时对象
    swap(temp.Head, Head); // 交换指针
    return *this;
}

迭代器详解

迭代器的效果是：如果是解引用，那么需拿到元素；如果是 ++，那么需要跳到下一个节点。因此迭代器的指针不能是固定的，否则解引用拿到的就是节点而非数据。

迭代器结构

对于非连续空间的迭代器实现，最好的方法是单独封装为一个类。

template<class T>
struct __list_iterator {
    typedef __list_iterator<T> iterator;
    typedef list_node<T> Node;
    
    Node* _node;

    // 构造
    __list_iterator(Node* node) : _node(node) {}

    // 解引用
    T& operator*() {
        return _node->val;
    }

    // 后置++
    iterator& operator++(int) {
        iterator tmp(*this);
        _node = _node->next;
        return tmp;
    }

    // 判断是否相等
    bool operator!=(const iterator& it) {
        return _node != it._node;
    }
};

begin() 与 end()

iterator begin() {
    return iterator(Head->next);
}

iterator end() {
    return iterator(Head);
}

第一行会先执行 V.begin()，拿到节点，然后发生隐式转换，调用 iterator 类模板构造，参数是节点，完成转换，返回值再交给 it。

无法修改的迭代器

对于无法修改的迭代器（const_iterator），效果是只可以访问，不能修改访问元素。

有两种常见方法实现：

1. const 修饰返回值：最直接的方法，在 begin() 返回时加上 const 修饰。
2. 模板参数区分：通过类模板的参数去修改它。由于节点的类型模板参数是 T，我们可以保证它跟迭代器的第一个参数吻合。

// 定义两种迭代器类型
typedef __list_iterator<T, T&> iterator;
typedef __list_iterator<T, const T&> const_iterator;

这种方式下，const 类的迭代器和非 const 的迭代器，可以通过控制类模板的第二个参数去返回，从而达到'修改'和'不可修改'的效果。

总结

对于迭代器 const 与非 const 的转化，以及其它类型的转化，我们都是调用构造函数来完成的。一个节点类型转化为迭代器类型，或者一个迭代器从非 const 类型转化为 const 类型，这期间可能涉及到构造函数的重载，都是区分构造函数的参数来实现的。