问题标签 [unordered-map]

我最近才开始研究 boost 和它的容器，我在网上和 stackoverflow 上阅读了几篇文章，认为 boost::unordered_map 是大型集合中性能最快的容器。所以，我有这个类状态，它在容器中必须是唯一的（没有重复），容器中将有数百万甚至数十亿的状态。因此，我一直在尝试将其优化为小尺寸和尽可能少的计算。我之前使用过 boost::ptr_vector，但正如我在 stackoverflow 上所读到的，只要其中没有那么多对象，向量才是好的。在我的例子中，状态描述了来自机器人的感觉运动信息，因此可能存在大量状态，因此快速查找是重中之重。遵循boost 文档对于 unordered_map，我意识到我可以做两件事来加快速度：使用 hash_function，并使用相等运算符根据它们的 hash_function 比较状态。因此，我实现了一个私有 hash() 函数，它接收状态信息并使用 boost::hash_combine 创建一个 std::size_t 哈希值。operator== 基本上比较状态的哈希值。所以：

• std::size_t 是否足以涵盖数十亿可能的 hash_function 组合？为了避免重复状态，我打算使用它们的 hash_values。

• 创建 state_map 时，我应该使用 State* 还是哈希值作为键？即：boost::unordered_map<State*,std::size_t> state_map; 或 boost::unordered_map<std::size_t,State*> state_map;

• boost::unordered_map::iterator = state_map.find() 的查找时间是否比通过 boost::ptr_vector 并比较每个迭代器的键值更快？

• 最后，任何关于如何优化这种无序地图以实现速度和快速查找的提示或技巧将不胜感激。

编辑：我已经看到了很多答案，一个是不使用 boost 但 C++0X，另一个不使用 unordered_set，但老实说，我仍然想看看 boost::unordered_set 如何与散列函数一起使用. 我遵循了boost的文档并实现了，但我仍然无法弄清楚如何将boost的散列函数与有序集一起使用。

我有以下代码，我想在其中消除我最初创建的值为 10 的元素。我在设置迭代器和擦除它时遇到了麻烦。它是如何完成的？

我的应用程序中有一些静态 unordered_map，我希望能够在启动时对其进行初始化。他们不是一个班级的一部分。在我的初始设置中，头文件和源文件如下：

和源文件：

但是，每当我尝试这样做时，然后尝试在地图上进行查找（即 Game::Elements::NameElementMap[std::string("Air")] ）它总是返回一个空字符串，以及该使用的大小上下文为 0。

我尝试将初始化移动到头文件中（即在头文件中

但编译器随后抱怨没有默认构造函数。我究竟做错了什么？

提前致谢

我正在尝试使用迭代器在多层 unordered_map 中输出一个整数，但我遇到了问题，错误在代码下方。

下面的错误：

我想在 VS2010 C++ 下double的索引中存储约 3,000,000 个值。unsigned int我std::tr1:unordered_map<unsigned int, double>为此目的使用 a 。不幸的是，当我尝试存储值编号 2^21 时，会引发异常（好像只有 2^21-1 的空间，即某些索引只能使用 20 位）。我在存储值之前尝试过rehash，这也不起作用。

最后我得到了一些非常基本的测试程序（它甚至表现出一些不同的行为，但无论如何）：

我检查的一些案例：

1）如果我根本不重新散列，程序在输出后根据i == 32000（最终2 ^ 15）休息很长时间，然后继续i == 262000（2 ^ 18）。它永远存在（CPU 负载为 100%，内存不增加）。

2）如果我做 a rehash(1000)，它会达到i == 65000(2^16) 并永远保持（CPU 负载 100%，内存不增加）。

3) 如果我执行 a rehash(3000000)，则循环成功完成，但程序永远不会退出 - 即，显然析构函数存在问题。

那里发生了什么，甚至更重要的是：我该怎么办？！

非常感谢您的帮助！

所以我在玩unordered_mapSTL 的新标准化。我的代码有点像这样，我只是创建一个 unordered_map，填充它，然后打印出来：

但是，我得到的输出是这样排序的：

但我不想为订购我的地图而付出代价！这就是我使用 unordered_map 的原因......这里发生了什么？

附加说明：我正在使用gcc version 4.3.4 20090804 (release) 1 (GCC)并且正在像这样编译g++ -std=c++0X maptest.cpp

首先，有人可以澄清在 C++ 中使用 [] 运算符与用于查找的 unordered_map 是否包含对 find() 方法的调用，还是使用 [] 运算符比 find() 更快？

其次，在下面的代码中，我怀疑在键不在 unordered_map 中的情况下，我正在通过该行执行第二次查找，map[key] = value以便替换使用 [] 运算符在此处创建的默认值密钥不存在。

这是真的吗，如果是这样，有没有一种方法（可能通过使用指针或其他东西）我可能在任何情况下都只执行一次查找（可能通过存储放置值/读取值的地址）和仍然实现相同的功能？显然，如果是这样，这将是一个有用的效率改进。

这是修改后的代码摘录：

在我的以下程序中，我目前正在使用unordered_map只是因为我想要 O(1) 搜索/插入时间。但现在我想订购这些物品。每次对它进行排序是非常低效的。我的选择是什么？我读过它hash_map可以完成工作，但我读到的文章非常令人困惑，或者对我来说理解起来相当复杂。插入/搜索的复杂性hash_map是什么？它真的是有序的吗？如果是这样，它是否在 C++0x 中定义，我该如何实现它？如果不是我还能用什么？谢谢。

编辑：

我以前使用std::map过，但我有大量物品（以百万计）。因此，即使商品数量如此之多，map如果我要订购，你们都推荐吗？

unordered_map默认情况下C++0x使用什么位哈希？std::hash函数返回size_t。这是否意味着unordered_map使用 16 位散列函数？

我知道这可能是一个愚蠢的问题，但我想确定一下，但我无法轻易找到这些信息。

find() 在无序映射中的性能特点是什么？它是否与正常查找一样快/几乎一样快？

IE

对比

whereRows::NameRowMap是将字符串索引映射到 int 的无序映射。

就我而言，我不确定密钥是否会事先存在，所以第一个解决方案对我来说似乎更安全，但如果我能保证存在，第二种情况会更快（忽略我正在做的额外检查） ? 如果是这样，为什么？如果重要的话，我正在使用 1.46 boost 实现