c++ std中set与unordered_set区别和map与unordered_map区别类似,其底层的数据结构说明如下:
1、set基于红黑树实现,红黑树具有自动排序的功能,因此map内部所有的数据,在任何时候,都是有序的。
2、unordered_set基于哈希表,数据插入和查找的时间复杂度很低,几乎是常数时间,而代价是消耗比较多的内存,无自动排序功能。底层实现上,使用一个下标范围比较大的数组来存储元素,形成很多的桶,利用hash函数对key进行映射到不同区域进行保存。
更详细的区别,如下图:
set与unordered相比:
1、set比unordered_set使用更少的内存来存储相同数量的元素。
2、对于少量的元素,在set中查找可能比在unordered_set中查找更快。
3、尽管许多操作在unordered_set的平均情况下更快,但通常需要保证set在最坏情况下有更好的复杂度(例如insert)。
4、如果您想按顺序访问元素,那么set对元素进行排序的功能是很有用的。
5、您可以用<、<=、>和>=从字典顺序上比较不同的set集。unordered_set集则不支持这些操作。
一般来说,在如下情况,适合使用set:
1、我们需要有序的数据(不同元素)。
2、我们必须打印/访问数据(按排序顺序)。
3、我们需要知道元素的前任/继承者。
一般来说,在如下情况,适合使用unordered_set:
1、我们需要保留一组元素,不需要排序。
2、我们需要单元素访问,即不需要遍历。
3、仅仅只是插入、删除、查找的话。
示例:
set:
Input : 1, 8, 2, 5, 3, 9
Output : 1, 2, 3, 5, 8, 9
unordered_set:
Input : 1, 8, 2, 5, 3, 9
Output : 9 3 1 8 2 5 (顺序依赖于 hash function)
下面再给出一个以vector
1 set<vector<int>> s;
2 s.insert({1, 2});
3 s.insert({1, 3});
4 s.insert({1, 2});
5
6 for(const auto& vec:s)
7 cout<<vec<<endl;
8 // 1 2
9 // 1 3
因为vector重载了operator<,因此可以作为set的key。
但是如果直接使用unordered_set
1 struct VectorHash {
2 size_t operator()(const std::vector<int>& v) const {
3 std::hash<int> hasher;
4 size_t seed = 0;
5 for (int i : v) {
6 seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2);
7 }
8 return seed;
9 }
10 };
接下来这样使用:
1 unordered_set<vector<int>, VectorHash> s;
2 s.insert({1, 2});
3 s.insert({1, 3});
4 s.insert({1, 2});
5
6 for(const auto& vec:s)
7 cout<<vec<<endl;
8 // 1 2
9 // 1 3
或者模板特化struct hash
1 namespace std {
2 template<>
3 struct hash<std::vector<int>> {
4 size_t operator()(const vector<int> &v) const {
5 std::hash<int> hasher;
6 size_t seed = 0;
7 for (int i : v) {
8 seed ^= hasher(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
9 }
10 return seed;
11 }
12 };
13 }
14
15 // usage example
16 void test_unordered_set(){
17 unordered_set<std::vector<int>> s;
18 s.insert({1, 2});
19 s.insert({1, 3});
20 s.insert({1, 2});
21 for(const auto& vec:s)
22 cout<<vec<<endl;
23 // 1 3
24 // 1 2
25
26 std::hash<int> hasher;
27 cout<<"hasher(99): "<<hasher(99)<<" ,hasher(77): "<<hasher(77)<<endl;
28 // hasher(99): 99 ,hasher(77): 77
29 }
可以看到,在某些情况下,unordered_set的使用门槛还是挺高的。
Input : 1, 8, 2, 5, 3, 9
Output : 1, 2, 3, 5, 8, 9
原文链接: https://www.cnblogs.com/codingmengmeng/p/13992692.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/205123
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!