C++ multiset 与 multimap

前面学习的 set 和 map 容器都有一条硬性规则：里面的元素或键必须是唯一的，一旦放入重复数据就会被自动忽略。但在实际开发中，有些数据本身就允许重复，比如全班考试成绩里可能有好几名同学都考了 95 分，或者同一个部门下面对应着多名员工。

遇到这类 “既希望自动按顺序排列，又希望保留重复项” 的需求，我们可以使用 C++ 标准库提供的 std::multiset（多重集合）和 std::multimap（多重映射）。其中前缀 multi 在英文中是 “多个、多重” 的意思。

C++ multiset（多重集合）

在 C++ 中，std::multiset 的用法与前面学过的 std::set 非常相似。两者的主要区别在于 multiset 允许保存多个值相同的元素，并且相同的元素在容器内部会紧挨着排列在一起。

1. 创建、插入与统计次数

使用 std::multiset 之前，我们需要先通过 #include <set> 引入头文件。这里要留意一点，标准库里并没有名为 <multiset> 的独立头文件。

语法：

std::multiset<元素类型> 变量名 = {元素1, 元素2, ...};

说明：

创建好 std::multiset 之后，后续添加新元素同样调用 insert() 成员函数。与普通 set 忽略重复值不同，向 multiset 调用 insert() 时，每一次插入都会成功保存下来。

同时，统计某个值出现了多少次可以使用 count() 成员函数。在普通 set 中，count() 的结果只可能是 0 或 1；而在 multiset 中，count(x) 会返回元素 x 实际出现的总次数。它的常用操作如下表所示。

示例 1：创建 multiset 并统计次数

#include <iostream>
#include <set>

