一、两种思路的根本差别

先看同一个需求，两种容器的写法：

// 需求：记住每个人的年龄，之后按名字查

// ── 序列容器的做法：自己找 ──
vector<pair<string, int>> v;
v.push_back(make_pair("张三", 20));
v.push_back(make_pair("李四", 22));
// 查"李四"的年龄：得写个循环一个个比
int age = -1;
for (size_t i = 0; i < v.size(); i++)
    if (v[i].first == "李四") { age = v[i].second; break; }

// ── 关联式容器的做法：它自己知道该在哪 ──
map<string, int> m;
m["张三"] = 20;
m["李四"] = 22;
int age2 = m["李四"];        // ★ 一句就到手

差别的本质：序列容器只保证"位置"，你得自己知道"东西放在第几个"；关联式容器自己维护"按什么排"，你只需要给出"键"。

最后两行很关键，顺序记不住就容易犯错： - 不能改元素：set 里的值就是它的"排序依据"，一改就破坏有序性 → 只能 erase 再 insert。 - 迭代器只有双向：所以 set / map 也不能用 std::sort（因为它们本来就一直是排好序的，根本不需要排序）。

二、四个成员：一张表看全

"两两成对"的含义：set 和 multiset 的差别只有"允不允许重复"；map 和 multimap 也一样。所以学一个，另一个就是"加一条允许重复"。

那 set 和 map 的区别呢？ ——map 比 set 多存了一个"值"。可以这样理解：set 的每个元素是 key，map 的每个元素是一个 pair<const key, value>。

set<string>:       {"数学", "语文", "英语"}
                    ↑ 每个元素就是一个键

map<string,int>:   { {"数学", 95}, {"语文", 88}, {"英语", 92} }
                     ↑ 每个元素是"键 + 值"的一对

三、动手 Demo：同一份数据，两种存法

任务：统计一段文字里出现过哪些不重复的词，以及每个词出现的次数。

#include <iostream>
#include <set>
#include <map>
#include <sstream>
#include <string>
using namespace std;

int main() {
    string text = "apple banana apple cherry banana apple";

    // ── ① 去重（set 最典型的用法）──
    set<string> words;
    stringstream ss(text);
    string w;
    while (ss >> w) words.insert(w);          // ★ 自动去重 + 自动排序

    cout << "不重复的词有 " << words.size() << " 个：";
    for (const string &s : words) cout << s << " ";
    cout << endl;

    // ── ② 计数（map 最典型的用法）──
    map<string, int> cnt;
    stringstream ss2(text);
    while (ss2 >> w) {
        cnt[w]++;                             // ★ 没见过就自动建一个（值默认 0），再 +1
    }
    cout << "词频：" << endl;
    for (const map<string, int>::value_type &p : cnt)     // ★ value_type = pair<const string, int>
        cout << "  " << p.first << " -> " << p.second << endl;

    return 0;
}

看到什么算成功：

不重复的词有 3 个：apple banana cherry 
词频：
  apple -> 3
  banana -> 2
  cherry -> 1

两处"它就替我做了"：

注意 map 遍历时那个长类型：map<string, int>::value_type 就是 pair<const string, int>。键是 const 的——这正是"不能改键"的语法体现。C++11 之后可以写 const auto &p : cnt，省掉这一长串。

30 秒实验

1. 改一下输入顺序：把 text 改成 "cherry apple banana"，重跑 → 输出顺序完全一样（set / map 都是自动排序的）。
2. set 和 multiset 对比：把 set<string> words; 改成 multiset<string> words; 重跑 → size() 变成 5，apple 出现了三次。这就是两兄弟唯一的差别。
3. 验证"不能改元素"：写 *words.begin() = "x"; → 报 assignment of read-only location（因为 set 的元素是 const 的）。
4. 验证"没有下标"：写 words[0] → 编译不过（set 没有 operator[]）。注意：map 有 operator[]，但那个参数是"键"不是"下标"。

常见误区

1. "set / map 也能用 sort"——不能（迭代器只有双向）。但它们本来就有序，不需要排。 想换排序规则，要在定义时给比较函数（13.2.3）。
2. "关联式容器比序列容器快，所以都该用它"——看操作：按值查找、去重、排序它快（O(log n) vs O(n)）；按下标遍历、频繁在尾部追加它反而慢（树结构到处跳，缓存不友好，且每个节点有额外开销）。"要按位置取"的场景，vector 才是正解。
3. "顺序容器就是无序，关联式容器才有顺序"——说反了一半：序列容器有"你放进来的顺序"，关联式容器有"排好的顺序"。 两个都有顺序，只是" 谁决定顺序"不同。
4. "改了 set 里的元素也没关系"——编译期就会拦你（元素是 const）。要改就 erase + insert——这个动作还顺便保证它在新的位置上排序正确。
5. "关联式容器里放的键，什么类型都行"——要求这个类型"能用 < 比较"（因为它要靠比较来建树）。存自定义类时，要么给它重载 <（11.2），要么在定义容器时给一个比较函数。 否则报一大串看不懂的模板错误（12.4 小结说的"模板报错看最后一条 note"在这里特别有用）。
6. "set 和 unordered_set 是一回事"——不是。set 有序、O(log n)；unordered_set（哈希表）无序、平均 O(1)。要"有序"或"按顺序遍历"就用 set；只要"快速去重/查找"用 unordered_set 更快。 教材只讲有序版，认得这个名字就好。

• ☐ 下一节（13.2.1 set类模板）

相关笔记

• 链表类模板 —— 上一节：序列容器的收尾
• set类模板（含实例02） —— 下一节：去重 + 排序一步到位
• map类模板 —— 最常用的关联式容器
• 简单类模板 —— std::pair 的来历
• 重载运算符 —— 想让自定义类型当键，得会重载 <
• 双向迭代器 —— 关联式容器的迭代器为什么只有双向
• 🔷 C++基础 · 索引 —— 全课路线图