问题标签 [unordered-map]

如果我希望无序映射查找函数返回一个布尔值，我将如何去做呢？

这是我现在的代码。

我还需要做什么？是否可以返回布尔值？我几乎没有找到这方面的文档。

这是我从http://msdn.microsoft.com/en-us/library/bb982431.aspx获得示例的地方

需要找到由我实现的树数据结构占用的确切大小（以字节为单位）。节点结构如下

我一直在做的是 size(int)*2(for word and count) + map.bucket_count() * (sizeof(int) + sizeof(Node*)) 并为每个节点重复执行此操作。如果我忽略了 unordered_map 中存储的元素开销，这是正确的方法吗？

此外，如果我是正确的 map.bucket_count() 给出了当前分配的桶数，包括预分配的桶数。我应该使用 map.size() 而不是忽略预分配的存储桶吗？

或者不是所有这些，使用 MemTrack 之类的工具来查找使用的内存会更好吗？

假设我有以下用户结构：

我需要存储一组用户记录（大约 10^5 个用户，也可以扩大规模）。如果我将其存储为 unordered_set 或 unordered_map，性能会更好吗？Unordered_set 在技术上与 HashSet 相同，unordered_map 与 HashMap 相同，对吧？使用常规集合（有序）不是一个选项，因为当元素数量增加时插入和删除会变得非常慢。

或者

我需要它在插入、删除和通过其 userId 访问特定用户对象方面非常快。

我正在使用 anunordered_map<float, unsigned short>在 C++ 中实现哈希表。

我知道在大多数情况下使用浮点数作为哈希表的键是一个坏主意，因为比较它们很容易出错。但是，在这些情况下，我正在从大文件中读取浮点数，并且它们的精度是已知且恒定的。

但是，我想知道如何unordered_map散列我的浮点数以估计碰撞频率的详细信息。创建unordered_map. 根据文档，默认哈希函数是std::hash<Key>. 在我的情况下是std::hash<float>。但是，当我查看std::hash文档时，它仅定义为“类型的模板参数char*, const char*, crope,wrope和内置整数类型”。

有谁知道在我将它们添加到 unordered_map 时调用什么函数来散列这些值？

unordered_map- http://msdn.microsoft.com/en-us/library/bb982522.aspx

std::hash- http://www.sgi.com/tech/stl/hash.html#1

我目前正在使用 Boost for C++，并尝试使用 CRC32 实现无序映射（又名哈希表）。据我所知，它将一个字符串作为初始键，对其进行哈希处理，然后应用另一个操作，以便它适合存储桶的数量。

虽然在我的情况下，我想事先对字符串键进行哈希处理（在 Boost 中使用单独的 CRC 函数），然后使用该 ID 来索引表。我需要帮助的问题是 CRC32 哈希有 2^32 个潜在值，我怀疑我是否需要一个包含 2^32 个元素的表。在这种情况下我该怎么办？

感谢您在这里的任何帮助！

Basically, I have an unordered_map and trying to add to it sets of pairs... about 500,000 of them. I've noticed that as I add pairs the insertion speed gets slower and slower until it finally stops all together. Any thoughts as to why this might be or how to fix this?

Map definition:

Hash function - note that for my case I don't have to worry about pair.first==pair.second, so I believe this hash function should be sufficient, correct me if am wrong:

Method to add values to the unordered_map... trying to add about 200,000-500,000 pairs:

EDIT: I am actually adding closer to 50,000,000 pairs... just ran a test...

EDIT2:

Example output before it freezes, where count is the number of entries in the map. I believe it is trying to rehash the map, but not sure why it is failing to do so and freezing the computer:

checking particle: 87500 count: 35430415 load factor: 0.988477

checking particle: 87600 count: 35470808 load factor: 0.989652

checking particle: 87700 count: 35511049 load factor: 0.990818

checking particle: 87800 count: 35555974 load factor: 0.992073

checking particle: 87900 count: 35595646 load factor: 0.993163

checking particle: 88000 count: 35642165 load factor: 0.994427

checking particle: 88100 count: 35679608 load factor: 0.995434

checking particle: 88200 count: 35721223 load factor: 0.996563

checking particle: 88300 count: 35760313 load factor: 0.997616

checking particle: 88400 count: 35799621 load factor: 0.9987

checking particle: 88500 count: 35833445 load factor: 0.999649

我写了这段代码：

运行时，该行出现错误

test3.exe 中 0x00411edd 处未处理的异常：0xC0000005：访问冲突读取位置 0x00000004。”

我有 Visual Studio Express 2008 和 Boost 1_47_0；

这是我的完整代码：

考虑 C++ 中键控的有序和无序关联容器double。

是NaN有效的密钥类型吗？

对于有序容器，我应该说“不”，因为它不尊重严格的弱排序。

对于无序容器，我不知道。

以下是 GCC 4.6.2 中发生的情况：

对于有序地图，我得到：

对于无序地图，我得到：

所以在有序映射中，所有的 NaN 都被同等对待，这是我所期望的，尽管看起来 NaN 会违反要求。然而，对于无序映射，我永远无法再次检索元素，并且所有 NaN 都是不同的。这也不是我所期望的。

标准是否必须在这件事上说什么？

更新：感谢下面的出色答案，请注意，std::map如果您在其中插入任何其他内容，则会中断NaN 。

（我将非常感谢有关其他语言如何处理关联容器中的浮点键的评论。）

我正在使用 stl unordered_map，但我似乎无法让 count 方法工作。这是我的程序：

unordered_map 的文档说unordered_map::count(const Key& k)返回带有 key 的元素数k。所以我希望这里的输出是3，而真正的输出是1。为什么？

为了支持用户定义的键类型，std::unordered_set<Key>必须std::unordered_map<Key, Value> 提供operator==(Key, Key)一个散列函子：

std::unordered_set<X> 仅使用type的默认哈希编写会更方便X，例如编译器和库附带的类型。咨询后

• C++ 标准草案 N3242 §20.8.12 [unord.hash] 和 §17.6.3.4 [hash.requirements]，
• Boost.Unordered
• 克++include\c++\4.7.0\bits\functional_hash.h
• VC10include\xfunctional
• Stack Overflow 中的各种相关问题

似乎可以专攻std::hash<X>::operator()：

鉴于对 C++11 的编译器支持尚处于试验阶段——我没有尝试 Clang——，这些是我的问题：

1. 将这样的专业化添加到命名空间是否合法std？我对此有复杂的感觉。

2. 哪个std::hash<X>::operator()版本（如果有）符合 C++11 标准？

3. 有便携的方法吗？