代码仓库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）。简化版节点结构如下：

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

容器主控结构

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

1
2
3
4
5
6
7
8
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接口高度兼容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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()（反向迭代器）
1
2
3
4
5
6
7
8
9
10
11
12
13
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)：初始化列表填充
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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指定位置，不复制元素，仅修改节点指针，无任何迭代器/引用失效，指向转移元素的迭代器依然有效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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仅对有序链表生效，无序链表合并后无排序效果。

1
2
3
4
5
6
7
8
9
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中连续重复的元素，仅保留一个，使用前需先排序，否则无法去除非连续重复项。

1
2
3
4
5
6
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容器，适合行、列数据都需要频繁增删，且每行元素数量不固定的不规则多维数据场景，比如动态层级的分类数据、不规则的矩阵结构，无需移动大量数据即可完成行、列的插入与删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 复用之前定义的通用打印函数
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的高效增删优势，适合行数量相对固定、需要快速定位到某一行，同时行内元素需要频繁增删的场景，比如多任务调度队列、多频道的消息缓存，每个队列/频道的消息需要频繁插入删除，同时需要快速定位到指定队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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)随机访问与高效遍历，适合行数量不固定、需要频繁增删整行数据，同时行内元素需要高频随机访问的场景，比如动态增减的表格数据、多组批量统计数据，整行数据频繁新增或移除，每行内的元素需要快速查询与遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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)，但完全放弃了随机访问能力，内存开销更大，仅适合全位置频繁增删、无需随机访问的场景。