核心结论：multiset时允许重复元素的set,multimap时匀速重复键的map，他们底层都是红黑树，除了”允许重复“这一点外，其他所有的基础特性与set/map完全相同。

一、multiset 容器详解

1. 与 set 的完整异同对比

特性	set	multiset
底层实现	红黑树	红黑树
自动排序	是（按值升序）	是（按值升序）
元素唯一性	不允许重复	允许重复
插入 / 删除 / 查找时间复杂度	O(log n)	O(log n)
迭代器类型	双向迭代器	双向迭代器
元素可修改性	不可修改（const）	不可修改（const）
迭代器失效规则	插入不失效，删除仅失效被删元素	完全相同
自定义比较函数	支持	支持

唯一本质区别：multiset 允许存储多个相同值的元素，set 不允许。

2. 定义与初始化

基本语法与 set 完全相同，只是会自动保留重复元素：

#include <set>
using namespace std;

// 1. 空multiset
multiset<int> ms1;

// 2. 拷贝构造
multiset<int> ms2(ms1);

// 3. 迭代器范围构造（重点：保留所有重复元素）
int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
multiset<int> ms3(arr, arr + 11);
// set会变成：{1,2,3,4,5,6,9}
// multiset会变成：{1,1,2,3,3,4,5,5,5,6,9} （保留所有重复）

// 4. 列表初始化（同样保留重复）
multiset<int> ms4 = {5, 2, 8, 1, 9, 3, 5, 2};
// ms4: {1,2,2,3,5,5,8,9}

// 5. 自定义比较函数
multiset<int, greater<int>> ms5; // 降序排列

3. 插入操作（关键差异）

（1）基本插入

插入重复元素总是成功，这是与 set 最大的不同：

multiset<int> ms;

ms.insert(10); // 成功，插入第一个10
ms.insert(10); // 成功，插入第二个10
ms.insert(10); // 成功，插入第三个10
// 现在ms中有三个10：{10,10,10}

（2）返回值差异（非常重要）

• set.insert()：返回 pair<iterator, bool>
  • bool 表示是否插入成功
  • iterator 指向插入位置或已存在的元素
• multiset.insert()：只返回 iterator
  • 因为总是插入成功，所以不需要 bool
  • 迭代器指向刚刚插入的那个元素

multiset<int> ms;
auto it1 = ms.insert(10); // 返回指向第一个10的迭代器
auto it2 = ms.insert(10); // 返回指向第二个10的迭代器

cout << *it1 << endl; // 输出10
cout << *it2 << endl; // 输出10
cout << (it1 == it2) << endl; // 输出0（false，指向不同的元素）

（3）其他插入方式

emplace()、插入迭代器范围等方式与 set 完全相同：

ms.emplace(20); // 原地构造，更高效

int arr[] = {30,30,30};
ms.insert(arr, arr+3); // 插入三个30

4. 删除操作（最容易踩坑的地方）

multiset 有两种完全不同的删除方式，这是所有初学者都会踩的坑：

方式一：按值删除 ms.erase(value)

• 作用：删除所有等于 value 的元素
• 返回值：删除的元素个数（可以大于 1）

multiset<int> ms = {1,1,2,3,3,3,4,5};

int num_erased = ms.erase(3);
cout << "删除了" << num_erased << "个元素" << endl; // 输出3
// ms现在变成：{1,1,2,4,5}

方式二：按迭代器删除 ms.erase(iterator)

• 作用：只删除迭代器指向的那一个元素
• 返回值：指向被删除元素下一个元素的迭代器（C++11 及以上）

multiset<int> ms = {1,1,2,3,3,3,4,5};

auto it = ms.find(1); // 找到第一个1
ms.erase(it); // 只删除这一个1
// ms现在变成：{1,2,3,3,3,4,5}

常见错误示例

// 错误：只想删除一个3，结果删除了所有3
multiset<int> ms = {1,2,3,3,3,4};
ms.erase(3); // 错误！删除了所有3
// ms变成：{1,2,4}

