STL 源码剖析：list 容器从迭代器到算法实现

构造逻辑简单，支持默认构造、节点地址构造及拷贝构造。

运算符重载

比较操作直接比对节点地址，自增自减则通过 next 或 prev 指针移动。

template <class T, class Ref, class Ptr>
struct __list_iterator {
    typedef __list_node<T>* link_type;
    link_type node;

    bool operator==(const self& x) const {
        return node == x.node;
    }
    bool operator!=(const self& x) const {
        return node != x.node;
    }

    reference operator*() const {
        return (*node).data;
    }

#ifndef __SGI_STL_NO_ARROW_OPERATOR
    pointer operator->() const {
        return &(operator*());
    }
#endif

    self& operator++() {
        node = (link_type)((*node).next);
        return *this;
    }
    self operator++(int) {
        self tmp = *this;
        ++*this;
        return tmp;
    }

    self& operator--() {
        node = (link_type)((*node).prev);
        return *this;
    }
    self operator--(int) {
        self tmp = *this;
        --*this;
        return tmp;
    }
};

list 数据结构与哨兵位

list 是一个循环双向链表，并在首尾之间设置了一个哨兵节点（dummy node）。这个空白节点至关重要，它统一了'前闭后开'区间的处理逻辑，使得空列表判断和边界操作变得一致。

容器内部只需维护哨兵位的地址即可管理整个链表。

template <class T, class Alloc = alloc>
class list {
protected:
    typedef void* void_pointer;
    typedef __list_node<T> list_node;
    typedef list_node* link_type;
    
protected:
    link_type node; // 记录哨兵位节点的地址
};

示意图中，begin() 对应哨兵位的 next，end() 对应哨兵位自身。利用这一点，我们可以轻松实现空判断和元素统计。

template <class T, class Alloc = alloc>
class list {
public:
    iterator begin() {
        return (link_type)((*node).next);
    }
    iterator end() {
        return node;
    }
    bool empty() const {
        return node->next == node;
    }
    size_type size() const {
        size_type result = 0;
        distance(begin(), end(), result);
        return result;
    }
    reference front() {
        return *begin();
    }
    reference back() {
        return *(--end());
    }
    protected:
    link_type node;
};

构造与内存管理

list 默认使用 alloc 作为空间配置器，并封装了专门的节点分配接口。

template <class T, class Alloc = alloc>
class list {
protected:
    typedef simple_alloc<list_node, Alloc> list_node_allocator;
    link_type get_node() {
        return list_node_allocator::allocate();
    }
    void put_node(link_type p) {
        list_node_allocator::deallocate(p);
    }
};

template <class T, class Alloc>
class simple_alloc {
public:
    static T* allocate(size_t n) {
        return 0 == n ? 0 : (T*)Alloc::allocate(n * sizeof(T));
    }
    static T* allocate(void) {
        return (T*)Alloc::allocate(sizeof(T));
    }
    static void deallocate(T* p, size_t n) {
        if (0 != n) Alloc::deallocate(p, n * sizeof(T));
    }
    static void deallocate(T* p) {
        Alloc::deallocate(p, sizeof(T));
    }
};

get_node 负责开辟空间，put_node 负责释放。创建节点时还会调用 construct 初始化数据，销毁时先析构再释放。

即使是空 list，内部也会初始化一个指向自身的哨兵节点，确保链表始终处于合法状态。

核心接口实现

插入与删除

insert 操作分为两步：申请节点并链接入链表。注意指针修改的顺序，避免断链。

iterator insert(iterator position, const T& x) {
    link_type tmp = create_node(x); // 开辟新节点
    tmp->next = position.node;
    tmp->prev = position.node->prev;
    (link_type(position.node->prev))->next = tmp;
    position.node->prev = tmp;
    return tmp;
}

push_front 和 push_back 本质上都是调用 insert 在特定位置插入。

删除操作 erase 同样分两步：断开连接与销毁节点。

iterator erase(iterator position) {
    link_type next_node = (link_type)(position.node->next);
    link_type prev_node = (link_type)(position.node->prev);
    prev_node->next = next_node;
    next_node->prev = prev_node;
    destroy_node(position.node);
    return iterator(next_node);
}

迁移与合并

transfer 是 list 内部的核心工具函数，用于将一段区间 [first, last) 迁移到 position 之前。它涉及 6 个指针的重新指向，实现了 O(1) 复杂度的区间移动。

void transfer(iterator position, iterator first, iterator last) {
    if (position != last) {
        (*(link_type((*last.node).prev))).next = position.node;
        (*(link_type((*first.node).prev))).next = last.node;
        (*(link_type((*position.node).prev))).next = first.node;
        link_type tmp = (link_type)((*position.node).prev);
        (*position.node).prev = (*last.node).prev;
        (*last.node).prev = (*first.node).prev;
        (*first.node).prev = tmp;
    }
}

基于 transfer，splice 接口得以实现，支持整表、单节点或区间迁移。这使得 merge 操作变得高效，两个有序链表可直接合并为一个新的有序链表。

void merge(list& x) {
    iterator first1 = begin();
    iterator last1 = end();
    iterator first2 = x.begin();
    iterator last2 = x.end();
    while (first1 != last1 && first2 != last2) {
        if (*first2 < *first1) {
            iterator next = first2;
            transfer(first1, first2, ++next);
            first2 = next;
        } else {
            ++first1;
        }
    }
    if (first2 != last2) {
        transfer(last1, first2, last2);
    }
}

排序与逆置

reverse 通过不断将后续节点迁移至头部实现逆置。

void reverse() {
    if (node->next == node || (link_type)(node->next)->next == node)
        return;
    iterator first = begin();
    ++first;
    while (first != end()) {
        iterator old = first;
        ++first;
        transfer(begin(), old, first);
    }
}

由于 list 不支持随机访问，标准库的 sort 无法直接使用。list 内部实现了自底向上的归并排序。该算法省略了分割阶段，直接从长度为 1 的子链表开始两两合并，逐步构建出完整有序链表。

void sort() {
    if (node->next == node || (link_type)(node->next)->next == node)
        return;
    list carry;
    list counter[64];
    int fill = 0;
    while (!empty()) {
        carry.splice(carry.begin(), *this, begin());
        int i = 0;
        while (i < fill && !counter[i].empty()) {
            counter[i].merge(carry);
            carry.swap(counter[i++]);
        }
        carry.swap(counter[i]);
        if (i == fill)
            ++fill;
    }
    for (int i = 1; i < fill; ++i)
        counter[i].merge(counter[i - 1]);
    swap(counter[fill - 1]);
}

理解这些底层逻辑，能帮助我们在实际开发中更合理地选择数据结构，并在遇到性能瓶颈时找到优化方向。