第 7 章 STL 容器与迭代器 · C++ 新手进阶教材（7/13）

🎯 本章你会学到：vector 扩容、map/set 用法、迭代器失效。建议边读边敲代码，每节的练习先自己做，再展开答案对照。

STL 是 C++ 最宝贵的资产，也是你以后写代码的主力工具。一句话概括它的架构：算法通过迭代器操作容器。本章目标：把 vector 用熟、map/set 会统计、防住迭代器失效。

7.1 vector 与迭代器

心智模型：迭代器是“容器的通用指针”——它把“怎么在容器里移动”这件事标准化了。std::sort 不关心你传的是数组还是 vector，只要求一对迭代器。

迭代器的基本操作

auto it = v.begin(); 指向第一个元素，v.end() 指向最后一个元素的下一个位置（左闭右开）。*it 取元素，++it 前进，it->成员访问成员。范围 for 就是迭代器循环的语法糖。

示例代码

for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << ' ';
}

⚠️ 易错点　end() 是开区间：不指向元素，不能解引用 *v.end()。

扩容机制：reserve 为什么重要

size() 是当前元素个数，capacity() 是已申请空间能放多少。push_back 遇到 size == capacity 时，标准库会申请更大内存（常见实现是 1.5~2 倍）、搬元素、释放旧内存。因为指数增长，平摊每次 push_back 是 O(1)。已知规模先 reserve(1000) 避免反复扩容。

⚠️ 易错点　扩容会让所有迭代器、指针、引用失效：int* p = v.data(); v.push_back(4); 之后 *p 是未定义行为。

图 4：push_back 触发的扩容与迭代器失效

✍️ 本节练习

7.1.1必做正数计数

读入 n 个整数存入 vector，输出其中正数的个数。

输入　第一行 n；第二行 n 个整数。

输出　正数的个数。

样例输入

6
-1 2 -3 4 5 -6

样例输出

💡 提示　范围 for 遍历，if (x > 0) 计数。

✅ 查看参考答案与解析

#include <iostream>
#include <vector>
int main() {
    int n;
    std::cin >> n;
    std::vector<int> v(n);
    for (int i = 0; i < n; ++i) { std::cin >> v[i]; }
    int cnt = 0;
    for (int x : v) { if (x > 0) { ++cnt; } }
    std::cout << cnt << '\n';
    return 0;
}

解析　范围 for 里 x 是拷贝，只读遍历最合适。

7.1.2挑战reserve 观察扩容

写程序：创建 vector<int>，循环 push_back 20 个元素，每 push 一个就输出一次 size() 和 capacity()，观察 capacity 翻倍的时刻。再创建一个 reserve(20) 的 vector 做同样的事，对比两次的 capacity 变化。

输入　无

输出　两段，每段 20 行“size=xx capacity=xx”。第一段不 reserve，第二段先 reserve(20)。

样例输入

（本题无输入）

样例输出

size=1 capacity=1
size=2 capacity=2
size=3 capacity=4
...

💡 提示　输出示例只展示前 3 行；真实输出以你的编译器为准，重点是观察 capacity 翻倍点。

✅ 查看参考答案与解析

#include <iostream>
#include <vector>
void show(const std::vector<int>& v) {
    std::cout << "size=" << v.size() << " capacity=" << v.capacity() << '\n';
}
int main() {
    std::vector<int> v1;
    for (int i = 1; i <= 20; ++i) { v1.push_back(i); show(v1); }
    std::vector<int> v2;
    v2.reserve(20);
    for (int i = 1; i <= 20; ++i) { v2.push_back(i); show(v2); }
    return 0;
}

解析　reserve 后 capacity 一直是 20，一次扩容都没有；这就是已知规模先 reserve 的价值。

7.2 map / set：关联容器

set 去重且有序，map 按键存值且有序。它们在统计频率、去重排序、查找配对里是主力。

map 的两个坑

第一个坑：m["apple"] 在键不存在时会插入一个默认值再返回引用——用它判断“键存在吗”会悄悄改变容器大小。只想查询就用 m.count(key) 或 m.find(key)。第二个坑：map 的键是 const 的（红黑树要靠它维持顺序），不能改。

