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

1.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 类型定义和迭代器

begin() 返回第一个有效元素位置，end() 返回头节点位置，符合 STL 左闭右开原则。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; } 

2.2.2 构造函数和初始化

初始化时创建头节点并构成环，大小置为 0。

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 插入操作

核心在于调整指针指向。insert 默认在 pos 之前插入，复用此逻辑可实现 push_front/push_back。

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 删除操作

删除时需确保不删头节点，并返回下一个有效位置的迭代器以处理失效问题。

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 赋值操作

利用 swap 实现深拷贝，避免重复内存分配。

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; 
    // 删除偶数
    it = lt.begin(); 
    while (it != lt.end()) { 
        if (*it % 2 == 0) { 
            it = lt.erase(it); // 必须接收返回值
        } else { 
            ++it; 
        } 
    } 
} 

2.4 完整实现代码

#pragma once
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <initializer_list>
using namespace std;

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.5 设计要点总结

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

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

3. list 与 vector 的对比