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

迭代器失效规则

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

错误的删除写法示例：

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

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

list 的模拟实现

基本结构

节点类 (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) {}
};

每个节点包含数据、指向上一个节点的指针和指向下一个节点的指针。

迭代器类 (list_iterator)

迭代器需要支持解引用、箭头操作符以及前后遍历：

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

这里利用模板参数 Ref 和 Ptr 实现了 const 和非 const 迭代器的统一，避免了代码重复。

容器类实现

类型定义与迭代器

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

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

构造函数与初始化

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

插入与删除操作

插入操作的核心在于调整指针指向：

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

删除操作需要注意释放内存并返回下一个有效位置的迭代器：

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

容量与赋值

size_t size() const { return _size; }
bool empty() const { return _size == 0; }

void clear() {
    auto it = begin();
    while (it != end()) {
        it = erase(it); // erase 返回下一个地址
    }
}

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

测试示例

以下是完整的测试逻辑，涵盖了基本功能、迭代器失效处理及赋值操作：

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

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

    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);
        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 test_list04() {
        list<int> lt1 = {1, 2, 3, 4, 5};
        print_container(lt1);
    }
}

设计要点总结

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

list 与 vector 的对比