Lecture 5 (Week 3 - Tuesday): 容器 (Containers)

目录 · ← l4 · l6 →

Lecture 5 (Week 3 - Tuesday): 容器 (Containers)

概述

本讲介绍 C++ 标准库（STL）的容器（containers）：std::vector、std::deque、std::map、std::set、std::unordered_map、std::unordered_set。你将学会每种容器的数据结构本质、时间复杂度权衡与适用场景，以及如何统一地遍历它们（for-each 循环，其底层机制是下一讲的主角——迭代器）。容器解决”如何存储一组相关的东西”，是 STL 三大件（容器 / 迭代器 / 算法）的基石，也是 A2（Marriage Pact）的核心工具。幻灯片为图片型（文本极少），本笔记依据课程主题、课堂代码（temperature.cpp、double-agent.cpp）与 C++ 专业知识整理。

核心特性与语法详解

1. 容器是什么（Container）

定义与目的：容器是”存储一组对象”的数据结构抽象。STL 提供多种容器，各有不同的底层实现与操作代价，对应不同场景。
核心语法：std::vector<int> v {1, 2, 3};（C++11 起支持 {} 列表初始化）。
设计意图：不自己手写链表/数组/树——标准库已经实现并优化好了。选择容器的本质是选择时间复杂度：同一个操作在不同容器上开销可以差出几个数量级。

2. 序列容器：std::vector 与 std::deque

定义与目的：按”位置”组织元素，元素有先后顺序、可按下标访问。
std::vector——动态数组：元素存储在一块连续内存中。
- 随机访问 v[i]：O(1)
- 尾部插入/删除 push_back/pop_back：均摊 O(1)（容量不足时整体搬家扩容，均摊后仍为常数）
- 头部/中间插入删除 insert/erase：O(n)（后续元素全部平移）
- 适用：绝大多数默认选择——需要随机访问、主要在尾部增删。
std::deque——双端队列：分块连续内存（多段连续缓冲拼接）。
- 头部与尾部插入/删除 push_front/push_back/pop_front/pop_back：均摊 O(1)
- 随机访问：O(1)（分块定位）
- 中间插入删除：O(n)
- 适用：需要在两端都频繁增删（本讲课后小测：”Which type(s) lets you insert at the back and front equally efficiently?” → std::deque）。
vector 没有 push_front：头部插入只能用 insert(v.begin(), x)（O(n)）——这是设计上”不给你慢方法”的体现（下一讲会再次遇到这个哲学）。

3. 有序关联容器：std::map 与 std::set

定义与目的：按键（key）组织数据，内部是红黑树（平衡二叉搜索树），元素按键有序存储。
std::map：键 → 值的映射，键唯一。查找/插入/删除：O(log n)。遍历时按键升序输出。
std::set：只有键、没有值的”集合”，键唯一、有序，查找/插入/删除 O(log n)。

核心语法：

std::map<std::string, int> ages {{"Alice", 20}, {"Bob", 21}};
ages["Carol"] = 19;                 // 插入或更新
if (ages.find("Alice") != ages.end()) { /* 存在 */ }
std::set<int> s {3, 1, 2};          // 内部按 1,2,3 排序存储

比较运算符要求：map/set 的键类型必须支持 operator<（严格弱序），因为红黑树靠比较维持有序性——这正是课后小测第二问：”Which type(s) requires a comparison operator on the element type?” → std::map, std::set。
适用：需要有序遍历、范围查询、按序输出；能接受 O(log n) 的代价。

4. 哈希关联容器：std::unordered_map 与 std::unordered_set

定义与目的：用哈希表（hash table）组织数据，以空间换时间。
查找/插入/删除：均摊 O(1)（理想情况；最坏 O(n)，取决于哈希质量与负载因子）。
不需要比较运算符，需要的是哈希函数（键类型提供 std::hash<T>）与相等比较 operator==。
遍历顺序无意义：元素按桶（bucket）存放，顺序与插入顺序、大小关系都无关。
为什么通常更快：课后小测第三问：”Which is usually faster: unordered_set or set? Why?” → unordered_set：哈希 + 较小的负载因子（load factor）让查找期望 O(1)，而 set 的红黑树查找严格 O(log n)；元素多时差距明显。
适用：只需要”键存在与否 / 键 → 值”、不需要有序输出时，优先选 unordered 版本。

5. 容器的初始化方式

核心语法（C++11 起，{} 统一初始化 + initializer_list）：

std::vector<int> v {1, 2, 3};                 // 三个元素 1,2,3
std::vector<int> v2(3, 7);                    // 三个元素都是 7（大小 + 初值）
std::map<std::string, int> m {{"a", 1}, {"b", 2}};   // 嵌套 {} 表示键值对
std::set<std::string> names {"Chris", "Nick", "Sean"};

