标签: unordered-set

我想要有类似的东西

 unordered_set<vector<pair<int,int>>> us;

但即使没有配对:

#include <vector>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<vector<int>> um;
}

它失败:

In file included from /usr/include/c++/4.8/bits/hashtable.h:35:0,
                 from /usr/include/c++/4.8/unordered_set:47,
                 from prog.cpp:2:
/usr/include/c++/4.8/bits/hashtable_policy.h: In instantiation of ‘struct std::__detail::_Hash_code_base<std::vector<int>, std::vector<int>, std::__detail::_Identity, std::hash<std::vector<int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>’:
/usr/include/c++/4.8/bits/hashtable_policy.h:1402:10:   required from ‘struct std::__detail::_Hashtable_base<std::vector<int>, std::vector<int>, std::__detail::_Identity, std::equal_to<std::vector<int> >, std::hash<std::vector<int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, true, true> >’
/usr/include/c++/4.8/bits/hashtable.h:174:11:   required from ‘class std::_Hashtable<std::vector<int>, std::vector<int>, std::allocator<std::vector<int> >, std::__detail::_Identity, std::equal_to<std::vector<int> >, std::hash<std::vector<int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >’
/usr/include/c++/4.8/bits/unordered_set.h:96:18:   required from …

在我的申请中,我有以下要求 -

1. 数据结构将仅使用一些值(不是键/值对)填充一次.值可能会重复,但我希望数据结构只存储一次.

2. 我将通过上面创建的数据结构的所有元素迭代100次.元素在迭代中出现的顺序并不重要.

约束1表明我将不得不使用set或unordered_set,因为数据不是键值对的形式.

现在set插入比unordered_set插入更昂贵,但数据结构只在我的程序开头填充一次.

我相信决定因素是我可以多快地迭代数据结构的所有元素.我不确定set或unordered_set对于此目的是否会更快.我相信标准没有提到这个事实,因为这个操作对于任一数据结构都是O(n).但我想知道iterator.next()哪个数据结构会更快.

问题

对于用户定义类型的std :: unordered_map或std :: unordered_set的第三个模板参数,std :: hash有什么好的特殊性,所有成员数据类型都已经具有良好的std :: hash特性？

对于这个问题,我将"好"定义为易于实现和理解,合理有效,并且不太可能产生哈希表冲突.商品的定义不包括任何有关安全性的陈述.

什么是谷歌的状态

目前,两个StackOverflow问题是Google搜索"std hash specialization"的第一个问题.

第一个,如何在无序容器中为用户定义的类型专门化std :: hash :: operator()？,解决了打开std命名空间和添加模板特化是否合法的问题.

第二个,如何专门化来自其他库的类型的std :: hash,基本上解决了同样的问题.

这留下了当前的问题.鉴于C++标准库的实现为标准库中的基本类型和类型定义了散列函数,为用户定义的类型专门化std :: hash的简单有效方法是什么？有没有一种很好的方法来组合标准库实现提供的哈希函数？

(编辑感谢dyp.)StackOverflow的另一个问题是如何组合一对哈希函数.

谷歌的其他结果没有任何帮助.

这篇 Dobbs博士的文章指出,两个令人满意的哈希的XOR将产生一个新的令人满意的哈希值.

这篇文章似乎是从知识中说出并暗示了很多东西,但却注重细节.它与第一个例子中的简短评论中的Dr. Dobbs文章相矛盾,称使用XOR组合散列函数会产生一个弱的结果散列函数.

因为XOR应用于任何两个相等的值导致0,我可以看出为什么XOR本身很弱.

元问题

一个很好的理由回答解释为什么这个问题无效且一般无法回答也是受欢迎的.

中find方法的时间复杂度是多少unordered_set<int>？

还可以更改哈希函数吗？

我想将 astd::pmr::unordered_map与 a一起使用std::pmr::monotonic_buffer_resource。两者配合得很好，因为集合的节点是稳定的，所以我不会通过重新分配在缓冲区资源中创建很多漏洞：

 std::pmr::monotonic_buffer_resource res;
 std::pmr::unordered_set<T> set(&res);

也就是说，除了桶列表，当集合超过max_load_factor(). 假设我无法reserve()摆脱这种情况，并且我实际上关心自增长以来旧桶列表留下的缓冲区资源中的漏洞，我有什么选择？

