C++ STL list 容器详解：使用与模拟实现

1.2.6 list 的迭代器失效

这是 list 最容易踩坑的地方。由于底层是双向循环链表，插入操作不会导致迭代器失效。只有在删除元素时，指向被删除节点的迭代器才会失效，其他迭代器不受影响。

错误的删除写法示例：

while (it != l.end()) { 
    l.erase(it); // it 失效了
    ++it;        // 错误，it 已无效
} 

正确的做法是接收 erase 的返回值，或者先保存下一个迭代器。

2. list 的模拟实现

理解了接口怎么用，咱们再看看怎么自己造一个轮子。这有助于深入理解内存管理和指针操作。

2.1 基本结构

2.1.1 节点类 (list_node)

每个节点需要存数据、指向上一个节点、指向下一个节点。

template<class T> class list_node {
public:
    T _data;
    list_node<T>* _next;
    list_node<T>* _prev;
    list_node(const T& data = T()) :_data(data), _next(nullptr), _prev(nullptr) {}
};

2.1.2 迭代器类 (list_iterator)

为了同时支持 const 和非 const 迭代器，我们采用模板参数传递引用和指针类型。

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->_data; }
    Ptr operator->() { return &_node->_data; }
    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& s) { return _node != s._node; }
};

这里利用单参数构造函数实现了 Node* 到 iterator 的隐式转换，写起来更简洁。

2.2 list 容器类核心逻辑

2.2.1 类型定义和迭代器

template<class T> class list {
    typedef list_node<T> Node;
public:
    typedef list_iterator<T, T&, T*> iterator;
    typedef list_iterator<T, const T&, const T*> const_iterator;
    iterator begin() { return _head->_next; }
    iterator end() { return _head; }
    const_iterator begin() const { return _head->_next; }
    const_iterator end() const { return _head; }
private:
    Node* _head;
    size_t _size;
};

遵循 STL 左闭右开原则，end() 始终指向头节点。

2.2.2 初始化与析构

void empty_init() {
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
    _size = 0;
}
list() { empty_init(); }
~list() { clear(); delete _head; _head = nullptr; }

注意析构时要释放头节点，避免内存泄漏。

2.2.3 插入操作

插入的核心在于调整前后指针。

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

复用 insert 可以大幅减少代码量。

2.2.4 删除操作

删除后必须返回下一个有效位置的迭代器，方便调用者继续遍历。

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

2.2.5 容量与赋值

size_t size() const { return _size; }
bool empty() const { return _size == 0; }
void clear() {
    auto it = begin();
    while (it != end()) { it = erase(it); }
}
list<T>& operator=(list<T> lt) { swap(lt); return *this; }
void swap(list<T>& lt) {
    std::swap(_head, lt._head);
    std::swap(_size, lt._size);
}

赋值运算符采用'复制并交换'（Copy-and-Swap）惯用法，既安全又高效。

2.3 测试示例

实际开发中，记得处理迭代器失效的情况。

void test_list() {
    list<int> lt;
    lt.push_back(1); lt.push_back(2); lt.push_back(3);
    // 遍历输出
    for (auto it = lt.begin(); it != lt.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 删除偶数
    it = lt.begin();
    while (it != lt.end()) {
        if (*it % 2 == 0) {
            it = lt.erase(it); // 接收返回值
        } else {
            ++it;
        }
    }
}

2.4 设计要点总结

1. 双向循环链表：头节点简化边界判断。
2. 迭代器封装：隐藏指针细节，统一接口。
3. 异常安全：正确管理资源，避免内存泄漏。
4. STL 兼容：遵循标准接口规范。

3. list 与 vector 的对比

在实际选型时，如果频繁在中间插入删除，list 是更好的选择；如果需要随机访问或追求缓存命中率，vector 则更合适。