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

默认成员函数

构造与析构是内存管理的基石。list 的构造函数会初始化哨兵节点，使其形成一个自循环的空链表。

template<class T> void list<T>::CreateHead() {
    _head = new Node;       // 创建哨兵节点
    _head->_next = _head;   // 形成闭环
    _head->_prev = _head;
}

list() { CreateHead(); }

拷贝构造和赋值重载则利用了 push_back 和 swap 技巧，特别是赋值运算符中的'交换法'，能高效地释放旧资源并获取新资源。

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

析构函数中，先调用 clear() 释放所有有效节点，最后再删除哨兵节点本身。

迭代器重载实现

迭代器要像原生指针一样好用，必须重载一系列运算符。

解引用与箭头操作

operator* 返回节点数据的引用，operator-> 返回数据地址。C++ 编译器对 -> 有特殊处理，如果返回的是指针，会自动再次调用 ->，所以直接返回 &(_pnode->_data) 即可。

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

移动与比较

前置 ++ 和 -- 直接修改内部指针并返回引用，支持链式调用。后置版本则需要先保存副本再移动。

Self& operator++() { _pnode = _pnode->_next; return *this; }
Self operator++(int) { Self tmp = *this; ++(*this); return tmp; }

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

注意：比较两个迭代器是否相等，实际上是比较它们指向的节点指针是否相同，而不是比较数据内容。

常用操作实现

list 的大部分操作都可以复用 insert 和 erase 来实现，这体现了接口设计的复用性。

头尾插删

push_back 和 push_front 分别是在 end() 和 begin() 位置插入。pop_back 和 pop_front 则是删除对应位置的元素。

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

这里要注意 pop_back 的实现细节：erase(--end())。因为 end() 返回的是哨兵节点，不能直接删除，需要先向前移动一步找到最后一个有效节点。

插入与删除

插入操作需要调整四个指针：新节点的前驱、新节点的后继、原位置前驱的后继、原位置后继的前驱。

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

清空容器

clear 函数通过遍历链表逐个删除节点。利用 erase 返回下一个迭代器的特性，可以安全地遍历并释放内存。

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

总结

STL 的 list 实现展示了如何通过模板元编程和指针操作构建灵活的容器。理解哨兵节点的设计能帮你更好地处理边界情况，而迭代器的重载则是实现泛型算法的基础。在实际开发中，虽然 list 提供了 O(1) 的插入删除能力，但其随机访问性能较差且内存开销较大，选择容器时需权衡利弊。