注意区分：vector<int> v{3} 是”一个元素 3”；vector<int> v(3) 是”三个元素 0”。花括号优先匹配 initializer_list。

6. 遍历容器：for-each 循环

定义与目的：统一遍历所有容器（vector/deque/map/set/unordered_*）的方式。

核心语法：

for (const auto& elem : container) { /* 使用 elem */ }
for (const auto& [key, value] : map) { /* C++17 结构化绑定 */ }

机制：for-each 是语法糖，编译器把它展开成迭代器循环（auto b = c.begin(); auto e = c.end(); for (auto it = b; it != e; ++it) { auto& elem = *it; ... }）——这正是下一讲（L6）的核心内容。map 的元素类型是 std::pair<const K, V>，所以遍历 map 时 elem.first 是键、elem.second 是值。
最佳实践：只读遍历用 const auto&（避免拷贝大对象）；需要修改元素用 auto&；unordered_map 的遍历顺序不保证，别依赖。

7. 常用成员函数速查

操作	vector	deque	map/set	unordered_map/set
随机访问 `[i]` / `at(i)`	O(1)	O(1)	—（无下标）	—（无下标）
查找 `find`	O(n)（线性扫）	O(n)	O(log n)	均摊 O(1)
插入	尾部均摊 O(1)	两端 O(1)	O(log n)	均摊 O(1)
`push_back` / `push_front`	有 / 无	都有	—	—
有序遍历	插入序	插入序	按键升序	无序
元素类型要求	无	无	键支持 `operator<`	键支持 `std::hash` + `==`

代码示例与逐步解说（核心）

示例 1：std::vector 与线性扫描（课堂代码 temperature.cpp 补全）

// C++11
#include <iostream>
#include <vector>

// 返回最高温度；没有温度数据时返回 -1
int findPeakHeat(const std::vector<int>& temps) {
    if (temps.empty()) {
        return -1;                      // 空容器保护：不要访问 temps[0]
    }
    int best = temps[0];
    for (const auto& t : temps) {       // 遍历：t 是 const int&
        if (t > best) best = t;
    }
    return best;
}

int main() {
    // 未来 7 天最高气温预报（C++11 列表初始化）
    std::vector<int> weeklyForecast = {62, 63, 65, 68, 69, 66, 65};
    std::cout << "Max temp this week will be " << findPeakHeat(weeklyForecast) << '\n';
    return 0;
}

代码做什么：把 7 个温度放进 vector，用 for-each 找出最大值并打印。
特性机制解说：std::vector<int> 在堆上维护一块连续内存，weeklyForecast 只持有指向这块内存的指针、大小与容量。const auto& t 让 t 成为元素的引用（不拷贝 int 本身，虽然 int 拷贝便宜，但这是好习惯的起点）；empty() 先于 [0] 检查，避免对空容器访问未定义行为。若数据量更大，可直接用 <algorithm> 的 std::max_element（L10 之后会讲），但手写 for-each 更能理解容器语义。

示例 2：std::map + std::set 找”双重身份员工”（课堂代码 double-agent.cpp 补全）

// C++17（结构化绑定；若只支持 C++11 可改用 pair.first/.second）
#include <iostream>
#include <map>
#include <set>
#include <string>

// 找出出现在多个部门里的员工
std::set<std::string> findDoubleAgents(
        const std::map<std::string, std::set<std::string>>& departments) {
    std::set<std::string> seen;
    std::set<std::string> doubleAgents;

    for (const auto& [dept, members] : departments) {  // C++17 结构化绑定
        for (const auto& name : members) {             // 遍历每个部门的员工集合
            if (seen.count(name)) {                    // 之前见过 → 双重身份
                doubleAgents.insert(name);
            } else {
                seen.insert(name);
            }
        }
    }
    return doubleAgents;                               // 按名字升序返回
}

int main() {
    std::map<std::string, std::set<std::string>> company = {
        {"Sales",      {"Jim", "Dwight", "Phyllis"}},
        {"Accounting", {"Angela", "Oscar", "Kevin"}},
        {"Pranks",     {"Jim", "Pam"}}
    };

    std::set<std::string> multiTaskers = findDoubleAgents(company);
    std::cout << "Double Agents: ";
    for (const auto& name : multiTaskers) std::cout << name << " ";  // 应打印 Jim
    std::cout << '\n';
    return 0;
}

