C++ 练习册第 7 章 STL 容器与迭代器

📝 本章练习：15 题（A 识别 / B 理解 / C 改错 / D 写程序）。先自己做完再看答案——A、B 档不翻书做，C、D 档必须真的编译运行。

7.1 vector 与迭代器

A1识别判断题：vector 扩容时，之前拿到的迭代器、指针、引用都可能失效。

答：______________

✅ 查看答案与解析

答案　对

解析：map 底层是红黑树，迭代按键的有序顺序。

A2识别判断题：在范围 for 循环里对 vector 做 push_back，是未定义行为。

答：______________

✅ 查看答案与解析

答案　对

解析：m[\"apple\"] 若键不存在，会插入 0（对 int）再返回引用。所以用它判断键存在会悄悄改变容器大小。

B1理解选择题：std::vector<int> v; v.reserve(10); 的作用是？

把元素个数设为 10

预分配能放 10 个元素的空间，避免前 10 次 push_back 扩容

清空 v

把 v 变成定长数组

答：______________

✅ 查看答案与解析

答案　B

解析：find 返回迭代器（找不到返回 end()），count 返回 0 或 1。operator[] 会误插入，at() 找不到会抛异常。

C1应用改错题：下面代码在 push_back 后继续用旧指针，是未定义行为。

std::vector<int> v{1, 2, 3};
int* p = v.data();
v.push_back(4);      // 可能扩容，p 变成悬垂指针
std::cout << *p;     // 未定义行为

✅ 查看答案与解析

答案　if (m.count("b") != 0) { std::cout << "exists"; }

解析：查询用 find/count，别用 operator[]。

D1创造写程序：读 n 个数存进 vector，统计其中正数的个数并输出。

提示：遍历用范围 for (int x : v)。

✅ 查看答案与解析

答案　参考答案：

解析：++freq[word] 是统计频率的经典写法：不存在则插入 0 再自增。结构化绑定解包 pair。

#include <iostream>
#include <map>
#include <string>
int main() {
    std::map<std::string, int> freq;
    std::string word;
    while (std::cin >> word) { ++freq[word]; }
    for (const auto& [key, value] : freq) {
        std::cout << key << ' ' << value << '\n';
    }
    return 0;
}

7.2 关联容器 map / set

A1识别判断题：std::map 按键自动排序，遍历时按键从小到大。

答：______________

✅ 查看答案与解析（本站补充）

答案　对。

解析：map 底层是红黑树，按键严格弱序排列；用迭代器或范围 for 遍历都是按键升序。想按插入顺序遍历要额外记录 key 的顺序。

A2识别判断题：map::operator[] 在键不存在时会插入一个默认构造的值。

答：______________

✅ 查看答案与解析（本站补充）

答案　对。

解析：m[k] 在键不存在时会插入一个值初始化的元素（int 为 0）再返回引用，所以“查询”会改变容器大小；只查不写请用 find / count。

B1理解选择题：只想查询“键存不存在”，应该用哪个？

m[key] 判断是否非零

m.find(key) 或 m.count(key)

m.at(key)

遍历所有键

答：______________

✅ 查看答案与解析（本站补充）

答案　答案：B（m.count(key)）。

解析：count 返回 0 或 1 且不修改容器；C++20 起还可以用 contains。A 的 m[key] 会插入默认值，D 的 m.find(key) 需要再判断是否为 end()，多一步但也可用。

C1应用改错题：下面的查询逻辑会悄悄往 map 里插入脏数据。

std::map<std::string, int> m{{"a", 1}};
if (m["b"] != 0) { std::cout << "exists"; }
// 判断 m 里有没有 "b"：没有，但 m["b"] 已经插入了 {b:0}

✅ 查看答案与解析（本站补充）

答案　答案：把 if (m[key] == 0) 改成 if (m.count(key) == 0)。

解析：operator[] 在键不存在时会插入默认构造的值（int 为 0），于是“查询”变成了插入，容器被污染。查询用 count / find / contains，确定要写入时才用 []。

D1创造写程序：读入若干单词，用 std::map<std::string,int> 统计每个单词出现次数，最后按字典序输出“单词次数”。

提示：读取到文件结束：while (std::cin >> word)。

✅ 查看答案与解析（本站补充）

答案　参考答案：

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> freq;
    std::string w;
    while (std::cin >> w) {
        ++freq[w];                 // 不存在就插入 0 再自增
    }
    for (const auto& [word, cnt] : freq) {   // map 自动按键升序
        std::cout << word << ' ' << cnt << '\n';
    }
    return 0;
}

解析：++freq[w] 是统计频率的经典写法；遍历 map 得到的就是字典序，不需要额外排序。

7.3 迭代器失效与容器选型

A1识别判断题：vector::erase 会返回指向删除元素之后下一个元素的有效迭代器。

答：______________

✅ 查看答案与解析

答案　对

解析：所以循环里删除元素要写 it = v.erase(it); 并接住返回值。

B1理解选择题：std::list 插入删除是 O(1)，但遍历往往比 vector 慢，主要原因是？

list 的算法复杂度更高

链表节点分散在内存各处，缓存命中率极低

list 不能随机访问

list 不支持范围 for

答：______________

✅ 查看答案与解析

答案　B

解析：链表每次访问都要跳指针，CPU 缓存极不友好；vector 连续内存，实际常数小得多。工程里优先 vector。

B2理解选择题：std::priority_queue<int> 默认是什么堆？

小顶堆

大顶堆

无序数组

平衡树

答：______________

✅ 查看答案与解析

答案　B

解析：C++ 默认最大堆（top() 是最大值），和 Java 默认最小堆相反。要小顶堆写 std::priority_queue<int, std::vector<int>, std::greater<int>>。

C1应用改错题：下面循环删除偶数元素，删除后还 ++it，是未定义行为。

for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) { v.erase(it); }   // it 已失效，还继续 ++it
}

✅ 查看答案与解析

答案　for (auto it = v.begin(); it != v.end(); ) {

解析：erase 返回下一个有效迭代器，接住它；只有没删除时才手动 ++it。

    if (*it % 2 == 0) { it = v.erase(it); }
    else { ++it; }
}

D1创造写程序：读 n 个数，用 priority_queue 输出前 3 大的数（从大到小）。

提示：默认大顶堆，pop 三次即可。

✅ 查看答案与解析

答案　参考答案：

解析：priority_queue 的 top() 是 O(1)，push/pop 是 O(log n)。

#include <iostream>
#include <queue>
int main() {
    int n;
    std::cin >> n;
    std::priority_queue<int> pq;
    for (int i = 0; i < n; ++i) { int x; std::cin >> x; pq.push(x); }
    for (int i = 0; i < 3 && !pq.empty(); ++i) {
        std::cout << pq.top() << ' ';
        pq.pop();
    }
    std::cout << '\n';
    return 0;
}

📚 相关概念：编译与链接 · STL · map / set · 迭代器

← 第 6 章第 8 章 →