C++ STL List 容器使用指南及底层模拟实现

// 正向遍历
auto it = l.begin();
while(it != l.end()) {
    cout << *it << " ";
    ++it;
}

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

注意：begin() 返回第一个元素，end() 返回最后一个元素的下一个位置。反向迭代器 rbegin() 对应 end()，rend() 对应 begin()。

容量与访问

• empty(): 检测是否为空。
• size(): 获取有效节点个数。
• front(): 获取第一个元素的引用。
• back(): 获取最后一个元素的引用。

修改操作

list 的核心优势在于增删改查的高效性，尤其是头部和尾部的操作。

// 尾部插入，头部插入
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()); // 清空所有元素

// 交换与清空
l1.swap(l2);
l2.clear();

迭代器失效机制

这是使用 list 时需要特别注意的地方。由于底层是双向循环链表，插入操作不会导致其他迭代器失效，只有删除操作会导致被删除节点的迭代器失效。

// 错误示范：erase 后直接 ++it，此时 it 已无效
void TestBad() {
    auto it = l.begin();
    while(it != l.end()) {
        l.erase(it);
        ++it; // 危险！it 指向已被释放的节点
    }
}

// 正确示范：利用 erase 返回值或后置 ++
void TestGood() {
    auto it = l.begin();
    while(it != l.end()) {
        it = l.erase(it); // erase 返回下一个有效迭代器
        // 或者：l.erase(it++);
    }
}

模拟实现思路

理解了用法后，我们来看看如何从零实现一个简易版 list。核心在于封装节点结构和泛型迭代器。

节点与迭代器封装

我们需要定义一个节点结构体，并封装迭代器类以重载 *, ->, ++, -- 等操作符。

template<class T>
struct list_node {
    T _data;
    list_node* _next;
    list_node* _prev;
    list_node(const T& x = T()) : _data(x), _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--() {
        _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 类主体

主类需要管理头结点、大小统计以及实现各种接口。注意深拷贝时的资源管理。

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(initializer_list<T> lt) {
        empty_init();
        for(auto& e : lt) push_back(e);
    }

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

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

    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 中的重要序列式容器，但底层结构决定了适用场景的差异。

总结

C++ STL 中的 list 基于双向循环链表实现，适合频繁插入删除的场景。其核心特性包括通过迭代器遍历元素（支持正向/反向）、插入操作不引发迭代器失效（删除仅影响被删节点）。模拟实现需封装节点结构体，设计泛型迭代器并重载操作符，同时处理好默认成员函数与深拷贝逻辑。理解其底层实现有助于在实际开发中根据需求选择合适的数据结构。