如果我知道它unordered_set是作为 实现的std::vector<std::forward_list>，就像在（某些版本的）MSVC 中一样，那么我应该能够使用 ascoped_allocator为vector和forward_list. 但）我不能依赖unordered_set是一个vector<forward_list>可移植的代码和b）scoped_allocator是一个Allocator，而monotonic_buffer_resource是memory_resource，阻抗失配，这将使非常复杂的初始化。

或者我可以根据请求的大小编写一个switch_memory_resource委托给其他memory_resources 的 s 。然后，我可以使用monotonic_buffer_resource与节点大小匹配的请求（但是，我不能，可移植地，知道）以及default_memory_resource()其他所有内容。我可能会做出有根据的猜测，节点最多为sizeof(struct {void* next; size_t hash; T value;})，通过将其乘以 2 来添加一些误差幅度，并将其用作两个memory_resources之间的截止点，但我想知道是否有更简洁的方法？

双方std::set<>并std::map<>可以使用std::pair作为重点,但为什么不能std::unordered_set<>和std::unordered_map<>？

例如:

unordered_set<pair<int,int> > S;
S.insert(make_pair(0, 1));

不编译.

我见过人们提到可以在O(1)时间内从unordered_set中获取随机元素.我试图这样做:

std::unordered_set<TestObject*> test_set;

//fill with data

size_t index = rand() % test_set.size();
const TestObject* test = *(test_set.begin() + index);

但是,unordered_set迭代器不支持带整数的+. begin可以给出一个size_t参数,但它是一个桶而不是一个元素的索引.随机挑选一个桶然后在其中随机挑选一个元素将导致非常不平衡的随机分布.

适当的O(1)随机访问的秘诀是什么？如果重要,这是在VC++ 2010中.

我有这样的一套: set<weak_ptr<Node>, owner_less<weak_ptr<Node> > > setName;

它工作正常.但我想将它改为无序集.但是,当我这样做时,我得到大约六页的错误.任何想法如何做到这一点？

查看了所有错误消息页面后,我发现了可能有用的行.

/usr/include/c++/4.7/bits/functional_hash.h:60:7: error: static assertion failed: std::hash is not specialized for this type
/usr/include/c++/4.7/bits/stl_function.h: In instantiation of ‘bool std::equal_to<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = std::weak_ptr<Node>]’:

在我的自定义物理引擎中,最大的瓶颈是从空间分区(2D网格)获取所有实体的方法,并返回仅包含指向身体的唯一指针的集合.

template<typename T, typename V> bool contains(const T& mContainer, const V& mValue)
{
    return std::find(std::begin(mContainer), 
                     std::end(mContainer), mValue) != std::end(mContainer);
}

const vector<Body*>& GridInfo::getBodiesToCheck()
{
    bodiesToCheck.clear();
    for(auto& query : queries)
        for(auto& body : *query)
            if(!contains(bodiesToCheck, body)) bodiesToCheck.push_back(body);
    return bodiesToCheck;
}

使用分析器显示瓶颈在"包含"方法中.

显然,这std::unordered_set将是一个"理想"的解决方案.但是,它比当前解决方案慢很多.我也尝试过google::dense_hash_set,这std::unordered_set比当前解决方案更快,但仍然更慢.

const unordered_set<Body*>& GridInfo::getBodiesToCheck()
{
    bodiesToCheck.clear();
    for(auto& query : queries)
        for(auto& body : *query)
            /*if(!contains(bodiesToCheck, body))*/ bodiesToCheck.insert(body);
    return bodiesToCheck;
}

为什么"正确"的容器比一个慢std::vector？

有什么办法可以进一步加快这种方法的速度吗？

我有一个在类中定义的枚举类型,我想创建这些对象的unordered_set作为类的成员:

#include <unordered_set>

class Foo {
public:
  enum Bar {
    SOME_VALUE
  };

  // Error: implicit instantiation of std::hash
  std::unordered_set<Bar> getValues() const {
     return _values;
  }

private:
  std::unordered_set<Bar> _values;
};

现在,我知道明显的答案是在unordered_set中添加自定义哈希函数:

std::unordered_set<Bar, BarHasher>

但是,我想知道的是,是否有一种方法可以为bar枚举专门化std :: hash,这样任何使用unordered_map的人都会自动获得散列行为.

这适用于所有其他数据类型,但不适用于枚举 - 因为枚举不能向前声明.

为了使它工作,我必须在枚举定义之后放置std :: hash的定义,但是在第一次使用之前,这意味着我必须将它放在类主体的中间,这赢得了不行.