C++STL详解

C++STL详解

pdf版本下载链接

前言

用c++打算法比赛，STL是必须学习的，但是STL的内容还是很多的，因此有必要整理一下常用的STL函数和容器。

首先要先了解一下迭代器。迭代器的本质是一个行为类似指针的对象，可以简单理解为是一个通用型的指针。

迭代器通用语法：begin()（首元素）、end()（尾后位置，切记这个是没有元素存储的）、*it（解引用）、++it（遍历）是所有迭代器的基础操作。

还有c++中的区间，一般是遵循左闭右开的规则。

STL常用函数

sort

sortc++提供的一个排序函数，目的是对一个序列进行排序，无论是支持随机访问迭代器的STL容器还是数组都可以使用，其复杂度为 O ( N l o g ( N ) ) O(Nlog(N)) O(Nlog(N))

1. sort(begin,end,cmp)//第一个参数为指针的起始位置，第二个参数为指针的结束位置，第三个参数为比较规则可以不写
3. vector<int>a(100,0);
4. sort(a.begin(),a.end());//对vector容器按照从小到大排序
5. sort(a.begin(),a.end(),greater<int>());//对vector容器按照从大到小排序
6. sort(a.rbegin(), a.rend()); // 使用反向迭代器对vector容器按照从大到小排序
8. int b[100]={1,324,43,3,43,32443,432,324};
9. sort(b,b+100);//对数组按照从小到大排序
10. sort(b,b+100，greater<int>());//对数组按照从大到小排序
12. /*针对自定义排序的方法需要注意，自定义排序规则中的比较函数参数最好写成引用形式。
13. 非引用形式会进行参数拷贝，导致额外的时间性能损耗。参数为引用形式会避免这一点。*/
14. bool cmp(int &a,int &b){
15. return a>b;
16. }
17. sort(b,b+100,cmp);//使用自定义函数去进行排序

复制代码

stable_sort

stable_sort顾名思义这是一个稳定排序，其内部采用归并排序，与sort不同的是其可以保留相等元素的原始相对顺序，时间复杂度为 O ( N l o g ( N ) ) O(Nlog(N)) O(Nlog(N))，具体用法同sort。

lower_bound

lower_bound用于进行二分查找，找到有序数组里面的第一个大于等于x的元素，并返回该元素的地址。

1. lower_bound(begin,end,x,cmp);//在begin到end的范围内查找第一个大于等于x的元素的地址,可以按照cmp来定义排序规则
2. int a[100]={0};
3. lower_bound(a,a+n,x);

复制代码

upper_bound

lower_bound用于进行二分查找，找到有序数组里面的第一个大于x的元素，并返回该元素的地址。

1. upper_bound(begin,end,x,cmp)//在begin到end的范围内查找第一个大于x的元素的地址,可以按照cmp来定义排序规则
2. int a[100]={0};
3. upper_bound(a,a+n,x);

复制代码

find

find用于查找特定的值。

1. find(begin,end,v);//在[begin,end)里面查找到第一个等于v的元素,然后返回其迭代器,没有找到返回end
3. std::vector<int> v = {10, 20, 30, 40, 50};
5. auto it = std::find(v.begin(), v.end(), 30);//it=v.begin()+2

复制代码

max

max用于找到两个元素中的最大值。

1. max(a,b,cmp);//用于找到a和b两个数直接的最大值，cmp参数可选
2. int ma=max(1,2);//ma=2;
3. ma=max({1,2,3,4,5,6});//ma=6,这个是c++11及以上版本支持的

复制代码

min

min用于找到两个元素中的最小值，用法同max。

minmax

返回一个 pair 类型，第一个元素是 min(a, b) ， 第二个元素是 max(a, b)

1. pair<int,int> t=minmax(2,1);//t={1,2}
2. t=minmax({1,2,3,5,3,0});//t={0,5}

复制代码

max_element

max_element用于找到一定范围内的最大值的地址，时间复杂度为 O ( N ) O(N) O(N)。

1. max_element(begin,end,cmp);//在[begin,end)范围内寻找到最大值
2. int a[100];
3. int ma=*max_element(a,a+100);

复制代码

min_element

min_element用于找到一定范围内的最小值的地址，用法同max_element时间复杂度为 O ( N ) O(N) O(N)。

minmax_element

minmax_element用于找到一定范围内的最大和最小值的地址，用法同max_element时间复杂度为 O ( N ) O(N) O(N)。

nth_element

nth_element找到区间中第 n 小的元素并放到指定位置，同时保证该位置左侧元素≤它、右侧元素≥它。

1. nth_element(begin,nth,end,cmp);//[begin,end)为查找范围，nth要寻找的数的存放位置
3. vector<int> v = {9, 3, 7, 1, 8, 2, 5}; // 原始区间
4. int n = 3; // 找第3小的元素（索引3，从0开始）
6. // 执行nth_element：把第3小的元素放到v.begin()+3位置
7. nth_element(v.begin(), v.begin() + n, v.end());
9. for (int x : v) cout << x << " "; // 示例输出：3 1 2 5 8 7 9（左侧≤5，右侧≥5）

复制代码

accumulate

accumulate用于累加区间内的所有元素，时间复杂度为 O ( N ) O(N) O(N)。

1. accumulate(begin,end,init,op);//计算逻辑是init + *begin + *(begin+1) + ... + *(end-1),op可选为自定义二元操作
3. vector<int> v = {1,2,3,4,5};
4. int sum1 = accumulate(v.begin(), v.end(), 0);// 初始值0，累加1+2+3+4+5=15
6. int sum2 = accumulate(v.begin(), v.end(), 1, [](int a, int b) {return a*b;});//计算1*1*2*3*4*5=120

复制代码

reverse

reverse函数是对序列进行翻转，时间复杂度为 O ( N ) O(N) O(N)。

1. reverse(begin,end);\\第一个参数为指针的起始位置，第二个为指针的结束位置
3. string s="abc";
4. reverse(s.begin(),s.end());\\对字符串s进行翻转，s变成"cba"
6. int a[]={1,2,3,4};
7. reverse(a,a+3);\\对数组下标为[0,3)的元素进行翻转，a变成{3,2,1,4}

复制代码

__gcd

**__gcd**函数是用来求最大公约数的，但是前面两个__在新标准中(c++17及以上)可以去掉，直接用gcd，但是为了保险起见还是加上比较好。

1. __gcd(a,b);//参数为两个整数
2. int num=__gcd(12,15);//结果为3
3. num=__gcd(0,21);//结果为21

复制代码

__lcm

__lcm函数是用来求最小公倍数的，这个用法与__gcd是一样的。

1. int num=__lcm(12,18);//结果为36

复制代码

set_union

set_union是用来求两个有序集合的并集，注意这两个集合一定是要有序的。复杂度为 O ( N + M ) O(N+M) O(N+M)。

1. set_union(abegin,aend,bbegin,bend,outbegin,cmp);//前两个为第一个集合的范围，再后面两个是另一个集合的范围，第五个参数为输出位置的迭代器，第六个参数可选，是用来定义比较规则的
3. set<int> s1 = {1, 2, 3, 4};
4. set<int> s2 = {3, 4, 5, 6};
5. vector<int> res;
7. // 直接传入set的迭代器（天然有序），用back_inserter自动扩容
8. set_union(s1.begin(), s1.end(),s2.begin(), s2.end(),back_inserter(res)); // 无需提前预留空间，更便捷，res={1，2，3，4，5，6}

复制代码

set_intersection

set_intersection是用来求两个集合的交集，用法同set_union。

set_difference

set_difference是用来求两个集合的差集，用法同set_union。

stoi

atoi将字符串转成int类型。

1. stoi(s);//s为字符串
2. string s="123";
3. int a=stoi(s);//a=123

复制代码

stoll

stoll将字符串转成long long类型。

stof

stof将字符串转成float类型。

stod

stod将字符串转成double类型。

to_string

to_string将数字转换成字符串。

transform

transform用于进行区间转换。

1. transform(ibegin,iend,obegin,oend,op);//第四个参数可以没有，但是其他四个参数一定要有，op为一元自定义操作
3. vector<int> v1 = {1,2,3,4,5};
4. vector<int> res1(v1.size()); // 输出容器需提前分配空间
5. transform(v1.begin(), v1.end(), res1.begin(),
6. [](int x) { return x * x; });
8. transform(begin, end, obegin, ::tolower);//将[begin,end)里面的字母全部变成小写
9. transform(begin, end, obegin, ::toupper);//将[begin,end)里面的字母全部变成大写

复制代码

unique

unique用于移除有序区间内的连续重复元素，返回值是消除完重复元素的下一个位置的地址。

注意：该算法仅对连续重复元素生效，且不会真正删除元素，仅通过覆盖实现去重效果.

通用去重三步法：排序（sort）→ 去重（unique）→ 删除无效元素（erase)

1. unique(begin,end,cmp);//第三个是排序规则，可以不写
3. vector<int> v = {2, 1, 3, 2, 2, 4, 3, 4, 4}; // 无序，存在非连续重复
4. // 步骤1：排序，让所有重复元素连续（关键前提）
5. sort(v.begin(), v.end()); // 排序后：v={1,2,2,2,3,3,4,4,4}
6. // 步骤2：unique去重，获取去重后结束迭代器
7. auto new_last = unique(v.begin(), v.end());//此步执行过后v={1,2,3,4,3,3,4,4,4}
8. // 步骤3：删除尾部无效元素（真正减少容器长度）
9. v.erase(new_last, v.end());//v={1,2,3,4}

复制代码

count

count函数用于统计一定范围内等于v的值的个数。

1. count(begin,end,v);//统计[begin,end)内等于v的值的个数
3. vector<int> v = {2, 1, 3, 2, 2, 4, 3, 4, 4};
4. int num = count(v.begin(), v.end(), 2);//num=3

复制代码

count_if

count_if与count的区别在与其第三个参数为一个bool类型的比较函数，可以自定义比较规则。

1. count_if(begin,end,cmp);//统计[begin,end)内符合cmp的值的个数
3. vector<int> v = {2, 1, 3, 2, 2, 4, 3, 4, 4};
4. int num = count_if(v.begin(), v.end(), [&target](int x) {
5. return x == target; // cmp规则：x等于v
6. });//num=3

复制代码

fill

fill用来对一定范围的值进行初始化。

1. fill(begin,end,v);//将[begin,end)内的值变成v。
2. int a[100];
3. fill(a,a+100,1);//将a数组所有值赋1

复制代码

is_sorted

is_sorted用于判断在一定范围内这个序列是否有序。

1. is_sorted(begin,end);//有序会返回真，无序就返回假
2. int a[]={1,2,3,4};
3. bool flag=is_sorted(a,a+4);//flag=true

复制代码

iota

iota用于让序列递增赋值。

1. iota(begin,end,init);//init为起始值
2. vector<int> v(5);
3. iota(v.begin(), v.end(), 0); // 填充：0,1,2,3,4
4. iota(v.begin(), v.end(), 5); // 填充：5,6,7,8,9

复制代码

generate

generate可以自己去写生成规则，而iota只支持+1递增。

1. generate(begin,end,gen);//gen为自己写的生成规则，返回值为要生成的元素类型。
3. vector<int> v(5);
5. // 场景1：生成固定值（所有元素赋值为10）
6. generate(v.begin(), v.end(), []() { return 10; });
7. cout << "生成固定值10：";
8. for (int x : v) cout << x << " "; // 输出：10 10 10 10 10
9. cout << endl;
11. // 场景2：生成递增值（替代iota，支持任意步长）
12. int val = 0; // 外部变量，通过引用捕获到lambda中
13. generate(v.begin(), v.end(), [&val]() {
14. int res = val;
15. val += 2; // 步长2，而非iota的固定+1
16. return res;
17. });
18. cout << "步长2递增（0,2,4,6,8）：";
19. for (int x : v) cout << x << " "; // 输出：0 2 4 6 8
20. cout << endl;
22. // 场景3：生成随机值（0~99的随机整数）
23. random_device rd;
24. mt19937 rng(rd());
25. uniform_int_distribution<int> dist(0, 99);
26. generate(v.begin(), v.end(), [&]() { return dist(rng); });
27. cout << "生成0~99随机值：";
28. for (int x : v) cout << x << " "; // 输出：随机数（如 45 12 88 3 77）
29. cout << endl;
31. // 场景4：generate_n版（生成前3个元素为99）
32. vector<int> v2(5);
33. generate_n(v2.begin(), 3, []() { return 99; });
34. cout << "generate_n生成前3个元素为99：";
35. for (int x : v2) cout << x << " "; // 输出：99 99 99 0 0
36. cout << endl;

复制代码

next_permutation

next_permutation用于将当前区间的元素重排为字典序中的下一个更大排列并返回是否成功生成（若已是最后一个排列，返回 false，且会将区间重排为字典序最小的排列）

1. next_permutation(begin,end,cmp);//将[begin,end)范围内的数进行重排，cmp可选
3. vector<int> v = {1, 2, 3};
5. // ========== 场景1：升序字典序生成所有排列 ==========
6. // 第一步：排序为升序最小排列（1,2,3）—— 必须！
7. sort(v.begin(), v.end());
8. cout << "升序字典序的所有排列：" << endl;
9. int count = 0;
10. do {
11. // 输出当前排列
12. for (int x : v) cout << x << " ";
13. cout << endl;
14. count++;
15. } while (next_permutation(v.begin(), v.end())); // 默认升序规则
16. cout << "升序排列总数：" << count << endl << endl; // 输出6
18. // ========== 场景2：降序字典序生成所有排列 ==========
19. // 第一步：排序为降序最小排列（3,2,1）—— 必须！
20. sort(v.begin(), v.end(), greater<int>());
21. cout << "降序字典序的所有排列：" << endl;
22. do {
23. // 输出当前排列
24. for (int x : v) cout << x << " ";
25. cout << endl;
26. } while (next_permutation(v.begin(), v.end(), greater<int>())); // 自定义降序规则
27. cout << "降序排列总数：6" << endl;

复制代码

prev_permutation

prev_permutation用于将当前区间的元素重排为字典序中的上一个更小排列并返回是否成功生成（若已是最后一个排列，返回 false，且会将区间重排为字典序最大的排列），功能与next_permutation函数是相反的，用法相同。

__lg

__lg用于计算一个无符号整数的最高有效位（MSB）的位置，等价于求 floor(log2(x))。

1. __lg(x);//如果x是有符号数，传入有符号数会被隐式转为无符号数，负数结果无意义
2. unsigned int a = 1;
3. unsigned int b = 3;
4. unsigned int c = 8;
5. unsigned long long d = 64;
7. cout << "__lg(1) = " << __lg(a) << endl; // 输出：0
8. cout << "__lg(3) = " << __lg(b) << endl; // 输出：1
9. cout << "__lg(8) = " << __lg(c) << endl; // 输出：2
10. cout << "__lg(64) = " << __lg(d) << endl; // 输出：6（64=2^6）

复制代码

C++20 ranges

ranges主要用来简化迭代器操作，可以少写很多迭代器操作相关的代码。
ranges集成了很多STL函数

1. vector v={1, 2, 3, 4, 7, 6, 5};
2. ranges::sort(v); //这个等价于sort(v.begin(), v.end());
3. ranges::sort(v, greater<int>()); //这个等价于sort(v.begin(), v.end(), greater<int>());
4. int mx = *ranges::max_element(v);//等价于max_element(v.begin(),v.end);
5. int mn = *ranges::min_element(v);//等价于min_element(v.begin(),v.end);

复制代码

pair

pair 是 C++ STL 中轻量的二元组容器，用于封装一对任意类型的值，头文件为 （使用其他 STL 容器时会被间接包含，比赛中可省略显式引入）。pair 结构简单、操作高效，所有访问和修改操作均为 O(1)，是算法比赛中高频使用的工具，常用于存储键值对、坐标点、数对等场景，也可作为 map/set/unordered_map 的键、vector 的元素实现复杂数据的存储。

一、pair 核心特性

1. 二元存储：固定存储两个值，分别通过 first（第一个值）和**second**（第二个值）访问，两个值的类型可任意指定（可相同 / 不同，如pair、pair>）；
2. 轻量高效：无多余内存开销，底层仅为两个成员变量，所有访问、修改、交换操作均为 O(1)；
3. 默认比较规则：支持直接使用==/!=/<>/<=/>=比较，默认先比较first，first相等时再比较second，可直接用于排序、放入set/map等有序容器；
4. 可嵌套：支持 pair 嵌套（如pair>），用于存储三维数据或多层键值对，比赛中常用于存储「节点 + 权值 + 坐标」等复合信息；
5. 可作为容器元素 / 键：可直接作为vector/stack/queue的元素，也可作为set/map的键（需满足有序性，默认比较规则可直接使用）；
6. 无成员函数：pair 无复杂的成员函数，仅提供基础的构造、交换操作，核心操作通过直接访问first/second实现。

二、pair 初始化

pair 的模板格式为 pair，其中T1为第一个值的类型，T2为第二个值的类型，初始化方式灵活，比赛中以列表初始化和 make_pair 为核心。

1. 空初始化

默认调用两个类型的默认构造函数，仅适用于基础类型（默认初始化为 0）或有默认构造的自定义类型。

1. // 初始化int-int的pair，first=0，second=0
2. pair<int, int> p1;
3. // 初始化int-string的pair，first=0，second=""（空字符串）
4. pair<int, string> p2;

复制代码

2. 直接构造初始化

显式指定first和second的初始值，按顺序赋值。

1. // first=1，second=2
2. pair<int, int> p1(1, 2);
3. // first=10，second="abc"
4. pair<int, string> p2(10, "abc");
5. // 嵌套pair：first=1，second为pair(2,3)
6. pair<int, pair<int, int>> p3(1, pair<int, int>(2, 3));

复制代码

3. 列表初始化（C++11+）

简化写法，用{}替代括号，更简洁，支持嵌套。

1. // first=1，second=2（推荐，代码更简洁）
2. pair<int, int> p1{1, 2};
3. pair<int, int> p2 = {1, 2};
4. // 嵌套pair：first=1，second={2,3}
5. pair<int, pair<int, int>> p3 = {1, {2, 3}};
6. // 作为vector元素的列表初始化（比赛高频）
7. vector<pair<int, int>> vec = {{1,2}, {3,4}, {5,6}};

复制代码

4. 拷贝初始化

通过已有的 pair 对象拷贝生成新的 pair，类型需一致。

1. pair<int, int> p1 = {1, 2};
2. // 拷贝p1，p2={1,2}
3. pair<int, int> p2(p1);
4. pair<int, int> p3 = p1;

复制代码

5. make_pair 函数初始化

通过make_pair(T1, T2)自动推导类型，无需显式写pair，简化代码，是比赛中最常用的初始化方式。

1. // 自动推导为pair<int, int>，p1={1,2}
2. auto p1 = make_pair(1, 2);
3. // 自动推导为pair<int, string>，p2={10, "abc"}
4. auto p2 = make_pair(10, "abc");
5. // 嵌套pair，自动推导类型
6. auto p3 = make_pair(1, make_pair(2, 3));
7. // 结合容器使用（比赛高频）
8. vector<pair<int, int>> vec;
9. vec.push_back(make_pair(1, 2));
10. vec.emplace_back(make_pair(3, 4));

复制代码

三、pair 常用操作

pair 无专用的成员函数，核心操作围绕 **first/second的访问与修改 **、比较运算、交换展开，所有操作均为 O(1) 时间复杂度。

1. 访问成员：first & second

通过.直接访问first（第一个值）和second（第二个值），支持直接读写，是 pair 最核心的操作。

1. pair<int, int> p = {1, 2};
2. cout << p.first; // 访问第一个值，输出1
3. cout << p.second; // 访问第二个值，输出2
5. p.first = 10; // 修改第一个值为10
6. p.second = 20; // 修改第二个值为20
7. cout << p.first << " " << p.second; // 输出10 20
9. // 嵌套pair的访问：需逐层解引用
10. pair<int, pair<int, int>> pn = {1, {2, 3}};
11. cout << pn.first; // 输出1
12. cout << pn.second.first; // 输出2
13. cout << pn.second.second; // 输出3
14. pn.second.first = 20; // 修改嵌套pair的first值

复制代码

2. 比较运算

pair 重载了== != < > <= >=所有比较运算符，默认比较规则为：先比 first，first 相等时再比 second，无需自定义即可用于排序、有序容器的键值比较，是比赛中高频特性。

1. pair<int, int> p1 = {1, 3}, p2 = {2, 2}, p3 = {1, 2};
2. // 比较规则演示
3. cout << (p1 < p2); // true（1<2，无需比较second）
4. cout << (p1 > p3); // true（p1.first=p3.first，3>2）
5. cout << (p1 == p3); // false（second不相等）
6. cout << (p1 != p2); // true
8. // 直接对vector<pair>排序（按默认规则：first升序，再second升序）
9. vector<pair<int, int>> vec = {{3,1}, {1,3}, {1,2}};
10. sort(vec.begin(), vec.end());
11. // 排序后：{1,2}, {1,3}, {3,1}
12. for (auto& p : vec) cout << p.first << ":" << p.second << " ";

复制代码

3. 自定义排序规则

比赛中若需按second 优先或降序排序，可通过 lambda 表达式自定义 sort 的比较规则，灵活控制 pair 的排序逻辑。

1. vector<pair<int, int>> vec = {{3,1}, {1,3}, {1,2}};
2. // 规则1：按second升序，second相等按first降序
3. sort(vec.begin(), vec.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
4. if (a.second != b.second) return a.second < b.second;
5. return a.first > b.first;
6. });
7. // 结果：{3,1}, {1,2}, {1,3}
9. // 规则2：按first降序，无视second
10. sort(vec.begin(), vec.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
11. return a.first > b.first;
12. });
13. // 结果：{3,1}, {1,3}, {1,2}

复制代码

4. swap 交换

pair 提供swap成员函数，用于交换两个 pair 的first 和 second，要求两个 pair 的类型完全一致；也可使用 STL 的全局swap函数，效果相同。