示例代码

std::map<std::string, int> freq;
while (std::cin >> word) { ++freq[word]; }   // 频率统计经典写法
for (const auto& [key, value] : freq) {      // 结构化绑定
    std::cout << key << ' ' << value << '\n';
}

⚠️ 易错点　map 的 O(log n) 是标准硬性保证；unordered_map 的 O(1) 是平均情况，大量哈希冲突会退化。

set：去重 + 有序

std::set 自动去重且按升序排好，插入 O(log n)。读入一堆数去重排序输出，一个 set 就搞定。

⚠️ 易错点　unordered_set/map 的元素没有顺序；需要有序遍历就用 set/map。

✍️ 本节练习

7.2.1必做单词频率统计

读入若干单词（读到文件结束），用 std::map<std::string,int> 统计每个单词出现次数，按字典序输出“单词次数”。

输入　一行或多行英文单词，空格分隔，Ctrl+Z 结束。

输出　每行“单词次数”，按字典序。

样例输入

apple banana apple

样例输出

apple 2
banana 1

💡 提示　while (std::cin >> word) { ++freq[word]; }

✅ 查看参考答案与解析

#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;
}

解析　++freq[word] 是统计频率的经典写法：不存在就插入 0 再自增；map 自动按键排序。

7.2.2挑战set 去重排序

读入 n 个整数，用 std::set 去重后按升序输出。

输入　第一行 n；第二行 n 个整数。

输出　去重后的升序序列，空格分隔。

样例输入

6
3 1 4 1 5 3

样例输出

1 3 4 5

💡 提示　set 自动去重且有序，直接遍历输出。

✅ 查看参考答案与解析

#include <iostream>
#include <set>
int main() {
    int n;
    std::cin >> n;
    std::set<int> s;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        s.insert(x);
    }
    bool first = true;
    for (int x : s) {
        if (!first) { std::cout << ' '; }
        std::cout << x;
        first = false;
    }
    std::cout << '\n';
    return 0;
}

解析　set 底层红黑树：去重 + O(log n) 插入 + 有序遍历一次搞定。

7.3 容器适配器与迭代器失效

stack、queue、priority_queue 是适配器：把底层容器（默认 deque/vector）的接口裁剪成“只能在一端操作”。迭代器失效是容器用法错误的重灾区，必须防。

priority_queue：默认大顶堆

priority_queue 默认是最大堆，top() O(1)、push/pop O(log n)。和 Java 相反（Java 默认最小堆）！写 Dijkstra 要小顶堆时显式写 std::priority_queue<int, std::vector<int>, std::greater<int>>，建议用 using 起别名。

示例代码

std::priority_queue<int> pq;               // 大顶堆，top 是最大值
using MinHeap = std::priority_queue<int,
                std::vector<int>, std::greater<int>>;   // 小顶堆

⚠️ 易错点　priority_queue 没有 clear()，也没有迭代器，想清空只能一个个 pop 或重新赋值。

迭代器失效：循环删除的标准写法

erase 返回“删除后指向下一个元素的有效迭代器”，insert 返回“指向新插入元素的迭代器”。把返回值接住就不会失效。在范围 for 里增删元素会让迭代器失效，行为未定义。

示例代码

for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) { it = v.erase(it); }   // 接住返回值
    else { ++it; }
}

⚠️ 易错点　通用原则：只要循环体要修改容器结构，就不要用范围 for，改用显式迭代器循环并接住返回值。

✍️ 本节练习

7.3.1必做循环删除偶数

读入 n 个整数存入 vector，删除所有偶数，输出剩下的数。必须用“接住 erase 返回值”的正确写法。

输入　第一行 n；第二行 n 个整数。

输出　删除偶数后剩下的数，空格分隔（没有则输出空行）。

样例输入

6
1 2 3 4 5 6

样例输出

1 3 5

💡 提示　for (auto it = v.begin(); it != v.end(); ) { if (*it % 2 == 0) it = v.erase(it); else ++it; }

✅ 查看参考答案与解析

