问题标签 [unordered-set]

我有一个类（称为它Outer），它有一个私有成员类（Inner）。我想将 的实例存储Outer::Inner在无序的标准容器中，所以我想专门化std::hash<Outer::Inner>.

但是，在编写此代码时：

编译器抱怨：

我试图std::hash通过遵循这个答案来建立一个朋友结构，但这也不起作用：Outer::Inner失败的前向声明：

那么我应该如何进行（如果我打算做的事情是可能的）？

更新：我在使用 Visual Studio 2013 的 Windows 上看到了这个“问题”。在使用 Clang 3.3 和最新版本的 llvm 标准库的 Linux 上，我没有看到这个“问题”。尽管如此，我还没有准备好将其作为 Microsoft 错误注销。

我注意到我正在使用的 unordered_set 存在一个奇怪的问题。我的 load_factor 为 1，最大大小为数百万，但以下显示 maximum_bucket_count 仅为 8。我尝试使用不同类型的集合。

谁能解释一下？

这应该是系统或库实现限制，而不是初始化或配置相关数字。我已经看到下面的代码示例，其中 max_bucket_count 相同的是 max_count （即，百万）

请考虑以下代码：

Class MyClass是一个自定义类：

然后以下代码将Debug Assertion Failed在调用后立即进入循环it = T.erase(it);：

如何解决它，为什么？PS：我的环境：VS2010

如果在函数内部，我将数据存储在 unordered_set 中，然后返回指向所存储对象的指针，那么指针在函数范围之外是否仍然有效？

例如。

尝试访问*intptr另一个函数会导致错误吗？或者当 unordered_set 的范围结束时 unordered_set 中的数据是否被释放？

我将首先说明一个简单的用例示例：

• 考虑一个社会保障 ID 数据库的问题，其中 C++ 代码被建模为 a std::unordered_map，它的键是一个人的社会保障 ID，它的值是std::string带有那个人的全名的 a（例如，std::unordered_map<int, std::string> DB;）。

• 还请考虑，有一个打印此数据库的请求，该数据库根据人的 ID（即std::unordered_map's 键）按升序排序。

• 天真地，人们会考虑使用std::sort以便std::unordered_map根据请求的标准对它进行排序，然后打印它，如下面的示例代码：

• 但是，情况并非如此，因为在 a或 astd::sort范围内使用a会引发编译器错误。std::unordered_mapstd::unordered_set

问题：

1. 为什么 STL 的无序容器不能按 排序std::sort？
2. 是否有一种合法且有效的方法来对 astd::unordered_map或 a进行排序std::unordered_set？

当我尝试在此地图中插入时：

std::map<std::unordered_set<int >, std::pair<float, std::pair<float, float >> >

我收到了这个错误

错误 C2784: 'bool std::operator <(const std::_Tree<_Traits> &,const std::_Tree<_Traits> &)' : 无法推导出 'const std::_Tree<_Traits> &' 的模板参数从 'const std::unordered_set,std::equal_to<_Kty>,std::allocator<_Kty>>'

我的数据定义如下：

有问题的部分：

问题

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

对于这个问题，我将“好”定义为易于实现和理解、相当有效且不太可能产生哈希表冲突。良好的定义不包括任何关于安全的陈述。

Google 的现状

目前，两个 StackOverflow 问题是 Google 搜索“std hash specialization”的第一名。

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

第二，How to special std::hash for type from other library基本上解决了同样的问题。

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

（感谢 dyp 编辑。） StackOverflow 上的另一个问题解决了如何组合一对哈希函数。

其他谷歌结果没有更多帮助。

Dobbs 博士的这篇文章指出，两个令人满意的散列的异或将产生一个新的令人满意的散列。

这篇文章似乎是从知识上讲的，暗示了很多东西，但细节却很轻。它与 Dobbs 博士在第一个示例中的简短评论中的文章相矛盾，他说使用 XOR 组合散列函数会导致生成的散列函数很弱。

因为 XOR 应用于任何两个相等的值会导致 0，所以我可以看到为什么 XOR 本身很弱。

元问题

一个合理的答案解释为什么这个问题是无效的并且一般不能回答也是受欢迎的。

在我的应用程序中，我有以下要求 -

1. 数据结构将只用一些值（不是键/值对）填充一次。这些值可能会重复，但我希望数据结构只存储一次。

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

约束 1 表明我必须使用 set 或 unordered_set，因为数据不是键值对的形式。

现在集合插入比 unordered_set 插入成本更高，但数据结构在我的程序开始时只填充一次。

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

我有一个 C 字符串 ( wchar_t const*)，其生命周期由其他数据结构拥有；对字符串的引用通过指针传递。我想将这些实例放入unordered_map. 是否有一个标准工具我可以用来获取这个哈希而不构建临时std::wstring和调用std::hash<std::wstring>？

请注意，它std::hash<T*>返回指针的哈希值，而不是该指针指向的字节流内容的哈希值。

如果我在两个无序容器中插入相同的（大小和值）元素，使用两个迭代器遍历容器是否总是在相同的位置给出相同的元素？

如果是，是否可以制作（单个！）散列函数来打破这种确定性？