我需要一个关联容器，该容器使我可以通过字符串为某个对象建立索引，但也保持插入的顺序，因此我可以按名称查找特定对象，或者仅对其进行迭代并以与插入时相同的顺序检索对象他们。

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

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

@cristopher：所以，如果我做对了，区别就在于实现(以及性能)，而不是它在外部的行为方式。

解决方案

回答

我认为unordered_map和hash_map差不多是同一件事。区别在于STL正式没有hash_map(我们使用的可能是特定于编译器的东西)，因此unordered_map是解决该问题的方法。

unordered_map就是...无序。我们不能依赖它在迭代中保留任何顺序。

回答

@wesc：STL具有std :: map ...那么unordered_map有什么区别？我认为STL不会在同一件事上实现两次，并以不同的方式来称呼它。

回答

增强无序容器的文档

区别在于生成查询的方法。

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

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

请参阅哈希以了解其工作原理。

回答

我们确定所有STL实现中都存在std :: hash_map吗？ SGI STL实现了它，但是GNU g ++从4.3.1开始没有它(它位于__gnu_cxx命名空间中)。据我所知，hash_map一直是非标准的，现在tr1正在修复该问题。

回答

抱歉，我们最近的评论错了。是的，hash_map不在STL中，而map在。但是unordered_map和hash_map与我一直在阅读的内容相同。

映射->日志(n)的插入，检索，迭代效率很高(并通过键比较进行排序)

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

这些都不能单独为我们工作，因为地图是根据键内容而不是插入顺序来进行排序的(除非键中包含有关插入顺序的信息)。

我们必须执行我们描述的操作(列表+ hash_map)，或者创建一个具有插入序列号和适当比较功能的键类型。

回答

我们需要通过两种方式为关联容器建立索引：

• 插入顺序
• 字符串比较

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

回答

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