C++|STL学习

发表于 | 分类于

C++ 标准模板库 (STL, Standard Template Library) 是 C++ 标准库的核心组成部分，提供了一系列通用的模板类和函数，用于处理常见的数据结构和算法。其包含四个主要组件：算法 (Algorithms)、容器 (Containers)、函数对象 (Functors) 和迭代器 (Iterators)。

示例：

  • 算法：sort(a.begin(), a.end())
  • 容器：priority_queue<int> pque
  • 函数对象：greater<int>()
  • 迭代器：vector<int>::iterator it = a.begin()

1 前言

STL 作为一个封装良好、性能合格的库，在算法竞赛中广泛应用。它能显著节省解题时间，不仅因为可直接调用，还因其封装性提高了代码可读性，使思路更清晰，调试更顺利。

需要注意的是，STL 使用了复杂结构实现丰富功能，其效率通常不如手写、针对特定题目优化的数据结构和算法。因此，STL 的使用是在用更长的运行时间换取更高的编程效率，在实际比赛中需根据经验权衡利弊。

接下来将重点介绍算法竞赛中常用的 STL 容器和算法，函数对象和迭代器仅做简要说明。

2 STL 核心组件概述

STL 的设计基于泛型编程，使得它可以适应不同的数据类型，并支持代码的高度复用。其四个核心组件协同工作：

  • 容器 (Containers)：用于存储和管理数据的类模板，如 vector, list, map。
  • 算法 (Algorithms)：用于操作容器中数据的函数模板，如 sort, find。
  • 迭代器 (Iterators)：用于遍历容器中元素的对象，是连接容器与算法的桥梁。
  • 函数对象 (Functors)：重载了 operator()的类，其对象可以像函数一样调用，常用于自定义算法的行为。

3 常用容器

3.1 内容总览

打勾 (✅) 的是本文会详细讲解的，加粗的是算法竞赛中有必要学习的。

  • 顺序容器
    • array (C++11)
    • ✅ vector
    • deque
    • forward_list (C++11)
    • list
  • 关联容器
    • ✅ set
    • ✅ map
    • multiset
    • multimap
  • 无序关联容器 (C++11)
    • unordered_set
    • unordered_map
    • unordered_multiset
    • unordered_multimap
  • 容器适配器
    • ✅ stack
    • ✅ queue
    • ✅ priority_queue
  • 字符串
    • ✅ string (实际上是 basic_string<char>)
  • 对与元组
    • ✅ pair
    • tuple (C++11)

3.2 向量 (vector)

1
#include <vector>

连续的顺序存储结构（动态数组），长度可变。

3.2.1 常用方法

  • 构造：vector<类型> arr(长度, 初值)

    1
    2
    3
    4
    5
    vector<int> arr; // 空向量
vector<int> arr(100); // 初始长度为100，默认初始化
vector<int> arr(100, 1); // 初始长度为100，初值为1
// 二维向量
vector<vector<int>> mat(100, vector<int>(666, -1));

    时间复杂度：与元素数量成线性关系。

  • 尾接与尾删：

    • push_back(元素)：均摊 O(1) 时间在尾部添加元素。
    • pop_back()：O(1) 时间删除尾部元素。

  • 访问：

    • operator[]：O(1) 时间随机访问（不检查边界）。
    • at(size_t pos)：O(1) 时间随机访问（检查边界，越界则抛出 std::out_of_range异常）。

  • 容量：

    • size()：获取当前元素数量，O(1) 时间。
    • empty()：判断是否为空，O(1) 时间。
    • clear()：清空所有元素，O(n) 时间。
    • resize(新长度, 默认值)：改变向量大小，O(n) 时间。

3.2.2 适用情形

  • 需动态调整大小的数组。
  • 替代普通数组（除非卡常）。
  • 处理大型矩阵（如 vector<vector<int>> mat(n, vector<int>(m))），可避免栈溢出和内存浪费。

