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

1.2.5 修改操作

1.2.6 迭代器失效问题

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

每个节点包含存储数据的 _data，以及指向上一个和下一个节点的指针 _prev 和 _next。

2.1.2 迭代器类 (list_iterator)

为了统一处理 const 和非 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; } 
}; 

这种设计避免了重复代码，只需要一个模板类就能同时支持普通迭代器和 const 迭代器。

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

Node* 可以隐式转换为 iterator，因为 list_iterator 有单参数构造函数。begin() 返回第一个有效元素位置，end() 返回头节点位置，符合 STL 左闭右开原则。

2.2.2 构造函数和初始化

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

list() { empty_init(); } 

// 拷贝构造 
list(list<T>& lt) { 
    empty_init(); 
    for (auto& e : lt) { push_back(e); } 
} 

// 初始化列表构造 
list(initializer_list<int> il) { 
    empty_init(); 
    for (auto& e : il) { push_back(e); } 
} 

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 逻辑可以简化代码，push_back 和 push_front 只是传递不同的位置参数。

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

erase 返回下一个有效位置的迭代器，这样调用者可以继续安全地遍历。

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); // erase 返回下一个地址 
    } 
} 

2.2.6 赋值操作

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

利用交换语义实现高效的赋值操作，避免深拷贝开销。

2.3 测试示例

// 测试基本功能 
void test_list01() { 
    list<int> lt; 
    lt.push_back(1); 
    lt.push_back(2); 
    lt.push_back(3); 
    lt.push_back(4); 
    
    list<int>::iterator it = lt.begin(); 
    while (it != lt.end()) { 
        cout << *it << " "; 
        ++it; 
    } 
    cout << endl; 
} 

// 测试迭代器失效 
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; 
        } 
    } 
} 

2.4 设计要点总结

1. 双向循环链表：头节点连接首尾，简化边界处理。
2. 迭代器封装：隐藏底层指针，提供统一接口。
3. 模板复用：通过模板参数减少代码重复。
4. 异常安全：正确管理资源，避免内存泄漏。
5. STL 兼容：遵循 STL 接口规范。

这个实现展示了 list 容器的核心机制，包括节点管理、迭代器设计、插入删除操作等关键技术点。

3. list 与 vector 的对比