106 std::multiset (关联容器)
作者Lou Xiao, deepseek创建时间2025-04-02 17:44:58更新时间2025-04-02 17:44:58
1. 基本概念
1.1 定义
std::multiset 是 C++ STL 中的一个关联容器，它存储的元素按照特定排序准则自动排序，允许存储多个值相同的元素。
1.2 特点
- 有序容器：元素总是按照排序准则保持有序状态
- 允许重复元素
- 基于红黑树实现（通常是平衡二叉搜索树）
- 查找、插入和删除操作的时间复杂度为 O(log n)
- 不支持随机访问，只能通过迭代器顺序访问
2. 头文件和声明
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <set>
2
3
// 基本声明
4
std::multiset<Key> ms; // 默认升序排序
5
std::multiset<Key, Compare> ms; // 自定义排序准则
6
std::multiset<Key> ms(other_multiset); // 拷贝构造函数
7
std::multiset<Key> ms(begin, end); // 范围构造函数
3. 模板参数
| 参数 | 描述 |
|---|---|
Key | 存储元素的类型 |
Compare | 比较函数对象类型，默认为 std::less<Key> |
Allocator | 分配器类型，默认为 std::allocator<Key> |
4. 常用成员函数
4.1 容量相关
| 函数 | 描述 |
|---|---|
empty() | 检查容器是否为空 |
size() | 返回元素数量 |
max_size() | 返回容器可容纳的最大元素数量 |
4.2 修改操作
| 函数 | 描述 |
|---|---|
insert(const value_type& val) | 插入元素 |
insert(iterator position, const value_type& val) | 在指定位置插入元素 |
insert(InputIterator first, InputIterator last) | 插入范围元素 |
emplace(args...) | 原位构造并插入元素 |
erase(iterator position) | 删除指定位置元素 |
erase(const key_type& k) | 删除所有键为k的元素 |
erase(iterator first, iterator last) | 删除范围元素 |
clear() | 清空容器 |
swap(multiset& x) | 交换两个multiset内容 |
4.3 查找操作
| 函数 | 描述 |
|---|---|
find(const key_type& k) | 查找键为k的元素 |
count(const key_type& k) | 返回键为k的元素数量 |
lower_bound(const key_type& k) | 返回第一个不小于k的元素迭代器 |
upper_bound(const key_type& k) | 返回第一个大于k的元素迭代器 |
equal_range(const key_type& k) | 返回键为k的元素范围 |
4.4 迭代器
| 函数 | 描述 |
|---|---|
begin(), cbegin() | 返回指向第一个元素的迭代器 |
end(), cend() | 返回指向末尾的迭代器 |
rbegin(), crbegin() | 返回指向最后一个元素的反向迭代器 |
rend(), crend() | 返回指向开头前一个位置的反向迭代器 |
5. 使用示例
5.1 基本操作
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <set>
3
4
int main() {
5
std::multiset<int> ms = {5, 2, 4, 3, 2, 1};
6
7
// 插入元素
8
ms.insert(4);
9
ms.insert(6);
10
11
// 遍历元素
12
for (int x : ms) {
13
std::cout << x << " ";
14
}
15
// 输出: 1 2 2 3 4 4 5 6
16
17
// 查找元素
18
auto it = ms.find(3);
19
if (it != ms.end()) {
20
std::cout << "\nFound: " << *it;
21
}
22
23
// 删除元素
24
ms.erase(2); // 删除所有值为2的元素
25
26
// 计数
27
std::cout << "\nNumber of 4s: " << ms.count(4);
28
29
return 0;
30
}
5.2 自定义排序
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <set>
3
#include <string>
4
5
struct CaseInsensitiveCompare {
6
bool operator()(const std::string& a, const std::string& b) const {
7
return std::lexicographical_compare(
8
a.begin(), a.end(),
9
b.begin(), b.end(),
10
[](char c1, char c2) {
11
return tolower(c1) < tolower(c2);
12
});
13
}
14
};
15
16
int main() {
17
std::multiset<std::string, CaseInsensitiveCompare> ms;
18
19
ms.insert("Apple");
20
ms.insert("banana");
21
ms.insert("apple");
22
ms.insert("Banana");
23
24
for (const auto& s : ms) {
25
std::cout << s << " ";
26
}
27
// 输出顺序可能为: Apple apple Banana banana
28
29
return 0;
30
}
6. 性能分析
| 操作 | 时间复杂度 |
|---|---|
| 插入 | O(log n) |
| 删除 | O(log n) |
| 查找 | O(log n) |
| 计数 | O(log n + k) (k为匹配元素数量) |
| 范围查询 | O(log n + k) |
7. 与相关容器比较
| 特性 | std::multiset | std::set | std::unordered_multiset |
|---|---|---|---|
| 排序 | 有序 | 有序 | 无序 |
| 重复元素 | 允许 | 不允许 | 允许 |
| 实现 | 红黑树 | 红黑树 | 哈希表 |
| 查找时间 | O(log n) | O(log n) | 平均O(1)，最差O(n) |
| 插入时间 | O(log n) | O(log n) | 平均O(1)，最差O(n) |
| 内存使用 | 较高 | 较高 | 较低 |
| 迭代顺序 | 按键排序 | 按键排序 | 无特定顺序 |
8. 使用场景
- 需要维护有序数据集合
- 需要频繁查找、插入和删除操作
- 允许重复元素存在
- 不需要随机访问元素
- 需要按顺序遍历元素
9. 注意事项
- 插入和删除操作不会使迭代器失效（除了被删除元素的迭代器）
- 自定义比较函数必须满足严格弱序关系
- 对于复杂类型，考虑提供高效的比较操作以优化性能
- 当不需要排序时，
std::unordered_multiset可能提供更好的性能 - 迭代器是双向迭代器，不支持随机访问
10. 高级用法
10.1 提取节点(C++17)
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
std::multiset<int> ms = {1, 2, 3, 4, 5};
2
auto node = ms.extract(3); // 提取键为3的节点
3
if (!node.empty()) {
4
std::cout << "Extracted: " << node.value();
5
}
10.2 合并容器(C++17)
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
std::multiset<int> ms1 = {1, 2, 3};
2
std::multiset<int> ms2 = {3, 4, 5};
3
ms1.merge(ms2);
4
// ms1: {1, 2, 3, 3, 4, 5}
5
// ms2: 可能为空或保留部分元素
10.3 透明比较(C++14)
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
struct Compare {
2
using is_transparent = void;
3
bool operator()(int a, int b) const { return a < b; }
4
bool operator()(int a, double b) const { return a < b; }
5
bool operator()(double a, int b) const { return a < b; }
6
};
7
8
std::multiset<int, Compare> ms = {1, 2, 3, 4, 5};
9
auto it = ms.find(3.5); // 可以比较不同类型
std::multiset 常用 API 的整理表格
| 名称 | 用途 | 原型 | 代码示例 | 注释 |
|---|---|---|---|---|
| 构造函数 | 创建空的 multiset 或从其他容器/范围初始化 | multiset()multiset(InputIt first, InputIt last) | cpp<br>std::multiset<int> ms;<br>std::multiset<int> ms2(v.begin(), v.end());<br> | 默认构造函数创建空容器；范围构造函数从迭代器范围初始化。 |
| insert | 插入元素（允许重复） | iterator insert(const T& value) | cpp<br>ms.insert(42);<br>ms.insert({1, 2, 2}); // 插入多个元素<br> | 返回指向插入元素的迭代器。时间复杂度通常为 O(log n)。 |
| erase | 删除指定元素或范围内的元素 | size_type erase(const T& value)iterator erase(iterator pos) | cpp<br>ms.erase(2); // 删除所有值为2的元素<br>ms.erase(ms.begin()); // 删除第一个元素<br> | 返回删除的元素数量（或下一个有效迭代器）。 |
| find | 查找元素，返回首个匹配的迭代器 | iterator find(const T& value) | cpp<br>auto it = ms.find(42);<br>if (it != ms.end()) { /* 存在 */ }<br> | 未找到时返回 end()。时间复杂度 O(log n)。 |
| count | 返回匹配元素的数量 | size_type count(const T& value) | cpp<br>size_t n = ms.count(2); // 返回2的个数<br> | 时间复杂度 O(log n + k)，k 为匹配元素数量。 |
| lower_bound | 返回首个不小于 value 的元素的迭代器 | iterator lower_bound(const T& value) | cpp<br>auto it = ms.lower_bound(10); // 首个>=10的元素<br> | 用于范围查询（结合 upper_bound）。 |
| upper_bound | 返回首个大于 value 的元素的迭代器 | iterator upper_bound(const T& value) | cpp<br>auto it = ms.upper_bound(10); // 首个>10的元素<br> | 常与 lower_bound 配合实现区间查询。 |
| equal_range | 返回匹配元素范围的迭代器对（[lower_bound, upper_bound)） | std::pair<iterator, iterator> equal_range(const T& value) | cpp<br>auto [first, last] = ms.equal_range(2); // 所有2的范围<br> | 返回的 first 和 last 可用于遍历所有相同元素。 |
| size | 返回元素数量 | size_type size() const | cpp<br>size_t s = ms.size();<br> | 时间复杂度 O(1)。 |
| empty | 检查容器是否为空 | bool empty() const | cpp<br>if (ms.empty()) { /* 空 */ }<br> | 等价于 size() == 0。 |
| clear | 清空容器 | void clear() | cpp<br>ms.clear();<br> | 移除所有元素，容器大小变为 0。 |
| begin/end | 返回指向首元素和尾后位置的迭代器 | iterator begin()iterator end() | cpp<br>for (auto it = ms.begin(); it != ms.end(); ++it) { ... }<br> | 支持正向遍历。end() 不可解引用。 |
| rbegin/rend | 返回反向迭代器（用于逆序遍历） | reverse_iterator rbegin()reverse_iterator rend() | cpp<br>for (auto it = ms.rbegin(); it != ms.rend(); ++it) { ... }<br> | 从最后一个元素到第一个元素遍历。 |
| emplace | 直接构造并插入元素（避免临时对象复制） | iterator emplace(Args&&... args) | cpp<br>ms.emplace(42); // 直接构造int(42)<br> | 性能优于 insert（对于非简单类型）。 |
| max_size | 返回容器可容纳的最大元素数量（理论值） | size_type max_size() const | cpp<br>size_t m = ms.max_size();<br> | 实际值可能受系统内存限制。 |
关键特性说明：
- 允许重复元素：与
std::set不同，multiset允许存储多个值相同的元素。 - 自动排序：元素始终按比较器（默认
std::less<T>）排序，插入/删除时维护有序性。 - 底层实现：通常基于红黑树（平衡二叉搜索树），保证操作效率。
示例代码（综合使用）：
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <set>
3
4
int main() {
5
std::multiset<int> ms = {1, 2, 2, 3};
6
7
// 插入元素
8
ms.insert(2); // 允许重复
9
10
// 查找并计数
11
auto it = ms.find(2);
12
std::cout << "Count of 2: " << ms.count(2) << std::endl; // 输出 3
13
14
// 范围查询
15
auto [first, last] = ms.equal_range(2);
16
for (; first != last; ++first) {
17
std::cout << *first << " "; // 输出所有2: 2 2 2
18
}
19
20
return 0;
21
}
文章目录