C / C++ / 系统课时

multimap 和 multiset 有何不同

multimap 和 multiset 有何不同

当一个键可能对应多条记录,普通 map 或 set 的“键唯一”就不够用了。multimap 和 multiset 都允许重复键,但前者保存键值对,后者只保存可重复的值;配合 equal_range 可以一次定位某个键的完整区间。

学习目标

  • 区分 multimap、multiset 与 map、set 的数据模型
  • 使用 equal_range 遍历同一键对应的全部元素
  • 理解重复键容器在查询、插入和修改上的关键边界

两类容器保存的数据不同

std::multimap<Key, T> 保存的是“键 → 值”关系,同一个键可以出现多次。例如一个课程标签 cpp 可以对应多条成绩记录。std::multiset<T> 则只有元素本身,元素同时承担“值”和“键”的角色,适合保存允许重复的有序数据,如一组分数或事件优先级。

它们与单值关联容器的差别可以概括为:

容器 元素形态 是否允许重复键 常见用途
map key -> value 否 一个键唯一对应一个值
multimap key -> value 是 一个键对应多条记录
set value 否 去重并保持有序
multiset value 是 保留重复值并保持有序

multimap 不提供 operator[],因为当一个键对应多条记录时,“下标访问应该返回哪一条”没有唯一答案。

用 equal_range 取得完整范围

equal_range(key) 返回一对迭代器,表示半开区间 [first, second)。其中 first 指向第一个等于该键的元素,second 指向最后一个等值元素之后的位置;若键不存在,两者通常相等。

下面的完整程序同时演示 multimap 和 multiset:

cpp
#include <iostream>
#include <map>
#include <set>
#include <string>

int main() {
    std::multimap<std::string, int> scores{
        {"cpp", 90},
        {"python", 80},
        {"cpp", 95}
    };

    auto [first, last] = scores.equal_range("cpp");
    for (auto it = first; it != last; ++it) {
        std::cout << it->first << ": " << it->second << '\n';
    }

    std::multiset<int> values{3, 1, 3, 2, 3};
    auto [begin3, end3] = values.equal_range(3);

    std::cout << "count(3): ";
    int count = 0;
    for (auto it = begin3; it != end3; ++it) {
        ++count;
    }
    std::cout << count << '\n';
}

预期输出:

text
cpp: 90
cpp: 95
count(3): 3

如果只关心重复次数,可以直接使用 count(key);如果还要读取、删除或逐条处理这些元素,equal_range 更合适,因为它直接给出可遍历的区间。

插入、查找与删除时要注意什么

向 multimap 或 multiset 插入已存在的键不会覆盖旧元素,而是新增一个等值元素。按键查找时,find 只返回其中一个匹配位置,不能代表全部重复元素;需要完整集合时应使用 equal_range。

删除也有两种常见粒度。调用 erase(key) 会删除该键对应的所有元素;若只想删掉其中一条,应先取得具体迭代器,再调用 erase(iterator)。

什么时候选择 multimap 或 multiset

如果业务数据天然是“一对多”,并且希望元素始终按键排序,multimap 很合适;如果只需要保存可重复、自动排序的值,则选择 multiset。两者的查找和插入通常是对数复杂度,遍历某个键的全部 k 个匹配项时,总成本可看作 O(log n + k)。

若主要需求是按键快速定位而不要求有序,还可以考虑 unordered_multimap 或 unordered_multiset;但当你需要范围查询、稳定的排序遍历,或依赖比较顺序时,有序的多重关联容器更直接。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

multimap 和 multiset 有何不同

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通