STL¶

C++ 标准库提供了常用的容器和算法，做题时，不用什么都从头写。

容器，就是用来存放数据的工具。

不同容器的存法、取法不同，按题目需要选。

vector，动态数组¶

存一串数据，元素个数还会变化，可以用 vector，需要 <vector>。

也能像数组一样，用下标访问。

定义与初始化

下面是四种写法，n 是已经读入的非负整数。

vector<int> A;                 // 空vector
vector<int> B = {3, 5, 6, 8};  // 存入这4个数
vector<int> C(n);              // n个元素，都是0
vector<int> D(n, 7);           // n个元素，都是7

空 vector，逐个添加

int n;
cin >> n;

vector<int> A;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    A.push_back(x);
}

vector 添加元素，用 push_back。

在末尾添加一个元素，大小增加 1。

先确定大小，再按下标输入

int n;
cin >> n; // n是非负整数

vector<int> A(n);
for (int i = 0; i < n; i++) cin >> A[i];

也可以这样读，注意 &x，要修改的是原元素：

for (int &x : A) cin >> x;

遍历输出

int len = (int)A.size();
for (int i = 0; i < len; i++) cout << A[i] << ' ';

for (int x : A) cout << x << ' ';

这里先处理元素个数能放进 int 的情况。

常用操作

写法	作用
`A.size()`	当前元素个数
`A.empty()`	是否没有元素
`A.push_back(x)`	在末尾添加x
`A.pop_back()`	删除最后一个元素，不返回它
`A.back()`	访问最后一个元素
`A.clear()`	删除所有元素，大小变成0

访问、删除末尾元素，先保证非空。

if (!A.empty()) {
    cout << A.back();
    A.pop_back();
}

排序、翻转

需要头文件 <algorithm>。

sort(A.begin(), A.end()); // 从小到大

sort(A.begin(), A.end(), cmp); // 使用自定义比较函数

reverse(A.begin(), A.end()); // 翻转当前顺序，不是自动排序

空 vector，不能直接写 A[0]。

下标范围是 0 到 size() - 1，大小为 0 时没有可用下标。

set，集合¶

要去重，可以用 set，需要 <set>。

默认从小到大排，相同的值只存一份。

set<int> st = {3, 5, 3, 8}; // 实际保存3、5、8

输入与输出

int n;
cin >> n;

set<int> st;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    st.insert(x);
}

for (int x : st) cout << x << ' ';

set 添加元素，用 insert。

不支持 st[i] 这样的下标访问。

写法	作用
`st.insert(x)`	插入x，重复的整数不会再存一份
`st.count(x)`	x在不在集合里，结果为0或1
`st.erase(x)`	删除x，不存在就不删
`st.size()`	元素个数
`st.empty()`	是否为空
`st.clear()`	清空集合

if (st.count(x) != 0) cout << "存在";

pair，存一对数据¶

只存两个相关数据，也可以用 pair，需要 <utility>。

它不是容器，两个成员分别访问。

pair<int, int> p = {3, 4};

cout << p.first << ' ' << p.second;

first 是第一个成员，second 是第二个成员。

两个成员的类型也可以不同。

放进数组、vector、set

pair<int, int> a[110];
vector<pair<int, int>> A;
set<pair<int, int>> st;

使用这些容器，还要包含各自的头文件。

补充：类型简写（先不看）

typedef pair<int, int> PII;
vector<PII> A;

输入与输出

int n;
cin >> n;

vector<pair<int, int>> A(n);
for (int i = 0; i < n; i++) cin >> A[i].first >> A[i].second;

for (auto p : A) cout << p.first << ' ' << p.second << '\n';

默认排序，先比较 first，相同时再比较 second。

vector<pair<int, int>> A = {{3, 5}, {3, 2}, {1, 3}};
sort(A.begin(), A.end());

for (auto p : A) cout << p.first << ' ' << p.second << '\n';

输出顺序是 (1, 3)、(3, 2)、(3, 5)。

两个成员都相同，set 中才会被视作重复。

map，键与值的对应关系¶

要记录数据的对应关系，可以用 map，需要 <map>。

用一个键，找到它对应的值，比如用单词找到出现次数。

map<int, int> mp; // 键是int，值也是int

map<string, int> mp; // 键是string，值是int，还需要<string>

计数是 map 的常见用途，但它不只用来计数。

统计整数出现次数

int n, x;
cin >> n;

map<int, int> mp;
while (n--) {
    cin >> x;
    mp[x]++;
}

for (auto p : mp) cout << p.first << ' ' << p.second << '\n';

mp[x] 是键 x 对应的值。

新键第一次通过下标访问时，会插入它，int 值从 0 开始。

比如 n 为 3，依次输入 3 5 3，输出：

3 2
5 1

mp.size() 是不同键的个数，计数结果存在 second 里。

上例有 2 个不同的数，3 出现 2 次，5 出现 1 次。

统计字符串，也是同样的写法。

int n;
cin >> n;

map<string, int> mp;
string s;
while (n--) {
    cin >> s;
    mp[s]++;
}

for (auto p : mp) cout << p.first << ' ' << p.second << '\n';

first 是键，second 是对应的值。

默认按键从小到大遍历，不是按输入顺序。

只判断是否存在，用 count 或 find。

if (mp.count(x) != 0) cout << "存在";

不能用 mp[x] != 0 判断键是否存在：值可能本来就是 0。

而且下标访问会插入原本不存在的键。

stack，栈¶

需要头文件 <stack>。

后进先出，像一摞盘子，最后放上去的先拿走。

stack<int> st;
st.push(3);
st.push(5);
st.push(8);

while (!st.empty()) {
    cout << st.top() << ' ';
    st.pop();
}
// 输出8 5 3

写法	作用
`st.push(x)`	入栈
`st.top()`	访问栈顶
`st.pop()`	删除栈顶，不返回它
`st.empty()`	是否为空
`st.size()`	元素个数

栈添加元素，用 push。

先取值，再删除，不能写 x = st.pop()。

if (!st.empty()) {
    int x = st.top();
    st.pop();
    cout << x;
}

空栈不能调用 top、pop。

queue，队列¶

需要头文件 <queue>。

先进先出，像排队，先来的先走。

queue<int> q;
q.push(3);
q.push(5);
q.push(8);

while (!q.empty()) {
    cout << q.front() << ' ';
    q.pop();
}
// 输出3 5 8

写法	作用
`q.push(x)`	从队尾入队
`q.front()`	访问队头
`q.back()`	访问队尾
`q.pop()`	删除队头，不返回它
`q.empty()`	是否为空
`q.size()`	元素个数

队列添加元素，也用 push。

先读 front，再用 pop 删除。

空队列不能调用 front、back、pop。

迭代器、二分查找、多重集合等，放在其他（先不看）。