3.2.3 注意事项

  • 提前分配容量：若已知最终大小，应在构造时指定长度或使用 reserve()，避免 push_back多次重分配的开销。

    1
    2
    3
    4
    5
    6
    // 慢: 可能多次重分配
vector<int> a;
for (int i = 0; i < 1e8; i++) a.push_back(i);
// 快: 一次分配
vector<int> a(1e8);
for (int i = 0; i < a.size(); i++) a[i] = i;

  • 警惕 size_t溢出：.size()返回 size_t（无符号类型），在 32 位平台范围是 $ [0, 2^{32}-1] $，计算时需注意避免溢出和负数转换问题。

  • 迭代器失效：在修改 vector 后（如 push_back, insert, erase），已有的迭代器可能失效，需要重新获取。

3.3 栈 (stack)

1
#include <stack>

适配器容器，提供后进先出 (LIFO) 接口，默认基于 deque实现。

3.3.1 常用方法

作用 用法 示例
构造 stack<类型> stk stack<int> stk;
进栈 push(元素) stk.push(1);
出栈 pop() stk.pop();
取栈顶 top() int a = stk.top();
大小/清空/判空 size()/ empty() if (stk.empty()) ...

时间复杂度：所有操作均为 O(1)。

3.3.2 适用情形

  • 需要 LIFO 语义的场景，如递归转迭代、括号匹配、表达式求值等。
  • vector也可模拟栈（用 push_back, pop_back, back）。

3.3.3 注意事项

  • 无法访问内部元素：不能通过下标或迭代器访问（这是设计初衷）。
  • 底层容器可指定：可基于 vector或 list实现 stack（如 stack<int, vector<int>>），但通常没必要。

3.4 队列 (queue)

1
1
#include <queue>

适配器容器，提供先进先出 (FIFO) 接口，默认基于 deque实现。

3.4.1 常用方法

作用 用法 示例
构造 queue<类型> que queue<int> que;
进队 push(元素) que.push(1);
出队 pop() que.pop();
取队首 front() int a = que.front();
取队尾 back() int a = que.back();
大小/清空/判空 size()/ empty() if (que.empty()) ...

时间复杂度：所有操作均为 O(1)。

3.4.2 适用情形

  • 需要 FIFO 语义的场景，如 BFS、缓存、任务调度等。

3.4.3 注意事项

  • 无法访问内部元素：不能通过下标或迭代器访问。
  • 底层容器可指定：可基于 list或 deque实现 queue（如 queue<int, list<int>>）。

3.5 优先队列 (priority_queue)

1
1
#include <queue>

适配器容器，提供常数时间获取最大（默认）元素，对数时间插入和提取，底层默认是 vector实现的二叉堆。

3.5.1 常用方法

  • 构造：

    priority_queue<类型, 容器, 比较器> pque

    1
    2
    priority_queue<int> pque1; // 大顶堆
priority_queue<int, vector<int>, greater<int>> pque2; // 小顶堆

  • 操作：

    • push(元素)：O(log n) 时间插入。
    • pop()：O(log n) 时间删除堆顶。
    • top()：O(1) 时间获取堆顶。
    • empty(), size().

3.5.2 适用情形

  • 持续维护动态集合的极值：Dijkstra 算法、Huffman 编码、连续中位数等。
  • 对比：每次插入后排序为 O(n log n)，使用优先队列维护为 O(n log k)（k 为插入操作数）。

3.5.3 注意事项

  • 仅堆顶可读：无法直接访问其他元素。
  • 元素不可修改：修改非堆顶元素会破坏堆性质。需修改堆顶时，应先 pop，修改后再 push。
  • 自定义比较器：可通过重载 operator<、传入函数对象或 Lambda 表达式实现自定义优先级比较。

3.6 集合 (set)

1
#include <set>

关联容器，基于红黑树实现，提供对数时间的插入、删除和查找。元素唯一（multiset允许多次）且有序。

集合性质 set multiset unordered_set
确定性 ✔️ ✔️ ✔️
互异性 ✔️ ❌ ✔️
无序性 ❌ (有序) ❌ (有序) ✔️

