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

Multiset是一种类似于set的关联容器类型，唯一的区别是允许有多个元素具有相同的值。 一些与multiset相关的基本函数：

begin() – 返回multiset中第一个元素的迭代器 -> O(1)
end() – 返回multiset中最后一个元素的迭代器之后的理论元素 -> O(1)
size() – 返回multiset中的元素个数 -> O(1)
max_size() – 返回multiset可以容纳的最大元素数 -> O(1)
empty() – 返回multiset是否为空 -> O(1)
insert(x) – 在multiset中插入元素x -> O(log n)
clear() – 从multiset中删除所有元素 -> O(n)
erase(x) – 移除所有等于x的元素 -> O(log n)

实现：

// CPP程序演示multiset的实现 
      #include <iostream> 
      #include <iterator> 
      #include <set> 
       
      using namespace std; 
       
      int main() 
      { 
          // 空的multiset容器 
          multiset<int, greater<int> > gquiz1; 
       
          // 以随机顺序插入元素 
          gquiz1.insert(40); 
          gquiz1.insert(30); 
          gquiz1.insert(60); 
          gquiz1.insert(20); 
          gquiz1.insert(50); 
       
          // 与set不同，50将再次被添加到multiset中 
          gquiz1.insert(50); 
          gquiz1.insert(10); 
       
          // 打印multiset gquiz1 
          multiset<int, greater<int> >::iterator itr; 
          cout << "\nThe multiset gquiz1 is : \n"; 
          for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) { 
              cout << *itr << " "; 
          } 
          cout << endl; 
       
          // 从gquiz1分配元素给gquiz2 
          multiset<int> gquiz2(gquiz1.begin(), gquiz1.end()); 
       
          // 打印multiset gquiz2的所有元素 
          cout << "\nThe multiset gquiz2 \n" 
                  "after assign from gquiz1 is : \n"; 
          for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) { 
              cout << *itr << " "; 
          } 
          cout << endl; 
       
          // 从gquiz2中删除所有小于值为30的元素 
          cout << "\ngquiz2 after removal \n" 
                  "of elements less than 30 : \n"; 
          gquiz2.erase(gquiz2.begin(), gquiz2.find(30)); 
          for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) { 
        cout << *itr << " "; 
          } 
       
          // 在gquiz2中删除所有值为50的元素 
          int num; 
          num = gquiz2.erase(50); 
          cout << "\ngquiz2.erase(50) : \n"; 
          cout << num << " removed \n"; 
          for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) { 
              cout << *itr << " "; 
          } 
       
          cout << endl; 
       
          // multiset gquiz1的下限和上限 
          cout << "\ngquiz1.lower_bound(40) : \n" 
               << *gquiz1.lower_bound(40) << endl; 
          cout << "gquiz1.upper_bound(40) : \n" 
               << *gquiz1.upper_bound(40) << endl; 
       
          // multiset gquiz2的下限和上限 
          cout << "gquiz2.lower_bound(40) : \n" 
               << *gquiz2.lower_bound(40) << endl; 
          cout << "gquiz2.upper_bound(40) : \n" 
               << *gquiz2.upper_bound(40) << endl; 
       
          return 0; 
      }

输出

The multiset gquiz1 is : 
60 50 50 40 30 20 10 

The multiset gquiz2 
after assign from gquiz1 is : 
10 20 30 40 50 50 60 

gquiz2 after removal 
of elements less than 30 : 
30 40 50 50 60 
gquiz2.erase(50) : 
2 removed 
30 40 60 

gquiz1.lower_bound(40) : 
40
gquiz1.upper_bound(40) : 
30
gquiz2.lower_bound(40) : 
40
gquiz2.upper_bound(40) : 
60

从多重集中移除具有相同值的元素：

a.erase() – 移除多重集中所有具有相同值的元素
a.erase(a.find()) – 仅移除多重集中一个具有相同值的元素

在多重集上执行各种操作的时间复杂度为 –

元素插入 – O(logN)
元素访问 – O(logN)
元素删除 – O(logN)

// 用于从具有相同值的多重集中移除元素的CPP代码
# include <bits/stdc++.h>
using namespace std;
 
int main()
{
    multiset<int> a;
    a.insert(10);
    a.insert(10);
    a.insert(10);
 
    // it will give output 3
    cout << a.count(10) << endl;
 
    // 从多重集中移除一个实例
 
    // 它将仅从多重集中移除一个值为10的值
    a.erase(a.find(10));
 
    // it will give output 2
    cout << a.count(10) << endl;
 
    // 从多重集中移除所有元素实例
    // 它将移除所有值为10的元素实例
    a.erase(10);
 
    // 它将输出0，因为所有值的实例
    // 已从多重集中移除
    cout << a.count(10) << endl;
 
    return 0;
}