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

2. list 的模拟实现

要实现一个标准的 list，我们需要关注节点结构、迭代器设计以及容器类的逻辑。

2.1 基础结构

节点类

每个节点存储数据及前后指针，采用双向链表设计：

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

迭代器类

迭代器需要支持解引用、箭头操作符以及自增自减。为了同时支持 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 容器类实现

类型定义

利用迭代器的模板特性，定义普通迭代器和常量迭代器：

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

这里 _head 是头结点，begin 返回头结点的下一个节点，end 返回头结点本身，符合 STL 左闭右开的习惯。

初始化与析构

构造时创建一个空的循环链表，析构时清理所有节点：

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

list() { empty_init(); }
~list() { clear(); delete _head; _head = nullptr; }

插入与删除

插入操作的核心在于调整前后指针。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;
}

删除操作则需断开连接并释放内存，同时返回下一个有效位置的迭代器：

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

赋值与交换

利用拷贝交换原则实现高效的赋值操作：

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);
    for (auto it = lt.begin(); it != lt.end(); ++it) {
        cout << *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);
    // 插入不失效
    auto 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;
        }
    }
}

3. list 与 vector 对比

完整实现参考

以下是整合后的完整代码，包含节点、迭代器及容器类定义：

#pragma once
#include <iostream>
#include <algorithm>
#include <initializer_list>
#include <assert.h>

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

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;
        --_size;
        return next;
    }

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

private:
    Node* _head;
    size_t _size;
};

总结

实现 list 的关键在于处理好头结点的循环链接以及迭代器的边界条件。通过模板参数统一 const 与非 const 行为，可以大幅减少代码冗余。在实际开发中，若频繁进行中间插入删除且无需随机访问，list 是比 vector 更合适的选择。