极客教程在C++中的无序向量集及例子
什么是无序集合？
在C++中，无序集合是一个无序的容器，可以容纳许多独特的元素。与set不同，无序集合中的元素没有按任何特定顺序排列。在内部，使用哈希表实现无序集合，其中键被哈希到哈希表的索引中，因此插入总是随机的。无序集合上的所有操作在平均情况下都需要恒定的时间O(1)，但在最坏情况下可能需要线性时间O(n)，这也取决于内部使用的哈希函数。
unordered_set可以包含任何类型的键，预定义的或用户定义的数据结构，但是当我们定义用户定义类型的键时，需要根据比较函数指定我们的键将被比较。
与无序集合相关的函数：
- insert() ： 在无序集合容器中插入一个新{元素}。
- begin() ： 返回一个指向无序集合容器中第一个元素的迭代器。
- end() ： 返回一个指向超出尾部元素的迭代器。
- count() ： 计算一个无序集合容器中特定元素的出现次数。
- find() ： 在容器中搜索一个元素。
- clear() ： 从无序集合中删除所有元素并清空它。
什么是向量？
在C++中，向量类似于具有重新调整大小功能的动态数组。向量的元素存储在相邻的内存位置中，可以使用迭代器访问它们。
一些与向量相关的函数如下所述：
- begin() ： 返回一个指向向量中第一个元素的迭代器。
- end() ： 返回一个指向理论上的超尾元素的迭代器。
- rbegin() ： 返回一个指向向量中最后一个元素的反向迭代器(反向开始)。它从最后一个元素向前移动。
- rend() ： 返回一个指向理论上在向量中第一个元素之前的元素的反向迭代器(被认为是反向尾部)。
- cbegin() ： 返回一个指向向量中第一个元素的常量迭代器。
- cend() ： 返回一个指向理论上的超尾元素的常量迭代器。
- crbegin() ： 返回一个指向向量中最后一个元素的常量反向迭代器(反向开始)。它从最后一个元素向前移动。
- crend() ： 返回一个指向理论上在向量中第一个元素之前的元素的常量反向迭代器(被认为是反向尾部)。
什么是无序向量集？
一个无序集合向量是一个无序关联容器，用于将唯一的向量组合在一起。如果向量的对应元素相等，那么两个向量被认为是相同的。
与向量的集合不同，在无序集合向量中，向量不以任何特定顺序排列。默认情况下，C++不提供创建无序集合向量的功能。我们需要传递一个哈希函数，使用这个哈希函数，人们可以轻松创建一个无序集合的向量。
语法：
unordered_set <vector<dataType>, hashFunction> myUnorderedSet;
在这里，
dataType: 一个数据类型。它表示存储在无序集合中每个向量中的值的类型。
hashFunction:
sctruct hashFunction
{
size_t operator()(const vector<int> &myVector) const
{
std::hash<int> hasher;
size_t answer = 0;
for (int i : myVector)
{
answer ^= hasher(i) + 0x9e3779b9 +
(answer << 6) + (answer >> 2);
}
return answer;
}
};
注意：
一个人可以根据需要自定义哈希函数，但是上面的哈希函数相当有效地处理冲突。
示例1： 下面是整数类型向量的无序集合的C++程序。
// C++ program to demonstrate the
// working of unordered set of vectors
#include <bits/stdc++.h>
using namespace std;
// Hash function
struct hashFunction
{
size_t operator()(const vector<int>
&myVector) const
{
std::hash<int> hasher;
size_t answer = 0;
for (int i : myVector)
{
answer ^= hasher(i) + 0x9e3779b9 +
(answer << 6) + (answer >> 2);
}
return answer;
}
};
// Function to iterate over
// vector elements
void printVector(vector<int> myVector)
{
cout << "[ ";
for(auto element : myVector)
cout << element << ' ';
cout << "]\n";
}
// Function to iterate over unordered
// set elements
void print(unordered_set<vector<int>,
hashFunction> &unorderedsetOfVectors)
{
for (auto it = unorderedsetOfVectors.begin();
it != unorderedsetOfVectors.end();
it++)
{
// Each element is a vector
printVector(*it);
}
}
// Driver code
int main()
{
// Declaring a unordered set of vectors
// Each vector is of integer type
// We are passing a hash function as
// an argument to the unordered set
unordered_set<vector<int>,
hashFunction> unorderedsetOfVectors;
// Initializing vectors
vector<int> myVector1 {3, 6, 9, 10};
vector<int> myVector2 {5, 10, 11, 7};
vector<int> myVector3 {3, 6, 9, 10};
vector<int>4; {1, 9, 11, 22};
vector<int> myVector5 {50, 20, 30, 40};
// Inserting vectors into unorderedset
unorderedsetOfVectors.insert(myVector1);
unorderedsetOfVectors.insert(myVector2);
unorderedsetOfVectors.insert(myVector3);
unorderedsetOfVectors.insert(myVector4);
unorderedsetOfVectors.insert(myVector5);
// Calling print function
print(unorderedsetOfVectors);
return 0;
}
输出:
[ 50 20 30 40 ]
[ 1 9 11 22 ]
[ 3 6 9 10 ]
[ 5 10 11 7 ]
解释：
Vector1和vector3在上面的例子中是相同的。由于无序集合只包含唯一的元素，因此它只在无序集合内打印了一次。另外，请注意，无序集合没有遵循任何特定的元素顺序。
示例2: 下面是一个布尔类型向量的无序集合的C++程序。
// C++ program to demonstrate the
// working of unordered set
// of vectors
#include <bits/stdc++.h>
using namespace std;
// Hash function
struct hashFunction
{
size_t operator()(const vector<bool>
&myVector) const
{
std::hash<bool> hasher;
size_t answer = 0;
for (int i : myVector)
{
answer ^= hasher(i) + 0x9e3779b9 +
(answer << 6) + (answer >> 2);
}
return answer;
}
};
// Function to iterate over
// vector elements
void printVector(vector<bool> myVector)
{
cout << "[ ";
for(auto element : myVector)
cout << element << ' ';
cout << "]\n";
}
// Function to iterate over unordered
// set elements
void print(unordered_set<vector<bool>,
hashFunction> &unorderedsetOfVectors)
{
for (auto it = unorderedsetOfVectors.begin();
it != unorderedsetOfVectors.end();
it++)
{
// Each element is a vector
printVector(*it);
}
}
// Driver code
int main()
{
// 声明布尔类型向量的无序集合
// 每个向量都是bool类型的
// 我们将哈希函数作为参数传递给无序集合
unordered_set<vector<bool>, hashFunction> unorderedsetOfVectors;
// 初始化布尔类型的向量
vector<bool> myVector1
{ true, true, true, true };
vector<bool> myVector2
{ false, false, false, false };
vector<bool> myVector3
{ true, true, true, false };
vector<bool> myVector4
{ true, true, false, false };
vector<bool> myVector5
{ true, true, false, true };
vector<bool> myVector6
{ true, true, true, true };
//将向量插入到无序集合中
unorderedsetOfVectors.insert(myVector1);
unorderedsetOfVectors.insert(myVector2);
unorderedsetOfVectors.insert(myVector3);
unorderedsetOfVectors.insert(myVector4);
unorderedsetOfVectors.insert(myVector5);
unorderedsetOfVectors.insert(myVector6);
//调用print函数
print(unorderedsetOfVectors);
return 0;
}
输出：
[ 1 1 0 1 ]
[ 1 1 0 0 ]
[ 1 1 1 0 ]
[ 1 1 1 1 ]
[ 0 0 0 0 ]
解释：
Vector1和Vector6在上面的例子中是相同的。由于无序集合只包含唯一的元素，因此它只在无序集合内打印了一次。另外，请注意，无序集合没有遵循任何特定的元素顺序。