我不明白 std::tr1::unordered_map

Question

我需要一个关联容器，它使我可以通过字符串索引某个对象，但同时也保留插入顺序，因此我可以通过名称查找特定对象，或者只是对其进行迭代并按照插入顺序检索对象他们。

我认为这 链表和哈希图的混合 应该完成这项工作，但在我尝试使用之前 std::tr1::unordered_map 以为它按照我描述的方式工作，但事实并非如此。那么有人可以向我解释一下的含义和行为吗 unordered_map?

---

@wesc：我确信 std::map 是由 STL 实现的，而我确信 std::hash_map 不在 STL 中（我认为旧版本的 Visual Studio 将其放在名为 stdext 的命名空间中）。

@克里斯托弗：因此，如果我做对了，区别在于实现（以及性能），而不是其外部行为方式。

Answer 1

增强无序容器的文档

不同之处在于生成查找的方法。

在地图/集合容器中 operator< 用于生成有序树。

在无序容器中， operator( key ) => index 用来。

有关其工作原理的描述，请参阅散列。

Answer 2

您已经询问了制作 Boost::MultiIndex 的规范原因：通过键快速查找列出插入顺序。 Boost MultiIndex 教程：列表快速查找

Answer 3

您需要通过两种方式对关联容器进行索引：

• 广告订单
• 字符串比较

尝试 Boost.MultiIndex 或者 增强侵入式. 。我没有用过这种方式，但我认为这是可能的。

Answer 4

抱歉，你上次的评论读错了。是的，hash_map不在STL中，map是。但 unordered_map 和 hash_map 与我读到的内容相同。

map -> log(n) 插入、检索、迭代高效（并且按键比较排序）

hash_map/unordered_map -> 常数时间插入和检索，迭代时间不保证高效

这些本身都不适合您，因为映射根据键内容而不是插入顺序对事物进行排序（除非您的键包含有关其中插入顺序的信息）。

您必须执行您所描述的操作（列表+ hash_map），或者创建一个具有插入序列号和适当的比较函数的键类型。

Answer 5

我 思考 unordered_map 和 hash_map 或多或少是相同的。不同之处在于 STL 没有正式的 hash_map（您使用的可能是编译器特定的东西），因此 unordered_map 是对这一遗漏的修复。

unordered_map 就是这样......无序的。您不能依赖它在迭代时保留任何顺序。

Answer 6

您确定 std::hash_map 存在于 全部 STL 实现？SGI STL 实现了它，但是从 4.​​3.1 开始，GNU g++ 还没有它（它位于 __gnu_cxx 命名空间中）。据我所知，hash_map 一直是非标准的，现在 tr1 正在修复这个问题。

Answer 7

@wesc：STL 有 std::map...那么和unordered_map有什么区别呢？我不认为 STL 会实现两次相同的东西并以不同的方式调用它。