第 36 章 STL与语法进阶 · 知识细节练习

STL 的三大组成部分是？

STL 容器的三大类是？

判断题：序列容器（vector/deque/list）按下标顺序存储——vector 随机访问 $O(1)$、头部插入慢；list 任意位置插入 $O(1)$、但不支持随机访问。

判断题：set/map 基于红黑树——元素自动按键有序，插入、删除、查找都是 $O(\log n)$。

判断题：stack/queue/priority_queue 是容器适配器——本身不存数据，底层靠别的容器（默认 deque/vector）实现。

STL 总表是？

vector 的核心操作是？

判断题：vector 的 size 是元素个数、capacity 是已分配空间——push_back 超出 capacity 时按倍数（常为 2 倍）扩容并把元素搬过去。

string 的常用操作是？

判断题：s.find(x) 找不到时返回 string::npos（一个很大的 size_t 值）——判断要写 != string::npos 而不是 != -1 的整数比较习惯。

判断题：stoi("123") 把字符串转 int、to_string(45) 把数转字符串——两者互为逆操作。

判断题：vector 扩容或 erase 后，之前的迭代器会失效——继续使用是未定义行为。

判断题：vector 比普通数组安全/方便——自动扩容、知道自己的 size、可整体排序赋值，代价是常数略大。

set 的特点是？

判断题：multiset 允许重复元素——count(x) 返回 x 的出现次数，erase(x) 会删掉所有 x。

map 的特点是？

判断题：for (auto &p : m) 遍历 map 时按键的升序输出——因为底层是红黑树。

判断题：set/map 用成员函数 s.lower_bound(x) 是 $O(\log n)$；用 std::lower_bound(s.begin(), s.end(), x) 则是 $O(n)$——树结构不能随机访问。

判断题：m[key] 访问不存在的键会插入一个默认值（int 为 0）——判断存在要用 count 或 find。

判断题：unordered_map 的遍历顺序与插入顺序一致。

stack 的核心操作是？

判断题：queue 的 push 在队尾、pop 在队头、front 取队头——先进先出（FIFO）。

判断题：priority_queue<int> 默认是小根堆——队首是全局最小值。

判断题：priority_queue<int, vector<int>, greater<int>> 是小根堆——队首是全局最小值。

判断题：优先队列自定义比较器的方向与 sort 相反——a < b 返回 true 意味着 a 排在堆的后面（大根堆）。

判断题：deque 支持头尾两端 $O(1)$ 插入删除（push_front/push_back/pop_front/pop_back），也支持随机访问。

栈队列选择矩阵是？

sort(v.begin(), v.end(), [](int a, int b){ return a > b; }) 的效果是？

判断题：lower_bound(v.begin(), v.end(), x) 返回迭代器（第一个 ≥x 的位置），取下标要减 v.begin()，取元素用 *it。

判断题：unique 只去掉相邻的重复元素，返回新末尾迭代器——配合 erase 才真正删除，前提是先 sort。

判断题：binary_search(v.begin(), v.end(), x) 返回 bool（是否存在），要求序列已排序，复杂度 $O(\log n)$。

判断题：next_permutation 把序列变成字典序下一个排列，返回 false 表示已是最后一个排列。

判断题：min_element/max_element 返回最值的迭代器（取元素要解引用）；count(begin, end, x) 返回 x 出现次数。

lambda 表达式的语法是？

lambda 的捕获列表 [&] 与 [=] 的含义是？

判断题：sort 的比较器写 return a <= b; 也行，效果与 < 一样。

判断题：函数对象 = 重载了 operator() 的类/结构体实例——像函数一样调用，且能携带状态，常用于自定义比较器。

判断题：pair<int,int> 存两个值（first/second，自带字典序比较）；tuple 可存任意多个值（get<0> 取值）。

判断题：自定义排序比较器三种写法等价——lambda、普通函数、函数对象（重载 operator()）。

位运算六种操作是？

判断题：lowbit(x) = x & (-x) 取出 x 二进制中最低位的 1 及其后的 0——树状数组的核心。

判断题：x & (x - 1) 把 x 二进制中最低位的 1 清零——统计 1 的个数（popcount）可反复用此式。

判断题：for (sub = mask; sub; sub = (sub - 1) & mask) 枚举 mask 的全部非空子集（含 mask 本身）。

