一 无序集 使用哈希表实现，其中键被散列到哈希表的索引中，以便插入总是随机化的。所有的行动 无序集 需要固定的时间 O（1） 平均可以达到线性时间 O（n） 在最坏的情况下，这取决于内部使用的哈希函数，但实际上它们的性能非常好，通常提供一个恒定时间的查找操作。 这个 无序集 可以包含任何类型的键–预定义的或用户定义的数据结构，但当我们定义用户定义类型的键时，我们需要根据要比较的键指定比较函数。 集合与无序集合 设置 是唯一密钥的有序序列，而无序_集是密钥可以以任意顺序存储的集合，因此无序。Set被实现为一个平衡的树结构，这就是为什么可以保持元素之间的顺序（通过特定的树遍历）。集合运算的时间复杂度为O（logn），而对于无序的_集合，时间复杂度为O（1）。 无序集上的方法： 对于无序的_集，定义了许多函数，其中最常用的是大小和容量为空、查找用于搜索键、插入和删除用于修改。 Unordered_集合只允许唯一键，对于重复键，应使用Unordered_multiset。 无序_集合中的声明、查找、插入和迭代示例如下所示：
CPP
// C++ program to demonstrate various function of unordered_set #include <bits/stdc++.h> using namespace std; int main() { // declaring set for storing string data-type unordered_set <string> stringSet ; // inserting various string, same string will be stored // once in set stringSet.insert( "code" ) ; stringSet.insert( "in" ) ; stringSet.insert( "c++" ) ; stringSet.insert( "is" ) ; stringSet.insert( "fast" ) ; string key = "slow" ; // find returns end iterator if key is not found, // else it returns iterator to that key if (stringSet.find(key) == stringSet.end()) cout << key << " not found" << endl << endl ; else cout << "Found " << key << endl << endl ; key = "c++" ; if (stringSet.find(key) == stringSet.end()) cout << key << " not found" ; else cout << "Found " << key << endl ; // now iterating over whole set and printing its // content cout << "All elements : " ; unordered_set<string> :: iterator itr; for (itr = stringSet.begin(); itr != stringSet.end(); itr++) cout << (*itr) << endl; } |
输出：
slow not foundFound c++All elements : isfastc++incode
查找、插入和擦除平均需要固定的时间。如果key不在set中，find（）函数返回一个iterator to end（），否则返回一个iterator to key position。迭代器充当指向键值的指针，这样我们就可以通过使用*运算符取消对键值的引用来获取键值。 一个基于无序_集的实际问题 –给定一个整数数组（列表），找出其中的所有重复项。
Input : arr[] = {1, 5, 2, 1, 4, 3, 1, 7, 2, 8, 9, 5}Output : Duplicate item are : 5 2 1
下面是使用unOrdEdSeT集合的C++解决方案。
CPP
// C++ program to find duplicate from an array using // unordered_set #include <bits/stdc++.h> using namespace std; // Print duplicates in arr[0..n-1] using unordered_set void printDuplicates( int arr[], int n) { // declaring unordered sets for checking and storing // duplicates unordered_set< int > intSet; unordered_set< int > duplicate; // looping through array elements for ( int i = 0; i < n; i++) { // if element is not there then insert that if (intSet.find(arr[i]) == intSet.end()) intSet.insert(arr[i]); // if element is already there then insert into // duplicate set else duplicate.insert(arr[i]); } // printing the result cout << "Duplicate item are : " ; unordered_set< int > :: iterator itr; // iterator itr loops from begin() till end() for (itr = duplicate.begin(); itr != duplicate.end(); itr++) cout << *itr << " " ; } // Driver code int main() { int arr[] = {1, 5, 2, 1, 4, 3, 1, 7, 2, 8, 9, 5}; int n = sizeof (arr) / sizeof ( int ); printDuplicates(arr, n); return 0; } |
输出：
Duplicate item are : 5 1 2
无序_集的方法：
- 插入（） –在无序的集合容器中插入一个新的{element}。
- 开始 –返回指向无序集合容器中第一个元素的迭代器。
- 结束（） –返回指向结束元素的过去的迭代器。
- 计数（） –统计无序集合容器中特定元素的出现次数。
- 查找（） –在容器中搜索元素。
- 清除（） –从无序的_集合中移除所有元素并清空它。
- cbegin（） –返回指向无序集合容器中第一个元素的常量迭代器。
- cend（） –返回一个常量迭代器，指向无序集合容器或其中一个桶中的结束元素。
- 水桶大小（） –返回无序集合容器中特定存储桶中存在的元素总数。
- 抹去 –移除单个元素或从开始（包含）到结束（排除）的一系列元素。
- 大小（） –返回无序集合容器中的元素数。
- 互换 –交换两个无序容器的值。
- 安置（） –在无序的集合容器中插入一个元素。
- 最大尺寸（） –返回无序集合容器可以容纳的最大元素数。
- 空的（） –检查无序的容器是否为空。
- 等距 –返回包含与给定值相等的所有元素的范围。
- 接线员= –将无序_集复制（或移动）到另一个无序_集，无序_集：：operator=是相应的运算符函数。
- hash_函数（） –该散列函数是一元函数，它只接受一个参数，并基于该参数返回一个类型为size_t的唯一值。
- 储备 –用于请求无序_组的容量更改。
- 桶（） –返回特定元素的桶号。
- 桶数 –返回无序集合容器中存在的桶总数。
- 荷载系数（） –返回无序集合容器中的当前负载系数。
- rehash（） –将无序容器中的桶数设置为给定大小或更大。
- 最大载荷系数（） –返回（或设置）无序集合容器的当前最大负载系数。
- 安放_hint（） –仅当要插入的值是唯一的且带有给定提示时，才在无序_集中插入新元素。
- ==运算符 – ‘==’是C++中的一个运算符，在两个无序集合之间执行相等比较操作，而unOrdEdSySt::运算符==是对应的操作符函数。
- 键_eq（） –根据比较返回布尔值。它返回无序_集使用的键等价比较谓词。
- 接线员= -那个！=在C++ STL中是一个关系操作符，它比较无序的集合容器之间的相等和不相等。
- 最大桶数 –找到无序_集合可以拥有的最大存储桶数。
最近关于无序_集的文章 本文由 乌特卡什·特里维迪 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
