STL 源码剖析：深入理解 list 容器实现机制

STL 源码剖析：深入理解 list 容器实现机制

本文基于 SGI STL 版本源码进行解析，适合已掌握 C++ 模板、内存管理及数据结构基础，希望深入理解 STL 内部实现的开发者阅读。

前言

在数据结构学习中，大家通常知道 vector 的头插和头删效率较低（O(N)），而 list 在这些操作上均能达到 O(1)。此外，list 的任意位置插入和删除也是 O(1)，且每个节点独立分配，不存在连续线性地址空间的问题。这意味着除非显式删除了节点，否则迭代器不会失效。同时，list 无需像 vector 那样进行二倍扩容，它是按需开辟空间的。

本文将从六个板块对 list 的源码进行剖析：

1. list 概述；
2. list 节点设计；
3. list 的迭代器；
4. list 的数据结构；
5. list 的构造和内存管理；
6. list 的核心接口实现。

一、list 概述

除了上述优势，list 也存在一些劣势需要留意：

• 不支持随机访问索引操作，没有重载 [] 运算符，元素访问不如 vector 方便；
• 数据非集中存储，内存局部性差，缓存利用率相对较低；
• 内存开销较大，每个节点除了存储数据外，还需额外维护两个指针。

二、list 的节点

list 的节点与容器本身是分离设计的。从节点结构可以看出，list 本质上是一个双向循环链表。

template <class T>
struct __list_node {
    typedef void* void_pointer;
    // 使用 void* 存储地址，也可以用 __list_node<T>*
    void_pointer next;  // 存储下一个节点的地址
    void_pointer prev;  // 存储上一个节点的地址
    T data;             // 存储有效数据
};

三、list 迭代器

3.1 定义

由于 list 节点不连续存放，迭代器的加减操作不能像 vector 那样通过普通指针偏移实现。list 的节点存储了前驱和后继的地址，因此其迭代器属于 Bidirectional Iterators（双向迭代器）。

查看 list 迭代器的成员定义：

template <class T, class Ref, class Ptr>
struct __list_iterator {
    typedef __list_iterator<T, T&, T*> iterator;
    typedef __list_iterator<T, const T&, const T*> const_iterator;
    typedef __list_iterator<T, Ref, Ptr> self;
    typedef T value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef __list_node<T>* link_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    
    link_type node; // 存储该迭代器指向的节点
};

list 迭代器的核心成员只有一个：当前节点的地址。主要的操作集中在重载 ++, --, ==, != 等运算符上。

3.2 构造

构造逻辑相对简单，包括无参构造、节点地址构造以及拷贝构造。

__list_iterator(link_type x) : node(x) {}
__list_iterator() {}
__list_iterator(const iterator& x) : node(x.node) {}

3.3 重载

对于 == 和 !=，直接比较 node 成员的地址即可。++ 和 -- 则分别指向下一个或上一个节点的地址。

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 /* __SGI_STL_NO_ARROW_OPERATOR */

    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 不仅是一个双向链表，它首尾相连形成循环双向链表。在起始位置和结束位置还有一个哨兵位（空白节点），通过该哨兵节点可以满足 STL 对于'前闭后开'区间的要求。

list 中只需要存储哨兵位的地址，就可以对整个链表进行操作。

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() 对应 node->next，end() 对应 node。判断链表是否为空、获取元素个数等操作都可以通过该哨兵位作为标记处理。

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 的构造和内存管理

list 缺省使用 alloc 作为空间配置器，并据此定义出了一个 list_node_allocator，专门以一个节点的大小进行空间配置。

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 是 list 中专门用来开辟一个节点空间的接口，而 put_node 则是专门用来释放一个节点的。

template <class T, class Alloc = alloc>
class list {
protected:
    link_type create_node(const T& x) {
        link_type p = get_node(); // 开辟一个节点
        __STL_TRY {
            construct(&p->data, x); // 用 x 对空间进行初始化
        } __STL_UNWIND(put_node(p));
        return p;
    }
    void destroy_node(link_type p) {
        destroy(&p->data); // 析构对象
        put_node(p);       // 释放空间
    }
};

create_node 用来创建一个带有元素值的节点，destroy_node 负责销毁（析构 + 释放空间）一个节点。

list 有一个无参构造，这并不代表该链表内部不用开辟空间。即使是空链表，内部也有一个哨兵位，并且该哨兵节点指向自己。

六、list 的接口

list 的接口繁多，此处列举几个最频繁、最重要的实现逻辑。

insert 插入

iterator insert(iterator position, const T& x) 分为两步：

1. 开辟空间，创建节点；
2. 将节点插入到目标位置。

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_back() 和 push_front() 都是调用 insert 实现的：

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

erase 删除

iterator erase(iterator position) 指定位置删除也分两步：

1. 将前一个节点与后一个节点相连，将目标节点移除链表；
2. 释放节点空间。

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

同理 pop_back() 和 pop_front() 也调用 erase() 实现：

void pop_front() {
    erase(begin());
}
void pop_back() {
    iterator tmp = end(); // tmp 是哨兵位
    erase(--tmp);
}

clear 清除所有节点

将所有节点进行销毁，将哨兵节点头尾相连。

template <class T, class Alloc>
void list<T, Alloc>::clear() {
    link_type cur = (link_type)node->next; // 从头结点开始
    while (cur != node) {
        link_type tmp = cur;
        cur = (link_type)cur->next;        // 移动到下一个节点
        destroy_node(tmp);                 // 销毁
    }
    node->next = node;                     // 哨兵节点头尾相连
    node->prev = node;
}