// 正确：只删除一个3
auto it = ms.find(3);
if (it != ms.end()) {
    ms.erase(it); // 正确！只删除一个3
}
// ms变成：{1,2,3,3,4}
//要删除第二个3
auto its=ms.find(3);
if(its!=ms.end())
{
    ms.erase(++its);
}
//ms就变成了{1,2,3,4}

5. 查找与遍历重复元素

（1）count(value) 统计个数

• 返回值是 value 出现的次数（可以大于 1）
• 时间复杂度 O (log n + k)，其中 k 是重复元素的个数

multiset<int> ms = {1,1,2,3,3,3,4,5};
cout << ms.count(1) << endl; // 输出2
cout << ms.count(3) << endl; // 输出3
cout << ms.count(6) << endl; // 输出0

（2）find(value) 查找第一个匹配元素

• 返回指向第一个等于 value 的元素的迭代器
• 如果不存在，返回 ms.end()

multiset<int> ms = {1,1,2,3,3,3,4,5};
auto it = ms.find(3);
cout << *it << endl; // 输出3（第一个3）

（3）equal_range(value) 遍历所有重复元素（推荐）

这是遍历 multiset 中所有重复元素的标准且最高效的方式：

• 返回值是 pair<iterator, iterator>
• first 指向第一个等于 value 的元素
• second 指向第一个大于 value 的元素
• 两个迭代器之间的范围就是所有等于 value 的元素

multiset<int> ms = {1,1,2,3,3,3,4,5};

auto range = ms.equal_range(3);
cout << "所有的3：";
for (auto it = range.first; it != range.second; ++it) {
    cout << *it << " ";
}
// 输出：3 3 3

（4）lower_bound 和 upper_bound

equal_range 本质上就是 lower_bound 和 upper_bound 的组合：

auto first = ms.lower_bound(3); // 第一个>=3的元素
auto last = ms.upper_bound(3);  // 第一个>3的元素
// [first, last) 就是所有等于3的元素

6. 常见问题与陷阱

1. 删除单个重复元素必须用迭代器：永远不要用 erase(value) 只想删除一个重复元素
2. equal_range 是遍历重复元素的最佳方式：比多次 find 高效得多
3. 迭代器指向不同的重复元素：即使值相同，不同的重复元素有不同的迭代器
4. 排序与重复元素的顺序：重复元素的相对顺序是稳定的，先插入的排在前面

---

二、multimap 容器详解

1. 与 map 的完整异同对比

特性	map	multimap
底层实现	红黑树	红黑树
自动排序	是（按键升序）	是（按键升序）
键唯一性	不允许重复键	允许重复键
插入 / 删除 / 查找时间复杂度	O(log n)	O(log n)
迭代器类型	双向迭代器	双向迭代器
元素可修改性	键不可修改，值可修改	完全相同
迭代器失效规则	插入不失效，删除仅失效被删元素	完全相同
自定义比较函数	支持	支持
operator [] 和 at ()	有	无

唯一本质区别：multimap 允许存储多个具有相同键的键值对，map 不允许。

2. 定义与初始化

基本语法与 map 完全相同，只是会自动保留重复键：

#include <map>
#include <string>
using namespace std;

// 1. 空multimap
multimap<int, string> mm1;

// 2. 拷贝构造
multimap<int, string> mm2(mm1);

// 3. 迭代器范围构造（保留所有重复键）
pair<int, string> arr[] = {{1, "one"}, {2, "two"}, {1, "yi"}, {3, "three"}, {2, "er"}};
multimap<int, string> mm3(arr, arr + 5);
// map会变成：{1:"yi", 2:"er", 3:"three"}（后面的覆盖前面的）
// multimap会变成：{1:"one", 1:"yi", 2:"two", 2:"er", 3:"three"}（保留所有）

// 4. 列表初始化（同样保留重复键）
multimap<int, string> mm4 = {{1, "apple"}, {2, "banana"}, {1, "orange"}};
// mm4: {1:"apple", 1:"orange", 2:"banana"}

