C++标准模板库（STL）中的Multiset

C++标准模板库（STL）是C++中非常有用的一部分，它也是C++成为一种广泛使用语言的原因之一。STL中有许多非常有用的模板结构，其中之一就是Multiset。Multiset是一个有序的关联容器，可以同时拥有多个相同值的元素。Multiset使用红黑树来表示有序集合，所以它的所有操作都是对数级别的，这使它成为非常优秀的数据结构。

在STL中，Multiset头文件是，可以通过以下代码引入：

#include <set>

Multiset的语法如下：

multiset<Type, Compare, Alloc>

Type是元素的类型，Compare是一个可选的比较函数，它可以用来自定义元素的排序方法。Alloc是一个可选的分配器对象，用来分配存储器。

Multiset的关键方法包括以下几个：

insert() – 向multiset中插入元素
erase() – 从multiset中删除元素
find() – 查找是否存在指定元素
count() – 统计multiset中指定元素的数量

下面我们将详细了解每个方法。

插入元素

Multiset中的insert()方法用于向multiset中插入元素。insert()方法的语法如下：

iterator insert(const value_type& val);

这个方法将元素插入到multiset中并返回一个迭代器指向这个元素。如果插入的元素已经存在于multiset中，insert()方法不会做任何事情，仍然返回元素的迭代器。

下面是插入元素的示例代码：

#include <iostream>
#include <set>

using namespace std;

int main() {
    multiset<int> myset = { 10, 20, 30 };
    auto it = myset.insert(25);
    it = myset.insert(it, 26);
    it = myset.insert(it, 27);
    cout << "myset contains:";
    for (int i : myset) cout << ' ' << i;
    cout << '\n';
    return 0;
}

输出结果为：

myset contains: 10 20 25 26 27 30

在上面的示例中，我们首先创建了一个multiset，然后使用insert()方法插入三个元素。接着，我们使用迭代器指定位置插入剩下的三个元素。最后，我们使用for循环打印multiset中的所有元素。

删除元素

Multiset中的erase()方法用于从multiset中删除元素。erase()方法的语法如下：

iterator erase(iterator position);
size_type erase(const value_type& val);
iterator erase(iterator first, iterator last);

第一个版本的erase()方法删除由迭代器指定的元素。第二个版本的erase()方法删除所有等于给定值的元素。第三个版本的erase()方法删除指定范围内的所有元素。

下面是删除元素的示例代码：

#include <iostream>
#include <set>

using namespace std;

int main() {
    multiset<int> myset = { 10, 20, 30, 20 };
    myset.erase(20);
    cout << "myset contains:";
    for (int i : myset) cout << ' ' << i;
    cout << '\n';
    return 0;
}

输出结果为：

myset contains: 10 30

在上面的示例中，我们首先创建了一个multiset，然后使用erase()方法删除等于20的元素。

查找元素

Multiset中的find()方法用于查找multiset中是否存在指定元素。find()方法返回一个迭代器，如果元素不存在于multiset中，则返回multiset::end()方法返回的迭代器。

下面是查找元素的示例代码：

#include <iostream>
#include <set>

using namespace std;

int main() {
    multiset<int> myset = { 10, 20, 30, 20 };
    auto it = myset.find(20);
    if (it != myset.end()) {
        cout << "Element found in myset: " << *it << endl;
    } else {
        cout << "Element not found in myset" << endl;
    }
    return 0;
}

输出结果为：

Element found in myset: 20

在上面的示例中，我们首先创建了一个multiset，然后使用find()方法查找值为20的元素。如果元素存在于multiset中，则打印其值，否则打印“Element not found”。

统计元素数量

Multiset中的count()方法用于统计multiset中指定元素的数量。count()方法返回元素出现的次数。

下面是统计元素数量的示例代码：

#include <iostream>
#include <set>

using namespace std;

int main() {
    multiset<int> myset = { 10, 20, 30, 20 };
    cout << "20 appears " << myset.count(20) << " times in myset." << endl;
    cout << "40 appears " << myset.count(40) << " times in myset." << endl;
    return 0;
}

输出结果为：

20 appears 2 times in myset.
40 appears 0 times in myset.

在上面的示例中，我们首先创建了一个multiset，然后使用count()方法统计值为20和40的元素出现次数。

自定义元素排序

Multiset中的元素是有序的，排序方式由Multiset模板的第二个参数Compare指定。如果没有指定Compare参数，则默认使用less函数对象来排序元素。可以自定义Compare函数对象以使用其他排序方式。

下面是自定义元素排序的示例代码：

#include <iostream>
#include <set>

using namespace std;

struct Student {
    int id;
    string name;
    bool operator<(const Student& s) const {
        return id < s.id;
    }
};

int main() {
    multiset<Student> myset = { {1, "Tom"}, {5, "Jerry"}, {3, "Mickey"}, {2, "Donald"} };
    cout << "Multiset contains:";
    for (auto it : myset) {
        cout << " (" << it.id << ", " << it.name << ")";
    }
    cout << endl;
    return 0;
}

输出结果为：

Multiset contains: (1, Tom) (2, Donald) (3, Mickey) (5, Jerry)

在上面的示例中，我们自定义了一个Student结构体，并在其中重载了小于号运算符。然后我们使用这个结构体创建了一个multiset，multiset中的元素按照id从小到大排序。

结论

Multiset是C++标准模板库（STL）中非常有用的一个容器，它可以同时拥有多个相同值的元素，并使用红黑树实现有序存储和查找。Multiset是一个非常高效的数据结构，其所有操作都是对数级别的。可以通过insert()方法向multiset中插入元素，而erase()方法则用于从multiset中删除元素。可以使用find()方法查找元素是否存在，使用count()方法统计元素出现次数。对于排序方式，可以默认使用less函数对象，也可以自定义比较函数来实现其他排序方式。了解这些关键方法，可以在实际应用中更好地使用Multiset。