C++ STL List 容器详解与模拟实现

// 使用 auto 简化写法（推荐）
auto it = l.begin();
while(it != l.end()) {
    cout << *it << " ";
    ++it;
}
cout << endl;

// 反向遍历
auto rit = l.rbegin();
while(rit != l.rend()) {
    cout << *rit << " ";
    ++rit;
}

注意：如果是 const_iterator，不能修改元素值，编译会报错。

3. 常用接口概览

除了基本的增删改查，还有一些容量和访问接口：

• 访问：front() 取首元素，back() 取尾元素。
• 容量：empty() 判断是否为空，size() 获取节点个数。
• 修改：push_front/back 头尾插入，pop_front/back 头尾删除。
• 插入/删除：insert(pos, val) 在指定位置插入，erase(pos) 删除指定位置元素。

实际使用中，这些接口大多直接调用即可，核心在于理解它们对链表结构的影响。

int array[] = {1, 2, 3};
list<int> L(array, array + sizeof(array)/sizeof(array[0]));

// 头尾操作
L.push_back(4); L.push_front(0);
L.pop_back(); L.pop_front();

// 指定位置插入
auto pos = ++L.begin(); // 指向第二个节点
L.insert(pos, 4);       // 插入单个元素
L.insert(pos, 5, 5);    // 插入 5 个值为 5 的元素
vector<int> v{7, 8, 9};
L.insert(pos, v.begin(), v.end()); // 插入区间元素

// 删除操作
L.erase(pos);             // 删除单点
L.erase(L.begin(), L.end()); // 清空所有

// 交换与清空
list<int> l2; l1.swap(l2);
l2.clear();

4. 迭代器失效问题

这是面试和实战中的高频考点。因为 list 是双向循环链表，插入操作不会导致其他迭代器失效，只有删除操作会导致指向被删除节点的迭代器失效。

错误的删除写法：

void TestListIterator1() {
    list<int> l(...);
    auto it = l.begin();
    while(it != l.end()) {
        l.erase(it); // 此时 it 已失效
        ++it;        // 对失效迭代器操作，危险！
    }
}

正确的写法有两种：

// 方法一：利用 erase 返回值
void TestListIterator() {
    list<int> l(...);
    auto it = l.begin();
    while(it != l.end()) {
        it = l.erase(it); // erase 返回下一个有效迭代器
    }
}

// 方法二：后置自增
void TestListIterator2() {
    list<int> l(...);
    auto it = l.begin();
    while(it != l.end()) {
        l.erase(it++); // 先保存当前值再自增，erase 前 it 有效
    }
}

List 的模拟实现

实现 list 的核心在于封装节点结构和迭代器。既然之前做过 string 和 vector，这次重点看迭代器的泛型封装。

首先定义迭代器结构体，它需要支持解引用、自增、自减以及比较运算：

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& it) { return _node != it._node; }
    bool operator==(const Self& it) { return _node == it._node; }
};

主类 list 则负责管理头节点 _head 和节点计数 _size。这里省略了部分细节，重点展示核心逻辑：

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 iterator(_head->_next); }
    iterator end() { return iterator(_head); }
    const_iterator begin() const { return const_iterator(_head->_next); }
    const_iterator end() const { return const_iterator(_head); }

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

    list() { empty_init(); }
    
    // 拷贝构造与赋值重载
    list(const list<T>& lt) {
        empty_init();
        for(auto& e : lt) push_back(e);
    }
    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() { clear(); delete _head; _head = nullptr; }

    void clear() {
        iterator it = begin();
        while(it != end()) {
            it = erase(it);
        }
    }

    size_t size() const { return _size; }

    void push_back(const T& x) { insert(end(), x); }
    void push_front(const T& x) { insert(begin(), x); }
    void pop_front() { erase(begin()); }
    void pop_back() { erase(--end()); }

    // 插入：在 pos 前插入 x
    void 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;
    }

    // 删除：删除 pos 指向的节点，返回下一个有效迭代器
    iterator erase(iterator pos) {
        assert(pos != end());
        Node* cur = pos._node;
        Node* nextNode = cur->_next;
        Node* prevNode = cur->_prev;
        prevNode->_next = nextNode;
        nextNode->_prev = prevNode;
        delete cur;
        --_size;
        return iterator(nextNode);
    }

private:
    Node* _head;
    size_t _size;
};

List 与 Vector 的对比

两者都是 STL 序列式容器，但底层结构决定了适用场景：

简单来说，如果你需要频繁随机访问，选 vector；如果需要频繁在中间或头尾进行插入删除，且不在乎随机访问速度，list 更合适。

总结

C++ STL 中的 list 是基于双向循环链表实现的序列容器，支持高效的插入删除操作（O(1) 时间复杂度），但随机访问效率较低。其核心特性包括通过迭代器遍历元素（支持正向/反向）、插入操作不引发迭代器失效（删除仅影响被删节点迭代器）。模拟实现需封装节点结构体，设计泛型迭代器并实现深拷贝控制。与 vector 对比，list 适合频繁增删场景，而 vector 更适合随机访问和内存连续需求。理解其底层实现有助于优化数据操作逻辑。