第七章容器：STL 的"数据仓库"

本章目标：vector、string（已学）、map、set、pair、tuple、容器的通用操作。会用容器 = 会写 80% 的实际程序。

7.1 vector：自动长大的数组（最常用）

#include <vector>
std::vector<int> v;          // 空 vector
v.push_back(10);             // 末尾追加，v = [10]
v.push_back(20);             // v = [10, 20]
v[0];                        // 10（下标访问，快但不检查）
v.at(0);                     // 10（越界会抛异常，安全）
v.size();                    // 2
v.pop_back();                // 删末尾，v = [10]
v.clear();                   // 清空

多种初始化方式：

std::vector<int> a{1, 2, 3};        // 直接给值
std::vector<int> b(5);              // 5 个 0
std::vector<int> c(5, 7);           // 5 个 7
std::vector<int> d = a;             // 拷贝一份（a 不变）

vector 内部是一块连续内存，满了会自动扩容。对随机访问 [i] 是 O(1)，末尾增删 O(1)，中间插入删除 O(n)。

7.2 遍历容器的正确姿势

// 方式 1（现代首选）：范围 for
for (int x : v) { std::println("{}", x); }       // 只读
for (int& x : v) { x *= 2; }                     // 想改，加 &
for (const auto& x : v) { /* 只读且元素很大 */ }  // 只读+不拷贝

// 方式 2：下标
for (std::size_t i = 0; i < v.size(); ++i) { v[i]; }

// 方式 3：迭代器（C 风格接口需要）
for (auto it = v.begin(); it != v.end(); ++it) { *it; }

记熟了没有？**遍历就用范围 for**。想同时要下标就方式 2。

7.3 map：键值对字典（第二常用）

#include <map>
std::map<std::string, int> scores;   // 键是 string，值是 int
scores["张三"] = 90;                  // 插入/更新
scores["李四"] = 85;
scores["张三"];                       // 90（不存在时会自动插入 0）

// 查是否存在（[ ] 会偷偷插入，要用 find 或 contains）
if (scores.contains("王五")) { ... }   // C++20
// 或 C++17 写法：
auto it = scores.find("王五");
if (it != scores.end()) { /* it->first 键，it->second 值 */ }

// 遍历（自动按键排序）
for (const auto& [name, score] : scores) {
    std::println("{}: {}", name, score);
}

特点：按键有序（红黑树），插入/查找 O(log n)。

unordered_map：不排序版，哈希表，查找 O(1) 平均：

#include <unordered_map>
std::unordered_map<std::string, int> m;   // 用法几乎相同

什么时候用哪个？要"有序遍历"用 map，只要快速查找用 unordered_map。

7.4 set：集合（去重、判存在）

#include <set>
std::set<int> s{3, 1, 2, 2, 3};   // 自动去重且有序：{1, 2, 3}
s.insert(4);
s.contains(2);        // true（C++20）
s.erase(1);
s.size();

典型用途：去重、快速判存在。 unordered_set 是不排序版（哈希）。

7.5 pair / tuple：打包多个值

// pair：两个值
std::pair<int, std::string> p{1, "一"};
p.first;   // 1
p.second;  // "一"

// tuple：任意多个值
std::tuple<int, double, std::string> t{1, 2.5, "x"};
std::get<0>(t);       // 1
std::get<2>(t);       // "x"

// 结构化绑定拆开（C++17，强烈推荐）
auto [n, d, s] = t;            // 按顺序绑定
auto [key, val] = *it;         // 遍历 map 时常用

7.6 其他容器一句话

deque：两头都能快速增删
list：双向链表，中间插入快但查找慢，99% 场景不如 vector
stack / queue / priority_queue：栈、队列、优先队列
array<int, 5>：固定大小的数组，现代版 int[5]
span<int>（C++20）：视图，不拥有数据，只"看"一段数组

重要观念：**默认就用 vector**。其他容器遇到明确需求再换。 "先 vector，够用就行"是现代 C++ 铁律。

7.7 容器通用操作速查

c.size() / c.empty()          // 大小、是否空
c.clear()                     // 清空
c.begin() / c.end()           // 迭代器范围
std::sort(c.begin(), c.end()) // 排序（vector/deque/array）
std::find(c.begin(), c.end(), x)  // 查找（返回迭代器）
c.push_back(x)                // 顺序容器末尾追加
c.insert(it, x)               // 迭代器位置插入

注意：sort/find 是"算法"不是容器方法，要传 begin/end。 C++20 有了 ranges 版本可以直接传容器名（第十二章细讲）。

7.8 迭代器：容器里的"游标"

迭代器像一个"指向容器元素的光标"，支持：

*it        // 取当前元素
++it       // 移到下一个
it != c.end()  // 判断是否到头

end() 是"最后一个元素之后的位置"，是个哨兵，不能解引用。常用写法：

auto it = std::find(v.begin(), v.end(), 5);
if (it != v.end()) {
    std::println("找到了 {}", *it);
} else {
    std::println("没找到");
}

vector 的迭代器失效规则（新手常踩）：向 vector 插入/删除元素后，之前拿到的迭代器和下标可能全部失效！要用新的。

本章小结

vector 是万能默认容器：push_back、[下标]、size、范围 for
map 是键值字典，unordered_map 更快但不排序
set 自动去重，contains 判断存在
pair/tuple 打包数据，结构化绑定 [] 拆包
迭代器 = 游标，begin/end 构成范围
遍历用范围 for，改元素记得加 &

练习题

统计一段文字（存成字符串数组）里每个单词出现次数：用 map。
用 set 给一个 vector 去重，输出排序后的结果。
用 vector 存 100 个随机数（rand() 或 <random>），

排序后打印前 10 个最大的。

用 map<string, vector<int>> 存每个学生的多门成绩，

计算并打印每人平均分。

把 1 万个数塞进 vector，用范围 for 求和，

对比下标 for 的方式看哪个先写完。