@TOC

前言

在C++标准模板库（STL）中，std::multiset 是一种重要的关联容器，用于存储有序的元素，并允许重复元素的存在。它适用于需要维护元素顺序且需要存储重复元素的场景。std::multiset 和 std::set 都基于红黑树（通常的实现方式）来存储元素，确保元素的有序性以及高效的查找、插入和删除操作。理解这两者的区别和用途对选择合适的容器至关重要。

什么是 std::multiset

std::multiset 是一个有序的关联容器，它能够存储多个具有相同键值的元素。与std::set不同，std::multiset 允许在集合中存在重复的元素。每个元素都被自动排序，保证了容器的有序性。它的主要特点包括：

• 元素有序：元素会根据指定的比较函数进行排序，默认是升序。
• 允许重复元素：多个具有相同键值的元素可以存在于同一个std::multiset中。
• 高效的查找：通过红黑树实现，提供对元素的对数时间复杂度的查找、插入和删除操作。

std::multiset与std::set的区别

std::multiset 和 std::set 都是有序的关联容器，但它们有一个关键的区别：

• 允许重复元素：
  • std::set：不允许存储重复的元素。每个元素在集合中是唯一的。
  • std::multiset：允许存储重复的元素。可以在容器中存在多个具有相同键值的元素。

字符串图示

// std::set（不允许重复元素）
set
 v
+---+    +---+    +---+
| 1 | -> | 2 | -> | 3 |
+---+    +---+    +---+

// std::multiset（允许重复元素）
multiset
 v
+---+    +---+    +---+    +---+
| 1 | -> | 1 | -> | 2 | -> | 3 |
+---+    +---+    +---+    +---+

如图所示，std::set 中的元素是唯一的，而std::multiset 中允许重复元素存在。

std::multiset的构造函数

1. 默认构造函数
   创建一个空的std::multiset。

   std::multiset<int> ms;
   

2. 指定比较函数的构造函数
   创建一个空的std::multiset，使用指定的比较函数（默认为升序）。

   std::multiset<int, std::greater<int>> ms;  // 创建一个降序排列的multiset
   

3. 区间构造函数
   使用迭代器范围初始化std::multiset。

   std::vector<int> vec = {1, 2, 2, 3, 4};
   std::multiset<int> ms(vec.begin(), vec.end());  // 用vector的元素初始化multiset
   

4. 复制构造函数
   创建一个std::multiset，它是另一个std::multiset的副本。

   std::multiset<int> ms1 = {1, 2, 3};
   std::multiset<int> ms2(ms1);  // 复制ms1到ms2
   

5. 移动构造函数
   使用另一个std::multiset的内容初始化当前std::multiset，并转移所有权。

   std::multiset<int> ms1 = {1, 2, 3};
   std::multiset<int> ms2(std::move(ms1));  // 移动构造ms1到ms2
   

std::multiset的操作函数

1. insert()
   向std::multiset中插入元素。

   std::multiset<int> ms = {1, 2, 2};
   ms.insert(3);  // ms = {1, 2, 2, 3}
   

2. emplace()
   在std::multiset中原地构造元素（效率更高）。

   std::multiset<int> ms = {1, 2, 2};
   ms.emplace(3);  // ms = {1, 2, 2, 3}
   

3. erase()
   删除指定的元素。对于std::multiset，删除指定值的所有实例。

   std::multiset<int> ms = {1, 2, 2, 3};
   ms.erase(2);  // ms = {1, 3}
   

4. erase(iterator)
   删除指定位置的元素。

   std::multiset<int> ms = {1, 2, 2, 3};
   auto it = ms.find(2);
   if (it != ms.end()) {
       ms.erase(it);  // 删除第一个2，ms = {1, 2, 3}
   }
   

5. find()
   查找并返回指向指定值的迭代器。

   std::multiset<int> ms = {1, 2, 2, 3};
   auto it = ms.find(2);  // it指向第一个2
   

6. count()
   返回指定值的出现次数。

   std::multiset<int> ms = {1, 2, 2, 3};
   size_t count = ms.count(2);  // count = 2
   

7. clear()
   清空std::multiset中的所有元素。

   std::multiset<int> ms = {1, 2, 2, 3};
   ms.clear();  // ms = {}
   

8. empty()
   判断std::multiset是否为空。

   std::multiset<int> ms;
   bool isEmpty = ms.empty();  // isEmpty = true
   

9. size()
   返回std::multiset中元素的数量。

   std::multiset<int> ms = {1, 2, 2, 3};
   size_t size = ms.size();  // size = 4
   

示例代码

#include <iostream>
#include <set>
#include <iterator>

int main() {
    // 创建一个std::multiset并插入元素
    std::multiset<int> ms = {1, 2, 2, 3, 4};

    // 插入更多元素
    ms.insert(2);  // ms = {1, 2, 2, 2, 3, 4}

    // 计算特定元素的数量
    size_t count = ms.count(2);  // count = 3
    std::cout << "Count of 2: " << count << std::endl;

    // 删除指定元素
    ms.erase(2);  // 删除所有2，ms = {1, 3, 4}

    // 查找特定元素
    auto it = ms.find(3);
    if (it != ms.end()) {
        std::cout << "Found element: " << *it << std::endl;  // Found element: 3
    }

    // 清空multiset
    ms.clear();
    std::cout << "Size after clearing: " << ms.size() << std::endl;  // Size after clearing: 0

    return 0;
}

总结

std::multiset 是一个有序的关联容器，允许存储重复元素，并为这些元素提供高效的查找、插入和删除操作。与 std::set 不同，std::multiset 允许重复元素，这使得它在需要存储多个相同键值的元素时非常有用。通过了解 std::multiset 的构造函数和操作函数，你可以更好地利用这个容器来满足特定的需求，无论是在需要有序集合还是在允许重复元素的场景中。