C++ STL 详解：list 容器底层实现分析

核心成员 _head 指向哨兵节点，所有元素都围绕它组织。

二、默认成员函数

2.1 list_node 构造函数

list_node(const T& data = T(), Node* prev = nullptr, Node* next = nullptr)
    : _data(data), _prev(prev), _next(next) {}

使用常引用接收数据可避免大型对象的拷贝开销，默认参数允许灵活构造。

2.2 list_iterator 构造函数

// 默认构造
list_iterator(Node* pnode = nullptr) : _pnode(pnode) {}

// 允许从普通迭代器构造 const 迭代器
list_iterator(const list_iterator<T, T&, T*>& it) : _pnode(it._pnode) {}

2.3 class list 构造函数与析构

无参构造时创建哨兵节点并自循环：

template<class T> void list<T>::CreateHead() {
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
}

list() { CreateHead(); }

拷贝构造遍历源容器逐个插入：

list(const list& lt) {
    CreateHead();
    for (const auto& elem : lt) push_back(elem);
}

赋值重载利用交换语义提高效率：

template<class T> void list<T>::swap(list<T>& lt) {
    std::swap(_head, lt._head);
}

list<T>& operator=(list<T> lt) {
    swap(lt);
    return *this;
}

析构函数需释放除哨兵外的所有结点，最后清理哨兵：

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

三、list 的迭代器

迭代器是实现泛型算法的关键，需要重载一系列运算符。

3.1 重载运算符 *

Ref operator*() {
    return _pnode->_data;
}

返回迭代器所指向值的引用。对于普通迭代器返回 T&，常量迭代器返回 const T&，从而控制是否可修改数据。

3.2 重载运算符 ->

Ptr operator->() {
    return &(_pnode->_data);
}

C++ 编译器对 -> 有特殊处理。如果 operator->() 返回指针，编译器会自动再次调用 -> 访问成员。因此直接返回数据地址即可，用户端使用体验如同原生指针。

3.3 重载运算符 ++ 和 --

前置版本返回引用以支持链式调用，后置版本需保存旧状态：

// 前置 ++
Self& operator++() {
    _pnode = _pnode->_next;
    return *this;
}

// 后置 ++
Self operator++(int) {
    Self tmp = *this;
    ++(*this);
    return tmp;
}

// 前置 --
Self& operator--() {
    _pnode = _pnode->_prev;
    return *this;
}

// 后置 --
Self operator--(int) {
    Self tmp = *this;
    --(*this);
    return tmp;
}

3.4 重载运算符 == 和 !=

比较两个迭代器指向的结点指针是否相同：

bool operator==(const Self& s) { return _pnode == s._pnode; }
bool operator!=(const Self& s) { return _pnode != s._pnode; }

四、list 相关函数操作

4.1 begin 与 end

iterator begin() { return iterator(_head->_next); }
const_iterator begin() const { return const_iterator(_head->_next); }

iterator end() { return iterator(_head); }
const_iterator end() const { return const_iterator(_head); }

begin 返回第一个有效元素的迭代器，end 返回哨兵节点位置作为结束标记。

4.2 insert 与 erase

在指定位置插入新元素：

template<class T>
typename list<T>::iterator list<T>::insert(iterator pos, const T& x) {
    Node* newnode = new Node(x);
    Node* cur = pos._pnode;
    newnode->_prev = cur->_prev;
    newnode->_next = cur;
    cur->_prev->_next = newnode;
    cur->_prev = newnode;
    return iterator(newnode);
}

删除指定位置元素，注意不能删除哨兵节点：

template<class T>
typename list<T>::iterator list<T>::erase(iterator pos) {
    assert(pos._pnode != _head);
    Node* cur = pos._pnode;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    prev->_next = next;
    next->_prev = prev;
    delete cur;
    return iterator(next);
}

4.3 头尾插删

这些操作可以复用 insert 和 erase 实现，保持代码一致性：

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

4.4 clear

移除所有元素，使容器大小变为 0：

template<class T> void list<T>::clear() {
    auto it = begin();
    while (it != end()) {
        it = erase(it);
    }
}

通过复用 erase 返回的下一个迭代器，确保遍历安全且高效。