bitset 类的特点是？

判断题：位运算应用——状态压缩集合、快速判奇偶 x & 1、乘除 2 的幂 x << k / x >> k、交换两数 a ^= b ^= a ^= b 思想。

判断题：遍历中删除 vector 元素的正确写法是 it = v.erase(it)（erase 返回下一个元素的新迭代器）；v.erase(it) 后继续 it++ 会迭代器失效。

判断题：for (int x : v) 的 x 是拷贝——改 x 不影响原元素；要修改必须写 for (int &x : v)。

判断题：v[i] 越界不检查（未定义行为）；v.at(i) 越界会抛异常——稳妥用 at 或先查 size。

判断题：ios::sync_with_stdio(false) 关闭与 C 输入输出的同步能大幅加速 cin/cout——代价是不能再混用 scanf/printf。

判断题：以下结论全部正确——"set/map 有序 $O(\log n)$、unordered_* 哈希平均 $O(1)$；priority_queue 默认大根堆；unique 要先 sort 且只去相邻重复；erase 返回下一个迭代器；范围 for 修改要引用；lambda 捕获 [&] 引用 [=] 值"。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    vector<int> v;
05    v.push_back(3); v.push_back(1); v.push_back(2);
06    sort(v.begin(), v.end());
07    for (int x : v) cout << x << " ";
08    cout << endl << v.size();
09    return 0;
10}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    string s = "abcde";
05    cout << s.substr(1, 3) << endl;   // 从下标 1 起截 3 个
06    cout << s.substr(2) << endl;      // 从下标 2 到末尾
07    return 0;
08}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    string s = "banana";
05    cout << s.find("na") << " ";                       // 第一次出现位置
06    cout << (s.find("xyz") == string::npos) << endl;   // 找不到返回 npos
07    return 0;
08}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    cout << stoi("123") + 1 << endl;
05    cout << to_string(45) + "6" << endl;
06    return 0;
07}

单选题：程序输出是？

01// 遍历中删除所有偶数（正确写法）：
02for (auto it = v.begin(); it != v.end(); ) {
03    if (*it % 2 == 0) it = ______;   // erase 返回下一个元素的新迭代器
04    else ++it;
05}

单选题：横线处应填入？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    vector<int> v = {1, 2, 3};
05    v.insert(v.begin() + 1, 9);        // 在下标 1 处插入 9
06    for (int x : v) cout << x << " ";
07    return 0;
08}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    set<int> s;
05    s.insert(3); s.insert(1); s.insert(2);
06    s.insert(1); s.insert(2);          // 重复插入无效
07    for (int x : s) cout << x << " ";
08    cout << endl << s.size();
09    return 0;
10}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    multiset<int> ms;
05    ms.insert(3); ms.insert(1); ms.insert(2);
06    ms.insert(1); ms.insert(2);
07    cout << ms.count(2) << " " << ms.size();
08    return 0;
09}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    map<string, int> m;
05    m["b"] = 2; m["a"] = 1; m["c"] = 3;   // 插入顺序打乱
06    for (auto &p : m) cout << p.first << p.second << " ";
07    return 0;
08}

单选题：程序输出是？（map 按键升序遍历）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    map<int, int> m;
05    m[1] = 10;
06    cout << m.count(1) << " " << m.count(2) << endl;
07    m[2];                               // 访问不存在的键——会插入默认值 0
08    cout << m.size();
09    return 0;
10}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    set<int> s = {1, 3, 5, 7, 9};
05    cout << *s.lower_bound(5) << " ";    // 第一个 >= 5
06    cout << *s.lower_bound(6);           // 第一个 >= 6
07    return 0;
08}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    set<int> s;
05    s.insert(3); s.insert(1); s.insert(2);
06    s.erase(2);                         // 删除 2
07    for (int x : s) cout << x << " ";
08    cout << endl << s.size();
09    return 0;
10}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    stack<int> st;
05    st.push(1); st.push(2); st.push(3);
06    while (!st.empty()) {
07        cout << st.top() << " ";
08        st.pop();
09    }
10    return 0;
11}

单选题：程序输出是？（后进先出）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    queue<int> q;
05    q.push(1); q.push(2); q.push(3);
06    while (!q.empty()) {
07        cout << q.front() << " ";
08        q.pop();
09    }
10    return 0;
11}

