logo标签列表

我不理解std::tr1::unordered_map是什么。

c++tr1unordered-map
4
我需要一个关联容器，可以通过字符串索引特定对象，但也保持插入顺序，这样我可以按名称查找特定对象或只是迭代它，并以我插入它们的相同顺序检索对象。 我认为这个链表和哈希映射的混合体应该可以胜任此工作，但是之前我尝试使用std :: tr1 :: unordered_map，认为它是按照我描述的方式工作的，但实际上并不是。所以有人能解释一下unordered_map的含义和行为吗？

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

@cristopher: 所以，如果我理解正确，区别在于实现方式（因此性能不同），而不是外部行为上的区别。

7个回答
17
7
您需要对关联容器进行两种索引：
  • 插入顺序
  • 字符串比较
尝试使用 Boost.MultiIndex 或 Boost.Intrusive。我没有以这种方式使用过，但我认为这是可能的。
我知道这是一个非常老的问题，但是由于一些答案提供了Boost Multi Index作为OP需求的解决方案，这些答案是正确的，但是对Boost Multi Index的任何推荐IMO也应该有指向Boost.Intrusive的链接（http://www.boost.org/doc/libs/1_50_0/doc/html/intrusive.html）。虽然使用更加复杂，但通常更有效和灵活。 - nhed
1
是的，我认为 Intrusive 在 2008 年甚至不存在。 - Adam Mitz
4

无序容器的 Boost 文档

区别在于查找方式的不同。

在 map/set 容器中，使用 operator< 生成有序树。

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

请参阅哈希散列的描述以了解其工作原理。

2

对不起，我误读了你的最后一条评论。是的，hash_map不在STL中，而map在其中。但根据我所阅读的资料，unordered_map和hash_map是相同的。

map -> 对数（n）插入、检索和迭代效率高（并按键比较有序）

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

这两个选项都无法单独解决您的问题，因为map基于键内容而不是插入顺序进行排序（除非您的键包含有关插入顺序的信息）。

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

0

我认为unordered_map和hash_map基本上是一样的东西。不同之处在于STL没有官方的hash_map（你使用的可能是编译器特定的东西），因此unordered_map是弥补这个遗漏的方法。

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

0
你确定std::hash_map在所有STL实现中都存在吗？SGI STL中实现了它，然而GNU g++没有它（它位于__gnu_cxx命名空间中），至少在4.3.1版本中是这样。据我所知，hash_map一直都是非标准的，现在tr1正在修复这个问题。
-3

@wesc：STL有std::map……那么unordered_map有什么不同呢？我不认为STL会实现两次相同的东西并以不同的方式命名。

3
Map是用平衡二叉树实现的，具有其限制和优点。unordered_map则是哈希表。 - David Rodríguez - dribeas
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接