3.6.1 常用方法

  • 构造：set<类型, 比较器> st

    1
    2
    set<int> st1; // 升序
set<int, greater<int>> st2; // 降序

  • 操作：

    • insert(元素)：O(log n) 时间插入。
    • erase(元素或迭代器)：O(log n) 时间删除。
    • find(元素)：O(log n) 时间查找，返回迭代器（找不到返回 end()）。
    • count(元素)：O(log n) 时间返回出现次数（对 set只能是 0 或 1）。
    • lower_bound(key), upper_bound(key)：O(log n) 时间返回边界迭代器。
    • empty(), size(), clear().

  • 遍历：使用迭代器（有序）。

    1
    2
    for (set<int>::iterator it = st.begin(); it != st.end(); ++it)
for (auto &ele : st) // C++11 范围 for

3.6.2 适用情形

  • 元素去重且需有序。
  • 动态维护有序集合（查询、插入、删除混合操作）。
  • 判断元素是否存在（当元素范围大或非整数，无法用数组 vis时）。

3.6.3 注意事项

  • 无下标索引：只能通过迭代器访问，不支持 operator[]。
  • 元素只读：迭代器指向的元素是 const（修改会破坏红黑树结构）。需修改应先删除再插入新值。
  • 迭代器不支持算术运算：it2 - it1无法编译（树结构非连续存储）。

3.7 映射 (map)

1
#include <map>

关联容器，基于红黑树实现，存储键值对，提供对数时间的操作。键唯一（multimap允许多次）且有序。

映射性质 map multimap unordered_map
互异性 ✔️ ❌ ✔️
无序性 ❌ (键有序) ❌ (键有序) ✔️

3.7.1 常用方法

  • 构造：map<键类型, 值类型, 比较器> mp

    1
    2
    map<string, int> mp1; // 键升序
map<string, int, greater<string>> mp2; // 键降序

  • 操作：

    • operator[key]：O(log n) 时间访问或插入（若键不存在，则插入值初始化的新元素）。
    • insert({key, value})：O(log n) 时间插入。
    • find(key)：O(log n) 时间查找，返回迭代器（找不到返回 end()）。
    • erase(key或迭代器)：O(log n) 时间删除。
    • count(key)：O(log n) 时间返回键出现次数（对 map只能是 0 或 1）。
    • lower_bound(key), upper_bound(key)：O(log n) 时间返回边界迭代器。
    • empty(), size(), clear().

  • 遍历：使用迭代器（元素为 pair<const Key, T>）。

    1
    2
    3
    4
    5
    6
    for (map<string, int>::iterator it = mp.begin(); it != mp.end(); ++it)
    cout << it->first << it->second;
for (auto &pr : mp) // C++11 范围 for
    cout << pr.first << pr.second;
for (auto &[key, val] : mp) // C++17 结构化绑定
    cout << key << val;

3.7.2 适用情形

  • 需要键值对关联，且键有序。
  • 统计频率、建立映射关系（如字符串到 ID 的映射）。

3.7.3 注意事项

  • operator[]的副作用：若键不存在，会插入一个具有默认值的元素。仅检查是否存在时宜用 find或 count。
  • 迭代器指向的键为 const：不能修改 it->first（会破坏红黑树秩序）。
  • 迭代器不支持算术运算：it2 - it1无法编译。

3.8 字符串 (string)

1
#include <string>

动态字符序列，实质是 basic_string<char>。

3.8.1 常用方法

  • 构造：

    1
    2
    3
    string s1;
string s2 = "hello";
string s3(10, 'a'); // "aaaaaaaaaa"

  • 操作：

    • operator[], at(pos)：访问字符（at会检查边界）。
    • ==, !=, <等：比较运算符（按字典序）。
    • +, +=：连接字符串。
    • append(str), push_back(c)：追加。
    • substr(起始位置, 长度)：获取子串。
    • find(字符串, 起始位置)：查找子串，返回位置或 string::npos。
    • empty(), size()/length(), clear().

  • 输入输出：

    1
    2
    3
    4
    5
    string s;
