标准模板库list

代码仓库shanchuann/CPP-Learninng

在 C++ STL 序列容器家族中， vector 主打连续内存与极致随机访问， deque 兼顾双端高效操作与随机访问，而list则是另一种定位完全不同的序列容器——它基于双向链表实现，核心优势是容器任意位置 O(1)常数时间的插入与删除操作，完美弥补了 vector 和 deque 中间操作效率低下的短板。

但 list 也牺牲了随机访问能力，且存在额外的内存开销，只有吃透它的底层设计、接口特性与适用场景，才能在开发中精准选型，避开性能陷阱。本文将从底层结构、核心接口、迭代器规则、容器对比、实操代码到工程应用，全面拆解 STL list ，帮你彻底掌握这个链表型容器。

list 是 STL 标准的双向循环链表容器，属于序列式容器，它将每个元素独立存储在不同的内存节点中，通过前后指针将节点串联成线性结构，支持双向迭代遍历。

• 优势：容器任意位置的插入、删除、元素移动均为 O(1)常数时间（只需修改节点指针，无需移动大量元素）；插入/删除操作不会导致迭代器失效（仅被删除元素的迭代器失效）；元素内存地址固定，不会因扩容或插入操作变动。
• 短板：不支持随机访问，无法通过下标[]或at()直接访问元素，访问指定位置元素需从头/尾迭代遍历，时间复杂度 O(n)；迭代器仅支持双向移动（++/--），不支持随机跳跃（+=/-=）；存储密度低，每个节点需额外存储前后指针，小元素场景内存开销更明显。

简单来说：需要频繁在任意位置增删元素，选 list ；需要随机访问，选 vector/deque。

底层结构

list 的底层是双向链表，整体结构分为链表节点与容器主控结构两部分，和 vector/deque 的连续/分段内存设计有本质区别，这也是它特性的根源。

链表节点结构

每个 list 元素对应一个独立节点，节点包含三个核心部分：存储的元素值、指向前一个节点的指针（ prev ）、指向后一个节点的指针（ next ）。简化版节点结构如下：

template<class _Ty>
struct _Node {
    _Ty _Value;        // 存储实际元素
    _Node* _Prev;      // 指向前一个节点
    _Node* _Next;      // 指向后一个节点
};

容器主控结构

list 容器本身只维护两个核心成员：一个指向链表头节点的指针，一个记录元素总数的大小变量。为了实现双向迭代与边界判断， STL 中 list 通常采用带头节点的双向循环链表设计，空 list 也会有一个空的头节点，简化迭代逻辑。

template<class _Ty>
class list {
protected:
    typedef _Node* _Nodeptr;  // 节点指针别名
private:
    _Nodeptr _Head;           // 链表头节点指针
    size_type _Size;          // 容器内元素总数
};

存储模型

• 空 list 模型：仅有头节点，头节点的_Prev和_Next都指向自身，_Size=0，无实际元素节点。
• 有数据 list 模型：头节点串联首尾元素节点，首尾节点相互指向，形成循环结构，_Size记录实际元素个数。

这种设计的好处是：无论链表是否为空，迭代器的首尾判断逻辑统一，避免空指针异常，同时双向遍历更便捷。

接口与实操代码

构造函数

list 提供了多样化的构造方式，适配不同初始化场景，和 vector/deque 接口高度兼容：

#include <list>
#include <iomanip>
using namespace std;
// 通用打印函数
template<class _Con>
void PrintList(const _Con& ilist) {
    cout << "元素个数:" << ilist.size() << " | 数据:";
    for (const auto& x : ilist) {
        cout << setw(3) << x;
    }
    cout << endl;
}

int main() {
    const int n = 10;
    int arr[n] = {1,2,3,4,5,6,7,8,9,10};
    // 1. 默认构造：空list
    list<int> ilista;
    // 2. 初始化列表构造（C++11）
    list<int> ilistb = {12,23,34,45,56};
    // 3. 填充构造：n个指定值
    list<int> ilistc(5,23);
    // 4. 迭代器区间构造
    list<int> ilistd(arr, arr + n);
    // 5. 拷贝构造
    list<int> iliste(ilistb);
    // 6. 移动构造（C++11）：转移所有权，零拷贝
    list<int> ilistf(move(ilistb));
    PrintList(ilista);
    PrintList(ilistb);  // 移动后为空
    PrintList(ilistc);
    PrintList(ilistd);
    PrintList(iliste);
    PrintList(ilistf);
    return 0;
}