1. pair<int, int> p1 = {1,2}, p2 = {3,4};
2. // 方式1：成员函数swap
3. p1.swap(p2);
4. // 方式2：全局swap函数（比赛更常用，更简洁）
5. swap(p1, p2);
6. // 交换后p1={3,4}，p2={1,2}

复制代码

5. 作为容器的键 / 元素

（1）作为 vector/queue 等容器的元素

比赛中最常用，用于存储坐标 (x,y)、数对 (值，下标)、** 节点 (点，权值)** 等，结合 sort 可实现灵活排序。

1. // 存储二维坐标
2. vector<pair<int, int>> pos;
3. pos.push_back({0,0}); // 原点
4. pos.push_back({1,2}); // 点(1,2)
5. // 存储数组值与原下标（比赛中排序后保留原下标常用）
6. vector<int> nums = {3,1,2};
7. vector<pair<int, int>> val_idx;
8. for (int i = 0; i < nums.size(); i++) {
9. val_idx.emplace_back(nums[i], i); // {值，原下标}
10. }
11. sort(val_idx.begin(), val_idx.end()); // 按值升序，再下标升序

复制代码

（2）作为 set/map 的键

pair 的默认比较规则满足严格弱序，可直接作为set/map的键，用于存储唯一数对、键值对映射。

1. // set<pair>：存储唯一的坐标对，自动按默认规则排序
2. set<pair<int, int>> st;
3. st.insert({1,2});
4. st.insert({1,2}); // 重复，插入失败
5. st.insert({2,1});
6. // 遍历结果：{1,2}, {2,1}
8. // map<pair<int, int>, int>：键为坐标，值为该坐标的权值/次数
9. map<pair<int, int>, int> mp;
10. mp[{1,2}] = 10;
11. mp[{2,1}] = 20;
12. cout << mp[{1,2}]; // 输出10

复制代码

注意：unordered_map的键不支持默认的 pair（无默认哈希函数），若需将 pair 作为unordered_map的键，需自定义哈希函数（比赛中极少用，优先用map, T3>）。

array

array 是 C++11 新增的 STL 固定大小数组容器，头文件为 ，核心特性是「编译期固定大小、连续内存存储、随机访问高效、类型安全且兼容原生数组」。与原生数组（int a[5]）相比，array 保留了原生数组的高性能，同时补充了安全的边界检查、便捷的成员函数（如size()/swap()）；与 vector 相比，array 无动态扩容开销、栈分配更高效，但大小不可修改。算法比赛中常用于「已知固定大小的数组场景」（如固定维度的矩阵、有限长度的缓存），是原生数组的安全替代方案。

一、array 核心特性

1. 编译期固定大小：大小是模板参数（array），编译时确定且不可修改，无扩容 / 缩容操作，内存分配在栈上（默认），效率远高于堆分配的 vector；
2. 连续内存存储：与原生数组一样，元素在内存中连续排布，支持随机访问（[]/at()），时间复杂度 O(1)；
3. 类型安全与边界检查：at() 函数会做越界检查，抛出out_of_range异常；[] 不检查（与原生数组一致），比原生数组更安全；
4. 兼容原生数组：可通过data()获取底层原生数组指针，支持传递给需要原生数组的函数（如 C 风格 API）；
5. 轻量无开销：无额外内存开销（仅存储元素），大小等于sizeof(T) * N，与原生数组完全一致；
6. 完整的迭代器支持：提供随机访问迭代器（支持++it/it+n/it[]等），可直接使用所有 STL 算法（如sort/find/reverse）；
7. 无默认构造空数组：必须显式指定大小（如array），无法像 vector 一样定义空数组后动态扩容。

二、array 初始化

array 的模板格式为 array，其中T是元素类型，N是编译期常量（必须是常量表达式，如5/const int n=5，不可用变量），初始化方式灵活且兼容原生数组。

1. 固定大小初始化（最基础）

指定大小和元素类型，未显式赋值时，基础类型默认初始化为 0，自定义类型调用默认构造。

1. // 初始化大小为5的int型array，所有元素默认初始化为0
2. array<int, 5> arr1;
3. // 初始化大小为3的string型array，所有元素默认初始化为空字符串
4. array<string, 3> arr2;

复制代码

2. 列表初始化（C++11+）

用{}直接赋值，元素个数不能超过 array 的大小，不足时剩余元素默认初始化。

1. // 大小为5，前3个元素赋值，后2个默认0 → {1,2,3,0,0}
2. array<int, 5> arr1 = {1, 2, 3};
3. // 大小为3，完全赋值 → {10,20,30}
4. array<int, 3> arr2 = {10, 20, 30};
5. // C++17+简化写法（类模板参数推导），自动推导大小为3
6. array arr3 = {1, 2, 3}; // 等价于array<int,3> arr3 = {1,2,3}

复制代码

3. 拷贝初始化

通过已有的 array 拷贝生成新 array，要求类型和大小完全一致。

1. array<int, 3> arr1 = {1,2,3};
2. // 拷贝arr1，arr2 = {1,2,3}
3. array<int, 3> arr2(arr1);
4. array<int, 3> arr3 = arr1;

复制代码

4. 聚合初始化

支持原生数组的聚合初始化方式，代码更简洁。

1. // 等价于array<int,4> arr = {1,2,3,4}
2. array<int,4> arr{1,2,3,4};

复制代码

注意：大小必须是编译期常量

array 的大小N必须是常量表达式，不可用运行时变量，否则编译报错。

1. int n = 5;
2. // 错误：n是运行时变量，array大小必须编译期确定
3. // array<int, n> arr;
5. const int m = 5;
6. // 正确：m是编译期常量
7. array<int, m> arr;

复制代码

三、常用函数

array 的函数围绕「固定大小数组的安全访问、基础操作」展开，所有函数时间复杂度均为 O(1)（除fill/swap为 O(N)），核心与 vector 的基础函数一致，无动态扩容相关函数。

（一）元素访问

[] 运算符

与原生数组一致，直接按索引访问元素，支持读写，无越界检查（越界行为未定义，可能崩溃）。

1. arr[index] // 访问索引index的元素，支持读写
2. array<int, 3> arr = {1,2,3};
3. cout << arr[0]; // 输出1
4. arr[1] = 20; // 修改索引1的元素为20，arr变为{1,20,3}
5. // arr[5] = 5; // 越界，无检查，可能导致程序崩溃

复制代码

at

按索引访问元素，越界时抛出out_of_range异常，比[]更安全，比赛中少用（需捕获异常），但调试时推荐使用。

1. at(index) // 访问索引index的元素，支持读写，越界抛异常
2. array<int, 3> arr = {1,2,3};
3. arr.at(1) = 20; // 修改为20，正常
4. // arr.at(5); // 越界，抛出out_of_range异常

复制代码

front /back

快速访问第一个 / 最后一个元素，支持读写，调用前无需判空（array 大小固定，非空时可用，空 array 编译期就会报错）。

1. front() // 返回第一个元素的引用
2. back() // 返回最后一个元素的引用
3. array<int, 3> arr = {1,2,3};
4. cout << arr.front(); // 输出1
5. cout << arr.back(); // 输出3
6. arr.front() = 10; // 修改首元素为10，arr变为{10,2,3}
7. arr.back() = 30; // 修改尾元素为30，arr变为{10,2,30}

复制代码

data

返回指向 array 底层原生数组的指针，可用于兼容 C 风格函数（如memcpy/printf）。

1. data() // 返回T*类型的指针，指向第一个元素
2. array<int, 3> arr = {1,2,3};
3. int* p = arr.data();
4. cout << *(p+1); // 输出2（等价于arr[1]）
5. // 传递给C风格函数
6. printf("%d", p[0]); // 输出10

复制代码

（二）容量与判断

size / max_size

size()返回 array 的元素个数（等于模板参数 N），max_size()返回最大可容纳元素数（与 size () 一致，因 array 大小固定），均为 O(1)。

1. size() // 返回元素个数（N）
2. max_size() // 返回最大元素数（N）
3. array<int, 5> arr;
4. cout << arr.size(); // 输出5
5. cout << arr.max_size(); // 输出5

复制代码

empty

判断 array 是否为空（仅当 N=0 时返回 true），比赛中极少用（array 大小固定，N=0 无实际意义）。

1. empty() // 空返回true，否则false
2. array<int, 0> arr_empty;
3. cout << arr_empty.empty(); // 输出true
4. array<int, 3> arr;
5. cout << arr.empty(); // 输出false

复制代码

（三）操作函数

fill（填充所有元素）

将 array 的所有元素赋值为指定值，时间复杂度 O(N)，比赛中常用于快速初始化数组。

1. fill(val) // 将所有元素设为val
2. array<int, 5> arr;
3. arr.fill(10); // 所有元素变为10 → {10,10,10,10,10}

复制代码

swap（交换两个 array）

交换两个类型和大小完全一致的 array 的所有元素，时间复杂度 O(N)（元素逐一遍历交换）。

1. swap(arr) // 交换当前array与arr的内容
2. array<int, 3> arr1 = {1,2,3}, arr2 = {4,5,6};
3. arr1.swap(arr2);
4. cout << arr1[0]; // 输出4
5. cout << arr2[0]; // 输出1

复制代码

（四）迭代器（随机访问迭代器，支持所有 STL 算法）

array 提供随机访问迭代器，支持++it/--it/it+n/it[]等操作，可直接使用所有 STL 算法（如sort/reverse/find）。

1. begin() // 指向第一个元素的随机访问迭代器
2. end() // 指向最后一个元素下一个位置的迭代器
3. rbegin() // 指向最后一个元素的反向迭代器
4. rend() // 指向第一个元素前一个位置的反向迭代器
5. cbegin()/cend() // 常量迭代器（不可修改元素）
7. // 正向遍历（随机访问迭代器支持it+2）
8. array<int, 5> arr = {3,1,4,1,5};
9. for (auto it = arr.begin(); it != arr.end(); ++it) {
10. cout << *it << " "; // 输出3 1 4 1 5
11. }
12. // 反向遍历
13. for (auto it = arr.rbegin(); it != arr.rend(); ++it) {
14. cout << *it << " "; // 输出5 1 4 1 3
15. }
16. // 范围for遍历（推荐，简洁）
17. for (int x : arr) cout << x << " ";
19. // 使用STL算法排序（随机访问迭代器支持全局sort）
20. sort(arr.begin(), arr.end()); // 升序 → {1,1,3,4,5}
21. reverse(arr.begin(), arr.end()); // 反转 → {5,4,3,1,1}

复制代码

tuple

tuple 是 C++ STL 中通用的多元组容器（头文件 ），是 pair 的超集 ——pair 仅能存储 2 个元素，而 tuple 可存储任意数量（≥0）、任意类型的元素，核心特性是「编译期固定类型和长度、轻量无开销、支持默认 / 自定义比较、可嵌套」。tuple 访问效率为 O(1)，算法比赛中常用于「存储多维度数据（如三元组、四元组）」「函数返回多个值」「替代简单自定义结构体」，是处理复合数据的轻量化工具。

一、tuple 核心特性

1. 多元素存储：支持 0 个或多个元素，每个元素类型可不同（如 tuple 存储 int、字符串、浮点数），pair 本质是「2 元素的 tuple」；
2. 编译期固定属性：元素的类型和数量在定义时确定，运行时不可修改（无扩容 / 缩容，无增删元素操作）；
3. 轻量高效：底层仅存储元素本身，无额外内存开销，元素访问、比较、交换均为 O(1)（除解包 / 拷贝外）；
4. 默认比较规则：支持 ==/!=/<>/<=/>= 所有比较运算符，按元素顺序逐一比较（先比第一个元素，相等则比第二个，依此类推）；
5. 可嵌套：支持 tuple 嵌套（如 tuple>），用于存储超过 3 维的复合数据；
6. 无命名成员：无法像结构体 /pair 那样通过 first/second 访问元素，需通过 get<索引>(tuple) 访问（索引是编译期常量）；
7. 兼容 STL 算法：可作为 vector/set/map 等容器的元素，结合 sort 等算法使用（依赖比较规则）；
8. 支持解包：通过 tie()（C++11+）或「结构化绑定」（C++17+）可将 tuple 元素解包为独立变量，简化代码。

二、tuple 初始化

tuple 的模板格式为 tuple（Tn 为第 n 个元素的类型），初始化方式灵活，比赛中以 make_tuple 和列表初始化为主。

1. 空初始化

仅定义空 tuple（无元素），无实际业务价值：

1. // 空tuple，无元素
2. tuple<> t_empty;

复制代码

2. 直接构造初始化

显式指定元素类型和初始值，按顺序赋值：

1. // 3元素tuple：int=1，string="abc"，double=3.14
2. tuple<int, string, double> t1(1, "abc", 3.14);
3. // 2元素tuple（等价于pair<int, int>）
4. tuple<int, int> t2(10, 20);
5. // 嵌套tuple：第一个元素int=1，第二个元素是tuple<string, double>
6. tuple<int, tuple<string, double>> t3(1, tuple<string, double>("def", 6.28));

复制代码

3. 列表初始化（C++11+）

用 {} 替代括号初始化，语法更简洁，支持嵌套：

1. // 3元素tuple：{1, "abc", 3.14}
2. tuple<int, string, double> t1 = {1, "abc", 3.14};
3. // 嵌套tuple：{1, {"def", 6.28}}
4. tuple<int, tuple<string, double>> t2 = {1, {"def", 6.28}};

复制代码

4. make_tuple 初始化

通过 make_tuple(值1, 值2, ...) 自动推导元素类型，无需显式写 tuple，是比赛中最常用的初始化方式。

1. // 自动推导为 tuple<int, string, double>
2. auto t1 = make_tuple(1, "abc", 3.14);
3. // 自动推导为嵌套tuple：tuple<int, tuple<string, double>>
4. auto t2 = make_tuple(1, make_tuple("def", 6.28));
5. // 作为vector元素（存储多维度数据，比赛高频）
6. vector<tuple<int, string, int>> vec;
7. vec.push_back(make_tuple(1, "a", 10));
8. vec.emplace_back(2, "b", 20); // 等价于push_back(make_tuple(...))

复制代码

5. 拷贝初始化

通过已有的 tuple 拷贝生成新 tuple，要求元素类型和数量完全一致。

1. auto t1 = make_tuple(1, "abc", 3.14);
2. // 拷贝t1，t2与t1类型、值均相同
3. tuple<int, string, double> t2(t1);
4. auto t3 = t1; // 自动推导类型，更简洁

复制代码

三、tuple 常用操作

tuple 无复杂成员函数，核心操作围绕「元素访问」「比较运算」「解包」「交换」展开，所有操作时间复杂度均为 O(1)（解包 / 拷贝除外）。

1. 元素访问：get(t)（核心）

通过 get<索引>(tuple) 访问 / 修改元素，索引 N 必须是编译期常量（如 0/1/2，不可用变量），支持读写。

1. get<N>(t) // 访问tuple t的第N个元素（从0开始），返回引用
2. auto t = make_tuple(1, "abc", 3.14);
3. // 访问第0个元素（int），输出1
4. cout << get<0>(t);
5. // 访问第1个元素（string），输出abc
6. cout << get<1>(t);
7. // 访问第2个元素（double），输出3.14
8. cout << get<2>(t);
10. // 修改元素值
11. get<0>(t) = 10; // 第0个元素变为10
12. get<2>(t) = 6.28; // 第2个元素变为6.28
13. cout << get<0>(t) << " " << get<2>(t); // 输出10 6.28
15. // 嵌套tuple的访问：逐层get
16. auto t_nest = make_tuple(1, make_tuple("def", 6.28));
17. // 访问外层第1个元素（tuple）的第0个元素，输出def
18. cout << get<0>(get<1>(t_nest));

复制代码

2. 比较运算（默认 / 自定义）

（1）默认比较规则

按元素顺序逐一比较，先比第 0 个，相等则比第 1 个，依此类推。

1. auto t1 = make_tuple(1, "abc", 3.14);
2. auto t2 = make_tuple(2, "def", 2.71);
3. auto t3 = make_tuple(1, "abd", 3.14);
5. cout << (t1 < t2); // true（第0个元素1<2，无需比较后续）
6. cout << (t1 < t3); // true（第0个相等，第1个"abc"<"abd"）
7. cout << (t1 == make_tuple(1, "abc", 3.14)); // true（所有元素相等）

复制代码

（2）自定义比较规则

比赛中若需按「非默认顺序」排序（如优先比较第 2 个元素），需自定义 sort 的比较器。

1. vector<tuple<int, string, double>> vec = {
2. {1, "abc", 3.14},
3. {2, "def", 2.71},
4. {1, "abd", 3.14}
5. };
7. // 自定义规则：按第2个元素（double）升序，相等则按第0个元素降序
8. sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) {
9. if (get<2>(a) != get<2>(b)) {
10. return get<2>(a) < get<2>(b);
11. }
12. return get<0>(a) > get<0>(b);
13. });
15. // 排序后顺序：{2,"def",2.71}, {1,"abc",3.14}, {1,"abd",3.14}
16. for (auto& t : vec) {
17. cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << endl;
18. }

复制代码

3. 元素解包

tuple 无命名成员，直接用 get 访问多元素时代码繁琐，可通过「tie 解包」或「结构化绑定」将元素解为独立变量。

（1）tie 解包（C++11+）

通过 tie(变量1, 变量2, ...) 将 tuple 元素绑定到变量，自动赋值；若某元素无需接收，用 ignore 占位。

1. auto t = make_tuple(1, "abc", 3.14);
2. int a;
3. string b;
4. double c;
6. // 将tuple元素解包到a、b、c
7. tie(a, b, c) = t;
8. cout << a << " " << b << " " << c; // 输出1 abc 3.14
10. // 仅接收第0个和第2个元素，第1个忽略
11. int x;
12. double y;
13. tie(x, ignore, y) = t;
14. cout << x << " " << y; // 输出1 3.14

复制代码

（2）结构化绑定（C++17+）

直接将 tuple 元素解包为变量，无需提前定义，比赛中编译器（如 GCC）均支持。

1. auto t = make_tuple(1, "abc", 3.14);
2. // 直接解包为变量a、b、c，类型自动推导
3. auto [a, b, c] = t;
4. cout << a << " " << b << " " << c; // 输出1 abc 3.14
6. // 嵌套tuple的结构化绑定
7. auto t_nest = make_tuple(1, make_tuple("def", 6.28));
8. auto [x, y] = t_nest; // x=1，y是内部tuple
9. auto [s, d] = y; // s="def"，d=6.28
10. // 一次性解包（C++17+支持）
11. auto [m, [n, p]] = t_nest;
12. cout << m << " " << n << " " << p; // 输出1 def 6.28

复制代码

4. 其他基础操作

swap 交换

交换两个类型和元素数量完全一致的 tuple 的所有元素，时间复杂度 O(N)（N 为元素个数）。

1. auto t1 = make_tuple(1, "abc");
2. auto t2 = make_tuple(2, "def");
3. t1.swap(t2); // 交换后t1={2,"def"}, t2={1,"abc"}
4. // 全局swap函数（更常用）
5. swap(t1, t2);

复制代码

tuple_size /tuple_element

用于编译期获取 tuple 的「元素个数」或「第 N 个元素的类型」，比赛中极少直接使用，主要用于模板编程。

1. auto t = make_tuple(1, "abc", 3.14);
2. // 编译期获取元素个数：3
3. constexpr size_t size = tuple_size<decltype(t)>::value;
4. cout << size; // 输出3
6. // 编译期获取第1个元素的类型：string
7. using T = tuple_element<1, decltype(t)>::type;
8. T s = get<1>(t); // s="abc"

复制代码

vector

vector 是 C++ STL 中最常用的动态数组容器，支持随机访问（同普通数组），且能自动扩容，无需手动管理内存，是算法比赛中替代普通数组的首选工具。其底层基于连续内存实现，兼具数组的高效访问和动态扩容的灵活性。

一、vector 核心特性

1. 内存连续：元素存储在连续的内存空间中，可通过下标 [] 直接访问，时间复杂度 O(1)；
2. 动态扩容：当存储空间不足时，会自动申请更大的内存（通常扩容为原大小的 2 倍），并拷贝原元素（基于这个操作，可以提前分配好内存，避免拷贝原元素浪费时间），扩容操作的时间复杂度为 O(N)（但均摊后仍为 O(1)）；
3. 支持随机访问迭代器：可直接使用 STL 排序、查找等通用算法（如 sort、lower_bound）。

二、vector 初始化

初始化需包含头文件

1.空初始化

1. // 初始化一个空的int类型vector，后续可动态添加元素
2. vector<int> v;

复制代码

2.指定大小初始化(个人感觉最常用)

1. // 初始化大小为10的int类型vector，所有元素默认初始化为0
2. vector<int> v1(10);
4. // 初始化大小为10的int类型vector，所有元素初始化为5
5. vector<int> v2(10, 5);
7. // 初始化大小为5的string类型vector，所有元素初始化为"abc"
8. vector<string> v3(5, "abc");

复制代码

3.列表初始化

1. // 直接初始化并赋值，元素为1,2,3,4,5
2. vector<int> v = {1, 2, 3, 4, 5};
4. // 简化写法（C++17）
5. vector v = {1, 2, 3, 4, 5};

复制代码

4. 拷贝初始化

1. vector<int> v1 = {1, 2, 3};
2. // 拷贝v1的所有元素生成v2
3. vector<int> v2(v1);
4. // 拷贝v1中[begin(), end())区间的元素（等价于v3(v1)）
5. vector<int> v3(v1.begin(), v1.end());
6. // 拷贝v1中从下标1到3（左闭右开）的元素，v4 = {2,3}
7. vector<int> v4(v1.begin() + 1, v1.begin() + 3);

复制代码

5. 其他容器转换初始化

1. // 从数组初始化：将数组a的[0,5)区间元素导入vector
2. int a[] = {1,2,3,4,5};
3. vector<int> v(a, a + 5);
5. // 从set初始化（有序）
6. set<int> s = {1,3,5};
7. vector<int> v(s.begin(), s.end());

复制代码

三、常用函数

push_back

push_back用于在 vector 的尾部添加一个元素，若当前容量不足会触发自动扩容。

