极客教程C++中的无序pair集合及示例
什么是pair？
C++中的utility库提供了pair容器。一个pair由两个数据元素或对象组成。
- 第一个元素被称为“first”，第二个元素被称为“second”，并且它们的顺序是固定的（first, second）。
- Pair用于将两个可能类型不同的值组合在一起。Pair提供了一种将两个异构对象存储为单个单元的方法。
- 可以对pair进行分配、复制和比较。在一个map或hash_map中分配的对象数组默认为“pair”，其中所有的“first”元素都是唯一键，与它们的“second”的值对象相关联。
- 要访问这些元素，我们使用变量名、点运算符和关键字first或second。
如何访问pair？
我们可以使用下面的代码片段中所解释的点（.）运算符来访问pair元素。
auto fistElement = myPair.first;
auto fistElement = myPair.second;
什么是无序集合？
无序集合是一种关联容器，与集合类似，但是在无序集合的情况下，元素不按任何特定顺序排列。无序集合可以像集合一样持有唯一的元素。无序集合内部使用哈希表实现，键被散列到哈希表的索引中。在无序集合中插入元素总是不可预测的或随机的。无序集合中的大部分操作时间复杂度为常数级别O(1)，但在最坏情况下，时间复杂度可能上升到O(n)。
与无序集合相关的函数：
- insert(x) : 在无序集合容器中插入一个新元素“x”。
- begin() : 返回一个指向无序集合容器中第一个元素的迭代器。
- end() : 返回一个指向虚拟的结束元素旁边的元素的迭代器。
- count() : 计算无序集合容器中特定元素出现的次数。
- erase() : 删除单个元素或从起始到结束（不包括）范围内的一系列元素。
- size() : 返回无序集合容器中的元素数量。
- swap() : 交换两个无序集合容器的值。
- max_size() : 返回无序集合容器可以容纳的最大元素数量。
- empty() : 检查无序集合容器是否为空。
在实现复杂的数据结构时，无序对的集合很有用。本文重点介绍如何在C++中创建无序对集合。
无序对集合
无序对集合是一个无序集合，其中每个元素本身都是一个pair。默认情况下，C++不允许我们直接创建无序对集合，但可以向无序集合容器传递一个哈希函数。
语法：
**unordered_set <pair<dataType1, dataType2>, hashFunction> myUnorderedSet; **
这里，
dataType1： 一个数据类型。
dataType2： 另一个数据类型。
hashFunction： 一个哈希函数。
//哈希函数
结构体HashFunction
{
size_t operator()(const pair<int, int>&x) const{
return x.first^x.second;
}
};
注意: dataType1和dataType2可以相似或不相似。
示例1: 下面是C++程序，演示一组无序的键值对的工作方式。
// C++ program to demonstrate
// the working of unordered set
// of pairs
#include <bits/stdc++.h>
using namespace std;
// Hash function
struct hashFunction
{
size_t operator()(const pair<int ,
int>&x) const
{
return x.first ^ x.second;
}
};
// Function to print unordered set elements
void print(unordered_set<pair<int, int>,
hashFunction>& myUnorderedSet)
{
// Iterating over unordered set elements
for (auto currentPair : myUnorderedSet)
{
// Each element is a pair itself
pair<int, int> pr = currentPair;
cout << "[ ";
// Printing pair elements
cout << pr.first << " " <<
pr.second;
cout << " ]";
cout << "\n";
}
}
// Driver code
int main()
{
// Declaring an unordered set of pairs
unordered_set<pair<int, int>,
hashFunction> myUnorderedSet;
// Initializing pairs of int type
pair<int, int> pair1;
pair1 = make_pair(4, 2);
pair<int, int> pair2;
pair2 = make_pair(2, 3);
pair<int, int> pair3;
pair3 = make_pair(2, 3);
pair<int, int> pair4;
pair4 = make_pair(5, 8);
pair<int, int> pair5;
pair5 = make_pair(9, 5);
// Inserting pairs in the unordered set
myUnorderedSet.insert(pair1);
myUnorderedSet.insert(pair2);
myUnorderedSet.insert(pair3);
myUnorderedSet.insert(pair4);
myUnorderedSet.insert(pair5);
// Calling print function
print(myUnorderedSet);
return 0;
}
输出:
[ 9 5 ]
[ 5 8 ]
[ 4 2 ]
[ 2 3 ]
示例2: 下面是C++程序，演示一组无序的键值对的工作方式。
// C++程序演示无序pair集合的工作
#include <bits/stdc++.h>
using namespace std;
// 哈希函数
struct hashFunction
{
size_t operator()(const pair<bool,
bool> &x) const
{
return x.first ^ x.second;
}
};
// 打印无序集合元素的函数
void print(unordered_set<pair<bool, bool>,
hashFunction> &myUnorderedSet)
{
// 遍历无序集合元素
for (auto currentPair : myUnorderedSet)
{
// 每个元素本身就是一个pair
pair<bool, bool> pr = currentPair;
cout << "[ ";
// 打印pair元素
cout << pr.first << " " <<
pr.second;
cout << " ]";
cout << "\n";
}
}
// 主函数
int main()
{
// 通过将哈希函数作为第二个参数传递给无序集合，声明一个pair无序集合
unordered_set<pair<bool, bool>,
hashFunction> myUnorderedSet;
// 初始化布尔类型的pairs
pair<bool, bool> pair1;
pair1 = make_pair(0, 0);
pair<bool, bool> pair2;
pair2 = make_pair(0, 1);
pair<bool, bool> pair3;
pair3 = make_pair(1, 0);
pair<bool, bool> pair4;
pair4 = make_pair(1, 1);
pair<bool, bool> pair5;
pair5 = make_pair(0, 0);
// 将pairs插入无序集合
myUnorderedSet.insert(pair1);
myUnorderedSet.insert(pair2);
myUnorderedSet.insert(pair3);
myUnorderedSet.insert(pair4);
myUnorderedSet.insert(pair5);
// 调用print函数
print(myUnorderedSet);
return 0;
}
输出:
[ 1 1 ]
[ 0 0 ]
[ 1 0 ]
[ 0 1 ]