int main() {
    std::multiset<int> scores = {85, 95, 78, 95, 90};
    scores.insert(85);    // 继续插入重复元素

    std::cout << "元素总个数：" << scores.size() << '\n';
    std::cout << "95 出现次数：" << scores.count(95) << '\n';

    for (int s : scores) {
        std::cout << s << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

元素总个数：6
95 出现次数：2
78 85 85 90 95 95

分析：

在这个例子中，初始化 scores 时放入了两个 95，随后调用 scores.insert(85); 又放入了第 2 个 85。所有重复分数都被完整保留了下来，因此 scores.size() 返回 6，scores.count(95) 准确统计出 95 出现了 2 次。

接着我们使用范围 for 循环遍历集合，输出结果自动按从小到大的顺序排成了 78、85、85、90、95、95。需要注意，和普通 set 一样，multiset 中的元素也是只读的，不能通过迭代器直接修改元素的值。

2. 删除单个或全部重复元素

在使用 std::multiset 时，初学者最容易踩坑的地方是 erase() 删除操作。假如集合里有 3 个 20，直接写 nums.erase(20) 会删掉 1 个还是全部删光呢？

答案是会把所有的 20 一次性全部删光。如果我们只想删掉其中的 1 个重复项，比如游戏背包里有两瓶相同的药水、使用一瓶后还需保留另一瓶，就需要先调用 find() 找到第 1 个匹配元素的位置，再将该位置传给 erase()。请看下面例子。

示例 2：单删与全删重复元素

#include <iostream>
#include <set>

int main() {
    std::multiset<int> nums = {10, 20, 20, 20, 30};

    // 1. 先定位再删除，只移除 1 个 20
    auto pos = nums.find(20);
    if (pos != nums.end()) {
        nums.erase(pos);
    }
    std::cout << "单删后 20 的个数：" << nums.count(20) << '\n';

    // 2. 直接按值删除，移除剩余所有的 20
    auto removed = nums.erase(20);
    std::cout << "按值删除的个数：" << removed << '\n';

    for (int n : nums) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

单删后 20 的个数：2
按值删除的个数：2
10 30

分析：

nums 一开始包含 3 个 20。在第 1 步中，nums.find(20) 返回指向第 1 个 20 的迭代器 pos。确认 pos != nums.end() 后，执行 nums.erase(pos) 只会移除这 1 个节点，集合里还剩下 2 个 20。

到了第 2 步，我们直接传入数值调用 nums.erase(20)，函数会把剩余的 2 个 20 全部移除，并返回本次删除的个数 2。平时写代码时，小伙伴们一定要分清下面这 2 种删除写法的区别。

// 方式 1
auto pos = nums.find(20);
if (pos != nums.end()) {
    nums.erase(pos);
}

// 方式 2
nums.erase(20);

简单来说，方式 1 传入位置迭代器，每次最多只删除 1 个匹配项；方式 2 直接传入元素值，会把集合里所有等于该值的元素全部清空。

C++ multimap（多重映射）

当我们需要保存 “键 → 值” 的配对数据，同时又允许同一个键出现多次、关联多条记录时，比如记录 “部门 → 员工姓名” 或 “作者 → 著作名称”，就可以使用 std::multimap。

1. 创建、插入与遍历

std::multimap 直接定义在 <map> 头文件中，标准库里同样没有名为 <multimap> 的头文件。容器中的每一个元素都是一组 std::pair 键值对。

语法：

std::multimap<键类型, 值类型> 变量名 = {
    {键1, 值1},
    {键2, 值2},
    ...
};

说明：

与前面学过的 std::map 相比，std::multimap 在插入和访问数据时有以下 2 个重要差异：

• insert() 总是插入新记录：在普通 map 中，插入已存在的 key 会被忽略；而在 multimap 中，每次调用 insert({key, value}) 都会新增一条记录，并且相同的 key 会自动紧挨着排在一起。
• 不支持 [] 下标与 at() 访问：std::multimap 没有提供 [] 运算符和 at() 成员函数，我们不能写成 staff["Tech"] 来读写数据。

可能有些小伙伴会问：“前面操作 map 时经常使用 [] 读写数据，为什么在 multimap 里不能写 staff["Tech"] 呢？”

原因其实很好理解：在普通 map 中，一个键只对应唯一的值，写 m["Tech"] 目标非常明确。而在 multimap 中，"Tech" 下面可能同时对应着多名员工，编译器根本无法判断你想读取或修改哪一个，因此添加键值对统一使用 insert()。

示例 3：保存一对多的部门员工

#include <iostream>
#include <map>
#include <string>

int main() {
    std::multimap<std::string, std::string> staff = {
        {"Sales", "Lucy"},
        {"Tech", "Jack"}
    };

    staff.insert({"Tech", "Tony"});    // 同一部门新增第 2 人
    staff.insert({"Sales", "Tom"});    // 同一部门新增第 2 人

    std::cout << "总记录数：" << staff.size() << '\n';

    for (const auto& item : staff) {
        std::cout << item.first << ": " << item.second << '\n';
    }
    return 0;
}

运行结果如下。

总记录数：4
Sales: Lucy
Sales: Tom
Tech: Jack
Tech: Tony

分析：

在这个例子中，"Sales" 和 "Tech" 两个部门各自录入了 2 名员工，4 条记录全部成功保存。遍历输出时，容器会自动按部门名称的字母顺序排列，同一个部门下的员工也会紧挨在一起输出。

大家平时写代码时要注意，千万不要习惯性地对 multimap 使用中括号赋值。下面这种写法就是错误的，编译时会直接报错。

std::multimap<std::string, std::string> staff;
staff["Tech"] = "Jack";

2. 查找同一个键的全部值：equal_range()

如果一个键在 multimap 中对应着多条记录，调用 find(key) 只会返回第 1 条匹配记录的位置。那如果我们想把同一个部门下的所有员工一次性全部找出来，应该怎么写呢？

最直接的做法是调用成员函数 equal_range(key)。因为相同的键在容器内部都是连续紧挨着存放的，该函数会一次性返回这段连续记录的 “起始位置” 和 “结束边界”，如下图所示。

语法：

auto range = 映射名.equal_range(key);

说明：

equal_range(key) 返回的结果是一个 std::pair 对象。你可以把这个 range 看作一对卡住首尾的书签，两个成员的含义如下：

• range.first：指向第 1 条键等于 key 的记录位置。
• range.second：指向最后一条键等于 key 的记录 “再往后一格” 的结束边界。

这两个位置刚好构成左闭右开区间 [range.first, range.second)。如果容器里根本不存在这个 key，range.first 和 range.second 就会相等，循环一次也不会执行。

示例 4：查找指定部门的所有成员

#include <iostream>
#include <map>
#include <string>

int main() {
    std::multimap<std::string, std::string> staff = {
        {"Tech", "Jack"},
        {"Sales", "Lucy"},
        {"Tech", "Tony"},
        {"Tech", "Tom"}
    };

    auto range = staff.equal_range("Tech");
    if (range.first != range.second) {
        std::cout << "Tech 部门成员：";
        for (auto it = range.first; it != range.second; ++it) {
            std::cout << it->second << ' ';
        }
        std::cout << '\n';
    }

    auto emptyRange = staff.equal_range("HR");
    if (emptyRange.first == emptyRange.second) {
        std::cout << "未找到 HR 部门记录\n";
    }
    return 0;
}

运行结果如下。

Tech 部门成员：Jack Tony Tom
未找到 HR 部门记录

分析：

staff.equal_range("Tech") 找出了所有键为 "Tech" 的起止范围。随后在 for 循环中，我们让迭代器 it 从起点 range.first 出发，每轮通过 ++it 移向下一条记录，直到抵达结束边界 range.second 停止。循环体内通过 it->second 读取当前记录的值，依次将 "Jack"、"Tony"、"Tom" 打印出来。

再看下半部分查询不存在的 "HR" 部门时，返回的 emptyRange.first 与 emptyRange.second 指向同一个位置，满足相等条件，因此安全输出未找到提示而不会发生越界。另外，和 multiset 一样，调用 staff.erase("Tech") 也会把该键对应的全部记录一次性删光。

四种有序关联容器如何选择？

学到这里，C++ 标准库中按大小自动排序的 4 种关联容器我们就全部认识了。它们在头文件与重复规则上的对应关系如下表所示。

在实际开发中，如果只是保存不重复的数据或一对一映射，我们优先使用更常见的 std::set 和 std::map。只有明确遇到 “既要自动排序，又要保留重复元素或一对多键值” 时，才选用 std::multiset 或 std::multimap。

此外，表达 “一个键对应多个值” 还有一种常见替代方案：把普通 map 的值定义成 std::vector，写成 std::map<std::string, std::vector<std::string>>。如果业务里经常需要按序号读取某个键下的第几个元素，嵌套 vector 会更方便；如果经常逐条增删配对记录或从头到尾扁平遍历，直接使用 std::multimap 会更简洁。