remove 移除特定值

void remove(const T& value) 将链表中值为 value 的节点都删除。因为前面已经有 erase 了，所以在找到 value 节点时，可以直接进行删除。

template <class T, class Alloc>
void list<T, Alloc>::remove(const T& value) {
    iterator first = begin();
    iterator last = end();
    while (first != last) {
        iterator next = first;
        ++next;
        if (*first == value)
            erase(first);
        first = next;
    }
}

unique 移除重复元素

void unique() 移除数值相同的连续元素，只有'连续且相同的元素'才会被移除剩一个。

template <class T, class Alloc>
void list<T, Alloc>::unique() {
    iterator first = begin();
    iterator last = end();
    if (first == last)
        return;
    iterator next = first;
    while (++next != last) {
        if (*first == *next) // first 和下一个位置相同，删除下一个位置
            erase(next);
        else {
            first = next;    // 不相同，让 first 走到下一个位置
            next = first;    // 让 next 再赋值为 first，使得 next 与 first 比较的时候永远在 first 的下一个位置
        }
    }
}

在上述比较的时候，如果 first 后面的 next 于 first 相同，就将 next 移除，此时 first 后面的节点就是第三个节点了，可能还是与 first 相同，所以不能移动 first 的位置。

transfer 迁移操作

list 内部提供了一个所谓的迁移操作 transfer，可以将某一个链表的一部分迁移到当前链表的其他位置，或另一个链表上。这个操作也为后续的 splice, sort, merge 奠定了良好的基础。

template <class T, class Alloc>
class list {
protected:
    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 就是将指针的指向进行一定的修改：将 [first, last) 移动到 position 位置之前，一共要修改 6 个指针的指向：

1. position + 1 与 position 中间插入 [first, last - 1] 需要改变 4 个指针指向，分别是 first.prev, position.prev, (last - 1).next, (position + 1).next；
2. 还要将 first - 1 与 last 连接起来。

splice 拼接

transfer 是 protected 的，并没有向外公开。对外公开的是另一个接口 splice，该函数有三个重载，分别可以满足将整条 list 迁移到指定位置，将一个节点迁移到指定位置，将一个区间迁移到指定位置。

public:
void splice(iterator position, list& x) {
    // x 必须于*this 不同
    if (!x.empty())
        transfer(position, x.begin(), x.end());
}
void splice(iterator position, list&, iterator i) {
    // x 可以在*this 上
    iterator j = i;
    ++j;
    if (position == i || position == j)
        return;
    transfer(position, i, j);
}
void splice(iterator position, list&, iterator first, iterator last) {
    if (first != last) // position 不能在区间内
        transfer(position, first, last);
}

merge 合并

有了 transfer 这个接口，merge() 的实现也就不难了。merge() 可以将两个递增的链表进行合并，合并后的链表依旧有序。

public:
template <class T, class Alloc>
void list<T, Alloc>::merge(list<T, Alloc>& x) {
    iterator first1 = begin();
    iterator last1 = end();
    iterator first2 = x.begin();
    iterator last2 = x.end();
    while (first1 != last1 && first2 != last2) {
        if (*first2 < *first1) { // first2 小，将其迁移到 first1 前
            iterator next = first2;
            transfer(first1, first2, ++next);
            first2 = next;
        } else
            ++first1;
    }
    if (first2 != last2)
        transfer(last1, first2, last2); // first2 还没遍历完，直接迁移到 first1 末尾
}

reverse 逆置

list 中提供了一个 reverse() 接口，可以将链表进行逆置。时间复杂度上就是对链表中的节点进行迁移，将起始位置后面的节点依次迁移到起始节点前面。

public:
template <class T, class Alloc>
void list<T, Alloc>::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);
    }
}

sort 排序

list 的迭代器不是随机访问迭代器，属于双向迭代器，因此不能直接使用库中提供的 sort 进行排序，list 类中实现了自己的排序算法。

list 的排序底层逻辑采用的是归并排序，只不过这种归并是自底向上的，即省略了上层分割的操作，直接从底依次拼接出完整的链表。

• carray 存放要进行合并的链表；
• counter[i] 存放长度为 $2^i$ 还没进行归并的链表，让 carray 来归并；
• fill 存储 counter 的最大索引，还没使用的最小位置。

实际步骤如下：

1. 先从 *this 中取节点放到 carray 上，此时 carray 有一个节点；
2. 看 counter[0] 是否存在链表，如果有就让 counter[0] 和 carray 归并；
3. 将归并的结果放到 carray 中，再判断 counter[1] 是否有链表，如果有继续归并；
4. 重复上面的操作；
5. 最后 counter 中存放着不同长度但是都是有序的链表，再将这些链表进行归并即可。

public:
template <class T, class Alloc>
void list<T, Alloc>::sort() {
    if (node->next == node || (link_type)(node->next)->next == node)
        return;
    list<T, Alloc> carry;           // 临时存储还未排序的链表，但是该链表内部必须递增
    list<T, Alloc> 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);                 // carray 和对应相同长度的链表进行归并放到 counter[i] 上
            carry.swap(counter[i++]);                // 将 count[i] 交换到 carray 上，让 carray 继续向上去归并
        }
        carry.swap(counter[i]);                      // 将 carray 已经排好的数据放回 counter[i] 中
        if (i == fill)
            ++fill;
    }
    for (int i = 1; i < fill; ++i)
        counter[i].merge(counter[i - 1]);
    swap(counter[fill - 1]);
}