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

1.2.6 list 的迭代器失效

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

错误的删除写法示例：

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

2. list 的模拟实现

2.1 基本结构

2.1.1 节点类 (list_node)

这是 list 的基础节点结构，采用双向链表设计，每个节点包含数据及前后指针。

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)

迭代器封装了节点指针，提供解引用、箭头操作符及前后遍历功能。通过模板参数 Ref 和 Ptr 实现 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; } 
}; 

2.2 list 容器类

2.2.1 类型定义和迭代器

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

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

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

2.2.3 插入操作

核心在于修改前后节点的指针指向。push_back 和 push_front 可复用 insert 逻辑。

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

2.2.4 删除操作

删除时需处理前后节点的连接，并释放内存。erase 返回下一个有效位置的迭代器，方便链式调用或循环删除。

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

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 迭代器模板技巧

通过模板参数 Ref 和 Ptr 区分普通迭代器和 const 迭代器，避免代码重复。

typedef list_iterator<T, T&, T*> iterator; 
typedef list_iterator<T, const T&, const T*> const_iterator; 

2.4 测试示例

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); 
    list<int>::iterator it = lt.begin(); 
    lt.insert(it, 10); 
    *it += 100; 
    print_container(lt); 
    it = lt.begin(); 
    while (it != lt.end()) { 
        if (*it % 2 == 0) { it = lt.erase(it); } 
        else { ++it; } 
    } 
    print_container(lt); 
} 

2.5 完整源码参考

#pragma once 
#include<assert.h> 
namespace bit { 
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) { } 
}; 

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--(int) { Self tmp(*this); _node = _node->_prev; return tmp; } 
    Self& operator--() { _node = _node->_prev; return *this; } 
    bool operator!=(const Self& s) { return _node != s._node; } 
}; 

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; } 
    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); } 
    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); } } 
    void push_back(const T&x) { insert(end(), x); } 
    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_front(const T& x) { insert(begin(), x); } 
    void pop_back() { erase(--end()); } 
    void pop_front() { erase(begin()); } 
    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; 
        return next; 
    } 
    size_t size() const { return _size; } 
    bool empty() const { return _size == 0; } 
private: 
    Node* _head; 
    size_t _size; 
}; 

struct AA { int _a1; int _a2; }; 
template<class Container> void print_container(const Container& con) { 
    auto it = con.begin(); 
    while (it != con.end()) { cout << *it << " "; ++it; } 
    cout << endl; 
} 

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; 
    list<AA> lta; 
    lta.push_back(AA()); lta.push_back(AA()); lta.push_back(AA()); lta.push_back(AA()); 
    list<AA>::iterator ita = lta.begin(); 
    while (ita != lta.end()) { cout << ita->_a1 << ":" << ita->_a2 << endl; ++ita; } 
    cout << endl; 
    print_container(lt); 
} 

void test_list02() { 
    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(); 
    lt.insert(it, 10); 
    *it += 100; 
    print_container(lt); 
    it = lt.begin(); 
    while (it != lt.end()) { 
        if (*it % 2 == 0) { it=lt.erase(it); } 
        else { ++it; } 
    } 
    print_container(lt); 
} 

void test_list03() { 
    list<int> lt1; 
    lt1.push_back(1); lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); 
    list<int> lt2(lt1); 
    print_container(lt1); 
    print_container(lt2); 
    list<int> lt3; 
    lt3.push_back(10); lt3.push_back(20); lt3.push_back(30); lt3.push_back(40); 
    lt1 = lt3; 
    print_container(lt1); 
    print_container(lt3); 
} 

void func(const list<int>& lt) { print_container(lt); } 
void test_list04() { 
    list<int> lt0 ( { 1,3,5 }); 
    list<int> lt1= {1, 2, 3, 4, 5}; 
    print_container(lt1); 
    auto il = { 1,2,3,4 }; 
    cout << typeid(il).name() << endl; 
    func(lt1); 
    func({ 1,3,6,7 }); 
} 
}

2.6 设计要点总结

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

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

3. list 与 vector 的对比