代码做什么：公司是 map<部门, set<员工>>；遍历所有部门的所有员工，凡在多个部门出现的名字（Jim 同时在 Sales 和 Pranks）放入结果 set 并打印。
特性机制解说：
- std::map 的遍历元素是 std::pair<const std::string, std::set<std::string>>——C++17 结构化绑定 [dept, members] 等价于 C++11 的 pair.first/pair.second。
- set 的 count(x) 返回 0 或 1（键唯一），可当”是否存在”用；insert 保持有序（红黑树），所以结果自动按字母序输出。
- 嵌套容器 map<string, set<string>> 展示了容器可任意组合，这是 STL”组件可拼装”的设计。
- 整个函数是纯”容器 + 遍历”逻辑，没有手写任何内存管理——这正是容器的价值。

示例 3：std::unordered_map 词频统计（补充示例）

// C++17（结构化绑定；C++11 可用 pair.first/.second）
#include <iostream>
#include <sstream>
#include <string>
#include <unordered_map>

int main() {
    std::string text = "the quick brown fox jumps over the lazy dog the end";
    std::stringstream ss(text);

    std::unordered_map<std::string, int> freq;
    std::string word;
    while (ss >> word) {        // 按空白分词
        ++freq[word];           // operator[]：不存在则默认构造 0，再自增
    }

    for (const auto& [w, c] : freq) {
        std::cout << w << ": " << c << '\n';
    }
    return 0;
}

代码做什么：统计一句话里每个单词出现次数。
特性机制解说：++freq[word] 依赖 operator[] 的语义——键不存在时默认构造一个 int{0} 并插入，然后自增。这是 map/unordered_map 最方便但也最危险的操作（见陷阱 1）。哈希表让每个单词的查找均摊 O(1)；遍历顺序由桶布局决定、与输入顺序无关。若要”按词频从高到低”输出，需要先把条目搬到 vector 再排序——unordered_map 本身不提供有序遍历。

示例 4：map 的 operator[] 陷阱（补充示例）

// C++11
#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> scores;
    scores["Alice"] = 92;       // 插入

    std::cout << scores["Bob"] << '\n';   // 危险：查询时也插入了 {"Bob", 0}！

    if (scores.find("Bob") != scores.end()) {   // C++20 可写作 scores.contains("Bob")
        std::cout << "Bob exists\n";
    } else {
        std::cout << "Bob does not exist\n";
    }

    std::cout << "size = " << scores.size() << '\n';   // 2，而不是 1！
    return 0;
}

代码做什么：试图”查询”Bob 的成绩，结果 Bob 被凭空插入 map。
特性机制解说：m[k] 的完整语义是”如果键不存在，就默认构造一个值插进去，然后返回值的引用”。因此只做存在性检查绝不能用 []——应该用 find（C++20 起可用 contains）。这个陷阱对 std::map 与 std::unordered_map 同样成立。

示例 5：std::deque 双端操作（补充示例）

// C++11
#include <deque>
#include <iostream>
#include <vector>

int main() {
    std::deque<int> d;
    d.push_back(1);             // 尾部插入 O(1)
    d.push_front(0);            // 头部插入 O(1)
    d.push_back(2);
    std::cout << d[0] << ' ' << d[1] << ' ' << d[2] << '\n';  // 0 1 2（随机访问 O(1)）

    std::vector<int> v {1};
    v.push_back(2);             // 尾部均摊 O(1)
    // v.push_front(0);         // ❌ vector 没有 push_front！
    v.insert(v.begin(), 0);     // 头部插入要整体平移：O(n)
    return 0;
}

代码做什么：对比 deque 与 vector 在头部插入的代价。
特性机制解说：deque 内部是”分块连续 + 中央索引”的结构，两端都能 O(1) 增删、仍支持 O(1) 下标访问（比 std::list 强）。课后小测第一问的答案正是 std::deque。而 vector 没有 push_front——C++ 的哲学是不提供注定慢的操作，逼你根据场景选对容器。

与旧标准（如C++98）的对比

std::vector、std::deque、std::map、std::set C++98 已有（源自 1994 年左右的 SGI STL），底层结构与复杂度约定至今未变。真正的变化在使用体验：
无序容器：unordered_map/unordered_set 在 C++11 才进入标准（C++98 时代只能靠 TR1 的 std::tr1::unordered_map 或第三方库）。此前要实现 O(1) 查找只能手写哈希表。
初始化：C++98 没有 {} 列表初始化，容器只能”先构造再逐个 insert/push_back”；C++11 的 initializer_list 让 std::map<std::string, int> m {{"a",1},{"b",2}}; 一行完成。
遍历：C++98 写 for (std::map<std::string, int>::iterator it = m.begin(); it != m.end(); ++it)，类型冗长易错；C++11 的 auto + 范围 for 让遍历变成 for (const auto& p : m)。
C++17 结构化绑定：for (const auto& [k, v] : m) 取代了 pair.first/.second 的手工解包；C++17 的 map::try_emplace 解决”先查再插”的重复哈希问题。
C++20 contains()：m.contains(k) 比 m.find(k) != m.end() 更直白；C++20 的 ranges 视图进一步简化了容器管道操作（L10 之后涉及）。

