17370845950

std::multiset和std::multimap是基于红黑树的有序关联容器，允许键重复；multiset存单一元素，multimap存key-value对，二者均按key升序排列，支持equal_range、count等操作，但无operator[]，erase(key)删除所有匹配项。

std::multiset 和 std::multimap 是 C++ STL 中支持重复键的有序关联容器，底层基于红黑树实现，自动维持元素有序，且允许键值重复 —— 这是它们与 set/map 的核心区别。

std::multiset：允许重复的有序集合

multiset 存储单一元素（即只有 key），所有元素按升序排列，相同值可多次插入。它不提供下标访问，但支持迭代器遍历、范围查找和计数。

• 插入用 insert()，可插入多个相同值：ms.insert(5); ms.insert(5);
• 查找用 find() 返回首个匹配迭代器；用 count() 获取重复个数（O(log n + k)，k 是重复次数）
• 批量删除某值用 erase(key)（注意：这是重载版本，会删掉所有等于 key 的元素）
• 要删单个元素，得用 erase(iterator)，例如：auto it = ms.find(5); if (it != ms.end()) ms.erase(it);
• 获取等价元素范围用 equal_range(key)，返回 pair，左闭右开区间

std::multimap：允许重复键的有序键值对容器

multimap 存储 key-value 对，按 key 升序排序，相同 key 可对应多个不同 value。key 不可修改（因影响排序），但 value 可改。

• 插入用 insert({key, value}) 或 emplace(key, value)，支持重复 key
• 通过 key 查找时，find() 只返回第一个匹配项；equal_range(key) 更实用，能拿到所有该 key 的键值对区间
• 遍历某 key 的所有映射：auto [first, last] = mm.equal_range(42); for (auto it = first; it != last; ++it) cout second
• 注意：multimap 的迭代器解引用得到的是 const pair&，key 是 const，不能写 it->first = ...

常见操作对比：set/map vs multiset/multimap

关键差异不在接口，而在语义和行为：

• insert()： set/map 插入重复 key 会失败（返回 pair，bool 为 false）；multiset/multimap 总成功，返回迭代器
• operator[]： multimap 没有重载 []，因为 key 不唯一；multiset 根本没有 []（无 key-value 结构）
• erase(key)： 在 multiset/multimap 中会删除所有匹配 key 的元素；在 set/map 中只删一个（实际是删掉那个唯一存在的）
• size() 与性能： 插入/查找/删除仍为 O(log n)，但 count() 和 equal_range 在大量重复时可能接近 O(n)，需留意场景

使用建议与注意事项

适合需要按序管理、又允许重复的场景，比如事件时间队列（同一时刻多个事件）、词频统计中间结构、区间索引等。

• 若只需统计重复次数，考虑用 std::map 更节省空间
• 若插入后不再修改，且查询以范围为主，multiset/multimap 很合适；若频繁随机查某个 key 的全部 value，equal_range 是标配用法
• 自定义比较函数时，确保“等价”逻辑与 operator== 一致（尤其用自定义类型作 key 时），否则 find/equal_range 行为可能不符合预期
• 避免对 multimap 的 key 做非常规修改：虽然技术上可通过 const_cast 强转，但会破坏红黑树结构，导致未定义行为