C++ 0x正在引入unordered_set,可以在boost许多其他地方使用.我理解的是unordered_set具有O(1)查找复杂性的哈希表.另一方面,set只是具有log(n)查找复杂性的树.为什么人们会使用set而不是unordered_set？即是否需要set了？
C++ 0x添加hash<...>(...).
我找不到一个hash_combine函数,如boost中所示.实现这样的事最简洁的方法是什么？也许,使用C++ 0x xor_combine？
遇到了这个很好的问题,这个问题类似但完全不同,因为它讨论了Java,它具有不同的哈希表实现,因为它具有同步访问器/ mutators HashMap和Hashtable之间的差异？
那么set和unordered_set的C++实现有什么不同呢？对于其他C++容器,这个问题可以扩展到map vs unordered_map等等.
这是我的初步评估
set:虽然标准并没有明确要求它实现为树,但时间复杂性约束要求查找/插入操作,这意味着它将始终实现为树.通常作为RB树(如GCC 4.8中所见),它是高度平衡的.由于它们是高度平衡的,因此它们具有可预测的find()时间复杂度
优点:紧凑(与其他DS相比)
Con:访问时间复杂度为O(lg n)
unordered_set:虽然标准并没有明确要求它实现为树,但时间复杂度约束要求查找/插入操作,这意味着它将始终实现为哈希表.
优点:
缺点:
注意:哈希表的O(1)来自假设没有冲突.即使负载系数为.5,每隔一次变量插入也会导致碰撞.可以观察到,散列表的负载因子与访问其中的元素所需的操作数成反比.我们减少了#operations,sparser hash-table.当存储的元素大小与指针相当时,开销非常重要.
编辑:由于大多数人都说问题中包含足够的答案,我正在将问题改为"我是否会错过地图/集合之间的任何区别,以便进行性能分析？"
基本上我的问题是，为什么不能编译？
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
int main() {
vector<int> v{1,2,3};
auto hash_function=[](const vector<int>& v){
size_t hash;
for (int i = 0; i < v.size(); ++i) {
hash+=v[i]+31*hash;
}
return hash;
};
unordered_set<vector<int>, decltype(hash_function)> s(hash_function);
std::cout<<s.bucket_count();
std::cout<<"here";
}
但如果我将 unordered_set 行更改为此
unordered_set<vector<int>, decltype(hash_function)> s(10,hash_function);
它会。为什么需要初始桶计数？使用 lambda 迫使我添加初始存储桶计数，但使用函子则不会，这似乎很奇怪。请参阅此处的示例：C++ unordered_set of 矢量，以证明函子版本不需要初始数量的存储桶。