STL 源码剖析：深入理解 list 容器与核心算法实现 | 极客日志

C++算法

STL 源码剖析：深入理解 list 容器与核心算法实现

基于 SGI STL 源码深度解析 std::list 容器。涵盖双向循环链表节点设计、双向迭代器重载逻辑、哨兵位机制及内存分配策略。重点剖析 insert、erase、splice 等核心接口的指针操作细节，以及自底向上归并排序的实现原理。适合具备 C++ 模板基础及数据结构知识的开发者阅读，旨在通过源码理解 STL 底层优化与算法思想。

赛博朋克发布于 2026/3/210 浏览

STL 源码剖析：深入理解 list 容器与核心算法实现

STL 源码剖析：深入理解 list 容器与核心算法实现

本文基于 SGI STL 版本，从源码层面剖析 std::list 的实现细节。适合具备 C++ 模板基础、熟悉内存管理且希望深入理解 STL 底层机制的开发者阅读。

一、list 概述

相较于 vector，list 在头插、头删及任意位置插入删除操作上均能达到 O(1) 复杂度。其节点独立分配，非连续线性存储，因此不会像 vector 那样因扩容导致迭代器失效（除非显式删除了节点）。当然，代价是失去了随机访问能力，且每个节点需额外维护两个指针，内存开销略高，缓存局部性也较差。

二、list 的节点设计

list 的节点与容器本身分离设计。SGI STL 中的节点结构如下：

template <class T>
struct __list_node {
    typedef void* void_pointer;
    void_pointer next; // 指向下一个节点
    void_pointer prev; // 指向上一个节点
    T data;            // 有效数据
};

可以看出，这是一个双向链表的基础结构。

三、list 迭代器

由于节点不连续，普通指针无法胜任迭代任务。list 采用双向迭代器（Bidirectional Iterator），通过重载运算符实现节点跳转。

3.1 定义

迭代器内部仅保存当前节点的地址：

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;
      difference_type;
    
    link_type node; 
};

__list_iterator(link_type x) : node(x) {}
__list_iterator() {}
__list_iterator(const iterator& x) : node(x.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

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

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; // 记录哨兵位节点的地址
};

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

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

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);
        } __STL_UNWIND(put_node(p));
        return p;
    }
    
    void destroy_node(link_type p) {
        destroy(&p->data);
        put_node(p);
    }
};

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

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

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

void pop_front() { erase(begin()); }
void pop_back() {
    iterator tmp = end();
    erase(--tmp);
}

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

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);
        else
            first = next;
    }
}

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)
            erase(next);
        else
            first = next;
    }
}

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

public:
void splice(iterator position, list& x) {
    if (!x.empty())
        transfer(position, x.begin(), x.end());
}

void splice(iterator position, list&, iterator i) {
    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)
        transfer(position, first, last);
}

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) {
            iterator next = first2;
            transfer(first1, first2, ++next);
            first2 = next;
        } else
            ++first1;
    }
    if (first2 != last2)
        transfer(last1, first2, last2);
}

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

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