1. push_back(v)//将值v添加到vector末尾
3. vector<int> v={1,2};
4. v.push_back(3);//v变为{1,2,3}

复制代码

emplack_back

emplace_back是 C++11 新增的尾部添加元素方法，直接在容器内存构造元素，在某些情况下效率高于 push_back，支持传入多个构造参数。

1. emplace_back(args...)//传入构造元素的参数，在vector末尾构造并添加元素
3. vector<pair<int,string>> vp;
4. vp.emplace_back(1,"abc");//vp变为{{1,"abc"}}

复制代码

insert

insert用于在 vector 指定位置插入元素 / 元素区间，插入位置后的元素会向后移动。

1. insert(pos,val)//在迭代器pos位置插入值val
2. insert(pos,n,val)//在pos位置插入n个值为val的元素
4. insert(pos,begin,end)//在pos位置插入[begin,end)区间的元素
5. vector<int> v={1,3};
6. v.insert(v.begin()+1,2);//v变为{1,2,3}

复制代码

pop_back

pop_back用于删除 vector 的最后一个元素，仅减少元素个数，不释放内存。

1. pop_back()//删除vector末尾的元素
3. vector<int> v={1,2,3};
4. v.pop_back();//v变为{1,2}

复制代码

erase

erase用于删除 vector 指定位置 / 区间的元素，删除位置后的元素会向前移动。

1. erase(pos)//删除迭代器pos位置的元素
2. erase(begin,end)//删除[begin,end)区间的元素
4. vector<int> v={1,2,3,4};
5. v.erase(v.begin()+2);//v变为{1,2,4}

复制代码

front

front用于返回 vector 第一个元素的引用，可直接读写该元素。

1. front()//返回vector首个元素的引用
3. vector<int> v={1,2,3};
4. cout<<v.front();//输出1
5. v.front()=10;//v变为{10,2,3}

复制代码

back

back用于返回 vector 最后一个元素的引用，可直接读写该元素。

1. back()//返回vector末尾元素的引用
3. vector<int> v={1,2,3};
4. cout<<v.back();//输出3
5. v.back()=30;//v变为{1,2,30}

复制代码

at

at用于返回 vector 指定下标位置的元素引用，会做下标越界检查，比 [] 更安全，但是实际上我还是用的[]，因为这个要习惯一点。

1. at(idx)//返回下标idx处元素的引用，越界抛出out_of_range异常
3. vector<int> v={1,2,3};
4. cout<<v.at(1);//输出2
5. v.at(1)=20;//v变为{1,20,3}

复制代码

size

size用于返回 vector 中当前元素的个数。

1. size()//返回vector的元素个数
3. vector<int> v={1,2,3};
4. cout<<v.size();//输出3
5. v.push_back(4);
6. cout<<v.size();//输出4

复制代码

empty

