一、唯一的差别：重复怎么办

先看一眼同样的输入在两个容器里的结果：

#include <iostream>
#include <set>
using namespace std;

int main() {
    int arr[] = {5, 1, 5, 3, 5, 1, 7};
    set<int>    s(arr, arr + 7);
    multiset<int> m(arr, arr + 7);

    cout << "原始数据： 5 1 5 3 5 1 7（共 7 个）" << endl;
    cout << "set       ：";
    for (int x : s) cout << x << " ";
    cout << " （size=" << s.size() << "）" << endl;

    cout << "multiset  ：";
    for (int x : m) cout << x << " ";
    cout << " （size=" << m.size() << "）" << endl;
    return 0;
}

看到什么算成功：

原始数据： 5 1 5 3 5 1 7（共 7 个）
set       ：1 3 5 7  （size=4）
multiset  ：1 1 3 5 5 5 7  （size=7）

注意 multiset 的输出是 1 1 3 5 5 5 7——重复的元素都留下来了，而且挨在一起、仍然整体有序。这就是 multiset 的全部性格：set 的所有好处 + 不去重。

为什么重复的元素一定挨在一起：因为排序规则是"相等就算同一位置"，相等的元素自然并排站着。这个性质正是下面 equal_range 能成立的基础。

二、三处必然不同

#include <iostream>
#include <set>
using namespace std;

int main() {
    multiset<int> m = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

    cout << "内容：";
    for (int x : m) cout << x << " ";
    cout << "（size=" << m.size() << "）" << endl;

    // ── ① count：真正的"数个数"──
    cout << "count(5) = " << m.count(5) << "（5 出现了几次）" << endl;
    cout << "count(7) = " << m.count(7) << "（没有 7）" << endl;

    // ── ② insert 返回"迭代器"，不是 pair ──
    multiset<int>::iterator it = m.insert(5);        // ★ 不是 pair
    cout << "插入 5 之后，它指向 " << *it << "，当前 count(5)=" << m.count(5) << endl;

    // ── ③ erase(键)：一次删掉所有 5 ────────
    size_t n = m.erase(5);                            // ★ 返回值是"删掉了几个"
    cout << "erase(5) 删掉了 " << n << " 个，现在 count(5)=" << m.count(5) << endl;

    // ── ④ 只想删"其中一个"5：得用迭代器 ─────
    m.insert(5); m.insert(5); m.insert(5);
    cout << "再插三个 5，count(5)=" << m.count(5) << endl;
    multiset<int>::iterator p = m.find(5);            // find 返回"第一个" 5
    if (p != m.end()) m.erase(p);                     // ★ 传迭代器：只删这一个
    cout << "用迭代器删掉一个后，count(5)=" << m.count(5) << endl;
    return 0;
}

看到什么算成功：

内容：1 1 2 3 3 4 5 5 5 6 9 （size=11）
count(5) = 3（5 出现了几次）
count(7) = 0（没有 7）
插入 5 之后，它指向 5，当前 count(5)=4
erase(5) 删掉了 4 个，现在 count(5)=0
再插三个 5，count(5)=3
用迭代器删掉一个后，count(5)=2

这张输出里藏着本节最值钱的一条经验：

erase(键) 和 erase(迭代器) 在这里的含义差得非常远： - m.erase(5) → 删掉所有 5（返回删了几个） - m.erase(m.find(5)) → 只删一个 5

在 multiset 里写错这一处，会一次性删掉好几个元素。 在 set 里因为最多只有一个，看不出区别——所以这个坑只有写 multiset 时才暴露。

三、equal_range：一次拿到"所有相同的键"

既然相等的元素必然挨在一起，那"这一段"就可以用一对迭代器表示出来：

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

int main() {
    multiset<string> m = {"apple", "banana", "apple", "cherry",
                          "apple", "banana", "date"};

    cout << "内容：";
    for (const string &s : m) cout << s << " ";
    cout << endl;

    // ── ① equal_range：拿到"apple 这一段"的 [首, 尾) ──
    pair<multiset<string>::iterator, multiset<string>::iterator> r = m.equal_range("apple");
    cout << "所有 apple：";
    for (multiset<string>::iterator it = r.first; it != r.second; ++it)
        cout << *it << " ";
    cout << endl;

    // ── ② lower_bound / upper_bound：分别拿首和尾 ──
    cout << "lower_bound(\"banana\") → " << *m.lower_bound("banana") << endl;
    cout << "upper_bound(\"banana\") → " << *m.upper_bound("banana") << endl;

    // ── ③ 实际用途：输出"每个词出现了几次"（有序版本）──
    cout << "-- 词频（按字典序，含重复）--" << endl;
    for (multiset<string>::iterator it = m.begin(); it != m.end(); ) {
        pair<multiset<string>::iterator, multiset<string>::iterator> range = m.equal_range(*it);
        int cnt = 0;
        for (multiset<string>::iterator j = range.first; j != range.second; ++j) cnt++;
        cout << "  " << *it << " × " << cnt << endl;
        it = range.second;                        // ★ 直接跳到"这一段之后"
    }
    return 0;
}

看到什么算成功：

内容：apple apple apple banana banana cherry date 
所有 apple：apple apple apple 
lower_bound("banana") → banana
upper_bound("banana") → cherry
-- 词频（按字典序，含重复）--
  apple × 3
  banana × 2
  cherry × 1
  date × 1

三个函数的分工（记住 lower / upper 的"不对称"）：

这个"边界不对称"的设计正是为了处理重复：lower_bound 含、upper_bound 不含，于是两者的差就是等于 x 的元素个数。在 set 里这个差别看不出来（最多一个），在 multiset 里就是它存在的全部理由。 顺带说一句：lower_bound / upper_bound 不是关联式容器的专利——<algorithm> 里也有同名的两个函数，用在已排序的 vector 上（13.3.3）。这正是 13.3.3 要讲的"二分查找"的地基。

