一、multiset简介
multiset是C++ STL（Standard Template Library）的一种关联式容器（Associative Container），基于红黑树实现。它可以存储任意类型的元素，并且自动按照元素的大小进行排序。multiset允许元素重复，在排序的时候不会把相同元素视作同一个。
// 代码示例：
#include <set>
#include <iostream>
int main() {
std::multiset<int> ms;
ms.insert(5);
ms.insert(2);
ms.insert(7);
ms.insert(2);
ms.insert(4);
for (auto it = ms.begin(); it != ms.end(); ++it) {
std::cout << *it << " ";
}
return 0;
}
// 输出结果：
// 2 2 4 5 7
从上面的代码示例中可以看出，multiset允许重复元素，并且在遍历时按照元素大小自动排序。
二、multiset的基本用法
1. 添加元素
multiset提供了多种添加元素的方法，具体如下：
- insert()：向multiset中添加元素。
- emplace()：在multiset中直接生成元素。
- emplace_hint()：在指定位置处直接生成元素，并返回生成元素的迭代器。
// 代码示例：
#include <set>
#include <iostream>
int main() {
std::multiset<int> ms;
ms.insert(5);
ms.insert(2);
ms.emplace(3);
ms.emplace_hint(ms.end(), 4);
for (auto it = ms.begin(); it != ms.end(); ++it) {
std::cout << *it << " ";
}
return 0;
}
// 输出结果：
// 2 3 4 5
从上面的代码示例中可以看出，multiset添加元素的方法使用起来非常简单。
2. 删除元素
multiset提供了多种删除元素的方法，具体如下：
- erase()：从multiset中删除指定元素。
- clear()：清空multiset中所有元素。
// 代码示例：
#include <set>
#include <iostream>
int main() {
std::multiset<int> ms;
ms.insert(5);
ms.insert(2);
ms.insert(3);
ms.insert(4);
ms.erase(2);
for (auto it = ms.begin(); it != ms.end(); ++it) {
std::cout << *it << " ";
}
ms.clear();
std::cout << "n" << ms.size() << std::endl;
return 0;
}
// 输出结果：
// 3 4 5
// 0
从上面的代码示例中可以看出，multiset删除元素的方法使用起来非常简单。
3. 查找元素
multiset提供了多种查找元素的方法，具体如下：
- count()：查找multiset中指定元素的个数。
- find()：查找multiset中指定元素的位置。
- equal_range()：返回multiset中指定元素的范围。
- lower_bound()：返回multiset中第一个大于或等于指定元素的位置。
- upper_bound()：返回multiset中第一个大于指定元素的位置。
// 代码示例：
#include <set>
#include <iostream>
int main() {
std::multiset<int> ms;
ms.insert(5);
ms.insert(2);
ms.insert(3);
ms.insert(4);
std::cout << ms.count(2) << std::endl;
auto it = ms.find(3);
if (it != ms.end()) {
std::cout << *it << std::endl;
}
auto range = ms.equal_range(4);
for (auto i = range.first; i != range.second; ++i) {
std::cout << *i << " ";
}
std::cout << std::endl;
auto lb = ms.lower_bound(3);
if (lb != ms.end()) {
std::cout << *lb << std::endl;
}
auto ub = ms.upper_bound(3);
if (ub != ms.end()) {
std::cout << *ub << std::endl;
}
return 0;
}
// 输出结果：
// 1
// 3
// 4
// 3
// 4
从上面的代码示例中可以看出，multiset查找元素的方法使用起来非常方便。
三、multiset的高级用法
1. 元素比较函数
multiset可以通过指定元素比较函数自定义元素排序规则。
// 代码示例：
#include <set>
#include <iostream>
struct Student {
int id;
std::string name;
int score;
};
bool cmp(const Student& s1, const Student& s2) {
return s1.score > s2.score; // 按照分数从高到低排序
}
int main() {
std::multiset<Student, bool (*)(const Student&, const Student&)> ms(cmp);
ms.insert({1, "Tom", 70});
ms.insert({2, "Jerry", 90});
ms.insert({3, "Mike", 80});
for (auto it = ms.begin(); it != ms.end(); ++it) {
std::cout <name << " " <score << std::endl;
}
return 0;
}
// 输出结果：
// Jerry 90
// Mike 80
// Tom 70
从上面的代码示例中可以看出，multiset可以通过自定义比较函数来排序元素。
2. 自定义存储类型
multiset可以存储任意类型的元素，我们也可以自定义存储类型。需要注意的是，自定义存储类型需要提供比较运算符（operator<）。
// 代码示例：
#include <set>
#include <iostream>
class Point {
public:
int x;
int y;
Point() : x(0), y(0) {}
Point(int x_, int y_) : x(x_), y(y_) {}
bool operator<(const Point& other) const {
if (x != other.x) {
return x < other.x;
}
return y < other.y;
}
};
int main() {
std::multiset<Point> ms;
ms.insert({1, 2});
ms.insert({4, 3});
ms.insert({3, 5});
for (auto it = ms.begin(); it != ms.end(); ++it) {
std::cout << "(" <x << "," <y << ")" << std::endl;
}
return 0;
}
// 输出结果：
// (1,2)
// (3,5)
// (4,3)
从上面的代码示例中可以看出，multiset可以存储自定义类型的元素，并且自动按照元素大小排序。
3. 迭代器失效问题
multiset的插入、删除操作会导致迭代器失效，需要重新获取。尤其是在使用erase()方法删除元素时，需要注意。
// 代码示例：
#include <set>
#include <iostream>
int main() {
std::multiset<int> ms;
ms.insert(5);
ms.insert(2);
ms.insert(3);
auto it = ms.find(2);
if (it != ms.end()) {
ms.erase(it);
}
for (auto it = ms.begin(); it != ms.end(); ++it) {
std::cout << *it << " ";
}
return 0;
}
// 输出结果：
// 3 5
从上面的代码示例中可以看出，使用erase()方法删除元素时需要注意迭代器失效问题。