单选题：程序输出是？（先进先出）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    priority_queue<int> q;             // 默认大根堆
05    q.push(3); q.push(1); q.push(2);
06    while (!q.empty()) {
07        cout << q.top() << " ";
08        q.pop();
09    }
10    return 0;
11}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    priority_queue<int, vector<int>, greater<int>> q;   // 小根堆
05    q.push(3); q.push(1); q.push(2);
06    while (!q.empty()) {
07        cout << q.top() << " ";
08        q.pop();
09    }
10    return 0;
11}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct Cmp {
04    bool operator()(int a, int b) { return a > b; }   // a 更大则 a 排在后面
05};
06int main() {
07    priority_queue<int, vector<int>, Cmp> q;          // 效果：小根堆
08    q.push(3); q.push(1); q.push(2);
09    while (!q.empty()) {
10        cout << q.top() << " ";
11        q.pop();
12    }
13    return 0;
14}

单选题：程序输出是？（注意：优先队列比较器方向与 sort 相反）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    deque<int> d;
05    d.push_back(1);      // [1]
06    d.push_front(2);     // [2,1]
07    d.push_back(3);      // [2,1,3]
08    d.pop_front();       // [1,3]
09    cout << d.front() << " " << d.back();
10    return 0;
11}

单选题：程序输出是？

// 用大根堆取前 3 大的数：{3,1,4,1,5,9,2,6} → 依次弹出 9 6 5

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    vector<int> v = {3, 1, 2};
05    sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
06    for (int x : v) cout << x << " ";
07    return 0;
08}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    vector<int> v = {1, 1, 2, 2, 3};
05    sort(v.begin(), v.end());                 // 先排序
06    v.erase(unique(v.begin(), v.end()), v.end());
07    for (int x : v) cout << x << " ";
08    cout << endl << v.size();
09    return 0;
10}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    vector<int> v = {1, 2, 3};
05    next_permutation(v.begin(), v.end());
06    for (int x : v) cout << x << " ";
07    cout << endl;
08    prev_permutation(v.begin(), v.end());
09    for (int x : v) cout << x << " ";
10    return 0;
11}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
05    cout << *min_element(v.begin(), v.end()) << " ";
06    cout << *max_element(v.begin(), v.end()) << " ";
07    cout << count(v.begin(), v.end(), 1);
08    return 0;
09}

单选题：程序输出是？

01sort(v.begin(), v.end(), [](int a, int b) {
02    return ______;                    // 降序
03});

单选题：横线处应填入？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    vector<int> v = {1, 2, 3, 4, 5};
05    cout << binary_search(v.begin(), v.end(), 3) << " ";
06    cout << *lower_bound(v.begin(), v.end(), 3) << " ";
07    cout << *upper_bound(v.begin(), v.end(), 3);
08    return 0;
09}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int x = 5;
05    auto addOne = [&x]() { x++; };     // 按引用捕获 x
06    addOne();
07    addOne();
08    cout << x;
09    return 0;
10}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    pair<int, int> p = {3, 1};
05    cout << p.first << " " << p.second << " ";
06    cout << (p > make_pair(2, 9));     // 字典序比较：3 > 2
07    return 0;
08}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int x = 12;                        // 二进制 1100
05    cout << (x & (-x));                // lowbit：最低位的 1 及其后的 0
06    return 0;
07}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    cout << (12 & 11) << " ";          // 1100 & 1011 = 1000
05    int x = 13, cnt = 0;               // 1101 中 1 的个数
06    while (x) { x &= (x - 1); cnt++; }
07    cout << cnt;
08    return 0;
09}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int mask = 6;                      // 二进制 110 = {2, 3}
05    for (int sub = mask; sub; sub = (sub - 1) & mask)
06        cout << sub << " ";
07    return 0;
08}

单选题：程序输出是？（mask = 6 的全部非空子集）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    bitset<8> b(10);                   // 10 的二进制 00001010
05    cout << b << endl;
06    cout << b.count() << " " << b.test(3) << " " << b[0];
07    return 0;
08}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    string s = "a b a c b a";
05    stringstream ss(s);
06    map<string, int> m;
07    string w;
08    while (ss >> w) m[w]++;
09    for (auto &p : m) cout << p.first << p.second << " ";
10    return 0;
11}

