C++中的Multiset of Pairs及示例

什么是Multiset？

Multiset是一种关联式容器，它可以按特定顺序容纳多个元素。与Set不同，Multiset可以包含多个相同元素的出现。

一些与Multiset相关的函数：

• begin() ： 返回Multiset中第一个元素的迭代器。
• end() ： 返回在Multiset中最后一个元素之后的理论元素的迭代器。
• size() ： 返回Multiset中元素的数量。
• max_size() ： 返回Multiset可以容纳的最大元素数量。
• empty() ： 返回Multiset是否为空。

什么是Pair？

C++中的Utility头文件为我们提供了Pair容器。Pair由两个数据元素或对象组成。

• 第一个元素被引用为“first”，第二个元素被引用为“second”，并且其顺序固定（first，second）。
• Pair用于组合两个可能不同类型的值。Pair提供了一种将两个异构对象作为单个单元存储的方法。
• Pair可以被分配、复制和比较。在默认情况下，映射或哈希图中分配的对象数组的类型为’pair’，其中所有’first’元素都是唯一的键，与它们的’second’值对象相关联。
• 要访问这些元素，我们使用变量名后跟点运算符后跟关键字first或second。

如何访问Pair？

使用点（.）运算符访问Pair的元素。

语法：

  auto firstElement = myPair.first;
  auto secondElement = myPair.second;

Pair的Multiset

Pair的Multiset是一个Multiset，其中每个元素本身就是一个Pair。如果相应的第一个和第二个元素相等，则认为两个Pair相等。如果需要存储一个Pair的多个副本，以及其他元素，而且还需要按特定顺序，此时Pair的Multiset就非常有用。

语法：

**multiset <pair<dataType1，dataType2>> myMultiset; **

在这里，

dataType1和dataType2 可以是相似或不同的数据类型。

示例1： 下面是一个C++程序的示例，演示了具有整数值的Pair的Multiset的工作方式。

// C++程序演示了
// 实现嵌套对的multiset
#include <bits/stdc++.h>
using namespace std;
 
// Function to print multiset
// elements
void print(multiset<pair<int,
           int>> &multisetOfPairs)
{ 
  // 遍历multiset嵌套对元素
  for (auto cuurentPair : multisetOfPairs)
  {
    // 每个元素本身就是一个元组
    pair<int, int> pr = cuurentPair;
 
    // 打印对元素
    cout << "[ " << pr.first << ' ' <<
             pr.second << " ]"<< '\n';
  }
}
 
// 驱动程序
int main()
{
  // 声明一个多元组的multiset
  multiset<pair<int,
  int>> multisetOfPairs;
 
  // 初始化一个对
  pair<int, int> pair1;
  pair1 = make_pair(1, 2);
 
  // 初始化一个对
  pair<int, int> pair2;
  pair2 = make_pair(3, 4);
 
  // 初始化另一个对
  pair<int, int> pair3;
  pair3 = make_pair(5, 6);
 
  // 初始化另一个对
  pair<int, int> pair4;
  pair4 = make_pair(7, 8);
 
  // 初始化另一个对
  pair<int, int> pair5;
  pair5 = make_pair(9, 10);
 
  // 插入到multiset中
  multisetOfPairs.insert(pair1);
  multisetOfPairs.insert(pair2);
  multisetOfPairs.insert(pair3);
  multisetOfPairs.insert(pair4);
  multisetOfPairs.insert(pair5);
 
  // 调用print函数
  print(multisetOfPairs);
 
  return 0;
}  

输出：

[ 1 2 ]   
[ 3 4 ]   
[ 5 6 ]   
[ 7 8 ]   
[ 9 10 ] 

时间复杂度: O(n* log n). //n是multiset中元素的个数。

空间复杂度: O(n).

解释：

在上面的输出中，元素按照multiset的对的排序顺序排列。

例2： 下面是演示具有字符串值的数字对链表的multiset的C++程序。

// C++程序演示了
// 实现嵌套对的multiset
#include <bits/stdc++.h>
using namespace std;
 
// Function to print multiset elements
void print(multiset<pair<string,
           string>> &multisetOfPairs)
{
  // 遍历multiset嵌套对元素
  for (auto currentPair : multisetOfPairs)
  {
    // 每个元素本身就是一个对
    pair<string, string> pr = currentPair;
 
    // 打印对元素
    cout << "[ " << pr.first << ' ' <<
             pr.second << " ]"<< '\n';
  }
}
 
//驱动程序
int main()
{
  // 声明一个多元组的multiset
  multiset<pair<string,
  string>> multisetOfPairs;
 
  // 初始化一个对
  pair<string, string> pair1;
  pair1 = make_pair("GeeksforGeeks",
                    "GFG");
 
  // 初始化一个对
  pair<string, string> pair2;
  pair2 = make_pair("Swift",
                    "Python");
 
  // 初始化另一个对
  pair<string, string> pair3;
  pair3 = make_pair("C++", "C");
 
  // 初始化另一个对
  pair<string, string> pair4;
  pair4 = make_pair("PHP",
                    "HTML");
 
  // 初始化另一个对
  pair<string, string> pair5;
  pair5 = make_pair("Javascript",
                    "CSS");
 
  // 插入到multiset中
  multisetOfPairs.insert(pair1);
  multisetOfPairs.insert(pair2);
  multisetOfPairs.insert(pair3);
  multisetOfPairs.insert(pair4);
  multisetOfPairs.insert(pair5);
 
  // 调用print函数
  print(multisetOfPairs);
 
  return 0;
}  

输出：

[ C++ C ]   
[ GeeksforGeeks GFG ]   
[ Javascript CSS ]   
[ PHP HTML ]   
[ Swift Python ] 

时间复杂度： O(n* log n)。//这里的n是一个multiset中的大小。

空间复杂度： O(n)。

解释：

以上输出中，元素按照multiset中对的排列顺序进行排序。