【STL源码分析】序列式容器之list

本文最后更新于：2023年12月17日下午

前言

本文主要内容参考：2 万字+20 图带你手撕 STL 序列式容器源码^[1]，原文内容非常详尽充实，建议大家阅读学习。而本文则是摘录总结关键部分，重点分析list的数据结构和关键函数实现。

list数据结构

首先简单概括一下，SGI STL里list的实现是一个双向链表，并定义了专属的list迭代器，来对访问list中的节点，而list_iterator其实就是list_node进行了一些封装。

下面给出list实现相关的类图：

list双向链表实现大致如下图所示，list含有一个_List_node 指针，代表着一个空节点（end函数返回该位置的迭代器），其next指向链表中实际的第一个节点（begin 对应的位置）。

list双向链表

list关键函数实现

begin ：返回第一个节点的迭代器。
end：返回空元素节点的迭代器。
insert：将某一个元素插入到链表的一个位置上，有多组重载，具体实现来说就是调整相关指针的值。
push_back：调用insert，在end( ) 位置上插入元素。
push_front：调用insert，在begin( ) 位置上插入元素。
erase ：删除节点，主要也是调整相关节点指针的值，然后回收节点内存和节点元素值的内存。
pop_back：调用erase，删除end( ) 前一个位置上的元素。
pop_front：调用erase，删除begin( ) 位置上的元素。
transfer(position, first, last) ：参数类型都是list迭代器，函数作用是将[first, last) 上的元素移动到 position 位置前。
splice：有多个重载，拼接元素或者是链表，实现上是去调用 transfer 函数。
merge ：将传入的 list 链表 x 与原链表按从小到大合并到原链表中(前提是两个链表都是已经从小到大排序了)。merge的实现也是去调用 transfer 函数。
reverse ：实现将链表翻转的功能，实现上简单来说就是将每个节点的 prev 与 next 值互换
operator= 赋值操作：需要考虑两个链表的实际大小不一样时的情况。如果原链表大，复制完后要删除掉原链表多余的元素；如果原链表小，复制完后要还要将x链表的剩余元素以插入的方式插入到原链表中。
resize：重新修改 list 的大小，传入一个 new_size，如果链表旧长度大于 new_size 的大小, 那就删除后面多余的节点，否则插入新节点。
clear：清除所有节点：遍历每一个节点，销毁(析构并释放)一个节点。
remove ：清除指定值的元素：遍历每一个节点，找到就移除。
unique ：清除数值相同的连续元素，注意只有“连续而相同的元素”，才会被移除剩一个。遍历每一个节点，如果在此区间段有相同的元素就移除之。

下面重点介绍下list根据自身数据结构特点，实现的sort成员函数。

sort 函数： list 容器自身实现一个排序（升序），其基本算法思想跟归并排序非常类似，并借助merge函数来排序。简单来说，使用一个链表数组来存储排序节点，每个下标为 i 的链表存储 2^i 的节点，每次从原链表中取出一个节点进行排序，并且排序节点的个数按 2^i 指数递增，最终将数组中的所有链表进行merge合并，从而实现原链表的排序。

sort函数源码

举一个简单的实现过程来帮助理解，例如对于链表元素 { 7, 6, 5, 4, 3, 2, 1 }，排序过程大致描述如下：

第1次排序 (7)
第2次排序 (6)
第3次排序 (7)、(6) 合并排序成 (6、7)
第4次排序 (5)
第5次排序 (4)
第6次排序 (5)、(4) 合并排序成 (4、5)
第7次排序（6、7）、(4、5）合并排序成（4, 5, 6, 7）
第8次排序 (3)
第9次排序 (2)
第10次排序 (3)、(2) 合并排序成 (2, 3)
第11次排序 (1)
最后合并所有链表，即 (1) 、（2,3) 、（4, 5, 6, 7) 依次合并
第12次排序 (1) 、（2,3) 合并排序成 (1, 2, 3)
第13次排序 (1, 2, 3) 、(4, 5, 6, 7) 合并排序成 (1, 2, 3, 4, 5, 6, 7)
完成排序，结束。

下图是排序过程实现的图解，参考了 C++ STL LIST SORT 排序算法图解_zp0int的博客^[2]。

注意其中的list、carry、counter[i] 都是双向链表，其实都包含有一个dummy节点（也就是end() 位置节点），但是为了方便，这里只画出了实际包含的节点值。
图里所说的while循环指的是第一层 while 循环，每次循环都是从list中取出一个节点，carry 作为中间过渡，所以每次循环结束后list节点数减一，carry 为空

sort函数整体实现过程

上图描述了整体的执行过程，下图则具体描述第四次while循环里的执行过程，关注carry 和 counter链表的交互。

第四次while循环具体过程

在leecode上也有一道算法题 https://leetcode.cn/problems/sort-list/ ，恰好就是要对一条链表实现排序，除了自顶向下的归并排序，大家也可以尝试使用上述的这种类归并排序算法进行实现，下面是我的实现，仅供参考。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        } 
        ListNode* carry = nullptr;
        ListNode* counter[16];      // 因为题目说明节点数小于50000个，所以用16条链表足够
        int fill = 0;               // 下一个填充链表的下标
        for (int i=0;i<16;i++) {
            counter[i] = nullptr;
        }
        while (head != nullptr) {
            // 拿出一个元素
            carry = head;
            head = head->next;
            carry->next = nullptr;
            
            int cur = 0;            // 当前排序链表下标
            while (cur < fill && counter[cur] != nullptr ) {
                counter[cur] = merge(counter[cur], carry);
                carry = nullptr;            
                std::swap(carry, counter[cur++]);
            }
            std::swap(carry,counter[cur]);
            if (cur == fill) {
                fill++;
            }
        
        }

        // 最后将所有链表元素合并
        for (int i=1;i<fill;i++) {
            counter[i] = merge(counter[i-1],counter[i]);
        }
        return counter[fill-1];
    }

    // 合并两条链表，并返回合并后的链表头结点
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode head;
        ListNode* cur = &head;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if (l1 == nullptr) {
            cur->next = l2;
        }
        if (l2 == nullptr) {
            cur ->next = l1;
        }
        return head.next;
    }

};