单选题：程序输出是？（词频统计，按键升序）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    vector<int> v = {3, 1, 2, 1};
05    set<int> s(v.begin(), v.end());          // 用 vector 初始化 set
06    vector<int> u(s.begin(), s.end());       // 用 set 初始化 vector
07    for (int x : u) cout << x << " ";
08    cout << endl << s.size();
09    return 0;
10}

单选题：程序输出是？

// 用小根堆维护前 3 大：依次处理 {3,1,4,1,5,9,2,6}
// 堆内始终是当前已见元素中最大的 3 个
// 5 顶掉 1、9 顶掉 4、6 顶掉 4 → 最终 {5,6,9}

单选题：程序输出是？（升序输出堆内元素）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    cout << ((8 & 7) == 0) << " ";     // 8 是 2 的幂
05    cout << ((12 & 11) == 0);          // 12 不是 2 的幂
06    return 0;
07}

单选题：程序输出是？

01priority_queue<int, vector<int>, ______> q;   // 小根堆

单选题：横线处应填入？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    string s = "1 2 3";
05    stringstream ss(s);
06    int x, sum = 0;
07    while (ss >> x) sum += x;
08    cout << sum;
09    return 0;
10}

单选题：程序输出是？（stringstream 逐个提取整数求和）

01vector<int> v = {3, 1, 2};
02sort(v.begin(), v.end(), ①);          // 降序排序

单选题：①处应填？

01map<int, int> m;
02if (①) cout << "存在";               // 判断键 5 是否存在

单选题：①处应填？

01priority_queue<int, vector<int>, ①> q;   // 小根堆

单选题：①处应填？

01vector<int> v = {1, 1, 2, 2, 3};
02sort(v.begin(), v.end());
03v.erase(①, v.end());                  // 删掉 unique 之后的多余元素

单选题：①处应填？

01int x = 0;
02auto add = [①](int v) { x += v; };    // 按引用捕获 x，累加
03add(3); add(4);

单选题：①处应填？

bitset<8> b(10);
cout << b.①;                          // 输出 1 的个数（10 → 2）

单选题：①处应填？

01for (auto it = v.begin(); it != v.end(); ) {
02    if (*it % 2 == 0) it = ①;         // 删除偶数，拿到下一个迭代器
03    else ++it;
04}

单选题：①处应填？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    vector<int> v = {1, 2, 4, 3};
05    for (auto it = v.begin(); it != v.end(); ++it) {
06        if (*it % 2 == 0)
07            v.erase(it);               // 注意：erase 后 it 失效，++it 会跳过元素
08    }
09    for (int x : v) cout << x << " ";
10    return 0;
11}

单选题：程序输出是？（正确结果应为 1 3——4 被漏删）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    vector<int> v = {1, 2, 3};
05    for (int x : v) x = 0;             // 注意：x 是拷贝，改它不影响原元素
06    for (int x : v) cout << x << " ";
07    return 0;
08}

单选题：程序输出是？（想清空却没清掉）

01// 想按升序排序，但 lambda 比较器写反了：
02vector<int> v = {3, 1, 2};
03sort(v.begin(), v.end(), [](int a, int b) { return a > b; });

单选题：程序输出是？（预期升序 1 2 3，实际得降序）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    map<int, int> m;
05    m[1] = 10;
06    if (m[2] == 0) {                   // 注意：m[2] 会把 2 插入 map
07        // 本想检查 2 是否存在
08    }
09    cout << m.size();                  // 应为 1，实际变 2
10    return 0;
11}

单选题：程序输出是？（正确结果应为 1）

01// 在 set 上查找：
02std::lower_bound(s.begin(), s.end(), x);   // 注意：这是 O(n) 的
03// 而成员函数 s.lower_bound(x) 才是 O(log n)

单选题：判断题——std::lower_bound 用在 set 上时，因为 set 迭代器不支持随机访问，复杂度退化为 $O(n)$？

判断题：以下五种易错写法都会导致程序出错或行为异常——①erase 后不接收返回迭代器继续 ++（漏删元素）②范围 for 用值拷贝想修改原元素（改不动）③sort 比较器方向写反（排序结果相反）④用 m[key] 检查键是否存在（误插入默认值）⑤在 set 上用 std::lower_bound（复杂度退化为 $O(n)$）。