四、动手 Demo：成绩统计（multiset 的正确用法）

任务：全班分数（有重复），要自动排好、能立刻算出某个分数有几人、还要取最高最低。

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

int main() {
    // 全班分数（含重复；multiset 自动排序）
    int raw[] = {88, 95, 72, 88, 60, 95, 88, 100, 72, 55};
    multiset<int> scores(raw, raw + 10);

    cout << "全班 " << scores.size() << " 人，成绩（已排序）：";
    for (int s : scores) cout << s << " ";
    cout << endl;

    // ① 最高 / 最低
    cout << "最低分 = " << *scores.begin() << "（第一个）" << endl;
    cout << "最高分 = " << *scores.rbegin() << "（最后一个）" << endl;

    // ② 每个分数有几个人（利用"相同元素挤在一起"）
    cout << "-- 分数分布 --" << endl;
    for (multiset<int>::iterator it = scores.begin(); it != scores.end(); ) {
        pair<multiset<int>::iterator, multiset<int>::iterator> r = scores.equal_range(*it);
        int n = 0;
        for (multiset<int>::iterator j = r.first; j != r.second; ++j) n++;
        cout << "  " << *it << " 分：" << n << " 人" << endl;
        it = r.second;                                // ★ 跳到下一段
    }

    // ③ 查"88 分有几个"
    cout << "88 分有 " << scores.count(88) << " 人" << endl;

    // ④ 及格率
    int pass = 0;
    for (int s : scores) if (s >= 60) pass++;
    cout << "及格 " << pass << " 人，及格率 "
         << (double)pass / scores.size() * 100 << "%" << endl;

    // ⑤ 删掉所有不及格的
    for (multiset<int>::iterator it = scores.begin(); it != scores.end(); ) {
        if (*it < 60) it = scores.erase(it);          // ★ erase 返回"下一个位置"
        else ++it;
    }
    cout << "清掉不及格后剩 " << scores.size() << " 人：";
    for (int s : scores) cout << s << " ";
    cout << endl;
    return 0;
}

看到什么算成功：

全班 10 人，成绩（已排序）：55 60 72 72 88 88 88 95 95 100 
最低分 = 55（第一个）
最高分 = 100（最后一个）
-- 分数分布 --
  55 分：1 人
  60 分：1 人
  72 分：2 人
  88 分：3 人
  95 分：2 人
  100 分：1 人
88 分有 3 人
及格 9 人，及格率 90%
清掉不及格后剩 9 人：60 72 72 88 88 88 95 95 100 

这个 Demo 里最有价值的是"分数分布"那段循环：

for (it = scores.begin(); it != scores.end(); ) {
    auto r = scores.equal_range(*it);      // 拿到"当前这个分数"的整段
    ... 数一数 ...
    it = r.second;                          // ★ 直接跳到下一段
}

如果不这么写（改成 ++it），循环次数会是 10 次（走遍每个元素）；用 equal_range 跳到下一段，只要 6 次（走遍每种分数）。这是"利用容器的结构特性写出高效代码"的典型例子。

30 秒实验

1. erase 的两种含义：写 multiset<int> m = {5,5,5}; m.erase(5); 看 size() → 变成 0（全删了）；改成 m.erase(m.find(5)); → 变成 2（只删一个）。
2. insert 返回值的类型：写 auto r = m.insert(7); 然后 cout << r.second; → 编译不过（multiset 的 insert 返回的是迭代器，不是 pair）。和 set 一起记：set 要 bool 说"插进去没有"，multiset 不必。
3. equal_range 的中间差：auto r = m.equal_range(88); cout << distance(r.first, r.second); → 正好是 88 的个数（这就是"边界不对称"的用途）。
4. count 的效率：m.count(x) 在 multiset 里不是 O(log n)，而是 O(log n + 个数)（要把这一段数一遍）。要"个数"就用 count，要"知道在不在"就用 find（或 count 也行，反正在 set 里一样）。

常见误区

1. "multiset 和 set 差不多，随便用哪个"——差在"删"上：ms.erase(x) 一次删光所有 x。很多人从 set 换到 multiset 时栽在这里——本来只想删一个，结果全没了。要删一个：ms.erase(ms.find(x))。
2. "multiset 的 insert 也能 if (m.insert(x).second)"——编译不过（返回的是 iterator）。这一条是"两兄弟接口不同"的具体体现。
3. "multiset 里的元素可以改"——和 set 一样不能改（元素仍是 const，因为它是排序依据）。要改就删了再插。
4. "count 在 multiset 里很快"——它要把相等的那一段数一遍，所以复杂度是 O(log n + 该值的个数)。数一个出现五万次的键，就是五万次。
5. "multiset 也能排序"——它本来就是有序的，不需要排序。也不能用 std::sort（迭代器只有双向，13.4.4）。
6. "multiset 适合当"购物车"（能加同名商品）"——思路可以，但通常 map<string, int>（商品名 → 数量）更合适（13.2.3）。因为"数量"这一维用 map 的值来记，比存一堆重复的键更省。
7. "multimap 和 multiset 是同一件事"——不是：multiset 只存键，multimap 存"键 + 值"（13.2.4）。

• ☐ 下一节（13.2.3 map类模板）

相关笔记

• set类模板（含实例02） —— 上一节：唯一键的那个
• map类模板 —— 下一节：加一个"值"
• 关联式容器 —— 四个成员的关系表
• 排序算法 —— <algorithm> 里同名的 lower_bound / upper_bound
• 向量类模板 —— 能存重复但不能快查的那个（对照着看）
• 🔷 C++基础 · 索引 —— 全课路线图