C++ STL list 容器深度解析：API 用法与底层模拟实现

4. 迭代器失效问题

由于底层是双向循环链表，插入操作不会导致现有迭代器失效。只有在删除元素时，指向被删除节点的迭代器才会失效，其他迭代器依然有效。

错误的删除写法示例：

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

正确的做法是接收 erase 返回的下一个有效迭代器。

二、list 的模拟实现

理解了接口后，我们来看看如何从零实现一个兼容 STL 规范的 list。核心在于节点设计、迭代器封装以及内存管理。

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) {}
};

迭代器类 (list_iterator)

为了同时支持普通迭代器和 const 迭代器，我们使用模板参数 Ref 和 Ptr 来区分引用类型和指针类型。

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

2. 容器类核心逻辑

类型定义与迭代器

利用隐式转换简化代码，Node 指针可直接转换为 iterator。

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; }
    // ... 省略部分辅助函数

初始化与析构

初始化时需要创建一个虚拟头节点，使其形成闭环。

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

list() { empty_init(); }
~list() { clear(); delete _head; _head = nullptr; }

插入与删除

插入操作的关键在于调整前后指针的连接关系。删除操作必须返回下一个有效位置的迭代器，以便调用者安全遍历。

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; // 返回新节点的迭代器
}

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; // 返回下一个有效位置
}

赋值与交换

利用拷贝交换语义实现高效的赋值操作。

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

3. 测试验证

实际开发中，我们需要验证迭代器失效场景及基本功能。

void test_list02() {
    list<int> lt;
    lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4);
    
    // insert 不会导致迭代器失效
    list<int>::iterator it = lt.begin();
    lt.insert(it, 10);
    *it += 100;
    
    // erase 会导致当前迭代器失效，需接收返回值
    it = lt.begin();
    while (it != lt.end()) {
        if (*it % 2 == 0) {
            it = lt.erase(it); // 正确用法
        } else {
            ++it;
        }
    }
}

三、list 与 vector 对比

这个实现展示了 list 容器的核心机制，包括节点管理、迭代器设计及异常安全处理。在实际工程中，若频繁在中间位置插入删除且无需随机访问，list 是更优选择；反之，vector 凭借缓存局部性通常性能更佳。