关键要点

先选对容器，再写代码：随机访问 + 尾部增删 → vector；双端频繁增删 → deque；按键有序查找 → map/set（O(log n)）；只要 O(1) 查找、不在乎顺序 → unordered_map/unordered_set。
有序 vs 无序是根本分歧：map/set 要求键支持 operator< 且遍历有序；unordered_* 要求键支持 std::hash + operator==，遍历无序但通常更快（哈希 + 小负载因子）。
for-each 统一遍历一切容器：for (const auto& elem : c) 对 vector/deque/map/set/unordered_* 都成立（map 元素是 pair）；只读用 const auto&。
operator[] 会插入默认值：存在性检查用 find/contains/count，不要用 []。
遍历时不要修改容器结构（插入/删除元素会使迭代器失效）——收集到新容器后再统一操作。

常见陷阱与注意事项

用 m[k] 做存在性检查：会默默插入默认值，污染数据、改变 size()。改用 find（C++20 contains）、set 用 count。
对空容器取元素：v[0]、v.front()、v.back() 在容器为空时是未定义行为——先 empty() 检查（示例 1 的 findPeakHeat 返回 -1 正是为此）。
vector<int> v{3} vs v(3)：前者是”一个元素 3”，后者是”三个元素 0”——花括号优先匹配 initializer_list，语义完全不同。
误以为 unordered 容器有序：unordered_map 的遍历顺序由哈希桶决定，与插入顺序、键大小都无关；需要有序输出时请用 map，或把条目搬到 vector 再 std::sort。
遍历中插入/删除元素：v.erase(it) 或 m.insert 使相关迭代器失效（vector 尤甚，可能全部失效），在循环里改容器会得到未定义行为——先收集、后修改。
键类型不满足要求：给 map/set 用没有 operator< 的键、给 unordered_* 用没有 std::hash 的类型，编译器直接报错——这不是 bug 而是设计的善意提醒。

关联作业提示

A2: Marriage Pact 的核心工具就是容器与指针：

Part 1 get_applicants：从 students.txt 逐行读名字，存进 std::set（或 std::unordered_set，二选一，需同步修改函数签名）。这正是本讲容器选择的实战：几千个名字、只需判存在/遍历，两者皆可；short_answer.txt 的 Q1 要求你书面回答两者权衡（有序 vs O(1) 哈希、内存、哈希函数质量）并举一个非课堂示例的合法哈希函数——本讲的复杂度对比表就是你的论据。
Part 2 find_matches：遍历 students 集合（用 for-each 或迭代器），对每个名字调用你自己写的 initials() 辅助函数，与 kYourName 的缩写比较；匹配的名字把指针放进 std::queue<const std::string*>——注意存的是 std::string*（指向 set 中字符串的地址）而不是字符串本身，这正是本讲”容器存对象、指针指对象”的衔接。
get_match：从 queue 取”真命天子”时注意 queue 为空的情况（打印 "NO MATCHES FOUND."）。
Q2 简答题：”为什么存指针而不是名字？set 出作用域后指针会怎样？”——答案与容器元素地址的稳定性、指针悬垂（dangling）有关，是 L6 指针内容的直接延伸，务必结合本讲容器内存模型回答。

Share on

Bluesky Facebook LinkedIn Mastodon X (formerly Twitter)

Runguo Li

Lecture 5 (Week 3 - Tuesday): 容器 (Containers)

概述

核心特性与语法详解

1. 容器是什么（Container）

2. 序列容器：std::vector 与 std::deque

3. 有序关联容器：std::map 与 std::set

4. 哈希关联容器：std::unordered_map 与 std::unordered_set

5. 容器的初始化方式

6. 遍历容器：for-each 循环

7. 常用成员函数速查

代码示例与逐步解说（核心）

示例 1：std::vector 与线性扫描（课堂代码 temperature.cpp 补全）

示例 2：std::map + std::set 找”双重身份员工”（课堂代码 double-agent.cpp 补全）

示例 3：std::unordered_map 词频统计（补充示例）

示例 4：map 的 operator[] 陷阱（补充示例）

示例 5：std::deque 双端操作（补充示例）

与旧标准（如C++98）的对比

关键要点

常见陷阱与注意事项

关联作业提示

Share on