cin >> s; // 读取单词
getline(cin, s); // 读取一行
cout << s;
printf("%s", s.c_str()); // C 风格输出

  • 数值转换（C++11）：

    1
    2
    3
    to_string(42); // int -> string
stoi("42"); // string -> int
stol, stoll, stof, stod, stold 等。

3.8.2 适用情形

  • 替代字符数组，处理字符串操作更安全便捷。

3.8.3 注意事项

  • 使用 +=而非 +进行拼接：s = s + "a"会创建临时对象，效率低下；s += "a"是原地追加，效率高。

    1
    2
    3
    4
    5
    6
    // 慢: O(n^2)
string s;
for (int i = 0; i < 5e5; i++) s = s + "a";
// 快: O(n)
string s;
for (int i = 0; i < 5e5; i++) s += "a";

  • substr参数：第一个是起始下标，第二个是子串长度（非结束下标）。

  • find的复杂度：实现为暴力匹配（O(n*m)），无高级算法（如 KMP）。

3.9 二元组 (pair)

1
#include <utility>

存储两个元素的模板结构体。

3.9.1 常用方法

  • 构造与赋值：

    1
    2
    pair<int, char> p1 = make_pair(1, 'a');
pair<int, char> p2 = {2, 'b'}; // C++11

  • 访问：

    1
    2
    cout << p1.first << p1.second;
auto [first, second] = p1; // C++17 结构化绑定

  • 比较：按字典序（先比较 first, 再比较 second）。

3.9.2 适用情形

  • 需要返回两个值（如函数返回值）。
  • 作为 map的元素（键值对）。
  • 需要组合两个值作为另一个容器的元素（如 vector<pair<int, int>>）。

3.9.3 注意事项

  • 无特殊注意事项，可放心使用。

4 迭代器 (Iterators) 简介

4.1 什么是迭代器？

迭代器是提供一种方法来顺序访问容器内元素的对象，行为类似指针。它抽象了不同容器的遍历方式。

1
2
3
4
vector<int> vec = {1, 2, 3};
// 使用迭代器遍历
for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it)
    cout << *it << endl;
  • begin()：返回指向第一个元素的迭代器。
  • end()：返回指向最后一个元素之后（尾后）的迭代器。

4.2 为何需要迭代器？

提供一种统一的访问容器元素的方式，使得算法（如 sort, find）能独立于特定容器工作。对于非线性结构（如 set, map），下标索引无意义，迭代器是唯一遍历方式。

4.3 迭代器类型与操作

迭代器按功能分类：

  • 输入迭代器：只读，单向。
  • 输出迭代器：只写，单向。
  • 前向迭代器：可读写，单向（如 forward_list的迭代器）。
  • 双向迭代器：可读写，双向移动（如 list, set, map的迭代器）。
  • 随机访问迭代器：可读写，支持随机访问（如 vector, deque的迭代器）。

支持的操作因类别而异：

1
2
3
4
5
6
// 随机访问迭代器支持（vector, deque）
it + n, it - n, it2 - it1, +=, -=, <, >, <=, >=
// 双向迭代器支持（list, set, map）
++, --
// 所有迭代器支持
*, ==, !=

常用函数：

  • next(it), prev(it)（C++11）：获取后一个/前一个迭代器。

4.4 注意事项

  • end()不可解引用：它指向容器尾后的“占位符”，解引用是未定义行为。

  • 迭代器失效：修改容器可能导致迭代器失效（如 vector的 push_back可能引起重分配；erase会使被删元素之后的迭代器失效）。修改容器后应谨慎使用之前的迭代器。

  • 不同容器迭代器功能不同：例如，vector迭代器是随机访问，list迭代器是双向。

  • 结合 auto（C++11）：简化迭代器声明。

    1
    for (auto it = vec.begin(); it != vec.end(); ++it)