执行结果：空 list 输出 0 个元素，填充构造输出 5 个 23 ，区间构造输出 1-10 ，拷贝/移动构造正常复制数据，移动后原容器置空。

元素访问

list不支持 operator[]下标访问和 at()函数，因为随机访问需要遍历，不符合链表设计逻辑，仅提供首尾元素的快速访问接口：

• front()：访问第一个元素， O(1)
• back()：访问最后一个元素， O(1)

注意：访问前需确保容器非空，否则触发未定义行为。

迭代器

list 的迭代器是双向迭代器，而非随机访问迭代器，核心规则：

• 支持++it/it++/--it/it--双向移动，不支持it += n/it -= n/it + n随机跳跃
• 不能直接用it + 5访问第 5 个元素，需循环++it遍历
• 常用迭代器接口：begin()/end()、cbegin()/cend()（常量迭代器）、rbegin()/rend()（反向迭代器）

int main() {
    list<int> ilist = {1,2,3,4,5};
    // 正向迭代器遍历
    for (list<int>::iterator it = ilist.begin(); it != ilist.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    // 范围for遍历（推荐，语法糖）
    for (const auto& elem : ilist) {
        cout << elem << " ";
    }
    return 0;
}

容量管理接口

list 基于链表节点存储，无需预分配内存，因此无reserve()/capacity()接口，仅提供基础容量接口：

• empty()：判断容器是否为空， O(1)
• size()：获取当前元素个数， O(1)
• max_size()：理论最大容纳元素数， O(1)
• resize(n)：调整元素数量，不足补默认值，超出删除尾部元素， O(n)

通用修改器

list 支持头尾、任意位置的增删操作，任意位置插入/删除均为 O(1)，核心接口：

• push_back(val)/emplace_back(args)：尾部插入/原地构造元素
• push_front(val)/emplace_front(args)：头部插入/原地构造元素
• pop_back()：删除尾部元素
• pop_front()：删除头部元素
• insert(pos, val)：指定迭代器位置插入元素， O(1)
• erase(pos)：删除指定迭代器位置元素， O(1)
• clear()：清空所有元素， O(n)
• assign：批量赋值，清空原有元素，重新填充，和 vector/deque 的 assign 用法一致

assign 函数详解

assign 用于批量替换容器内容，先清空 list 原有所有元素，再重新填充，支持三种重载：

• assign(n, val)：填充 n 个值为 val 的元素
• assign(first, last)：迭代器区间填充
• assign(initializer_list)：初始化列表填充

int main() {
    list<int> ilist = {1,2,3};
    // 1. 批量填充5个10
    ilist.assign(5, 10);
    PrintList(ilist);
    // 2. 区间赋值
    int arr[] = {6,7,8};
    ilist.assign(arr, arr+3);
    PrintList(ilist);
    // 3. 初始化列表赋值
    ilist.assign({100,200,300});
    PrintList(ilist);
    return 0;
}

专属操作函数

list 基于双向链表的特性，提供了多个独有的高效操作函数，这些操作仅修改节点指针，不拷贝/移动元素，效率极高，是 list 的核心竞争力。

splice 节点转移零拷贝

splice 是 list 最核心的专属函数，作用是将另一个 list 的节点转移到当前 list 指定位置，不复制元素，仅修改节点指针，无任何迭代器/引用失效，指向转移元素的迭代器依然有效。

int main() {
    list<int> arlist = {1,3,5,7,9};
    list<int> brlist = {2,4,6,8,10};

    cout << "转移前：arlist: ";
    PrintList(arlist);
    cout << "转移前：brlist: ";
    PrintList(brlist);

    // 迭代器后移2位，指向元素5
    auto it = arlist.begin();
    advance(it, 2);
    // 将brlist所有元素转移到arlist的it位置
    arlist.splice(it, brlist);

    cout << "转移后：arlist: ";
    PrintList(arlist);
    cout << "转移后：brlist: ";  // brlist变为空
    PrintList(brlist);
    return 0;
}

merge 合并有序链表

merge 用于合并两个有序的 list，合并后依然有序，源 list 变为空，默认升序，可自定义排序规则，仅修改指针，无元素拷贝。

注意： merge 仅对有序链表生效，无序链表合并后无排序效果。

int main() {
    list<int> arlist = {1,2,3,4,5,6,7,8,9,10};
    list<int> brlist = {2,4,6,8,10};

    arlist.merge(brlist);
    PrintList(arlist);  // 合并后有序
    PrintList(brlist);  // 空
    return 0;
}

unique 去重连续重复元素

unique 用于删除 list 中连续重复的元素，仅保留一个，使用前需先排序，否则无法去除非连续重复项。

int main() {
    list<int> ilist = {1,2,2,3,3,3,4};
    ilist.unique();
    PrintList(ilist);  // 输出：1 2 3 4
    return 0;
}

sort 链表专属排序

list 自带 sort 成员函数，采用归并排序实现，时间复杂度 O(nlogn)，和标准库std::sort（快速排序优化版）不同，std::sort不支持 list （需要随机访问迭代器）， list 只能用自身的 sort 函数。std::sort()则是整合了快速排序、堆排序与插入排序的自适应排序（ introspective sort ）：先通过快速排序递归至一定深度使子区域间有序，对数据量大于阈值（ 16 ）的子区域采用堆排序使其内部有序，最后对剩余小数据量子区域使用插入排序完成整体排序。

reverse 反转链表

reverse 用于反转 list 的元素顺序，仅修改节点指针，无需拷贝元素， O(n)时间复杂度。

迭代器失效规则

list 的迭代器失效规则和 vector/deque 完全不同，是链表结构的核心优势：

• 插入操作：任何位置插入元素，所有迭代器均不失效
• 删除操作：仅被删除元素的迭代器失效，其余迭代器全部有效
• splice/merge/swap等操作：迭代器不失效，仅转移所有权

这意味着在 list 中循环删除元素时，无需像 vector 那样重新获取迭代器，直接删除并递增迭代器即可。

list 、 vector 与 deque

特性	vector	deque	list
底层结构	整块连续内存	分段连续内存+主控 Map	双向循环链表
随机访问	O(1)，极快	O(1)，稍慢	不支持， O(n)遍历
头部增删	O(n)，极低	O(1)，高效	O(1)，高效
中间增删	O(n)，低效	O(n)，低效	O(1)，高效
内存开销	无额外开销	少量 Map 开销	节点指针开销大
迭代器类型	随机访问	随机访问	双向迭代
迭代器失效	扩容/插入全失效	插入全失效，指针有效	仅被删除元素失效

应用场景

list 的核心优势是任意位置 O(1)增删，适合频繁修改、无需随机访问的场景，典型应用如下：

• 频繁任意位置增删场景：日志记录系统、任务调度队列、事件处理队列，中间插入/删除频率极高， list 效率远超 vector/deque 。
• 双向迭代与顺序维护场景：文本编辑器的撤销/重做功能、浏览器历史记录、播放器播放列表，需要双向遍历且频繁调整元素顺序。
• 大对象存储场景：存储构造/拷贝代价高的大对象， list 插入删除仅修改指针，无需拷贝对象，性能优势明显。
• 链表专属算法场景：需要合并、拆分、反转链表的业务逻辑， splice/merge 等专属函数可零成本实现。

最佳实践

日常使用 STL list ，需牢牢贴合其双向链表的底层特性恪守核心用法准则，同时避开常见使用误区，才能最大化发挥容器优势、规避各类隐患。实操开发中优先选用 emplace_back 、 emplace_front 以及 emplace 系列原地构造接口，省去临时对象的拷贝与析构开销，进一步提升元素操作的整体效率；容器选型要精准匹配业务场景，但凡需要频繁在容器中间位置执行插入、删除操作， list 就是最优解，若业务依赖高频随机访问，则坚决舍弃 list ，转而选用 vector 或 deque 更为合适；调用 merge 、 unique 这类 list 专属函数前，务必提前对容器完成排序，才能保障函数功能正常生效、达到预期效果；遍历 list 时优先采用范围 for 循环或双向迭代器，避免手动计算元素位置，减少不必要的操作失误与代码漏洞。与此同时，几类核心禁忌需严格遵守， list 本身不支持下标[]访问，强行使用会直接触发编译报错； list 无法适配标准库的 std::sort 算法，只能调用容器自身的 sort 成员函数完成排序，这是双向迭代器的特性限制，切勿与普通随机访问容器的用法混淆； int 、 char 这类基础小元素场景慎用 list ，节点前后指针的额外内存开销远大于元素本身，会导致容器存储密度过低、造成不必要的内存浪费； unique 函数仅能去除连续重复的元素，针对非连续的重复项，需先对 list 完成排序，再调用 unique 才能实现完整去重。

容器嵌套

STL 容器支持灵活的相互嵌套，不仅限于同类型顺序容器之间的嵌套，不同类型的顺序容器也可自由组合，本质是将一个容器作为另一个容器的元素类型，以此构建二维乃至多维的复杂数据结构，同时兼顾不同容器的特性优势，适配更复杂的业务场景。除此之外，我们将对 vector 、 deque 、 list 三大核心顺序容器做系统性的横向对比，精简重复提及的核心特性，重点补充之前未展开的空间利用率、内存管理逻辑与场景化选型细节，帮你在开发中精准匹配最优容器。

容器嵌套的核心价值，是结合外层容器与内层容器的特性优势，规避单一容器的短板，无需手动实现复杂的多维数据结构，借助 STL 容器的原生接口即可完成数据管理。以下是三种最常用的嵌套形式，覆盖绝大多数开发场景。

list 嵌套 list

list 嵌套 list 本质是二维双向链表，外层 list 的每一个元素都是一个独立的 list 容器，适合行、列数据都需要频繁增删，且每行元素数量不固定的不规则多维数据场景，比如动态层级的分类数据、不规则的矩阵结构，无需移动大量数据即可完成行、列的插入与删除。

// 复用之前定义的通用打印函数
template<class _Con>
void PrintList(const _Con& ilist) {
    cout << "元素个数:" << ilist.size() << " | 数据:";
    for (const auto& x : ilist) {
        cout << setw(3) << x;
    }
    cout << endl;
}

int main() {
    const int n = 10;
    int ar[n] = { 1,2,3,4,5,6,7,8,9,10 };
    // 定义list嵌套list：外层list的元素为list<int>类型
    list<list<int>> arlist;

    // 向内层插入不同的list容器
    arlist.push_back(list<int>());          // 插入空list
    arlist.push_back(list<int>(5));         // 插入包含5个默认值的list
    arlist.push_back(list<int>(5, 25));     // 插入5个值为25的list
    arlist.push_back(list<int>(ar, ar + 10));// 从数组区间初始化list

    // 遍历外层list，打印每一个内层list
    for (const auto& inner_list : arlist) {
        PrintList(inner_list);
    }

    return 0;
}

vector 嵌套 list

vector 嵌套 list 的组合，外层 vector 支持 O(1)时间随机访问某一行，内层 list 支持行内元素的 O(1)时间任意位置增删，完美结合了 vector 的随机访问优势与 list 的高效增删优势，适合行数量相对固定、需要快速定位到某一行，同时行内元素需要频繁增删的场景，比如多任务调度队列、多频道的消息缓存，每个队列/频道的消息需要频繁插入删除，同时需要快速定位到指定队列。

int main() {
    const int n = 10;
    int ar[n] = { 1,2,3,4,5,6,7,8,9,10 };
    // 定义vector嵌套list：外层vector的元素为list<int>类型
    vector<list<int>> arver{
        list<int>{12,23},
        list<int>{},
        list<int>{12,23,34,45,56},
        list<int>{5,23},
        list<int>{ar,ar + n}
        // 注释行报错原因：初始化列表中，arver尚未完成初始化，无法引用自身的元素
        // list<int>{arver[1]},
        // list<int>{move(arver[1])}
    };

    // 遍历外层vector，打印每一个内层list
    for (const auto& inner_list : arver) {
        PrintList(inner_list);
    }

    // 可直接通过下标随机访问某一行，再操作内层list
    arver[2].push_back(100); // 给第3个list尾部添加元素
    cout << "修改后的第3行：";
    PrintList(arver[2]);

    return 0;
}

list 嵌套 vector

list 嵌套 vector 的组合，外层 list 支持行的 O(1)时间任意位置增删，内层 vector 支持行内元素的 O(1)随机访问与高效遍历，适合行数量不固定、需要频繁增删整行数据，同时行内元素需要高频随机访问的场景，比如动态增减的表格数据、多组批量统计数据，整行数据频繁新增或移除，每行内的元素需要快速查询与遍历。

#include <vector>

// vector通用打印函数
template<class _Con>
void PrintVector(const _Con& ivec) {
    cout << "元素个数:" << ivec.size() << " | 数据:";
    for (const auto& x : ivec) {
        cout << setw(3) << x;
    }
    cout << endl;
}

int main() {
    const int n = 10;
    int ar[n] = { 1,2,3,4,5,6,7,8,9,10 };
    // 定义list嵌套vector：外层list的元素为vector<int>类型
    list<vector<int>> arver{
        vector<int>{},
        vector<int>(5),
        vector<int>{5,23},
        vector<int>{ar,ar + n}
    };

    // 遍历外层list，打印每一个内层vector
    for (const auto& inner_vec : arver) {
        PrintVector(inner_vec);
    }

    // 外层list可高效增删整行，无需移动其他行数据
    arver.push_front(vector<int>{100, 200, 300}); // 头部新增一行
    cout << "新增行后，首行数据：";
    PrintVector(arver.front());

    return 0;
}

容器对比

vector 、 deque 、 list 作为 STL 最核心的三个顺序容器，我们已经分别讲解了各自的底层实现与核心特性，这里做横向对比梳理，之前反复提及的随机访问能力、基础增删效率、迭代器失效核心规则仅做精简总结，重点补充之前未展开的空间利用率、内存管理逻辑、初始化填充效率等细节，同时给出场景化的选型标准。

• vector 基于整块连续内存实现，拥有极致的 O(1)随机访问性能，尾部增删为 O(1)均摊时间复杂度，头部与中间增删为 O(n)，扩容时需要全量拷贝元素，迭代器、指针与引用极易因扩容、插入操作失效。
• deque 基于分段连续内存+主控 Map 实现，头部与尾部增删均为 O(1)时间复杂度，支持 O(1)随机访问（性能略低于 vector ），无全量扩容的性能损耗，插入操作会导致迭代器失效，但元素的指针与引用始终保持有效。
• list 基于双向循环链表实现，容器任意位置的插入、删除均为 O(1)时间复杂度，不支持随机访问，仅能通过迭代器双向遍历，插入操作不会导致任何迭代器失效，仅被删除元素的迭代器失效，内存开销相对更高。

空间利用率

vector 的空间利用率最高，无额外的指针开销，仅会预留部分容量的空闲内存，连续内存布局不会产生内存碎片，尤其在存储小元素时优势极为明显。 deque 的空间利用率中等，仅存在主控 Map 的少量指针开销，缓冲区会存在少量未使用的空闲空间，小元素场景下的内存效率远高于 list 。 list 的空间利用率最低，每个元素节点都需要额外存储前后两个指针，对于 int 、 char 这类小元素，指针的内存开销甚至会远超元素本身，同时离散的节点内存布局极易产生内存碎片。

内存扩展与收缩

vector 的扩展成本最高，扩容时需要申请更大的连续内存块，全量拷贝所有元素后释放旧内存；内存收缩需要通过 shrink_to_fit 实现，同样需要拷贝元素，全程伴随大量数据移动。 deque 的扩展与收缩成本极低，扩容仅需新增一块缓冲区，无需移动任何已有元素；收缩仅需释放完全空闲的缓冲区，无需改动已有数据，全程无元素拷贝。 list 的扩展与收缩成本为 O(1)，新增元素仅申请对应节点的内存，删除元素直接释放节点内存，全程不涉及任何元素的移动与拷贝，内存管理的灵活性最高。

初始化与批量填充

vector 的连续内存布局完美适配 CPU 缓存，批量初始化与填充操作的效率最高， assign 、 resize 等批量操作的性能远超另外两个容器。 deque 的分段内存布局会带来少量的间接寻址开销，批量填充效率略低于 vector ，但远高于 list 。 list 的批量填充需要为每个节点单独申请内存，伴随多次内存分配与释放，同时离散的节点无法利用 CPU 缓存优化，批量操作的效率最低。

如何选择

• 优先选择 vector ：你的场景需要高频随机访问元素、仅在尾部增删数据、数据量相对固定，或是需要兼容 C 语言接口传递连续内存数组，比如静态配置数据的存储与查询、固定格式的批量数据处理。
• 优先选择 deque ：你的场景需要频繁在容器头部与尾部双向增删元素、元素数量未知需要频繁扩容，或是需要长期保存元素的指针与引用不失效，比如网络数据流的环形缓冲区、银行叫号这类排队系统。
• 优先选择 list ：你的场景需要频繁在容器任意位置增删元素、存储拷贝与构造代价极高的大对象，或是需要频繁合并、拆分、反转序列，比如实时更新的游戏玩家排行榜、大对象的动态生命周期管理。

deque 与 list 都擅长高效的元素增删，但两者的适用场景有明确分界： deque 保留了随机访问能力，空间利用率更高，适合双端频繁增删、偶尔需要随机访问的场景； list 的优势在于任意位置增删均为 O(1)，但完全放弃了随机访问能力，内存开销更大，仅适合全位置频繁增删、无需随机访问的场景。