C++ list 容器的用法与简化实现

实际写代码时，迭代器怎么走要特别小心，尤其是删除操作之后。

迭代器失效

list 的一个好处是：插入不会让已有迭代器整体失效。只有被删除的那个节点对应的迭代器才会失效。这个特性在需要边遍历边删元素时很实用。

// 错误示范
while(it != l.end()){
    l.erase(it);
    ++it; // it 已失效
}
// 正确做法
while(it != l.end()){
    it = l.erase(it); // erase 返回下一个有效迭代器
}

二、list 的模拟实现

自己实现 list，关键不是把接口堆出来，而是把节点关系和迭代器封好。双向循环链表看起来简单，真正麻烦的地方都在指针连接上，插入和删除的时候最容易出错。

迭代器封装

list 的迭代器本质上是对节点指针的包装，需要重载解引用、自增、自减这些操作符。

template<class T, class Ref, class Ptr>
struct list_iterator {
    typedef list_node<T> Node;
    Node* _node;
    // ... operator* , operator++ 等实现
};

类结构

主类里一般会放头指针 _head 和大小 _size。构造时要把哨兵节点初始化好，析构时把整条链释放干净。

template<class T>
class list {
    Node* _head;
    size_t _size;
    // ... insert, erase, push_back 等
};

这里最值得盯紧的还是 insert 和 erase。链表实现只要这两块写对了，其他接口基本就是包装。

三、list 与 vector 的对比

四、总结

list 更适合那些需要频繁在中间位置插入或删除元素的场景。它牺牲了连续内存带来的访问优势，换来的是更稳定的修改性能。写业务代码时不一定常用，但搞清楚它的链表结构，选容器时会少很多误判。