3. 插入操作（关键差异）

（1）基本插入

插入重复键总是成功：

multimap<int, string> mm;

mm.insert({1, "one"}); // 成功，插入第一个键为1的元素
mm.insert({1, "yi"});  // 成功，插入第二个键为1的元素
mm.insert({1, "ichi"}); // 成功，插入第三个键为1的元素
// 现在mm中有三个键为1的元素

（2）返回值差异

• map.insert()：返回 pair<iterator, bool>
• multimap.insert()：只返回 iterator，指向刚刚插入的元素

multimap<int, string> mm;
auto it1 = mm.insert({1, "one"});
auto it2 = mm.insert({1, "yi"});

cout << it1->first << ": " << it1->second << endl; // 输出1: one
cout << it2->first << ": " << it2->second << endl; // 输出1: yi

4. 没有 operator [] 和 at () 方法（最大用法区别）

这是 multimap 与 map 最明显的用法区别，multimap 完全没有 [] 和 at() 方法。

原因很简单：如果有多个相同的键，mm[1] 不知道该返回哪个值，会产生歧义。

map<int, string> m;
m[1] = "one"; // 正确

multimap<int, string> mm;
// mm[1] = "one"; // 编译错误！multimap没有operator[]
// mm.at(1);     // 编译错误！multimap没有at()方法

5. 删除操作（与 multiset 完全相同）

同样有两种删除方式：

multimap<int, string> mm = {{1, "one"}, {1, "yi"}, {2, "two"}, {2, "er"}, {3, "three"}};

// 方式一：按键删除，删除所有具有该键的元素
int num_erased = mm.erase(1);
cout << "删除了" << num_erased << "个元素" << endl; // 输出2
// mm现在变成：{2:"two", 2:"er", 3:"three"}

// 方式二：按迭代器删除，只删除迭代器指向的那一个元素
auto it = mm.find(2);
mm.erase(it); // 只删除一个键为2的元素
// mm现在变成：{2:"er", 3:"three"}

6. 查找与遍历重复键

（1）count(key) 统计键出现的次数

multimap<int, string> mm = {{1, "one"}, {1, "yi"}, {2, "two"}, {2, "er"}, {3, "three"}};
cout << mm.count(1) << endl; // 输出2
cout << mm.count(2) << endl; // 输出2
cout << mm.count(3) << endl; // 输出1

（2）find(key) 查找第一个匹配键

auto it = mm.find(1);
cout << it->first << ": " << it->second << endl; // 输出1: one（第一个匹配的）

（3）equal_range(key) 遍历所有重复键（推荐）

这是遍历 multimap 中所有具有相同键的元素的标准方式：

auto range = mm.equal_range(1);
cout << "所有键为1的元素：" << endl;
for (auto it = range.first; it != range.second; ++it) {
    cout << it->first << ": " << it->second << endl;
}
// 输出：
// 1: one
// 1: yi

7. 常见问题与陷阱

1. 永远不要尝试用 [] 访问 multimap：编译会报错
2. find(key) 只返回第一个匹配的元素：要获取所有必须用 equal_range
3. 修改值：可以通过迭代器修改值，但不能修改键

   auto it = mm.find(1);
   // it->first = 10; // 错误！键不可修改
   it->second = "ONE"; // 正确！值可以修改
   

4. 重复键的顺序：相同键的元素按插入顺序排列，先插入的排在前面

三、最终核心对比总结

操作	set/map	multiset/multimap
元素 / 键唯一性	唯一	允许重复
insert 返回值	pair<iterator, bool>	iterator
erase(value/key)	删除一个匹配元素	删除所有匹配元素
erase(iterator)	删除一个元素	删除一个元素
count 返回值	0 或 1	0 或大于 1 的整数
operator[]	map 有，set 无	都没有
适用场景	需要唯一元素 / 键	允许重复元素 / 键