empty用于判断 vector 是否为空（元素个数为 0），返回布尔值 true(空）/false（非空）。

1. empty()//判断vector是否为空，为空返回true，否则返回false
3. vector<int> v;
4. cout<<v.empty();//输出true
5. v.push_back(1);
6. cout<<v.empty();//输出false

复制代码

clear

clear用于清空 vector 中所有元素，仅将元素个数置 0，不释放已分配的内存。

1. clear()//清空vector所有元素，size变为0，capacity不变
3. vector<int> v={1,2,3};
4. v.clear();
5. cout<<v.size();//输出0

复制代码

reserve

reserve用于预分配 vector 的内存容量，不创建元素，避免频繁扩容拷贝。

1. reserve(n)//预分配能存储n个元素的内存，size不变，capacity至少为n
3. vector<int> v;
4. v.reserve(1000);//capacity变为1000，size仍为0

复制代码

assign

assign用于替换 vector 所有元素，先清空原有元素，再添加新元素。

1. assign(n,val)//替换为n个值为val的元素
2. assign(begin,end)//替换为[begin,end)区间的元素
4. vector<int> v={1,2,3};
5. v.assign(2,5);//v变为{5,5}

复制代码

resize

resize用于调整 vector 的元素个数，扩容时可指定新元素默认值，缩容时删除多余元素。

1. resize(n)//调整size为n，新增元素默认初始化
2. resize(n,val)//调整size为n，新增元素初始化为val
4. vector<int> v={1,2};
5. v.resize(3,8);//v变为{1,2,8}

复制代码

string

string 是 C++ STL 中专门用于处理字符串的容器，底层基于连续的 char 数组实现，封装了丰富的字符串操作接口，无需手动管理内存（如 C 风格字符串的 strcpy/strlen 等），是算法比赛中处理字符串的首选工具，兼具易用性和高效性。

一、string 核心特性

1. 内存连续：字符存储在连续的内存空间中，支持下标 [] 随机访问，时间复杂度 O(1)；
2. 动态扩容：当存储空间不足时，自动申请更大的内存（通常扩容为原大小的 2 倍），扩容均摊时间复杂度 O(1)；
3. 兼容 STL 算法：支持随机访问迭代器，可直接使用 sort、reverse、find 等 STL 通用算法；
4. 原生支持字符串操作：内置拼接、查找、替换、截取等高频操作，无需手动实现，适配比赛中各类字符串场景。

二、string 初始化

初始化需包含头文件

1. 空初始化

1. // 初始化一个空字符串
2. string s;

复制代码

2. 直接赋值初始化

1. // 直接赋值字符串常量
2. string s1 = "hello world";
3. // 简化写法（C++17+）
4. string s2{"abc123"};
5. // 单个字符初始化
6. string s3(1, 'a'); // s3 = "a"

复制代码

3. 指定长度初始化

1. // 初始化长度为5的字符串，所有字符为'x'
2. string s1(5, 'x'); // s1 = "xxxxx"
3. // 初始化长度为10的空字符串（默认填充'\0'，输出为空）
4. string s2(10);

复制代码

4. 拷贝初始化

1. string s1 = "algorithm";
2. // 拷贝s1的所有字符生成s2
3. string s2(s1);
4. // 拷贝s1中[begin(), end())区间的字符（等价于s3(s1)）
5. string s3(s1.begin(), s1.end());
6. // 拷贝s1中从下标2开始的4个字符（左闭右开），s4 = "gori"
7. string s4(s1, 2, 4);
8. // 拷贝s1中从下标0到5（迭代器区间）的字符，s5 = "algor"
9. string s5(s1.begin(), s1.begin() + 5);

复制代码

5. 从其他类型转换初始化

1. // 从C风格字符串（字符数组）初始化
2. char c_arr[] = "cplusplus";
3. string s1(c_arr);
4. // 从字符数组的指定区间初始化（前5个字符）
5. string s2(c_arr, 5); // s2 = "cplus"
7. // 从vector<char>初始化
8. vector<char> vec = {'s', 't', 'l'};
9. string s3(vec.begin(), vec.end()); // s3 = "stl"

复制代码

三、常用函数

push_back

push_back 用于在字符串尾部添加单个字符，容量不足时触发自动扩容。

1. push_back(c) // 将字符c添加到字符串末尾
3. string s = "abc";
4. s.push_back('d'); // s变为"abcd"

复制代码

pop_back

pop_back 用于删除字符串最后一个字符，仅减少长度，不释放内存。

1. pop_back() // 删除字符串末尾的字符
3. string s = "abcd";
4. s.pop_back(); // s变为"abc"

复制代码

append

append 用于字符串尾部拼接（支持多类型拼接，比 + 更高效）。

1. append(str) // 拼接字符串str
2. append(n, c) // 拼接n个字符c
3. append(begin, end) // 拼接[begin,end)区间的字符
5. string s = "hello";
6. s.append(" world"); // s变为"hello world"
7. s.append(3, '!'); // s变为"hello world!!!"
8. vector<char> vec = {'1','2','3'};
9. s.append(vec.begin(), vec.end()); // s变为"hello world!!!123"

复制代码

insert

insert 用于在字符串指定位置插入字符 / 字符串，插入位置后的字符向后移动。

1. insert(pos, str) // 在下标pos位置插入字符串str
2. insert(pos, n, c) // 在下标pos位置插入n个字符c
3. insert(pos, begin, end) // 在pos位置插入[begin,end)区间的字符
5. string s = "ac";
6. s.insert(1, "b"); // s变为"abc"
7. s.insert(3, 2, 'd'); // s变为"abcdd"
8. string t = "12";
9. s.insert(0, t.begin(), t.end()); // s变为"12abcdd"

复制代码

erase

erase 用于删除字符串指定位置 / 区间的字符，删除位置后的字符向前移动。

1. erase(pos) // 删除从下标pos开始到末尾的所有字符
2. erase(pos, len) // 删除从下标pos开始的len个字符
3. erase(begin, end) // 删除[begin,end)区间的字符
5. string s = "123456";
6. s.erase(3); // s变为"123"
7. s.erase(1, 1); // s变为"13"
8. s.erase(s.begin(), s.begin()+1); // s变为"3"

复制代码

substr

substr 用于截取字符串的指定区间（左闭右开），返回截取后的新字符串。

1. substr(pos, len) // 截取从下标pos开始的len个字符；len省略则截取到末尾
3. string s = "algorithm";
4. string s1 = s.substr(2, 4); // s1 = "gori"
5. string s2 = s.substr(5); // s2 = "rithm"

复制代码

find

find 用于从左到右查找字符 / 字符串首次出现的下标，未找到返回 string::npos（本质是 -1）。

1. find(str, pos) // 从下标pos开始查找str（pos省略则从0开始）
2. find(c, pos) // 从下标pos开始查找字符c
4. string s = "ababcabc";
5. // 查找"abc"首次出现的下标，返回2
6. int idx1 = s.find("abc");
7. // 从下标3开始查找"abc"，返回5
8. int idx2 = s.find("abc", 3);
9. // 查找字符'c'首次出现的下标，返回4
10. int idx3 = s.find('c');
11. // 未找到返回string::npos
12. int idx4 = s.find("xyz"); // idx4 = string::npos

复制代码

rfind

rfind 用于从右到左查找字符 / 字符串最后一次出现的下标，未找到返回 string::npos。

1. rfind(str, pos) // 从下标pos开始（向左）查找str；pos省略则查末尾
3. string s = "ababcabc";
4. // 查找"abc"最后一次出现的下标，返回5
5. int idx = s.rfind("abc");

复制代码

replace

replace 用于替换字符串指定区间的字符为目标字符 / 字符串。

1. replace(pos, len, str) // 将pos开始的len个字符替换为str
2. replace(begin, end, str) // 将[begin,end)区间的字符替换为str
4. string s = "12345";
5. s.replace(1, 2, "ab"); // s变为"1ab45"
6. s.replace(s.begin()+3, s.end(), "67"); // s变为"1ab67"

复制代码

size / length

size 和 length 功能完全一致，均返回字符串的字符个数（不含结束符 \0）。

1. size() // 返回字符串字符个数
2. length() // 等价于size()
4. string s = "abc123";
5. cout << s.size(); // 输出6
6. cout << s.length(); // 输出6

复制代码

empty

empty 用于判断字符串是否为空（字符个数为 0），返回布尔值 true（空）/false（非空）。

1. empty() // 为空返回true，否则返回false
3. string s;
4. cout << s.empty(); // 输出true
5. s.push_back('a');
6. cout << s.empty(); // 输出false

复制代码

clear

clear 用于清空字符串所有字符，仅将长度置 0，不释放已分配的内存。

1. clear() // 清空字符串，size变为0，capacity不变
3. string s = "hello";
4. s.clear();
5. cout << s.size(); // 输出0

复制代码

reserve

reserve 用于预分配字符串的内存容量，避免频繁扩容拷贝，优化比赛性能。

1. reserve(n) // 预分配能存储n个字符的内存，size不变，capacity至少为n
3. string s;
4. s.reserve(10000); // 预分配1万个字符的空间，避免多次扩容

复制代码

resize

resize 用于调整字符串的字符个数，扩容时可指定填充字符，缩容时删除多余字符。

1. resize(n) // 调整size为n，新增字符默认填充'\0'
2. resize(n, c) // 调整size为n，新增字符填充为c
4. string s = "ab";
5. s.resize(4, 'c'); // s变为"abcc"
6. s.resize(2); // s变为"ab"

复制代码

at

at 用于返回指定下标位置的字符引用，会做下标越界检查，比 [] 更安全（比赛中少用，效率略低）。

1. at(idx) // 返回下标idx处字符的引用，越界抛出out_of_range异常
3. string s = "abc";
4. cout << s.at(1); // 输出b
5. s.at(1) = 'd'; // s变为"adc"

复制代码

front / back

front 返回字符串第一个字符的引用，back 返回最后一个字符的引用，均可直接读写。

1. front() // 返回首个字符的引用
2. back() // 返回末尾字符的引用
4. string s = "123";
5. cout << s.front(); // 输出1
6. s.back() = '4'; // s变为"124"

复制代码

c_str

c_str 用于返回字符串对应的 C 风格字符数组（以 \0 结尾），适配需 C 风格字符串的接口（如 printf）。

1. c_str() // 返回const char*类型的C风格字符串
3. string s = "test";
4. printf("%s\n", s.c_str()); // 输出test

复制代码

compare

compare 用于比较两个字符串的字典序，返回整数值：

• 返回 0：两字符串相等；
• 返回正数：当前字符串 > 目标字符串；
• 返回负数：当前字符串 < 目标字符串。

1. compare(str) // 比较当前字符串和str的字典序
3. string s1 = "abc";
4. string s2 = "abd";
5. cout << s1.compare(s2); // 输出-1（abc < abd）
6. cout << s2.compare(s1); // 输出1（abd > abc）
7. cout << s1.compare("abc"); // 输出0

复制代码

类型转换相关(这个前面有介绍过)

to_string

to_string 用于将数字（int/long long/double 等）转换为 string 类型。

1. to_string(num) // 将数字num转换为字符串
3. string s1 = to_string(123); // s1 = "123"
4. string s2 = to_string(3.14); // s2 = "3.14"

复制代码

stoi / stol / stoll / stod

用于将合法的数字字符串转换为对应数值类型，比赛中常用作字符串转数字。

1. stoi(s) // 字符串转int
2. stoll(s) // 字符串转long long
3. stod(s) // 字符串转double
5. string s1 = "12345";
6. int a = stoi(s1); // a = 12345
7. long long b = stoll(s1); // b = 12345
8. string s2 = "3.1415";
9. double c = stod(s2); // c = 3.1415

复制代码

stack

stack 是 C++ STL 中的栈容器适配器，遵循「后进先出（LIFO，Last In First Out）」的核心原则，仅支持对栈顶元素的访问、插入和删除操作，不支持随机访问或遍历。其底层默认基于 deque 容器实现（也可指定 vector/list 作为底层容器），封装了栈的核心操作，是算法比赛中处理栈类问题（如括号匹配、单调栈、表达式求值）的工具,如果不是过于复杂的话可以自己去通过数组手写，效率可能会更高。

一、stack 核心特性

1. 后进先出：仅能操作栈顶元素，最后入栈的元素最先出栈，符合栈的经典特性；
2. 适配器本质：本身不直接存储数据，而是封装底层容器（默认 deque）的接口，仅暴露栈相关操作（屏蔽底层容器的其他接口）；
3. 无迭代器支持：无法遍历栈内元素（也无 begin()/end() 接口），符合栈「只能访问栈顶」的设计初衷；
4. 操作高效：入栈、出栈、访问栈顶的时间复杂度均为 O(1)，无扩容开销（底层容器的扩容由自身管理）。

二、stack 初始化

初始化需包含头文件

1. 空初始化（最常用）

1. // 初始化一个存储int类型的空栈，底层默认用deque
2. stack<int> st;

复制代码

2. 指定底层容器初始化（比赛极少用）

stack 可指定 vector/list 作为底层容器（需容器支持 back()/push_back()/pop_back() 接口）：

1. // 指定vector为底层容器，初始化空栈
2. stack<int, vector<int>> st1;
3. // 指定list为底层容器，初始化空栈
4. stack<int, list<int>> st2;

复制代码

3. 拷贝初始化

1. stack<int> st1;
2. st1.push(1);
3. st1.push(2);
4. // 拷贝st1的所有元素生成st2
5. stack<int> st2(st1);

复制代码

三、常用函数

push

push 用于将元素压入栈顶，底层调用底层容器的 push_back() 实现。

1. push(val) // 将元素val压入栈顶
3. stack<int> st;
4. st.push(1); // 栈：[1]
5. st.push(2); // 栈：[1,2]（栈顶为2）

复制代码

emplace

emplace 是 C++11 新增的入栈方法，直接在栈顶原地构造元素（无需拷贝 / 移动），效率高于 push，支持传入元素的构造参数。

1. emplace(args...) // 传入元素的构造参数，在栈顶构造并压入元素
3. stack<pair<int, string>> st;
4. // 原地构造pair<int,string>并压入栈顶，等价于st.push({1, "abc"})，但效率更高
5. st.emplace(1, "abc");

复制代码

pop

pop 用于删除栈顶元素，无返回值；需先判空再调用，否则行为未定义（比赛中务必注意）。

1. pop() // 删除栈顶元素，无返回值
3. stack<int> st;
4. st.push(1);
5. st.push(2);
6. st.pop(); // 栈变为[1]（栈顶1被保留）

复制代码

top

top 用于返回栈顶元素的引用（可读写），需先判空再调用，否则行为未定义。

1. top() // 返回栈顶元素的引用
3. stack<int> st;
4. st.push(1);
5. st.push(2);
6. cout << st.top(); // 输出2（栈顶元素）
7. st.top() = 10; // 修改栈顶元素为10，栈变为[1,10]

复制代码

size

size 用于返回栈中当前元素的个数，返回值为 size_t 类型（无符号整数）。

1. size() // 返回栈的元素个数
3. stack<int> st;
4. st.push(1);
5. st.push(2);
6. cout << st.size(); // 输出2

复制代码

empty

empty 用于判断栈是否为空（元素个数为 0），返回布尔值 true（空）/false（非空），比赛中调用 top()/pop() 前必须先判空。

1. empty() // 为空返回true，否则返回false
3. stack<int> st;
4. cout << st.empty(); // 输出true
5. st.push(1);
6. cout << st.empty(); // 输出false

复制代码

swap

swap 用于交换两个栈的内容（包括底层容器的所有元素），时间复杂度 O(1)（仅交换底层容器的指针）。

1. swap(st) // 交换当前栈与st的所有元素
3. stack<int> st1, st2;
4. st1.push(1);
5. st2.push(2);
6. st1.swap(st2);
7. cout << st1.top(); // 输出2
8. cout << st2.top(); // 输出1

复制代码

queue

queue 是 C++ STL 中的队列容器适配器，遵循「先进先出（FIFO，First In First Out）」的核心原则，仅支持对队首（出队）和队尾（入队）的操作，不支持随机访问或遍历。其底层默认基于 deque 容器实现（也可指定 list 作为底层容器，不支持 vector，因 vector 不高效支持队首删除），封装了队列的核心操作，是算法比赛中处理队列类问题（如 BFS、滑动窗口、任务排队）的首选工具。

一、queue 核心特性

1. 先进先出：新元素从队尾入队，旧元素从队首出队，最先入队的元素最先出队；
2. 适配器本质：不直接存储数据，封装底层容器（默认 deque）接口，仅暴露队列相关操作；
3. 无迭代器支持：无法遍历队列内元素，无 begin()/end() 接口；
4. 操作高效：入队、出队、访问队首 / 队尾的时间复杂度均为 O(1)，底层容器扩容由自身管理。

二、queue 初始化

初始化需包含头文件

1. 空初始化

1. // 初始化存储int类型的空队列，底层默认基于deque实现
2. queue<int> q;

复制代码

2. 指定底层容器初始化（比赛极少用）

仅支持 list/deque 作为底层容器（vector 不支持，因 vector 的 pop_front 效率为 O(N)）：

1. // 指定list为底层容器的空队列
2. queue<int, list<int>> q1;
3. // 指定deque为底层容器（等价于默认初始化）
4. queue<int, deque<int>> q2;

复制代码

3. 拷贝初始化

1. queue<int> q1;
2. q1.push(1);
3. q1.push(2);
4. // 拷贝q1的所有元素生成q2
5. queue<int> q2(q1);

复制代码

三、常用函数

push

push 用于将元素压入队尾，底层调用底层容器的 push_back() 实现。

1. push(val) // 将元素val压入队尾
3. queue<int> q;
4. q.push(1); // 队列：[1]（队首1，队尾1）
5. q.push(2); // 队列：[1,2]（队首1，队尾2）

复制代码

emplace

C++11 新增，在队尾原地构造元素（无需拷贝 / 移动元素），效率高于 push，支持传入元素的构造参数。

1. emplace(args...) // 传入构造参数，在队尾构造并压入元素
3. queue<pair<int, string>> q;
4. // 原地构造pair<int,string>并压入队尾，等价于q.push({1, "abc"})但效率更高
5. q.emplace(1, "abc");

复制代码

pop

pop 用于删除队首元素，无返回值；调用前必须先判空，否则行为未定义（比赛核心避坑点）。

1. pop() // 删除队首元素，无返回值
3. queue<int> q;
4. q.push(1);
5. q.push(2);
6. q.pop(); // 队列变为[2]（队首/队尾均为2）

复制代码

front

front 用于返回队首元素的引用（可直接读写）；调用前必须判空，否则行为未定义。

1. front() // 返回队首元素的引用
3. queue<int> q;
4. q.push(1);
5. q.push(2);
6. cout << q.front(); // 输出1（队首元素）
7. q.front() = 10; // 队首改为10，队列变为[10,2]

复制代码

back

back 用于返回队尾元素的引用（可直接读写）；调用前必须判空，否则行为未定义。

1. back() // 返回队尾元素的引用
3. queue<int> q;
4. q.push(1);
5. q.push(2);
6. cout << q.back(); // 输出2（队尾元素）
7. q.back() = 20; // 队尾改为20，队列变为[1,20]

复制代码

size

size 用于返回队列中当前元素的个数，返回值为 size_t 类型（无符号整数）。

1. size() // 返回队列的元素个数
3. queue<int> q;
4. q.push(1);
5. q.push(2);
6. cout << q.size(); // 输出2

复制代码

empty

empty 用于判断队列是否为空（元素个数为 0），返回布尔值 true（空）/false（非空）；调用 front()/back()/pop() 前必须先调用该函数判空。

1. empty() // 为空返回true，否则返回false
3. queue<int> q;
4. cout << q.empty(); // 输出true
5. q.push(1);
6. cout << q.empty(); // 输出false

复制代码

swap

swap 用于交换两个队列的所有内容（包括底层容器的元素），时间复杂度 O(1)（仅交换底层容器的指针

1. swap(q) // 交换当前队列与队列q的所有元素
3. queue<int> q1, q2;
4. q1.push(1);
5. q2.push(2);
6. q1.swap(q2);
7. cout << q1.front(); // 输出2
8. cout << q2.front(); // 输出1

复制代码

priority_queue

priority_queue（优先队列）是 C++ STL 中基于堆（heap） 实现的适配器容器，核心特性是「队首始终是优先级最高的元素」，默认实现为大顶堆（最大值优先），也可自定义为小顶堆或按自定义规则排序。插入、弹出队首元素的时间复杂度为 O(logN)，访问队首为 O(1)，算法比赛中常用于「TopK 问题」「贪心算法」「堆排序」等场景（如找最大 / 最小的 k 个元素、动态维护最值）。

一、priority_queue 核心特性

1. 堆结构底层：默认基于 vector 实现堆（也可指定 deque），物理上是连续数组，逻辑上满足堆的性质；

2. 优先级规则：默认按「<」比较，构建大顶堆（队首是最大值）；可通过自定义比较器改为小顶堆或自定义优先级；

3. 受限的访问 / 操作：仅支持访问队首（优先级最高） 元素，不支持随机访问、不支持遍历（遍历无意义，堆结构无序）；

4. 操作效率

   ：

   • 插入元素（push/emplace）：O(logN)（堆调整）；
   • 弹出队首（pop）：O(logN)（堆调整）；
   • 访问队首（top）：O(1)；
   • 判空 / 大小：O(1)；

5. 无迭代器：与 queue/stack 类似，priority_queue 是容器适配器，不提供迭代器，无法遍历所有元素；

6. 元素可重复：允许存储重复元素，优先级相同的元素顺序无保证。

二、priority_queue 初始化

初始化需包含头文件 ，核心是指定「元素类型」「底层容器（可选）」「比较器（可选）」，格式为。

1. priority_queue<元素类型, 底层容器类型, 比较器类型> pq;

复制代码

1. 空初始化（最常用，默认大顶堆）

默认底层容器为 vector，比较器为 less（大顶堆）。

1. // 存储int的大顶堆（默认），队首是最大值
2. priority_queue<int> pq;
3. // 存储double的大顶堆
4. priority_queue<double> pq2;

复制代码

2. 小顶堆初始化（高频需求）

需显式指定比较器为 greater，注意需同时指定底层容器（默认 vector）。

1. // 存储int的小顶堆，队首是最小值
2. priority_queue<int, vector<int>, greater<int>> pq;
3. pq.push(3);
4. pq.push(1);
5. pq.push(2);
6. cout << pq.top(); // 输出1（最小值优先）

复制代码

3. 从其他容器初始化

可直接用数组 /vector/deque 等容器初始化，自动构建堆。

1. vector<int> vec = {3, 1, 2};
2. // 用vector初始化大顶堆，自动堆化，队首是3
3. priority_queue<int> pq(vec.begin(), vec.end());
4. // 用vector初始化小顶堆
5. priority_queue<int, vector<int>, greater<int>> pq2(vec.begin(), vec.end());

复制代码

4. 自定义类型优先级

存储结构体 / 类等自定义类型时，需通过「重载 < 运算符」或「自定义比较器」指定优先级。

方式 1：重载 < 运算符

适用于自定义类型（如结构体），注意重载的是 <，且要满足堆的比较逻辑。

1. // 定义结构体：存储值和优先级，按值从大到小（大顶堆）
2. struct Node {
3. int val;
4. int prio;
5. // 重载<，实现大顶堆（val大的优先级高）
6. bool operator<(const Node& other) const {
7. // 注意：堆的比较是“反向”的，想让val大的优先，需返回 this->val < other.val
8. return this->val < other.val;
9. }
10. };
12. // 初始化大顶堆，按val从大到小
13. priority_queue<Node> pq;
14. pq.push({3, 1});
15. pq.push({1, 2});
16. pq.push({2, 3});
17. cout << pq.top().val; // 输出3（val最大）

复制代码

方式 2：自定义比较器

用结构体 /lambda 表达式定义比较器，适用于不想修改原类型的场景。

1. // 自定义结构体
2. struct Node {
3. int val;
4. int prio;
5. };
7. // 自定义比较器：按prio从小到大（小顶堆，prio小的优先级高）
8. struct NodeCmp {
9. bool operator()(const Node& a, const Node& b) {
10. // 想让prio小的优先，返回a.prio > b.prio（反向比较）
11. return a.prio > b.prio;
12. }
13. };
15. // 初始化按prio排序的小顶堆
16. priority_queue<Node, vector<Node>, NodeCmp> pq;
17. pq.push({3, 1});
18. pq.push({1, 2});
19. pq.push({2, 3});
20. cout << pq.top().val; // 输出3（prio=1最小）

复制代码

三、常用函数

priority_queue 的函数极少，核心仅 5 个，重点注意「pop 无返回值」「top 需先判空」等坑点。

push

插入元素到优先队列，自动调整堆结构，保证队首是优先级最高的元素。

1. push(val) // 插入元素val，O(logN)
3. priority_queue<int> pq;
4. pq.push(3);
5. pq.push(1);
6. pq.push(2); // 堆内元素：3（队首）、1、2

复制代码

emplace

C++11 新增，原地构造元素（无需拷贝 / 移动），效率高于 push，自动调整堆。

1. emplace(args...) // 传入元素构造参数，原地构造并插入
3. // 插入自定义结构体Node，原地构造{3, 1}
4. priority_queue<Node> pq;
5. pq.emplace(3, 1); // 等价于pq.push(Node{3, 1})，效率更高

复制代码

pop

弹出队首（优先级最高）的元素，无返回值，需先通过 top 获取值再 pop；pop 前必须判空（否则未定义行为）。

1. pop() // 弹出队首元素，O(logN)，无返回值
3. priority_queue<int> pq;
4. pq.push(3);
5. cout << pq.top(); // 先获取队首：3
6. pq.pop(); // 弹出队首，堆变为空
7. // pq.pop(); // 空队列pop会崩溃，务必先判空

复制代码

top

访问队首（优先级最高）的元素，返回引用；top 前必须判空（否则未定义行为）。

1. top() // 返回队首元素的引用，O(1)
3. priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆
4. pq.push(3);
5. pq.push(1);
6. cout << pq.top(); // 输出1（小顶堆队首是最小值）
7. pq.top() = 0; // 可修改队首值（但会破坏堆结构，不推荐）

复制代码

size /empty

时间复杂度均为 O(1)，pop/top 前必须用 empty () 判空，避免崩溃。

1. size() // 返回优先队列中元素个数
2. empty() // 判断是否为空，空返回true，否则false
4. priority_queue<int> pq;
5. cout << pq.empty(); // 输出true
6. pq.push(1);
7. cout << pq.size(); // 输出1
8. cout << pq.empty(); // 输出false

复制代码

swap

交换两个优先队列的内容（包括堆结构、底层容器），时间复杂度 O(1)。

1. swap(pq) // 交换当前优先队列与pq的内容
3. priority_queue<int> pq1({3,1,2}), pq2({5,4});
4. pq1.swap(pq2);
5. cout << pq1.top(); // 输出5（pq2的原队首）

复制代码

deque

deque（双端队列，double-ended queue）是 C++ STL 中兼具「双端高效操作」和「随机访问」特性的容器，底层基于分段连续的内存块实现（非完全连续，但对外暴露随机访问接口），既支持队首 / 队尾的 O(1) 插入 / 删除，也支持下标随机访问（O(1)），是介于 vector（随机访问优、队首操作差）和 list（双端操作优、随机访问差）之间的折中选择，算法比赛中常用于需要「两端操作 + 随机访问」的场景（如滑动窗口、双端队列优化的单调队列）。

一、deque 核心特性

1. 双端高效操作：队首（front）、队尾（back）的插入 / 删除操作时间复杂度均为 O(1)（无需像 vector 那样移动元素，也无需像 list 那样维护指针）；
2. 随机访问支持：可通过下标 []/at() 直接访问元素，时间复杂度 O(1)（对外表现与 vector 一致，底层通过分段内存的索引映射实现）；
3. 分段连续内存：底层由多个固定大小的内存块组成，扩容时仅需分配新的内存块（无需整体拷贝原元素），扩容效率高于 vector；
4. 支持随机访问迭代器：可直接使用 sort、reverse 等 STL 通用算法，无迭代器失效风险（分段内存设计减少迭代器失效场景）；
5. 无容量预分配专用函数：虽有 reserve()，但因分段内存特性，实际作用远不如 vector 明显（比赛中极少用）。

二、deque 初始化

初始化需包含头文件

1. 空初始化（最常用）

1. // 初始化存储int类型的空双端队列
2. deque<int> dq;

复制代码

2. 指定大小初始化

1. // 初始化大小为10的deque，所有元素默认初始化为0
2. deque<int> dq1(10);
3. // 初始化大小为5的deque，所有元素初始化为3
4. deque<int> dq2(5, 3);

复制代码

3. 列表初始化（C++11+）

1. // 直接初始化并赋值，元素为1,2,3,4
2. deque<int> dq = {1, 2, 3, 4};
3. // 简化写法（C++17+）
4. deque dq = {1, 2, 3, 4};

复制代码

4. 拷贝初始化

1. deque<int> dq1 = {1, 2, 3};
2. // 拷贝dq1的所有元素生成dq2
3. deque<int> dq2(dq1);
4. // 拷贝dq1中[begin(), end())区间的元素（等价于dq3(dq1)）
5. deque<int> dq3(dq1.begin(), dq1.end());
6. // 拷贝dq1中从下标1到3（左闭右开）的元素，dq4 = {2,3}
7. deque<int> dq4(dq1.begin() + 1, dq1.begin() + 3);

复制代码

5. 其他容器转换初始化

1. // 从数组初始化：将数组a的[0,4)区间元素导入deque
2. int a[] = {10, 20, 30, 40};
3. deque<int> dq(a, a + 4);
5. // 从vector初始化
6. vector<int> vec = {5, 6, 7};
7. deque<int> dq(vec.begin(), vec.end());

复制代码

三、常用函数

push_back

push_back 用于在 deque 尾部添加元素，底层分配内存块（若需扩容），时间复杂度 O(1)。

1. push_back(val) // 将元素val添加到deque尾部
3. deque<int> dq = {1, 2};
4. dq.push_back(3); // dq变为{1,2,3}

复制代码

push_front

push_front 是 deque 核心特性之一，用于在 deque 头部添加元素，时间复杂度 O(1)（优于 vector 的队首插入）。

1. push_front(val) // 将元素val添加到deque头部
3. deque<int> dq = {2, 3};
4. dq.push_front(1); // dq变为{1,2,3}

复制代码

emplace_back

C++11 新增，在 deque 尾部原地构造元素（无需拷贝 / 移动），效率高于 push_back，支持传入元素构造参数。

1. emplace_back(args...) // 传入构造参数，在尾部构造并添加元素
3. deque<pair<int, string>> dq;
4. dq.emplace_back(1, "abc"); // dq变为{{1,"abc"}}

复制代码

emplace_front

C++11 新增，在 deque 头部原地构造元素，效率高于 push_front，支持传入元素构造参数。

1. emplace_front(args...) // 传入构造参数，在头部构造并添加元素
3. deque<pair<int, string>> dq;
4. dq.emplace_front(2, "def"); // dq变为{{2,"def"}}

复制代码

pop_back

pop_back 用于删除 deque 尾部元素，时间复杂度 O(1)。

1. pop_back() // 删除尾部元素
3. deque<int> dq = {1,2,3};
4. dq.pop_back(); // dq变为{1,2}

复制代码

pop_front

pop_front 是 deque 核心特性之一，用于删除 deque 头部元素，时间复杂度 O(1)（优于 vector 的队首删除）。

1. pop_front() // 删除头部元素
3. deque<int> dq = {1,2,3};
4. dq.pop_front(); // dq变为{2,3}

复制代码

insert

insert 用于在指定位置插入元素 / 区间，插入位置后元素向后移动（因分段内存，效率略高于 vector，但低于双端操作）。

1. insert(pos, val) // 在迭代器pos位置插入单个元素val
2. insert(pos, n, val) // 在pos位置插入n个值为val的元素
3. insert(pos, begin, end) // 在pos位置插入[begin,end)区间的元素
5. deque<int> dq = {1,3};
6. dq.insert(dq.begin() + 1, 2); // dq变为{1,2,3}
7. dq.insert(dq.end(), 2, 4); // dq变为{1,2,3,4,4}

复制代码

erase

erase 用于删除指定位置 / 区间的元素，删除位置后元素向前移动，时间复杂度与删除位置相关（两端删除 O(1)，中间 O(N)）。

1. erase(pos) // 删除迭代器pos位置的元素
2. erase(begin, end) // 删除[begin,end)区间的元素
4. deque<int> dq = {1,2,3,4};
5. dq.erase(dq.begin() + 2); // dq变为{1,2,4}
6. dq.erase(dq.begin() + 1, dq.end()); // dq变为{1}

复制代码

front

front 返回 deque 头部元素的引用（可读写），调用前需判空，时间复杂度 O(1)。

1. front() // 返回头部元素的引用
3. deque<int> dq = {1,2,3};
4. cout << dq.front(); // 输出1
5. dq.front() = 10; // dq变为{10,2,3}

复制代码

back

back 返回 deque 尾部元素的引用（可读写），调用前需判空，时间复杂度 O(1)。

1. back() // 返回尾部元素的引用
3. deque<int> dq = {1,2,3};
4. cout << dq.back(); // 输出3
5. dq.back() = 30; // dq变为{1,2,30}

复制代码

at

at 返回指定下标元素的引用，做越界检查（越界抛 out_of_range 异常），时间复杂度 O(1)。

1. at(idx) // 返回下标idx处元素的引用
3. deque<int> dq = {1,2,3};
4. cout << dq.at(1); // 输出2
5. dq.at(1) = 20; // dq变为{1,20,3}

复制代码

size

size 返回 deque 中当前元素个数，时间复杂度 O(1)。

1. size() // 返回元素个数
3. deque<int> dq = {1,2,3};
4. cout << dq.size(); // 输出3

复制代码

empty

empty 判断 deque 是否为空（size=0），返回 bool 值，调用 front()/back()/pop_front()/pop_back() 前必须判空，时间复杂度 O(1)。

1. empty() // 空返回true，非空返回false
3. deque<int> dq;
4. cout << dq.empty(); // 输出true
5. dq.push_back(1);
6. cout << dq.empty(); // 输出false

复制代码

clear

clear 清空 deque 所有元素（size=0），不释放底层分段内存，时间复杂度 O(N)。

1. clear() // 清空元素，size变为0
3. deque<int> dq = {1,2,3};
4. dq.clear();
5. cout << dq.size(); // 输出0

复制代码

resize

resize 调整 deque 的元素个数，扩容时可指定填充值，缩容时删除多余元素，时间复杂度 O ( ∣ n − 原 s i z e ∣ ) O(|n-原size|) O(∣n−原size∣)。

1. resize(n) // 调整size为n，新增元素默认初始化
2. resize(n, val) // 调整size为n，新增元素初始化为val
4. deque<int> dq = {1,2};
5. dq.resize(4, 5); // dq变为{1,2,5,5}
6. dq.resize(2); // dq变为{1,2}

复制代码

swap

swap 交换两个 deque 的所有内容（包括分段内存的指针），时间复杂度 O(1)。

1. swap(dq) // 交换当前deque与dq的元素
3. deque<int> dq1 = {1,2}, dq2 = {3,4};
4. dq1.swap(dq2);
5. cout << dq1.front(); // 输出3

复制代码

begin/end/rbegin/rend

支持随机访问迭代器，可用于遍历、排序等 STL 算法，时间复杂度 O(1)（获取迭代器）。

1. begin() // 返回指向第一个元素的正向迭代器
2. end() // 返回指向最后一个元素下一个位置的正向迭代器
3. rbegin() // 返回指向最后一个元素的反向迭代器
4. rend() // 返回指向第一个元素前一个位置的反向迭代器
6. // 正向遍历
7. deque<int> dq = {1,2,3};
8. for (deque<int>::iterator it = dq.begin(); it != dq.end(); it++) {
9. cout << *it << " "; // 输出1 2 3
10. }
11. // 反向遍历
12. for (deque<int>::reverse_iterator it = dq.rbegin(); it != dq.rend(); it++) {
13. cout << *it << " "; // 输出3 2 1
14. }

复制代码

set

set 是 C++ STL 中的有序关联容器，底层基于红黑树（平衡二叉搜索树）实现，核心特性是元素自动升序排列且唯一（无重复元素），不支持随机访问，所有插入、删除、查找操作的时间复杂度均为 O(logN)（N 为元素个数）。与无序的 unordered_set（哈希表，O(1) 查找）相比，set 优势在于「有序性」，算法比赛中常用于需要「去重 + 有序遍历」「有序集合的二分查找」的场景（如区间查询、去重后排序）；若仅需去重 / 高效查找且无需有序，优先用 unordered_set。

一、set 核心特性

1. 有序性：元素插入后自动按升序排列（可通过自定义比较规则改为降序），遍历结果始终有序；
2. 唯一性：不允许存储重复元素（插入重复元素会被忽略，无报错）；若需存储重复元素，使用 multiset（用法与 set 几乎一致，仅允许重复）；
3. 红黑树底层：插入 / 删除 / 查找均为 O(logN)，效率稳定，无扩容开销；
4. 无随机访问：不支持下标 []/at() 操作，仅能通过迭代器遍历 / 访问元素；
5. 迭代器稳定：插入 / 删除元素时，除被删除元素的迭代器外，其他迭代器均不会失效；
6. 无修改元素接口：不能直接修改 set 中的元素（会破坏红黑树的有序性），需先删除旧元素，再插入新元素。

二、set 初始化

初始化需包含头文件

1. 空初始化

1. // 初始化存储int类型的空set，默认升序排列
2. set<int> st;

复制代码

2. 指定比较规则初始化（如降序）

1. // 自定义降序规则，初始化空set
2. set<int, greater<int>> st; // 元素插入后按降序排列
3. st.insert(3);
4. st.insert(1);
5. st.insert(2); // 遍历结果：3 2 1

复制代码

3. 列表初始化（C++11+）

1. // 初始化并插入元素，自动去重+升序排列
2. set<int> st = {3, 1, 2, 2}; // 实际存储：1,2,3
3. // 简化写法（C++17+）
4. set st = {5, 3, 4}; // 存储：3,4,5

复制代码

4. 拷贝初始化

1. set<int> st1 = {1, 2, 3};
2. // 拷贝st1的所有元素生成st2（有序性保留）
3. set<int> st2(st1);
4. // 拷贝st1中[begin(), end())区间的元素（等价于st3(st1)）
5. set<int> st3(st1.begin(), st1.end());

复制代码

5. 其他容器转换初始化

1. // 从vector初始化（自动去重+升序）
2. vector<int> vec = {2, 1, 2, 4};
3. set<int> st(vec.begin(), vec.end()); // 存储：1,2,4
5. // 从数组初始化
6. int a[] = {5, 3, 3, 6};
7. set<int> st(a, a + 4); // 存储：3,5,6

复制代码

三、常用函数

insert

insert 用于插入元素，若元素已存在则插入失败（无操作），返回值为 pair：iterator 指向插入 / 已存在的元素，bool 表示是否插入成功。

1. insert(val) // 插入单个元素val
2. insert(begin, end) // 插入[begin,end)区间的元素
4. set<int> st;
5. // 插入新元素，返回{指向1的迭代器, true}
6. auto res1 = st.insert(1);
7. // 插入重复元素，返回{指向1的迭代器, false}
8. auto res2 = st.insert(1);
9. // 插入区间元素，自动去重+排序
10. vector<int> vec = {3, 2, 2};
11. st.insert(vec.begin(), vec.end()); // st存储：1,2,3

复制代码

emplace

C++11 新增，直接在 set 内部原地构造元素（无需拷贝 / 移动），效率高于 insert，返回值与 insert 一致。

1. emplace(args...) // 传入元素构造参数，原地构造并插入
3. set<pair<int, string>> st;
4. // 原地构造pair并插入，等价于st.insert({1, "abc"})，效率更高
5. auto res = st.emplace(1, "abc");

复制代码

erase

erase 用于删除元素，支持「按迭代器删除」「按值删除」「按区间删除」，删除成功无返回值（按值删除返回删除的元素个数，set 中仅 0 或 1）。

1. erase(pos) // 删除迭代器pos指向的元素（需保证pos有效）
2. erase(val) // 删除值为val的元素，返回删除个数（set中0/1）
3. erase(begin, end) // 删除[begin,end)区间的元素
5. set<int> st = {1,2,3,4};
6. // 按值删除：删除3，返回1
7. int delCnt = st.erase(3);
8. // 按迭代器删除：删除第一个元素（1）
9. st.erase(st.begin());
10. // 按区间删除：删除从2到末尾的元素（仅4）
11. st.erase(st.find(2), st.end()); // st最终为空

复制代码

find

find 用于查找值为 val 的元素，找到则返回指向该元素的迭代器，未找到返回 st.end()（尾后迭代器）。

1. find(val) // 查找元素val
3. set<int> st = {1,2,3};
4. // 找到元素2，返回指向2的迭代器
5. auto it = st.find(2);
6. if (it != st.end()) cout << *it; // 输出2
7. // 未找到元素4，返回st.end()
8. auto it2 = st.find(4);

复制代码

count

count 用于统计值为 val 的元素个数，因 set 元素唯一，返回值仅为 0（不存在）或 1（存在）；multiset 中可返回重复元素的个数。

1. count(val) // 统计val的个数
3. set<int> st = {1,2,3};
4. cout << st.count(2); // 输出1
5. cout << st.count(4); // 输出0

复制代码

lower_bound / upper_bound

利用 set 的有序性实现二分查找，时间复杂度 O(logN)，是比赛中 set 的核心高频用法：

• lower_bound(val)：返回指向第一个 ≥ val 的元素的迭代器；
• upper_bound(val)：返回指向第一个 > val 的元素的迭代器。

1. lower_bound(val) // 查找第一个≥val的元素
2. upper_bound(val) // 查找第一个>val的元素
4. set<int> st = {1,3,5,7};
5. // lower_bound(3) → 指向3的迭代器
6. auto it1 = st.lower_bound(3);
7. // lower_bound(4) → 指向5的迭代器
8. auto it2 = st.lower_bound(4);
9. // upper_bound(3) → 指向5的迭代器
10. auto it3 = st.upper_bound(3);
11. // upper_bound(7) → 指向st.end()
12. auto it4 = st.upper_bound(7);

复制代码

equal_range

返回一个 pair，包含 lower_bound(val) 和 upper_bound(val) 的迭代器，等价于一次性获取「≥val」和「>val」的边界，比赛中常用于区间查询。

1. equal_range(val) // 返回pair<iterator, iterator>
3. set<int> st = {1,3,5,7};
4. auto [left, right] = st.equal_range(3);
5. cout << *left; // 输出3（≥3的第一个元素）
6. cout << *right; // 输出5（>3的第一个元素）

复制代码

begin / end / rbegin / rend

返回迭代器用于遍历，遍历结果始终有序（默认升序，反向迭代器为降序）。

1. begin() // 指向第一个元素的正向迭代器
2. end() // 指向最后一个元素下一个位置的正向迭代器
3. rbegin() // 指向最后一个元素的反向迭代器
4. rend() // 指向第一个元素前一个位置的反向迭代器
6. set<int> st = {3,1,2};
7. // 正向遍历（升序）：1 2 3
8. for (auto it = st.begin(); it != st.end(); it++) {
9. cout << *it << " ";
10. }
11. // 反向遍历（降序）：3 2 1
12. for (auto it = st.rbegin(); it != st.rend(); it++) {
13. cout << *it << " ";
14. }
15. // 范围for遍历（升序）：1 2 3
16. for (int x : st) {
17. cout << x << " ";
18. }

复制代码

size / empty

基础容量判断函数，时间复杂度均为 O(1)。

1. size() // 返回set中元素个数
2. empty() // 判断是否为空（size=0返回true）
4. set<int> st = {1,2,3};
5. cout << st.size(); // 输出3
6. cout << st.empty(); // 输出false
7. st.clear();
8. cout << st.empty(); // 输出true

复制代码

clear

清空 set 所有元素，size 置 0，释放底层红黑树内存，时间复杂度 O(N)。

1. clear() // 清空所有元素
3. set<int> st = {1,2,3};
4. st.clear();
5. cout << st.size(); // 输出0

复制代码

swap

交换两个 set 的所有内容（仅交换红黑树的根节点指针），时间复杂度 O(1)。

1. swap(st) // 交换当前set与st的元素
3. set<int> st1 = {1,2}, st2 = {3,4};
4. st1.swap(st2);
5. cout << *st1.begin(); // 输出3

复制代码

front /back（C++11 新增）

返回第一个 / 最后一个元素的引用（等价于 *st.begin()/*st.rbegin()），调用前需判空。

1. front() // 返回第一个元素的引用
2. back() // 返回最后一个元素的引用
4. set<int> st = {1,2,3};
5. cout << st.front(); // 输出1
6. cout << st.back(); // 输出3

复制代码

multiset

multiset 是 C++ STL 中支持重复元素的有序关联容器，底层同样基于红黑树（平衡二叉搜索树）实现，核心特性是「元素自动升序排列且允许重复」，与 set 的唯一区别是不限制元素唯一性。所有插入、删除、查找操作的时间复杂度仍为 O(logN)（N 为元素总数），算法比赛中常用于需要「有序 + 允许重复元素」「统计重复次数」「有序区间查询」的场景（如频率统计、多路有序数据合并）。

一、multiset 核心特性

1. 有序性：元素插入后自动按升序排列（可自定义降序），遍历结果始终有序；
2. 可重复性：允许存储多个相同值的元素（核心区别于 set）；
3. 红黑树底层：插入 / 删除 / 查找均为 O(logN)，效率稳定，无扩容开销；
4. 无随机访问：不支持下标 []/at() 操作，仅能通过迭代器遍历 / 访问元素；
5. 迭代器稳定：插入 / 删除元素时，除被删除元素的迭代器外，其他迭代器均不会失效；
6. 无修改元素接口：不能直接修改元素（会破坏红黑树有序性），需先删除旧元素，再插入新元素。

二、multiset 初始化

初始化需包含头文件 （与 set 共用头文件），用法与 set 几乎完全一致，仅插入重复元素时会保留：

1. 空初始化

1. // 初始化存储int类型的空multiset，默认升序排列
2. multiset<int> ms;

复制代码

2. 指定比较规则初始化（如降序）

1. // 自定义降序规则，初始化空multiset
2. multiset<int, greater<int>> ms;
3. ms.insert(3);
4. ms.insert(1);
5. ms.insert(2);
6. ms.insert(2); // 允许重复，最终存储：3,2,2,1

复制代码

3. 列表初始化（C++11+）

1. // 初始化并插入重复元素，自动升序保留所有元素
2. multiset<int> ms = {3, 1, 2, 2}; // 实际存储：1,2,2,3

复制代码

4. 拷贝初始化

1. multiset<int> ms1 = {1, 2, 2, 3};
2. // 拷贝ms1的所有元素（包括重复元素）生成ms2
3. multiset<int> ms2(ms1);
4. // 拷贝ms1中[begin(), end())区间的元素
5. multiset<int> ms3(ms1.begin(), ms1.end());

复制代码

5. 其他容器转换初始化

1. // 从vector初始化（保留重复元素+升序）
2. vector<int> vec = {2, 1, 2, 4};
3. multiset<int> ms(vec.begin(), vec.end()); // 存储：1,2,2,4

复制代码

三、常用函数

multiset 函数与 set 基本通用，核心差异集中在「重复元素处理」，以下重点标注差异点：

insert

insert 用于插入元素，允许重复插入（所有元素都会被保留），返回值为指向插入元素的迭代器（无 bool 值，因插入始终成功）。

1. insert(val) // 插入单个元素val（允许重复）
2. insert(begin, end) // 插入[begin,end)区间的元素（保留重复）
4. multiset<int> ms;
5. // 插入1，返回指向1的迭代器
6. ms.insert(1);
7. // 再次插入1，返回指向新插入的1的迭代器（仍在有序位置）
8. ms.insert(1);
9. // 插入区间元素，保留重复+排序
10. vector<int> vec = {3, 2, 2};
11. ms.insert(vec.begin(), vec.end()); // ms存储：1,1,2,2,3

复制代码

emplace

C++11 新增，原地构造并插入元素（允许重复），效率高于 insert，返回指向插入元素的迭代器。

1. emplace(args...) // 传入构造参数，原地构造并插入
3. multiset<pair<int, string>> ms;
4. // 原地构造并插入2个相同的pair
5. ms.emplace(1, "abc");
6. ms.emplace(1, "abc"); // 保留重复，ms中有两个{1,"abc"}

复制代码

erase（核心差异点）

erase 有三种形式，处理重复元素时需特别注意：

• erase(pos)：删除迭代器 pos 指向的单个元素（仅删一个，即使有重复）；
• erase(val)：删除所有值为 val 的元素，返回删除的元素个数；
• erase(begin, end)：删除 [begin,end) 区间的元素（可删部分重复元素）。

1. multiset<int> ms = {1,1,2,2,3};
2. // 按值删除：删除所有1，返回删除个数2
3. int delCnt = ms.erase(1); // ms变为{2,2,3}
4. // 按迭代器删除：删除第一个2（仅删一个）
5. ms.erase(ms.find(2)); // ms变为{2,3}
6. // 按区间删除：删除从2到末尾的元素（2和3）
7. ms.erase(ms.find(2), ms.end()); // ms最终为空

复制代码

find

find 用于查找值为 val 的元素，找到则返回指向第一个该元素的迭代器，未找到返回 ms.end()。

1. find(val) // 查找第一个值为val的元素
3. multiset<int> ms = {1,1,2,2,3};
4. // 找到第一个2，返回指向该2的迭代器
5. auto it = ms.find(2);
6. if (it != ms.end()) cout << *it; // 输出2

复制代码

count（核心差异点）

count 用于统计值为 val 的元素总个数（区别于 set 的 0/1），时间复杂度 O(logN+k)（k 为重复次数）。

1. count(val) // 统计val的重复次数
3. multiset<int> ms = {1,1,2,2,3};
4. cout << ms.count(1); // 输出2
5. cout << ms.count(2); // 输出2
6. cout << ms.count(4); // 输出0

复制代码

lower_bound / upper_bound

利用有序性实现二分查找，行为与 set 一致，但需注意重复元素的边界：

• lower_bound(val)：返回指向第一个 ≥ val 的元素的迭代器；
• upper_bound(val)：返回指向第一个 > val 的元素的迭代器；

1. multiset<int> ms = {1,1,2,2,3};
2. // lower_bound(2) → 指向第一个2的迭代器
3. auto it1 = ms.lower_bound(2);
4. // upper_bound(2) → 指向3的迭代器
5. auto it2 = ms.upper_bound(2);
6. // 遍历[lower_bound(2), upper_bound(2))可获取所有2
7. for (auto it = it1; it != it2; it++) {
8. cout << *it << " "; // 输出2 2
9. }

复制代码

equal_range

返回 pair，包含 lower_bound(val) 和 upper_bound(val) 的迭代器，可快速获取「所有值为 val 的元素区间」（左闭右开），是处理重复元素的高频用法。

1. equal_range(val) // 获取所有val的迭代器区间
3. multiset<int> ms = {1,1,2,2,3};
4. auto [left, right] = ms.equal_range(1);
5. // 遍历区间，输出所有1
6. for (auto it = left; it != right; it++) {
7. cout << *it << " "; // 输出1 1
8. }

复制代码

begin / end / rbegin / rend

返回迭代器用于遍历，遍历结果始终有序（默认升序，反向迭代器为降序），重复元素连续排列。

1. multiset<int> ms = {3,1,2,2};
2. // 正向遍历（升序）：1 2 2 3
3. for (int x : ms) {
4. cout << x << " ";
5. }
6. // 反向遍历（降序）：3 2 2 1
7. for (auto it = ms.rbegin(); it != ms.rend(); it++) {
8. cout << *it << " ";
9. }

复制代码

size / empty / clear / swap

与 set 完全一致，无差异。

1. size() // 返回元素总个数（包括重复）
2. empty() // 判断是否为空
3. clear() // 清空所有元素
4. swap(ms) // 交换两个multiset的内容
6. multiset<int> ms = {1,1,2};
7. cout << ms.size(); // 输出3
8. ms.clear();
9. cout << ms.empty(); // 输出true

复制代码

front /back（C++11 新增）

返回第一个 / 最后一个元素的引用（重复元素仍取首个 / 最后一个），调用前需判空。

1. multiset<int> ms = {1,1,2,2,3};
2. cout << ms.front(); // 输出1（第一个元素）
3. cout << ms.back(); // 输出3（最后一个元素）

复制代码

unordered_set

unordered_set 是 C++ STL 中的无序关联容器，底层基于哈希表（开散列 / 链地址法）实现，核心特性是「元素唯一 + 无序存储」，插入、删除、查找操作的平均时间复杂度为 *O(1)*（最坏情况 O(N)，由哈希冲突导致）。与 set（红黑树、有序、O(logN)）相比，unordered_set 优势在于「高效的查找 / 插入 / 删除」，劣势是「无序性」，算法比赛中常用于仅需「去重 + 快速查找」且无需有序的场景（如存在性判断、快速去重）。

一、unordered_set 核心特性

1. 无序性：元素无固定顺序（按哈希值存储），遍历结果随机，不支持排序相关操作（如 lower_bound）；
2. 唯一性：不允许存储重复元素（插入重复元素会被忽略，无报错）；若需存储重复元素，使用 unordered_multiset；
3. 哈希表底层：平均 O(1) 查找 / 插入 / 删除，最坏 O(N)（哈希冲突严重时）；支持自定义哈希函数和等价判断规则；
4. 迭代器特性：仅支持前向迭代器（可 ++it，不可 --it/it + n），无反向迭代器（rbegin()/rend()）；
5. 迭代器不稳定性：插入 / 删除元素可能导致迭代器失效（哈希表扩容 / 桶结构变化），需重新获取迭代器；
6. 无排序接口：因无序，无 lower_bound/upper_bound/equal_range 等有序相关函数；
7. 自定义类型支持：存储自定义类型（如 pair）时，需手动提供哈希函数和 == 重载。

二、unordered_set 初始化

初始化需包含头文件

1. 空初始化（最常用）

1. // 初始化存储int类型的空unordered_set
2. unordered_set<int> us;

复制代码

2. 列表初始化（C++11+）

1. // 初始化并插入元素，自动去重（无序）
2. unordered_set<int> us = {3, 1, 2, 2}; // 实际存储：1,2,3（顺序随机）
3. // 简化写法（C++17+）
4. unordered_set us = {5, 3, 4}; // 存储顺序随机

复制代码

3. 拷贝初始化

1. unordered_set<int> us1 = {1, 2, 3};
2. // 拷贝us1的所有元素生成us2（顺序可能与us1不同）
3. unordered_set<int> us2(us1);
4. // 拷贝us1中[begin(), end())区间的元素
5. unordered_set<int> us3(us1.begin(), us1.end());

复制代码

4. 其他容器转换初始化

1. // 从vector初始化（自动去重，无序）
2. vector<int> vec = {2, 1, 2, 4};
3. unordered_set<int> us(vec.begin(), vec.end()); // 存储：1,2,4（顺序随机）
5. // 从数组初始化
6. int a[] = {5, 3, 3, 6};
7. unordered_set<int> us(a, a + 4); // 存储：3,5,6（顺序随机）

复制代码

5. 自定义哈希函数

存储自定义类型（如 pair）时，需自定义哈希函数：

1. // 自定义pair<int,int>的哈希函数
2. struct PairHash {
3. size_t operator()(const pair<int, int>& p) const {
4. // 组合两个int的哈希值（避免冲突）
5. return hash<int>()(p.first) ^ (hash<int>()(p.second) << 1);
6. }
7. };
9. // 初始化存储pair<int,int>的unordered_set
10. unordered_set<pair<int, int>, PairHash> us;
11. us.insert({1, 2});
12. us.insert({3, 4});

复制代码

三、常用函数

insert

insert 用于插入元素，若元素已存在则插入失败，返回值为 pair（与 set 一致）：iterator 指向插入 / 已存在的元素，bool 表示是否插入成功。

1. insert(val) // 插入单个元素val（去重）
2. insert(begin, end) // 插入[begin,end)区间的元素（去重）
4. unordered_set<int> us;
5. // 插入新元素，返回{指向1的迭代器, true}
6. auto res1 = us.insert(1);
7. // 插入重复元素，返回{指向1的迭代器, false}
8. auto res2 = us.insert(1);
9. // 插入区间元素，自动去重（无序）
10. vector<int> vec = {3, 2, 2};
11. us.insert(vec.begin(), vec.end()); // us存储：1,2,3（顺序随机）

复制代码

emplace

C++11 新增，直接在容器内原地构造元素（无需拷贝 / 移动），效率高于 insert，返回值与 insert 一致。

1. emplace(args...) // 传入元素构造参数，原地构造并插入
3. unordered_set<pair<int, string>> us;
4. // 原地构造pair并插入，等价于us.insert({1, "abc"})，效率更高
5. auto res = us.emplace(1, "abc");

复制代码

erase

erase 用于删除元素，支持「按迭代器删除」「按值删除」「按区间删除」，行为与 set 基本一致：

1. erase(pos) // 删除迭代器pos指向的元素（需保证pos有效）
2. erase(val) // 删除值为val的元素，返回删除的元素个数（0或1）
3. erase(begin, end) // 删除[begin,end)区间的元素
5. unordered_set<int> us = {1,2,3,4};
6. // 按值删除：删除3，返回1
7. int delCnt = us.erase(3);
8. // 按迭代器删除：删除第一个元素（随机，假设是1）
9. us.erase(us.begin());
10. // 按区间删除：删除剩余元素
11. us.erase(us.begin(), us.end()); // us最终为空

复制代码

find

find 用于查找值为 val 的元素，找到则返回指向该元素的迭代器，未找到返回 us.end()（核心高频函数）。

1. find(val) // 查找元素val
3. unordered_set<int> us = {1,2,3};
4. // 找到元素2，返回指向2的迭代器
5. auto it = us.find(2);
6. if (it != us.end()) cout << *it; // 输出2
7. // 未找到元素4，返回us.end()
8. auto it2 = us.find(4);

复制代码

count

count 用于统计值为 val 的元素个数，因元素唯一，返回值仅为 0（不存在）或 1（存在），可替代 find 做存在性判断（代码更简洁）。

1. count(val) // 统计val的个数（0/1）
3. unordered_set<int> us = {1,2,3};
4. cout << us.count(2); // 输出1
5. cout << us.count(4); // 输出0
6. // 存在性判断：if (us.count(x)) 等价于 if (us.find(x) != us.end())

复制代码

begin / end

返回前向迭代器用于遍历，遍历顺序随机（无规律），无反向迭代器。

1. begin() // 指向第一个元素的前向迭代器
2. end() // 指向最后一个元素下一个位置的前向迭代器
4. unordered_set<int> us = {3,1,2};
5. // 正向遍历（顺序随机，如：2 1 3）
6. for (auto it = us.begin(); it != us.end(); it++) {
7. cout << *it << " ";
8. }
9. // 范围for遍历（顺序随机）
10. for (int x : us) {
11. cout << x << " ";
12. }

复制代码

size / empty

基础容量判断函数，时间复杂度均为 O(1)。

1. size() // 返回unordered_set中元素个数
2. empty() // 判断是否为空（size=0返回true）
4. unordered_set<int> us = {1,2,3};
5. cout << us.size(); // 输出3
6. cout << us.empty(); // 输出false
7. us.clear();
8. cout << us.empty(); // 输出true

复制代码

clear

清空 unordered_set 所有元素，size 置 0，释放底层哈希表内存，时间复杂度 O(N)。

1. clear() // 清空所有元素
3. unordered_set<int> us = {1,2,3};
4. us.clear();
5. cout << us.size(); // 输出0

复制代码

swap

交换两个 unordered_set 的所有内容（仅交换哈希表的指针），时间复杂度 O(1)。

1. swap(us) // 交换当前unordered_set与us的元素
3. unordered_set<int> us1 = {1,2}, us2 = {3,4};
4. us1.swap(us2);
5. cout << *us1.begin(); // 输出3（顺序随机）

复制代码

bucket /bucket_count/load_factor（进阶）

哈希表相关函数，比赛中极少用，用于查看 / 调整哈希表参数（如解决哈希冲突）。

1. bucket(val) // 返回val所在的桶编号
2. bucket_count() // 返回哈希表的桶总数
3. load_factor() // 返回负载因子（元素个数/桶数），默认阈值1.0，超过则扩容
5. unordered_set<int> us = {1,2,3};
6. cout << us.bucket(2); // 输出2所在的桶编号
7. cout << us.bucket_count(); // 输出当前桶总数
8. cout << us.load_factor(); // 输出负载因子

复制代码

map

map 是 C++ STL 中有序键值对关联容器，底层基于红黑树（平衡二叉搜索树）实现，核心特性是以 键值对存储数据、键唯一且自动升序排列、值可灵活修改，插入、删除、按键查找的时间复杂度均为 O(logN)（N 为键值对个数）。与无序的 unordered_map（哈希表，平均 O(1) 查找）相比，map 的优势在于键的有序性，算法比赛中常用于需要「键值映射 + 键有序遍历」「按键区间查询」「有序统计频率」的场景（如按字符 / 数字有序统计次数、键的范围查找）；若仅需高效键值映射且无需有序，优先用 unordered_map。

一、map 核心特性

1. 键值对存储：每个元素是键值对，通过键（key） 唯一标识，值（value） 可任意修改（区别于 set 的元素不可改）；
2. 键的唯一性：不允许存在重复的键，插入重复键的键值对会被忽略，无报错；若需键可重复，使用multimap（用法与 map 几乎一致，仅键可重复）；
3. 键的有序性：插入后按键的升序自动排列（可通过自定义比较规则改为降序），遍历结果始终按键有序；
4. 红黑树底层：按键的插入 / 删除 / 查找均为 O(logN)，效率稳定，无扩容开销；
5. 键不可改，值可改：键是红黑树排序的依据，不能直接修改键（会破坏有序性），需先删除旧键值对，再插入新的；值可通过迭代器 /[] 直接修改；
6. 双向迭代器：支持++it/--it双向移动，不支持随机访问（无下标[]的随机访问，map 的[]是专属访问值的接口，非随机访问）；
7. 迭代器稳定：插入 / 删除元素时，除被删除元素的迭代器外，其他迭代器均不会失效；
8. 专属访问接口：提供[]和at()直接按键访问值，是 map 区别于其他关联容器的核心特性。

二、map 初始化

初始化需包含头文件

1. 空初始化（最常用）

1. // 初始化键为int、值为int的空map，键默认升序
2. map<int, int> mp;
3. // 键为string、值为int的空map（如统计字符出现次数）
4. map<string, int> mp2;
5. map<char, int> mp3;

复制代码

2. 指定比较规则初始化（如键降序）

通过自定义比较规则修改键的排序方式，仅需对键做约束：

1. // 键为int，按降序排列，值为int
2. map<int, int, greater<int>> mp;
3. mp.insert({1, 10});
4. mp.insert({3, 30});
5. mp.insert({2, 20}); // 按键降序存储：{3:30, 2:20, 1:10}

复制代码

3. 列表初始化（C++11+，比赛高频）

直接用{key, value}初始化键值对，自动按键去重 + 升序排列：

1. // 键int，值int，自动按键升序：{1:10, 2:20, 3:30}
2. map<int, int> mp = {{3, 30}, {1, 10}, {2, 20}, {2, 200}}; // 重复键{2,200}被忽略
3. // 键char，值int（统计字符频率），按键升序：{'a':1, 'b':2}
4. map<char, int> mp2 = {{'b', 2}, {'a', 1}};

复制代码

4. 拷贝初始化

1. map<int, int> mp1 = {{1,10}, {2,20}};
2. // 拷贝mp1所有键值对，有序性保留
3. map<int, int> mp2(mp1);
4. // 拷贝mp1[begin(), end())区间的键值对（等价于mp3(mp1)）
5. map<int, int> mp3(mp1.begin(), mp1.end());

复制代码

5. 其他容器转换初始化

从存储pair的容器（如 vector、deque）初始化，自动按键去重 + 升序：

1. // vector<pair<int, int>>转换为map
2. vector<pair<int, int>> vec = {{3,30}, {1,10}, {2,20}};
3. map<int, int> mp(vec.begin(), vec.end()); // 按键升序：{1:10,2:20,3:30}

复制代码

三、常用函数

map 函数围绕键展开操作，核心与 set 相通，但新增了[]/at()等值访问接口，以下按算法比赛使用频率排序，重点标注 map 专属特性和坑点。

[]

按键访问对应的值，是 map 最核心的高频用法，特性：若键不存在，会自动插入该键并将值初始化为默认值（int 为 0，string 为空，自定义类型为默认构造），这是比赛中最常见的坑点，不要通过这个判断键是否存在，需特别注意。

1. mp[key] // 访问/修改key对应的value，键不存在则自动插入{key, 默认值}
3. map<int, int> mp = {{1, 10}, {2, 20}};
4. cout << mp[1]; // 访问键1的值，输出10
5. mp[2] = 200; // 修改键2的值，mp变为{{1:10}, {2:200}}
6. cout << mp[3]; // 键3不存在，自动插入{3:0}，输出0
7. cout << mp.size(); // 输出3（因插入了键3）

复制代码

at（专属值访问接口，安全版 []）

按键访问对应的值，与[]的唯一区别：键不存在时会抛出 out_of_range 异常，不会自动插入新键，比赛中少用（需捕获异常，代码繁琐），但比[]更安全。

1. mp.at(key) // 访问key对应的value，键不存在抛异常，支持读写
3. map<int, int> mp = {{1, 10}};
4. mp.at(1) = 100; // 修改键1的值，输出100
5. // mp.at(2); // 键2不存在，抛出out_of_range异常

复制代码

insert

用于插入键值对，重复键插入失败，返回值为pair：

• 迭代器：指向插入成功的键值对 / 已存在的重复键值对；

• bool：

  1. true

  复制代码

  表示插入成功，

  1. false

  复制代码

  表示键重复插入失败。

  支持插入单个键值对、插入区间键值对两种形式。

1. insert({key, value}) // 插入单个键值对
2. insert(begin, end) // 插入[begin,end)区间的键值对（pair类型）
4. map<int, int> mp;
5. // 插入新键值对，返回{指向{1:10}的迭代器, true}
6. auto res1 = mp.insert({1, 10});
7. // 插入重复键，返回{指向{1:10}的迭代器, false}
8. auto res2 = mp.insert({1, 100});
9. // 从vector<pair>插入区间键值对
10. vector<pair<int, int>> vec = {{2,20}, {3,30}};
11. mp.insert(vec.begin(), vec.end()); // mp变为{{1:10}, {2:20}, {3:30}}

复制代码

emplace

C++11 新增，在 map 内部原地构造键值对，无需拷贝 / 移动 pair 对象，效率高于insert，返回值与insert一致（pair），重复键构造失败。

1. emplace(key_args..., value_args...) // 传入键和值的构造参数，原地构造键值对
3. map<int, string> mp;
4. // 原地构造{1, "abc"}，等价于mp.insert({1, "abc"})，效率更高
5. mp.emplace(1, "abc");
6. // 原地构造pair<string, int>，键为"test"，值为100
7. map<string, int> mp2;
8. mp2.emplace("test", 100);

复制代码

erase

支持按迭代器、按键、按区间三种删除方式，与 set 用法一致，仅操作对象为键值对：

• erase(pos)：删除迭代器 pos 指向的键值对，无返回值，需保证迭代器有效；
• erase(key)：按键删除键值对，返回删除的个数（map 中仅 0 或 1，键存在返回 1，否则 0）；
• erase(begin, end)：删除 [begin,end) 区间的键值对，无返回值。

1. map<int, int> mp = {{1:10}, {2:20}, {3:30}, {4:40}};
2. // 按键删除：删除键2，返回1，mp移除{2:20}
3. int delCnt = mp.erase(2);
4. // 按迭代器删除：删除第一个键值对{1:10}
5. mp.erase(mp.begin());
6. // 按区间删除：删除从{3:30}到末尾的键值对，mp变为空
7. mp.erase(mp.find(3), mp.end());

复制代码

find

按键查找键值对，找到则返回指向该键值对的迭代器，未找到返回mp.end()（尾后迭代器），遍历迭代器可通过->first访问键、->second访问值。

1. find(key) // 按键查找键值对，返回迭代器
3. map<int, int> mp = {{1:10}, {2:20}};
4. auto it = mp.find(2);
5. if (it != mp.end()) {
6. cout << it->first; // 访问迭代器指向的键，输出2
7. cout << it->second; // 访问迭代器指向的值，输出20
8. }
9. auto it2 = mp.find(3); // 未找到，返回mp.end()

复制代码

count

按键统计键值对的个数，因 map 键唯一，返回值仅为0（键不存在）或 1（键存在），可替代find做键的存在性判断，代码比find更简洁。

1. count(key) // 统计key的个数，0/1
3. map<int, int> mp = {{1:10}};
4. cout << mp.count(1); // 输出1（键存在）
5. cout << mp.count(2); // 输出0（键不存在）
6. // 存在性判断：if (mp.count(key)) 等价于 if (mp.find(key) != mp.end())

复制代码

lower_bound /upper_bound（有序核心，按键二分）

利用 map 键的有序性实现按键的二分查找，时间复杂度 O(logN)，是比赛中 map 有序特性的高频用法，行为与 set 一致：

• lower_bound(key)：返回指向第一个键 ≥ key的键值对迭代器；
• upper_bound(key)：返回指向第一个键 > key的键值对迭代器。

1. map<int, int> mp = {{1:10}, {3:30}, {5:50}, {7:70}};
2. auto it1 = mp.lower_bound(3); // 键≥3，指向{3:30}
3. auto it2 = mp.lower_bound(4); // 键≥4，指向{5:50}
4. auto it3 = mp.upper_bound(3); // 键>3，指向{5:50}
5. auto it4 = mp.upper_bound(7); // 键>7，返回mp.end()

复制代码

begin /end/rbegin /rend（迭代器遍历）

返回双向迭代器，用于遍历 map 的键值对，遍历结果按键有序（正向升序，反向降序），遍历中可通过->first访问键、->second访问值。

1. begin() // 指向第一个键值对的正向迭代器
2. end() // 指向最后一个键值对下一个位置的正向迭代器
3. rbegin() // 指向最后一个键值对的反向迭代器
4. rend() // 指向第一个键值对前一个位置的反向迭代器
6. map<int, int> mp = {{3:30}, {1:10}, {2:20}};
7. // 正向遍历（按键升序）：1:10 → 2:20 → 3:30
8. for (auto it = mp.begin(); it != mp.end(); it++) {
9. cout << it->first << ":" << it->second << " ";
10. }
11. // 反向遍历（按键降序）：3:30 → 2:20 → 1:10
12. for (auto it = mp.rbegin(); it != mp.rend(); it++) {
13. cout << it->first << ":" << it->second << " ";
14. }
15. // 范围for遍历（推荐，简洁），按键升序
16. for (auto& p : mp) { // 用引用避免拷贝，提升效率
17. cout << p.first << ":" << p.second << " ";
18. }

复制代码

size /empty（基础容量判断）

时间复杂度均为 O(1)，比赛中高频使用，用于判断 map 是否为空、获取键值对个数。

1. size() // 返回map中键值对的个数
2. empty() // 判断是否为空，size=0返回true，否则false
4. map<int, int> mp = {{1:10}};
5. cout << mp.size(); // 输出1
6. cout << mp.empty(); // 输出false
7. mp.clear();
8. cout << mp.empty(); // 输出true

复制代码

clear /swap（基础操作）

• clear：清空所有键值对，size置 0，不释放底层红黑树内存，时间复杂度 O(N)；
• swap：交换两个 map 的所有键值对（仅交换红黑树的根节点指针），时间复杂度 O(1)。

1. clear() // 清空所有键值对
2. swap(mp) // 交换当前map与mp的所有键值对
4. map<int, int> mp1 = {{1:10}}, mp2 = {{2:20}};
5. mp1.swap(mp2);
6. cout << mp1.begin()->first; // 输出2
7. mp1.clear();
8. cout << mp1.size(); // 输出0

复制代码

equal_range

返回pair，包含lower_bound(key)和upper_bound(key)的迭代器，等价于一次性获取「键≥key」和「键 > key」的边界，比赛中常用于按键的区间查询，时间复杂度 O(logN)。

1. equal_range(key) // 返回pair<lower_bound(key), upper_bound(key)>
3. map<int, int> mp = {{1:10}, {3:30}, {5:50}};
4. auto [left, right] = mp.equal_range(3);
5. cout << left->first; // 输出3（键≥3的第一个元素）
6. cout << right->first; // 输出5（键>3的第一个元素）

复制代码

unordered_map

unordered_map 是 C++ STL 中无序键值对关联容器，底层基于哈希表（开散列 / 链地址法）实现，核心特性是「以 键值对存储数据、键唯一且无序存储、值可灵活修改」，插入、删除、按键查找的平均时间复杂度为 *O(1)*（最坏 O(N)，由哈希冲突导致）。与有序的 map（红黑树、O(logN) 查找）相比，unordered_map 的优势在于「极致的查找 / 插入 / 删除效率」，劣势是「键的无序性」，算法比赛中常用于仅需「高效键值映射 + 去重」且无需有序的场景（如频率统计、快速存在性判断、缓存映射）；若需键的有序性，需改用 map。

一、unordered_map 核心特性

1. 键值对存储：每个元素是键值对，键唯一标识元素，值可任意修改（键不可改，值可改）；
2. 键的唯一性：不允许重复键，插入重复键的键值对会被忽略，无报错；需重复键则用unordered_multimap；
3. 无序性：元素按键的哈希值存储，遍历结果随机（无固定顺序），无有序相关操作（如lower_bound）；
4. 哈希表底层：平均 O(1) 按键查找 / 插入 / 删除，最坏 O(N)（哈希冲突严重时）；支持自定义哈希函数和等价判断；
5. 前向迭代器：仅支持++it前向移动，不支持--it反向移动、it + n随机移动，无反向迭代器（rbegin()/rend()）；
6. 迭代器不稳定性：插入 / 删除元素可能触发哈希表扩容 / 桶结构变化，导致迭代器失效，需重新获取；
7. 专属值访问接口：提供[]和at()直接按键访问值（与 map 一致），[]会自动插入不存在的键，是高频坑点；
8. 无有序接口：因无序，无lower_bound/upper_bound/equal_range等二分查找函数。

二、unordered_map 初始化

初始化需包含头文件 ，核心围绕键值对展开，用法与 map 相似，仅无有序比较规则。

1. 空初始化

1. // 键为int、值为int的空unordered_map
2. unordered_map<int, int> ump;
3. // 键为string、值为int（统计字符串频率）
4. unordered_map<string, int> ump2;
5. // 键为char、值为int（统计字符频率）
6. unordered_map<char, int> ump3;

复制代码

2. 列表初始化（C++11+）

直接用{key, value}初始化，自动去重（无序）：

1. // 键int、值int，无序存储（如：{2:20, 1:10, 3:30}）
2. unordered_map<int, int> ump = {{3, 30}, {1, 10}, {2, 20}, {2, 200}}; // 重复键{2,200}被忽略
3. // 键char、值int，无序存储
4. unordered_map<char, int> ump2 = {{'b', 2}, {'a', 1}};

复制代码

3. 拷贝初始化

1. unordered_map<int, int> ump1 = {{1,10}, {2,20}};
2. // 拷贝ump1所有键值对（顺序可能与ump1不同）
3. unordered_map<int, int> ump2(ump1);
4. // 拷贝ump1[begin(), end())区间的键值对
5. unordered_map<int, int> ump3(ump1.begin(), ump1.end());

复制代码

4. 自定义键的初始化

存储自定义类型（如pair）作为键时，需自定义哈希函数（默认哈希函数不支持pair）：

1. // 自定义pair<int, int>的哈希函数
2. struct PairHash {
3. size_t operator()(const pair<int, int>& p) const {
4. // 组合两个int的哈希值（减少冲突）
5. return hash<int>()(p.first) ^ (hash<int>()(p.second) << 1);
6. }
7. };
9. // 键为pair<int,int>、值为int的unordered_map
10. unordered_map<pair<int, int>, int, PairHash> ump;
11. ump.insert({{1, 2}, 10}); // 插入键{1,2}，值10
12. ump[{3, 4}] = 20; // 用[]插入键{3,4}，值20

复制代码

三、常用函数

unordered_map 函数与 map 核心差异在于「无有序相关函数」，其余围绕键值对的操作基本一致，重点标注差异和高频坑点。

[]

按键访问对应的值，特性与 map 完全一致：若键不存在，会自动插入该键并将值初始化为默认值（int 为 0，string 为空），这是比赛中最易踩的坑。

1. ump[key] // 访问/修改key对应的值，键不存在则自动插入{key, 默认值}
3. unordered_map<int, int> ump = {{1, 10}, {2, 20}};
4. cout << ump[1]; // 访问键1的值，输出10
5. ump[2] = 200; // 修改键2的值，ump变为{{1:10}, {2:200}}
6. cout << ump[3]; // 键3不存在，自动插入{3:0}，输出0
7. cout << ump.size(); // 输出3（因插入了键3）

复制代码

at

按键访问对应的值，与[]的唯一区别：键不存在时抛出out_of_range异常，不会自动插入新键，比赛中少用（需捕获异常），但更安全。

1. ump.at(key) // 访问key对应的值，键不存在抛异常，支持读写
3. unordered_map<int, int> ump = {{1, 10}};
4. ump.at(1) = 100; // 修改键1的值，输出100
5. // ump.at(2); // 键2不存在，抛出out_of_range异常

复制代码

insert

插入键值对，重复键插入失败，返回值为pair（迭代器指向键值对，bool 表示是否插入成功）。

1. insert({key, value}) // 插入单个键值对
2. insert(begin, end) // 插入[begin,end)区间的pair类型键值对
4. unordered_map<int, int> ump;
5. // 插入新键值对，返回{指向{1:10}的迭代器, true}
6. auto res1 = ump.insert({1, 10});
7. // 插入重复键，返回{指向{1:10}的迭代器, false}
8. auto res2 = ump.insert({1, 100});
9. // 从vector<pair>插入区间键值对
10. vector<pair<int, int>> vec = {{2,20}, {3,30}};
11. ump.insert(vec.begin(), vec.end()); // ump存储{1:10, 2:20, 3:30}（无序）

复制代码

emplace

C++11 新增，原地构造键值对（无需拷贝 pair），效率高于insert，返回值与insert一致（pair）。

1. emplace(key_args..., value_args...) // 传入键和值的构造参数，原地构造
3. unordered_map<int, string> ump;
4. // 原地构造{1, "abc"}，等价于ump.insert({1, "abc"})，效率更高
5. ump.emplace(1, "abc");
6. // 键为string、值为int，原地构造{"test", 100}
7. unordered_map<string, int> ump2;
8. ump2.emplace("test", 100);

复制代码

erase（核心删除函数）

支持「按迭代器、按键、按区间」删除，行为与 map 一致。

1. erase(pos) // 删除迭代器pos指向的键值对（需保证迭代器有效）
2. erase(key) // 按键删除，返回删除个数（0/1）
3. erase(begin, end) // 删除[begin,end)区间的键值对
5. unordered_map<int, int> ump = {{1:10}, {2:20}, {3:30}};
6. // 按键删除：删除键2，返回1，ump移除{2:20}
7. int delCnt = ump.erase(2);
8. // 按迭代器删除：删除第一个键值对（随机，假设是1:10）
9. ump.erase(ump.begin());
10. // 按区间删除：删除剩余元素，ump为空
11. ump.erase(ump.begin(), ump.end());

复制代码

find

按键查找键值对，找到返回指向该键值对的迭代器，未找到返回ump.end()；迭代器可通过->first访问键、->second访问值。

1. find(key) // 按键查找键值对，返回前向迭代器
3. unordered_map<int, int> ump = {{1:10}, {2:20}};
4. auto it = ump.find(2);
5. if (it != ump.end()) {
6. cout << it->first; // 输出键2
7. cout << it->second; // 输出值20
8. }
9. auto it2 = ump.find(3); // 未找到，返回ump.end()

复制代码

count

按键统计键值对个数，因键唯一，返回值仅为0（不存在）或 1（存在），可替代find做存在性判断（代码更简洁）。

1. count(key) // 统计key的个数，0/1
3. unordered_map<int, int> ump = {{1:10}};
4. cout << ump.count(1); // 输出1（键存在）
5. cout << ump.count(2); // 输出0（键不存在）
6. // 存在性判断：if (ump.count(key)) 等价于 if (ump.find(key) != ump.end())

复制代码

begin /end（迭代器遍历）

返回前向迭代器，遍历顺序随机（无规律），无反向迭代器。

1. begin() // 指向第一个键值对的前向迭代器
2. end() // 指向最后一个键值对下一个位置的前向迭代器
4. unordered_map<int, int> ump = {{3:30}, {1:10}, {2:20}};
5. // 正向遍历（顺序随机，如：2:20 1:10 3:30）
6. for (auto it = ump.begin(); it != ump.end(); it++) {
7. cout << it->first << ":" << it->second << " ";
8. }
9. // 范围for遍历（推荐，简洁），顺序随机
10. for (auto& p : ump) { // 用引用避免拷贝，提升效率
11. cout << p.first << ":" << p.second << " ";
12. }

复制代码

size /empty

时间复杂度均为 O(1)。

1. size() // 返回键值对个数
2. empty() // 判断是否为空（size=0返回true）
4. unordered_map<int, int> ump = {{1:10}};
5. cout << ump.size(); // 输出1
6. cout << ump.empty(); // 输出false
7. ump.clear();
8. cout << ump.empty(); // 输出true

复制代码

clear / swap

• clear：清空所有键值对，size 置 0，释放哈希表内存，时间复杂度 O(N)；
• swap：交换两个 unordered_map 的内容（仅交换哈希表指针），时间复杂度 O(1)。

1. clear() // 清空所有键值对
2. swap(ump) // 交换当前unordered_map与ump的内容
4. unordered_map<int, int> ump1 = {{1:10}}, ump2 = {{2:20}};
5. ump1.swap(ump2);
6. cout << ump1.begin()->first; // 输出2（顺序随机）
7. ump1.clear();
8. cout << ump1.size(); // 输出0

复制代码

list

list 是 C++ STL 中基于双向循环链表实现的线性容器，核心特性是任意位置的插入 / 删除操作时间复杂度为 *O(1)*，但不支持随机访问，仅提供双向迭代器。与 vector（连续内存、随机访问优、插入删除差）、deque（双端操作优、随机访问支持）相比，list 的优势在于频繁的任意位置增删操作，算法比赛中常用于需要「链表模拟」「频繁插入删除且无需随机访问」的场景（如约瑟夫环问题、数据的动态增删维护）。

一、list 核心特性

1. 双向链表底层：每个节点包含数据、前驱指针、后继指针，物理内存非连续，逻辑上双向有序，任意位置插入 / 删除仅需修改指针，时间复杂度 O(1)（需先找到目标位置，找位置为 O(N)）；
2. 无随机访问：不支持下标 []/at() 操作，无法直接通过索引访问元素，仅能通过迭代器遍历，访问指定位置元素需从头部 / 尾部遍历，时间复杂度 O(N)；
3. 双向迭代器：支持 ++it/--it 双向移动，不支持随机移动（it + n/it - n 非法），迭代器高度稳定—— 插入 / 删除元素时，除被删除元素的迭代器外，其他所有迭代器均不会失效（vector/deque 插入删除会导致迭代器失效）；
4. 无需扩容：节点按需动态分配，无固定容量，插入元素时直接创建新节点，无内存拷贝开销（区别于 vector 的扩容拷贝）；
5. 专属排序 / 合并函数：因不支持随机访问迭代器，无法使用 STL 全局sort算法，需使用自身的sort()成员函数；还提供merge/splice/remove等链表专属操作，效率高于通用算法；
6. 内存碎片：节点分散存储，频繁增删可能产生内存碎片，但对算法比赛的小规模数据影响可忽略；
7. 元素可重复：默认允许存储重复元素，无自动去重特性（需手动实现）。

二、list 初始化

初始化需包含头文件 ，语法与 vector/deque 基本一致，无随机访问相关的特殊初始化方式。

1. 空初始化

1. // 初始化存储int类型的空list
2. list<int> l;
3. // 初始化存储string类型的空list
4. list<string> l2;

复制代码

2. 指定大小初始化

1. // 初始化大小为5的int类型list，所有元素默认初始化为0
2. list<int> l1(5);
3. // 初始化大小为5的int类型list，所有元素初始化为3
4. list<int> l2(5, 3);
5. // 初始化大小为3的string类型list，所有元素初始化为"abc"
6. list<string> l3(3, "abc");

复制代码

3. 列表初始化（C++11+）

1. // 直接初始化并赋值，元素按顺序存储
2. list<int> l = {1, 2, 3, 4, 5};
3. // 简化写法（C++17+）
4. list l = {5, 4, 3, 2, 1};

复制代码

4. 拷贝初始化

1. list<int> l1 = {1, 2, 3};
2. // 拷贝l1的所有元素生成l2
3. list<int> l2(l1);
4. // 拷贝l1中[begin(), end())区间的元素（等价于l3(l1)）
5. list<int> l3(l1.begin(), l1.end());
6. // 拷贝l1中从迭代器l1.begin()+1到l1.end()-1的元素（需手动遍历定位，无随机访问）
7. list<int> l4(++l1.begin(), --l1.end()); // l4 = {2}

复制代码

5. 其他容器转换初始化

1. // 从vector初始化（按vector顺序存储）
2. vector<int> vec = {1, 2, 2, 3};
3. list<int> l(vec.begin(), vec.end()); // l = {1,2,2,3}
4. // 从数组初始化
5. int a[] = {10, 20, 30};
6. list<int> l2(a, a + 3); // l2 = {10,20,30}

复制代码

三、常用函数

list 的函数分为通用操作（与 vector/deque 一致）和链表专属操作，核心差异集中在插入删除（任意位置高效）、访问（无随机访问）、排序 / 合并（专属函数），按比赛使用频率排序。

（一）元素插入

push_back

在 list 尾部插入元素，仅需修改尾节点指针，时间复杂度 O(1)。

1. push_back(val) // 将元素val插入到list尾部
2. list<int> l = {1,2};
3. l.push_back(3); // l变为{1,2,3}

复制代码

push_front

在 list 头部插入元素，仅需修改头节点指针，时间复杂度 O(1)（vector 无此函数，deque 有但底层实现不同）。

1. push_front(val) // 将元素val插入到list头部
2. list<int> l = {2,3};
3. l.push_front(1); // l变为{1,2,3}

复制代码

emplace_back / emplace_front（C++11+）

原地构造元素，无需拷贝 / 移动，效率高于push_back/push_front，时间复杂度 O(1)，用法一致。

1. emplace_back(args...) // 尾部原地构造元素
2. emplace_front(args...) // 头部原地构造元素
3. list<pair<int, string>> l;
4. l.emplace_back(1, "abc"); // 尾部构造{1,"abc"}
5. l.emplace_front(2, "def"); // 头部构造{2,"def"}，l变为{{2,"def"}, {1,"abc"}}

复制代码

insert

在迭代器指定位置插入元素 / 区间，插入操作本身 O (1)（仅修改指针），需先通过迭代器定位目标位置（定位为 O(N)），支持三种形式。

1. insert(pos, val) // 在迭代器pos位置插入单个元素val
2. insert(pos, n, val) // 在pos位置插入n个值为val的元素
3. insert(pos, begin, end) // 在pos位置插入[begin,end)区间的元素
4. list<int> l = {1,3};
5. auto it = ++l.begin(); // 定位到元素3的位置
6. l.insert(it, 2); // 插入2，l变为{1,2,3}
7. l.insert(l.end(), 2, 4); // 尾部插入2个4，l变为{1,2,3,4,4}
8. vector<int> vec = {5,6};
9. l.insert(l.begin(), vec.begin(), vec.end()); // 头部插入vec，l变为{5,6,1,2,3,4,4}

复制代码

（二）元素删除

pop_back

删除 list 尾部元素，仅需修改尾节点指针，时间复杂度 O(1)，无返回值。

1. pop_back() // 删除尾部元素
2. list<int> l = {1,2,3};
3. l.pop_back(); // l变为{1,2}

复制代码

pop_front

删除 list 头部元素，仅需修改头节点指针，时间复杂度 O(1)，无返回值。

1. pop_front() // 删除头部元素
2. list<int> l = {1,2,3};
3. l.pop_front(); // l变为{2,3}

复制代码

erase（任意位置删除，核心函数）

删除迭代器指定位置 / 区间的元素，删除操作本身 O (1)，需先定位（定位 O(N)），支持两种形式。

1. erase(pos) // 删除迭代器pos指向的单个元素，返回指向删除位置下一个元素的迭代器
2. erase(begin, end) // 删除[begin,end)区间的元素，返回指向区间末尾下一个元素的迭代器
3. list<int> l = {1,2,3,4};
4. auto it = ++l.begin(); // 定位到2
5. it = l.erase(it); // 删除2，返回指向3的迭代器，l变为{1,3,4}
6. l.erase(it, l.end()); // 删除从3到末尾的元素，l变为{1}

复制代码

remove /remove_if（链表专属，比赛偶用）

remove：删除所有值为 val的元素，时间复杂度 O(N)；

remove_if：删除满足条件的所有元素，传入谓词（函数 /lamdba），时间复杂度 O(N)。

1. remove(val) // 删除所有值为val的元素
2. remove_if(pred) // 删除满足谓词pred的所有元素
3. list<int> l = {1,2,2,3,2};
4. l.remove(2); // 删除所有2，l变为{1,3}
5. l.remove_if([](int x) { return x < 2; }); // 删除所有小于2的元素，l变为{3}

复制代码

（三）元素访问（无随机访问，仅首尾 + 迭代器）

list无下标 []/at ()，仅能通过front()/back()访问首尾元素，或通过迭代器遍历访问中间元素，所有访问操作均为 O(1)（遍历定位为 O(N)）。

front

返回 list 头部元素的引用，支持读写，调用前需判空（否则未定义行为）。

1. front() // 返回头部元素的引用
2. list<int> l = {1,2,3};
3. cout << l.front(); // 输出1
4. l.front() = 10; // 修改头部元素，l变为{10,2,3}

复制代码

back

返回 list 尾部元素的引用，支持读写，调用前需判空（否则未定义行为）。

1. back() // 返回尾部元素的引用
2. list<int> l = {1,2,3};
3. cout << l.back(); // 输出3
4. l.back() = 30; // 修改尾部元素，l变为{1,2,30}

复制代码

（四）容量与判断（通用操作，O(1)）

size

返回 list 中当前元素的个数，时间复杂度 O(1)（C++11 后，早期 STL 为 O(N)，比赛编译器均支持 C++11+）。

1. size() // 返回元素个数
2. list<int> l = {1,2,3};
3. cout << l.size(); // 输出3

复制代码

empty

判断 list 是否为空（size=0），返回 bool 值，调用 front ()/back ()/pop_()/erase () 前必须判空，时间复杂度 O(1)。

1. empty() // 空返回true，非空返回false
2. list<int> l;
3. cout << l.empty(); // 输出true
4. l.push_back(1);
5. cout << l.empty(); // 输出false

复制代码

clear

清空 list 所有元素，释放所有节点内存，size 置 0，时间复杂度 O(N)。

1. clear() // 清空所有元素
2. list<int> l = {1,2,3};
3. l.clear();
4. cout << l.size(); // 输出0

复制代码

resize

调整 list 的元素个数，扩容时在尾部插入默认 / 指定值的元素，缩容时删除尾部多余元素。

1. resize(n) // 调整size为n，新增元素默认初始化
2. resize(n, val) // 调整size为n，新增元素初始化为val
3. list<int> l = {1,2};
4. l.resize(4, 5); // 扩容，l变为{1,2,5,5}
5. l.resize(2); // 缩容，l变为{1,2}

复制代码

（五）迭代器（双向迭代器，仅支持 ++/–）

list 仅提供双向迭代器，无随机访问迭代器，支持正向 / 反向遍历，无法使用it + n等随机移动操作，迭代器获取函数与其他容器一致。

1. begin() // 指向第一个元素的正向双向迭代器
2. end() // 指向最后一个元素下一个位置的正向双向迭代器
3. rbegin() // 指向最后一个元素的反向双向迭代器
4. rend() // 指向第一个元素前一个位置的反向双向迭代器
5. // 正向遍历（仅++it）
6. list<int> l = {1,2,3};
7. for (auto it = l.begin(); it != l.end(); ++it) {
8. cout << *it << " "; // 输出1 2 3
9. }
10. // 反向遍历（仅++it，反向迭代器的++等价于正向的--）
11. for (auto it = l.rbegin(); it != l.rend(); ++it) {
12. cout << *it << " "; // 输出3 2 1
13. }
14. // 范围for遍历（推荐，简洁）
15. for (int x : l) cout << x << " ";

复制代码

（六）链表专属操作

sort（专属排序函数，必须用此而非 STL 全局 sort）

list无法使用sort(l.begin(), l.end())（全局 sort 需要随机访问迭代器），需使用自身的sort()成员函数，底层基于归并排序，时间复杂度 O(NlogN)，支持自定义比较规则。

1. sort() // 默认按升序排序
2. sort(cmp) // 按自定义比较规则cmp排序
3. list<int> l = {3,1,2,5,4};
4. l.sort(); // 升序，l变为{1,2,3,4,5}
5. l.sort(greater<int>()); // 降序，l变为{5,4,3,2,1}
6. // 自定义规则：按绝对值升序
7. l.sort([](int a, int b) { return abs(a) < abs(b); });

复制代码

swap

交换两个 list 的所有内容，仅需交换头 / 尾指针，时间复杂度 O(1)（区别于 vector 的元素拷贝）。

1. swap(l) // 交换当前list与l的所有元素
2. list<int> l1 = {1,2}, l2 = {3,4};
3. l1.swap(l2);
4. cout << l1.front(); // 输出3

复制代码

merge

将另一个有序 list合并到当前 list，合并后原 list 保持有序，另一个 list 变为空，支持自定义比较规则，时间复杂度 O(N+M)

1. merge(l) // 合并有序list l，默认升序
2. merge(l, cmp) // 按自定义规则合并有序list l
3. list<int> l1 = {1,3,5}, l2 = {2,4,6};
4. l1.merge(l2); // 合并后l1={1,2,3,4,5,6}，l2为空

复制代码

reverse

反转 list 的所有元素，仅需修改节点的前驱 / 后继指针，时间复杂度 O(N)。

1. reverse() // 反转list
2. list<int> l = {1,2,3};
3. l.reverse(); // l变为{3,2,1}

复制代码

总结

STL常用函数

函数名	函数声明	返回值	函数作用	时间复杂度
sort	sort(begin, end) sort(begin, end, cmp)	无	对 [begin,end) 区间内的序列排序，默认升序；cmp 为自定义比较规则（可选），仅支持随机访问迭代器 / 数组	O(NlogN)
stable_sort	stable_sort(begin, end) stable_sort(begin, end, cmp)	无	稳定排序（保留相等元素原始相对顺序），用法同 sort，内部基于归并排序，仅支持随机访问迭代器 / 数组	O(NlogN)
lower_bound	lower_bound(begin, end, x) lower_bound(begin, end, x, cmp)	迭代器 / 指针	在有序 [begin,end) 区间中查找第一个≥x 的元素位置；cmp 为排序规则（可选），需与区间排序规则一致	O(logN)
upper_bound	upper_bound(begin, end, x) upper_bound(begin, end, x, cmp)	迭代器 / 指针	在有序 [begin,end) 区间中查找第一个 > x 的元素位置；cmp 为排序规则（可选），需与区间排序规则一致	O(logN)
find	find(begin, end, v)	迭代器 / 指针	在 [begin,end) 区间中线性查找第一个等于 v 的元素位置，支持所有可迭代容器	O(N)
max	max(a, b) max(a, b, cmp) max({元素列表}) max({元素列表}, cmp)	与输入元素同类型	返回两个元素 / 元素列表中的最大值；cmp 为比较规则（可选），C++11 + 支持列表参数	O(1)（两元素）O(N)（列表）
min	min(a, b) min(a, b, cmp) min({元素列表}) min({元素列表}, cmp)	与输入元素同类型	返回两个元素 / 元素列表中的最小值；cmp 为比较规则（可选），C++11 + 支持列表参数	O(1)（两元素）O(N)（列表）
minmax	minmax(a, b) minmax(a, b, cmp) minmax({元素列表}) minmax({元素列表}, cmp)	pair <元素类型，元素类型>	返回 pair（第一个为最小值，第二个为最大值）；cmp 为比较规则（可选），C++11 + 支持列表参数	O(1)（两元素）O(N)（列表）
max_element	max_element(begin, end) max_element(begin, end, cmp)	迭代器 / 指针	返回 [begin,end) 区间内最大值的迭代器 / 指针；cmp 为比较规则（可选）	O(N)
min_element	min_element(begin, end) min_element(begin, end, cmp)	迭代器 / 指针	返回 [begin,end) 区间内最小值的迭代器 / 指针；cmp 为比较规则（可选）	O(N)
minmax_element	minmax_element(begin, end) minmax_element(begin, end, cmp)	pair <迭代器，迭代器>	返回 pair（第一个为最小值迭代器，第二个为最大值迭代器）；cmp 为比较规则（可选）	O(N)
nth_element	nth_element(begin, nth, end) nth_element(begin, nth, end, cmp)	无	将 [begin,end) 中第 n 小的元素放到 nth 位置，左侧≤该元素、右侧≥该元素；cmp 为比较规则（可选）	平均O(N)
accumulate	accumulate(begin, end, init) accumulate(begin, end, init, op)	与 init 同类型	以 init 为初始值，累加 [begin,end) 区间元素；op 为自定义二元操作（可选，默认加法）	O(N)
reverse	reverse(begin, end)	无	翻转 [begin,end) 区间内的元素顺序	O(N)
__gcd	__gcd(a, b)	整数类型	返回两个整数的最大公约数；C++17 + 可省略下划线，仅 GCC/Clang 支持	O(log(min(a,b)))
__lcm	__lcm(a, b)	整数类型	返回两个整数的最小公倍数；仅 GCC/Clang 支持，用法同__gcd	O(log(min(a,b)))
set_union	set_union(abegin, aend, bbegin, bend, outbegin) set_union(abegin, aend, bbegin, bend, outbegin, cmp)	迭代器	求两个有序区间的并集，结果写入 outbegin 起始位置；cmp 为比较规则（可选）	O(N+M)
set_intersection	set_intersection(abegin, aend, bbegin, bend, outbegin) set_intersection(abegin, aend, bbegin, bend, outbegin, cmp)	迭代器	求两个有序区间的交集，结果写入 outbegin 起始位置；cmp 为比较规则（可选）	O(N+M)
set_difference	set_difference(abegin, aend, bbegin, bend, outbegin) set_difference(abegin, aend, bbegin, bend, outbegin, cmp)	迭代器	求两个有序区间的差集（A-B），结果写入 outbegin 起始位置；cmp 为比较规则（可选）	O(N+M)
stoi	stoi(s)	int	将合法数字字符串 s 转换为 int 类型，非法字符串会抛出异常	O(len(s))
stoll	stoll(s)	long long	将合法数字字符串 s 转换为 long long 类型，非法字符串会抛出异常	O(len(s))
stof	stof(s)	float	将合法数字字符串 s 转换为 float 类型，非法字符串会抛出异常	O(len(s))
stod	stod(s)	double	将合法数字字符串 s 转换为 double 类型，非法字符串会抛出异常	O(len(s))
to_string	to_string(num)	string	将数字（int/long long/float/double 等）转换为对应的字符串	数字位数
transform	transform(ibegin, iend, obegin, op) transform(ibegin1, iend1, ibegin2, obegin, op)	迭代器	将输入区间元素按 op 规则转换，结果写入 obegin；op 可为一元 / 二元操作（可选）	O(N)
unique	unique(begin, end) unique(begin, end, cmp)	迭代器 / 指针	移除有序 [begin,end) 区间内的连续重复元素，返回去重后末尾的下一个位置；cmp 为比较规则（可选）	O(N)
count	count(begin, end, v)	int	统计 [begin,end) 区间内值等于 v 的元素个数	O(N)
count_if	count_if(begin, end, cmp)	int	统计 [begin,end) 区间内满足 cmp 条件的元素个数（cmp 返回 bool）	O(N)
fill	fill(begin, end, v)	无	将 [begin,end) 区间内的所有元素赋值为 v	O(N)
is_sorted	is_sorted(begin, end) is_sorted(begin, end, cmp)	bool	判断 [begin,end) 区间是否按 cmp 规则有序（默认升序），有序返回 true	O(N)
iota	iota(begin, end, init)	无	从 init 开始，为 [begin,end) 区间元素依次赋值为 init、init+1、init+2…（仅支持 + 1 递增）	O(N)
generate	generate(begin, end, gen)	无	按 gen 无参函数的返回值，为 [begin,end) 区间元素赋值（支持自定义生成逻辑）	O(N)
next_permutation	next_permutation(begin, end) next_permutation(begin, end, cmp)	bool	将 [begin,end) 重排为字典序下一个更大排列；成功返回 true，失败则重置为最小排列并返回 false；cmp 为比较规则（可选）	O(N)（单次）
prev_permutation	prev_permutation(begin, end) prev_permutation(begin, end, cmp)	bool	将 [begin,end) 重排为字典序上一个更小排列；成功返回 true，失败则重置为最大排列并返回 false；cmp 为比较规则（可选）	O(N)（单次）
__lg	__lg(x)	int	返回无符号整数 x 的最高有效位位置（等价于 floor (log2 (x))）；仅 GCC/Clang 支持，x=0 行为未定义	O(1)
ranges::sort	ranges::sort(range) ranges::sort(range, cmp)	无	C++20 简化版 sort，直接传入容器（无需 begin/end），默认升序；cmp 为比较规则（可选）	O(NlogN)
ranges::max_element	ranges::max_element(range) ranges::max_element(range, cmp)	迭代器	C++20 简化版 max_element，直接传入容器（无需 begin/end）；cmp 为比较规则（可选）	O(N)
ranges::min_element	ranges::min_element(range) ranges::min_element(range, cmp)	迭代器	C++20 简化版 min_element，直接传入容器（无需 begin/end）；cmp 为比较规则（可选）	O(N)

vector

函数名	函数声明	返回值	函数作用	时间复杂度
push_back	push_back(v)	无	在 vector 尾部添加元素 v；若当前容量不足，触发自动扩容（通常扩容为原容量 2 倍）	均摊O(1)（扩容时为O(N)）
emplace_back	emplace_back(args...)	无	C++11 新增，在 vector 尾部直接构造元素（传入元素的构造参数 args…），避免拷贝 / 移动开销，效率优于 push_back	均摊O(1)（扩容时为O(N)）
insert	insert(pos, val) insert(pos, n, val) insert(pos, begin, end)	迭代器（指向插入的第一个元素）	在迭代器 pos 位置插入：单个元素 val、n 个 val 元素、[begin,end) 区间的元素；插入位置后元素向后移动	O(N)（元素移动开销）
pop_back	pop_back()	无	删除 vector 最后一个元素；仅减少元素个数（size），不释放已分配的内存（capacity 不变）	O(1)
erase	erase(pos) erase(begin, end)	迭代器（指向删除位置的下一个元素）	删除迭代器 pos 位置的单个元素、[begin,end) 区间的元素；删除位置后元素向前移动	O(N)（元素移动开销）
front	front()	vector 首个元素的引用	返回第一个元素的引用，支持直接读写该元素（无越界检查）	O(1)
back	back()	vector 末尾元素的引用	返回最后一个元素的引用，支持直接读写该元素（无越界检查）	O(1)
at	at(idx)	vector 下标 idx 处元素的引用	返回指定下标元素的引用；做下标越界检查，越界抛出 out_of_range 异常，比 [] 更安全	O(1)
size	size()	size_t（无符号整数）	返回 vector 当前的元素个数	O(1)
empty	empty()	bool（true 为空，false 非空）	判断 vector 是否为空（元素个数为 0）	O(1)
clear	clear()	无	清空 vector 所有元素；仅将 size 置 0，已分配的内存（capacity）不变	O(N)
reserve	reserve(n)	无	预分配至少能存储 n 个元素的内存；size 不变，capacity 至少为 n，避免频繁扩容导致的拷贝开销	O(1)（无需扩容）O(N)（需扩容时拷贝元素）
assign	assign(n, val) assign(begin, end)	无	先清空 vector 原有所有元素，再替换为：n 个值为 val 的元素、[begin,end) 区间的元素	O(N)
resize	resize(n) resize(n, val)	无	调整 vector 的元素个数（size）为 n：1. n > 原 size：新增元素（默认初始化 / 初始化为 val）；2. n < 原 size：删除末尾多余元素	O(n-原size)

string

函数名	函数声明	返回值	函数作用	时间复杂度
push_back	push_back(c)	无	在字符串尾部添加单个字符 c；容量不足时触发自动扩容	均摊（扩容时为）
pop_back	pop_back()	无	删除字符串最后一个字符；仅减少长度（size），不释放内存（capacity 不变）	O(1)
append	append(str)``append(n, c)``append(begin, end)	string&（自身引用）	尾部拼接：字符串 str、n 个字符 c、[begin,end) 区间的字符；比 + 更高效	（为拼接内容的长度）
insert	insert(pos, str)``insert(pos, n, c)``insert(pos, begin, end)	string&（自身引用）	在下标 pos 位置插入：字符串 str、n 个字符 c、[begin,end) 区间的字符；插入位置后字符后移	（为字符串总长度，字符移动开销）
erase	erase(pos)``erase(pos, len)``erase(begin, end)	string&（自身引用）	删除：从下标 pos 到末尾的字符、pos 开始的 len 个字符、[begin,end) 区间的字符；删除位置后字符前移	（为字符串总长度，字符移动开销）
substr	substr(pos, len)	string（新字符串）	截取从下标 pos 开始的 len 个字符；len 省略则截取到末尾（左闭右开）	（为截取长度）
find	find(str, pos)``find(c, pos)	size_t（下标值；未找到返回 string::npos）	从下标 pos（省略则从 0）开始，从左到右查找 str/ 字符 c 首次出现的位置	（为字符串长度，为查找串长度）
rfind	rfind(str, pos)	size_t（下标值；未找到返回 string::npos）	从下标 pos（省略则到末尾）开始，从右到左查找 str 最后一次出现的位置	（为字符串长度，为查找串长度）
replace	replace(pos, len, str)``replace(begin, end, str)	string&（自身引用）	替换：pos 开始的 len 个字符、[begin,end) 区间的字符为字符串 str	（为字符串总长度）
size / length	size()``length()	size_t（无符号整数）	两者功能完全一致，返回字符串的字符个数（不含结束符 \0）	O(1)
empty	empty()	bool（true 为空，false 非空）	判断字符串是否为空（字符个数为 0）	O(1)
clear	clear()	无	清空字符串所有字符；仅将 size 置 0，已分配的内存（capacity）不变	（析构所有字符，为原字符个数）
reserve	reserve(n)	无	预分配至少能存储 n 个字符的内存；size 不变，capacity 至少为 n，避免频繁扩容拷贝	（无需扩容）（需扩容时拷贝字符）
resize	resize(n)``resize(n, c)	无	调整字符串的字符个数（size）为 n：1. 原 < n：新增字符（默认 \0/ 指定为 c）；2. 原 > n：删除末尾多余字符	原
at	at(idx)	char&（字符引用）	返回下标 idx 处的字符引用；做越界检查，越界抛出 out_of_range 异常，比 [] 更安全	O(1)
front / back	front()``back()	char&（字符引用）	front() 返回首个字符引用，back() 返回末尾字符引用；均可直接读写	O(1)
c_str	c_str()	const char*（C 风格字符串指针）	返回以 \0 结尾的 C 风格字符数组，适配 printf 等 C 接口	O(1)
compare	compare(str)	int	比较当前字符串与 str 的字典序：- 返回 0：两字符串相等；- 返回正数：当前字符串 > str；- 返回负数：当前字符串 < str	（为当前字符串长度，为长度）
to_string	to_string(num)	string	将数字（int/long long/double 等）转换为字符串	数字位数
stoi / stoll / stod	stoi(s)``stoll(s)``stod(s)	对应数值类型（int/long long/double）	将合法的数字字符串 s 转换为对应数值类型	（为字符串长度）

stack

函数名	函数声明	返回值	函数作用	时间复杂度
push	push(val)	无	将元素 val 压入栈顶，底层调用底层容器的 push_back 实现	O(1)
emplace	emplace(args...)	无	C++11 新增，在栈顶原地构造元素（传入构造参数 args…），避免拷贝 / 移动开销，效率高于 push	O(1)
pop	pop()	无	删除栈顶元素，无返回值；调用前必须判空，否则行为未定义	O(1)
top	top()	栈内元素类型的引用	返回栈顶元素的引用，支持直接读写；调用前必须判空，否则行为未定义	O(1)
size	size()	size_t（无符号整数）	返回栈中当前的元素个数	O(1)
empty	empty()	bool（true为空，false非空）	判断栈是否为空，是调用 top/pop 前的最好用这个检查一下	O(1)
swap	swap(st)	无	交换当前栈与栈 st 的所有内容（包括底层容器的元素），仅交换底层容器指针	O(1)

queue

函数名	函数声明	返回值	函数作用	时间复杂度
push	push(val)	无	将元素 val 压入队尾，底层调用底层容器的 push_back 实现	O(1)
emplace	emplace(args...)	无	C++11 新增，在队尾原地构造元素（传入构造参数 args...），避免拷贝 / 移动开销，效率高于 push	O(1)
pop	pop()	无	删除队首元素，无返回值；调用前必须判空，否则行为未定义	O(1)
front	front()	队列元素类型的引用	返回队首元素的引用，支持读写；调用前必须判空，否则行为未定义	O(1)
back	back()	队列元素类型的引用	返回队尾元素的引用，支持读写；调用前必须判空，否则行为未定义	O(1)
size	size()	size_t（无符号整数）	返回队列中当前的元素个数	O(1)
empty	empty()	bool（true 为空，false 非空）	判断队列是否为空，是调用 front/back/pop 前的必做检查	O(1)
swap	swap(q)	无	交换当前队列与队列 q 的所有内容（包括底层容器的元素），仅交换底层容器指针	O(1)

priority_queue

函数名	函数声明	返回值	函数作用	时间复杂度
push	push(val)	void	插入元素 val 到优先队列，自动调整堆结构（默认大顶堆），保证队首始终是优先级最高的元素（默认最大值）	O(logN)
emplace	emplace(args...)	void	C++11 新增，原地构造元素并插入优先队列（避免拷贝 / 移动开销），效率高于 push；插入后自动调整堆结构	O(logN)
pop	pop()	void	弹出队首（优先级最高）元素，无返回值；调用前必须通过 empty () 判空，否则行为未定义	O(logN)
top	top()	元素类型的引用（T& /const T&）	返回队首（优先级最高）元素的引用；调用前必须判空，支持修改但不推荐（会破坏堆结构），默认大顶堆返回最大值	O(1)
size	size()	size_t（无符号整数）	返回优先队列中元素的总个数	O(1)
empty	empty()	bool（true 为空，false 非空）	判断优先队列是否为空，是调用 top()/pop() 前的必做检查（避免未定义行为）	O(1)
swap	swap(pq)	void	交换当前优先队列与 pq 的所有内容（包括堆结构和底层容器，优先队列底层默认用 vector 实现）	O(1)

deque

函数名	函数声明	返回值	函数作用	时间复杂度
push_back	push_back(val)	void	在 deque 尾部添加元素 val；底层按需分配内存块，无需整体扩容	O(1)
push_front	push_front(val)	void	deque 核心特性，在头部添加元素 val；效率远优于 vector 队首插入	O(1)
emplace_back	emplace_back(args...)	void	C++11 新增，在尾部原地构造元素（传入构造参数 args…），避免拷贝 / 移动开销，效率高于 push_back	O(1)
emplace_front	emplace_front(args...)	void	C++11 新增，在头部原地构造元素（传入构造参数 args…），效率高于 push_front	O(1)
pop_back	pop_back()	void	删除 deque 尾部元素；调用前需判空	O(1)
pop_front	pop_front()	void	deque 核心特性，删除头部元素；效率远优于 vector 队首删除，调用前需判空	O(1)
insert	insert(pos, val)``insert(pos, n, val)``insert(pos, begin, end)	迭代器（指向插入的第一个元素）	在迭代器 pos 位置插入：单个元素 val、n 个 val 元素、[begin,end) 区间元素；插入后元素后移，中间插入效率略优于 vector	O（1）（两端插入）/O（N)（中间插入）
erase	erase(pos)``erase(begin, end)	迭代器（指向删除位置的下一个元素）	删除迭代器 pos 位置的元素、[begin,end) 区间的元素；删除后元素前移	O(1)（两端删除）/O(N)（中间删除）
front	front()	元素类型的引用（T&）	返回头部元素的引用（可读写）；调用前必须通过 empty () 判空	O(1)
back	back()	元素类型的引用（T&）	返回尾部元素的引用（可读写）；调用前必须通过 empty () 判空	O(1)
at	at(idx)	元素类型的引用（T&）	返回下标 idx 处元素的引用；做越界检查，越界抛出 out_of_range 异常，比 [] 更安全	O(1)
size	size()	size_t（无符号整数）	返回 deque 当前的元素个数	O(1)
empty	empty()	bool（true 为空，false 非空）	判断 deque 是否为空；调用 front/back/pop_front/pop_back 前必查	O(1)
clear	clear()	void	清空所有元素，size 置 0；不释放底层分段内存，仅析构元素	O(N)
resize	resize(n)``resize(n, val)	void	调整元素个数为 n：1. n > 原 size：新增元素（默认初始化 / 指定为 val）；2. n < 原 size：删除末尾多余元素	O(n - 原 size)
swap	swap(dq)	void	交换当前 deque 与 dq 的所有内容（仅交换分段内存指针），效率极高	O(1)
begin/end	begin()/end()	正向随机访问迭代器（begin 指向首元素，end 指向尾后）	用于正向遍历、sort/reverse 等 STL 算法	O(1)（获取迭代器）
rbegin/rend	rbegin()/rend()	反向随机访问迭代器（rbegin 指向尾元素，rend 指向首前）	用于反向遍历 deque 元素	O(1)（获取迭代器）

set

函数名	函数声明	返回值	函数作用	时间复杂度
insert	insert(val) insert(begin, end)	insert(val)：pair（迭代器指向元素，bool 表示是否插入成功）；insert(begin,end)：void	插入单个元素 val（重复则忽略）、插入 [begin,end) 区间元素（自动去重 + 排序）	O(logN)（单个插入）；O(k*logN)（k为区间元素个数）
emplace	emplace(args...)	pair（同 insert (val)）	C++11 新增，原地构造并插入元素，效率高于 insert	O(logN)
erase	erase(pos) erase(val) erase(begin, end)	erase(pos)：void；erase(val)：size_t（删除个数，set 中 0/1）；erase(begin,end)：void	删除迭代器 pos 指向的元素、删除值为 val 的元素、删除 [begin,end) 区间元素	O(logN)（单个删除）；O(k*logN)（k为区间元素个数）
find	find(val)	iterator（找到则指向元素，否则返回 end ()）	查找值为 val 的元素	O(logN)
count	count(val)	size_t（set 中 0/1，multiset 中为重复次数）	统计值为 val 的元素个数	O(logN)
lower_bound	lower_bound(val)	iterator（指向第一个≥val 的元素，无则返回 end ()）	查找有序集合中第一个≥val 的元素	O(logN)
upper_bound	upper_bound(val)	iterator（指向第一个 > val 的元素，无则返回 end ()）	查找有序集合中第一个 > val 的元素	O(logN)
equal_range	equal_range(val)	pair（first=lower_bound(val)，second=upper_bound(val)）	获取≥val 和 > val 的迭代器边界	O(logN)
begin/end	begin()/end()	正向迭代器（begin () 指向首元素，end () 指向尾后）	用于正向遍历，遍历结果升序	O(1)
rbegin/rend	rbegin()/rend()	反向迭代器（rbegin () 指向尾元素，rend () 指向首前）	用于反向遍历，遍历结果降序	O(1)
size	size()	size_t（无符号整数）	返回 set 中元素个数	O(1)
empty	empty()	bool（true 为空，false 非空）	判断 set 是否为空	O(1)
clear	clear()	void	清空所有元素，size 置 0	O(N)
swap	swap(st)	void	交换当前 set 与 st 的所有内容	O(1)
front/back	front()/back()	元素类型的引用（C++11 新增）	返回第一个 / 最后一个元素的引用，调用前需判空	O(1)

multiset

函数名	函数声明	返回值	函数作用	时间复杂度
insert	insert(val) insert(begin, end)	insert(val)：iterator（指向插入的元素）；insert(begin,end)：void	插入单个元素 val（允许重复）、插入 [begin,end) 区间元素（保留重复 + 排序）	O(logN)（单个插入）；O(k*logN)（k为区间元素个数）
emplace	emplace(args...)	iterator（指向插入的元素）	C++11 新增，原地构造并插入元素（允许重复），效率高于 insert	O(logN)
erase	erase(pos) erase(val) erase(begin, end)	erase(pos)：void；erase(val)：size_t（删除的重复元素个数）；erase(begin,end)：void	删除迭代器 pos 指向的单个元素、删除所有值为 val 的元素、删除 [begin,end) 区间元素	O(logN)（单个删除）；O(k*logN)（k为区间元素个数）
find	find(val)	iterator（找到则指向第一个 val，否则返回 end ()）	查找第一个值为 val 的元素	O(logN)
count	count(val)	size_t（val 的重复元素总个数）	统计值为 val 的元素个数（核心区别于 set）	（为重复次数）
lower_bound	lower_bound(val)	iterator（指向第一个≥val 的元素，无则返回 end ()）	查找有序集合中第一个≥val 的元素	O(logN)
upper_bound	upper_bound(val)	iterator（指向第一个 > val 的元素，无则返回 end ()）	查找有序集合中第一个 > val 的元素	O(logN)
equal_range	equal_range(val)	pair（first=lower_bound(val)，second=upper_bound(val)）	获取所有值为 val 的元素的迭代器区间	O(logN)
begin/end	begin()/end()	正向迭代器（begin () 指向首元素，end () 指向尾后）	用于正向遍历，重复元素连续排列	O(1)
rbegin/rend	rbegin()/rend()	反向迭代器（rbegin () 指向尾元素，rend () 指向首前）	用于反向遍历，重复元素连续排列	O(1)
size	size()	size_t（无符号整数）	返回元素总个数（包括重复元素）	O(1)
empty	empty()	bool（true 为空，false 非空）	判断 multiset 是否为空	O(1)
clear	clear()	void	清空所有元素，size 置 0	O(N)
swap	swap(ms)	void	交换当前 multiset 与 ms 的所有内容	O(1)
front/back	front()/back()	元素类型的引用（C++11 新增）	返回第一个 / 最后一个元素的引用，调用前需判空	O(1)

unordered_set

函数名	函数声明	返回值	函数作用	时间复杂度
insert	insert(val) insert(begin, end)	insert(val)：pair（迭代器指向元素，bool 表示是否插入成功）；insert(begin,end)：void	插入单个元素 val（重复则忽略）、插入 [begin,end) 区间元素（自动去重）	平均O(1)（单个插入）；平均O(k)（k为区间元素个数）；最坏O(N)/O(k*N)
emplace	emplace(args...)	pair（同 insert (val)）	C++11 新增，原地构造并插入元素，效率高于 insert	平均O(1)，最坏O(N)
erase	erase(pos) erase(val) erase(begin, end)	erase(pos)：void；erase(val)：size_t（删除个数，0/1）；erase(begin,end)：void	删除迭代器 pos 指向的元素、删除值为 val 的元素、删除 [begin,end) 区间元素	平均O(1)（单个删除）；平均O(k)（k为区间元素个数）；最坏O(N)/O(k*N)
find	find(val)	iterator（找到则指向元素，否则返回 end ()）	查找值为 val 的元素（核心函数，基于哈希查找）	平均O(1)，最坏O(N)
count	count(val)	size_t（0/1，用于元素存在性判断）	统计值为 val 的元素个数，unordered_set 中仅返回 0 或 1	平均O(1)，最坏O(N)
begin/end	begin()/end()	前向迭代器（begin () 指向首元素，end () 指向尾后）	用于正向遍历，因哈希特性遍历顺序随机（无序）	O(1)
size	size()	size_t（无符号整数）	返回 unordered_set 中当前的元素个数	O(1)
empty	empty()	bool（true 为空，false 非空）	判断 unordered_set 是否为空（元素个数为 0）	O(1)
clear	clear()	void	清空所有元素，将 size 置 0，不释放底层哈希桶内存	O(N)
swap	swap(us)	void	交换当前 unordered_set 与 us 的所有内容，仅交换底层哈希表指针	O(1)
bucket	bucket(val)	size_t（桶编号）	返回 val 所在的哈希桶编号（进阶用法，用于调试哈希冲突）	平均O(1)，最坏O(N)
reserve	reserve(n)	void	预分配至少能容纳 n 个元素的哈希桶空间，减少哈希冲突概率，降低后续插入操作的平均时间复杂度	平均O(1)，最坏O(N)

map

函数名	函数声明	返回值	函数作用	时间复杂度
operator[]	operator[](key)	键对应值的引用（value&）	访问 / 修改 key 对应的值；键不存在则自动插入 {key, 默认值}，支持读写	O(logN)
at	at(key)	键对应值的引用（value&）	访问 / 修改 key 对应的值；键不存在抛出 out_of_range 异常，不插入新键	O(logN)
insert	insert({key,value}) insert(begin, end)	insert({k,v})：pair；insert(b,e)：void	插入单个键值对（重复键失败）；插入 [begin,end) 区间的 pair 类型键值对	O(logN)（单个插入）；O(k*logN)（k为区间元素个数）
emplace	emplace(key_args..., value_args...)	pair	C++11 新增，原地构造键值对，效率高于 insert；重复键构造失败	O(logN)
erase	erase(pos) erase(key) erase(begin, end)	erase(pos)：void；erase(key)：size_t（0/1）；erase(b,e)：void	按迭代器删除单个键值对；按键删除键值对，返回删除个数；按区间删除键值对	O(logN)（单个插入）；O(k+logN)（k为区间元素个数）
find	find(key)	迭代器（找到指向键值对，否则返回 end ()）	按键查找键值对，迭代器可通过 ->first/->second 访问键 / 值	O(logN)
count	count(key)	size_t（0/1）	统计 key 对应的键值对个数，用于键的存在性判断	O(logN)
lower_bound	lower_bound(key)	迭代器（指向第一个键≥key 的键值对）	按键二分查找，返回键≥key 的第一个键值对迭代器	O(logN)
upper_bound	upper_bound(key)	迭代器（指向第一个键 > key 的键值对）	按键二分查找，返回键 > key 的第一个键值对迭代器	O(logN)
equal_range	equal_range(key)	pair（first=lower_bound(key)，second=upper_bound(key)）	一次性获取键≥key 和键 > key 的迭代器边界	O(logN)
begin/end	begin()/end()	正向双向迭代器	begin () 指向首个键值对，end () 指向尾后位置，用于正向升序遍历	O(1)
rbegin/rend	rbegin()/rend()	反向双向迭代器	rbegin () 指向尾个键值对，rend () 指向首前位置，用于反向降序遍历	O(1)
size	size()	size_t（无符号整数）	返回 map 中键值对的总个数	O(1)
empty	empty()	bool（true 为空，false 非空）	判断 map 是否为空（size=0）	O(1)
clear	clear()	void	清空所有键值对，size 置 0，不释放底层红黑树内存	O(N)
swap	swap(mp)	void	交换当前 map 与 mp 的所有键值对，仅交换红黑树指针	O(1)

unordered_map

函数名	函数声明	返回值	函数作用	时间复杂度
operator[]	operator[](key)	值的引用（value&）	访问 / 修改 key 对应的值；键不存在则自动插入 {key, 默认值}，支持直接读写值	平均O(1)，最坏O(N)
at	at(key)	值的引用（value&）	访问 / 修改 key 对应的值；键不存在抛出 out_of_range 异常，不插入新键（比 [] 更安全）	平均O(1)，最坏O(N)
insert	insert({key,value}) insert(begin, end)	insert({k,v})：pair（迭代器指向键值对，bool 表示插入是否成功）；insert(b,e)：void	插入单个键值对（重复键则插入失败）；插入 [begin,end) 区间的 pair 类型键值对（自动去重）	平均O(1)（单个插入）/O(k)（区间插入），最坏O(N)/O(k*N)
emplace	emplace(key_args..., value_args...)	pair	C++11 新增，原地构造键值对（避免拷贝 / 移动开销），效率高于 insert；重复键则构造失败	平均O(1)，最坏O(N)
erase	erase(pos) erase(key) erase(begin, end)	erase(pos)：void；erase(key)：size_t（删除个数，0/1）；erase(b,e)：void	按迭代器删除单个键值对；按键删除键值对（返回删除个数）；按区间删除键值对	平均O(1)（单个删除）/O(k)（区间删除），最坏O(N)/O(k*N)
find	find(key)	前向迭代器（找到指向键值对，否则返回 end ()）	按键查找键值对，迭代器可通过 ->first/->second 访问键 / 值（哈希查找核心函数）	平均O(1)，最坏O(N)
count	count(key)	size_t（0/1）	统计 key 对应的键值对个数，仅返回 0 或 1，常用于键的存在性判断（比 find 更简洁）	平均O(1)，最坏O(N)
begin/end	begin()/end()	前向迭代器	begin() 指向首个键值对，end() 指向尾后位置；因哈希特性，遍历顺序无序	O(1)
size	size()	size_t（无符号整数）	返回 unordered_map 中键值对的总个数	O(1)
empty	empty()	bool（true 为空，false 非空）	判断 unordered_map 是否为空（size = 0 时返回 true）	O(1)
clear	clear()	void	清空所有键值对，将 size 置 0；不释放底层哈希桶内存，仅析构元素	O(N)
swap	swap(ump)	void	交换当前 unordered_map 与 ump 的所有内容，仅交换底层哈希表指针（效率极高）	O(1)
reserve	reserve(n)	void	预分配至少能容纳 n 个元素的哈希桶空间，减少哈希冲突概率，优化后续插入 / 查找的平均时间复杂度（进阶用法）	O(N)

list

函数名	函数声明	返回值	函数作用	时间复杂度
push_back	push_back(val)	无	尾部插入元素 val	O(1)
push_front	push_front(val)	无	头部插入元素 val	O(1)
emplace_back	emplace_back(args...)	无	尾部原地构造元素	O(1)
emplace_front	emplace_front(args...)	无	头部原地构造元素	O(1)
insert	insert(pos, val) insert(pos, n, val) insert(pos, begin, end)	迭代器（指向插入的第一个元素）	迭代器 pos 位置插入单个 / 多个 / 区间元素	O(1)（插入），定位O(N)
pop_back	pop_back()	无	删除尾部元素	O(1)
pop_front	pop_front()	无	删除头部元素	O(1)
erase	erase(pos) erase(begin, end)	迭代器（指向删除位置下一个元素）	删除 pos 位置 / 区间元素	O(1)（删除），定位O(N)
remove	remove(val)	无	删除所有值为 val 的元素	O(N)
front	front()	元素类型的引用	访问 / 修改头部元素	O(1)
back	back()	元素类型的引用	访问 / 修改尾部元素	O(1)
size	size()	size_t（无符号整数）	返回元素个数	O(1)
empty	empty()	bool（true 为空，false 非空）	判断是否为空	O(1)
clear	clear()	无	清空所有元素，释放节点内存	O(N)
resize	resize(n) resize(n, val)	无	调整元素个数为 n，新增元素默认 / 指定 val	O(n-原size)
sort	sort() sort(cmp)	无	升序 / 自定义规则排序	O(NlogN)
swap	swap(l)	无	交换两个 list 的内容	O(1)
reverse	reverse()	无	反转 list 所有元素	O(N)
merge	merge(l) merge(l, cmp)	无	合并有序 list l 到当前 list，l 变为空	O(N+M)
begin/end	begin()/end()	正向双向迭代器	指向首元素 / 尾后位置，用于正向遍历	O(1)
rbegin/rend	rbegin()/rend()	反向双向迭代器	指向尾元素 / 首前位置，用于反向遍历	O(1)