#include <iostream>
#include <vector>
int main() {
    int n;
    std::cin >> n;
    std::vector<int> v(n);
    for (int i = 0; i < n; ++i) { std::cin >> v[i]; }
    for (auto it = v.begin(); it != v.end(); ) {
        if (*it % 2 == 0) { it = v.erase(it); }   // 接住返回值
        else { ++it; }
    }
    for (size_t i = 0; i < v.size(); ++i) {
        std::cout << v[i] << (i + 1 == v.size() ? '\n' : ' ');
    }
    return 0;
}

解析　erase 返回下一个有效迭代器；只有没删除时才手动 ++it。这是迭代器失效的标准解法。

7.3.2挑战前 K 大

读入 n 和 k，用 std::priority_queue 输出前 k 大的数（从大到小）。

输入　第一行 n k；第二行 n 个整数。

输出　前 k 大的数，从大到小空格分隔。

样例输入

6 3
5 9 2 8 1 7

样例输出

9 8 7

💡 提示　默认大顶堆，pop k 次。

✅ 查看参考答案与解析

#include <iostream>
#include <queue>
int main() {
    int n, k;
    std::cin >> n >> k;
    std::priority_queue<int> pq;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        pq.push(x);
    }
    bool first = true;
    while (k-- && !pq.empty()) {
        if (!first) { std::cout << ' '; }
        std::cout << pq.top();
        pq.pop();
        first = false;
    }
    std::cout << '\n';
    return 0;
}

解析　priority_queue 默认大顶堆，top() O(1)、push/pop O(log n)。

本章小结

迭代器=通用指针；end() 是开区间。已知规模先 reserve。
m[key] 会插入默认值，查存在用 count/find；set 去重且有序。
priority_queue 默认大顶堆（和 Java 相反）；小顶堆显式写 greater。
循环里改容器结构：显式迭代器 + 接住 erase/insert 返回值。

🧩 本章综合练习

这几道题把本章多个知识点串起来，建议合上资料独立完成，再展开答案对照。

7.A综合词频榜：map 统计 + 排序排行 + 迭代器删除

读入若干单词直到输入结束，输出：不同单词个数；出现次数最多的前 3 个（次数降序，同次数按字典序）；删除只出现 1 次的单词后剩余个数。

输入　一行或多行英文单词，空格分隔，读到输入结束（Windows 下按 Ctrl+Z 再回车）。

输出　先输出 distinct=，再输出最多 3 行排行，最后输出 after remove singletons=。

样例输入

apple banana apple cherry banana apple

样例输出

distinct=3
apple 3
banana 2
cherry 1
after remove singletons=2

💡 提示　map 本身按 key 有序，要按次数排序得先把 (单词,次数) 拷进 vector 再 sort；删除元素用 it = freq.erase(it)。

✅ 查看参考答案与解析

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>

int main() {
    std::map<std::string, int> freq;
    std::string w;
    while (std::cin >> w) { ++freq[w]; }          // 读到输入结束

    std::cout << "distinct=" << freq.size() << '\n';

    std::vector<std::pair<std::string, int>> items(freq.begin(), freq.end());
    std::sort(items.begin(), items.end(), [](const auto& a, const auto& b) {
        if (a.second != b.second) { return a.second > b.second; }  // 次数降序
        return a.first < b.first;                                  // 同次数按字典序
    });
    for (std::size_t i = 0; i < items.size() && i < 3; ++i) {
        std::cout << items[i].first << ' ' << items[i].second << '\n';
    }

    for (auto it = freq.begin(); it != freq.end(); ) {   // 边遍历边删
        if (it->second == 1) { it = freq.erase(it); }    // 接住返回值
        else { ++it; }
    }
    std::cout << "after remove singletons=" << freq.size() << '\n';
    return 0;
}

解析　erase 返回下一个有效迭代器，只有没删除时才 ++it；这是容器内删除元素的标准写法。

📚 本文概念都在知识大全：

STL · vector · map / set · 迭代器 · 迭代器失效 · 优先队列

← 上一章：第 6 章模板与泛型编程下一章：第 8 章 STL 算法与常用编程范式 →