unordered_map 是个不错的选择吗？

Question

我想知道 unordered_map 作为我的特定问题的容器是否是一个不错的选择。我读到的关于地图的内容并没有真正涵盖我的领域，即：

• 容器将存储 100 到 500 个对象（不是 int/double...)
• 尺寸永远不变。
• 顺序并不重要，因为对象本身包含某种 "index"。
• 很多时候（！）我需要过滤容器中的所有元素 属性（例如有 color==blue）

目前我使用矢量，效果很好。但是，如果例如unordered_map 会提高性能（关于 "filtering"）我可以想象改变它。

Answer 1

如果您有多个搜索条件（有时 color == blue，有时 flavour == up），

std::unordered_map 不会真正帮助您，因为地图仅提供单个预搜索的快速查询确定键。

我会说 std::vector 对您来说刚刚好，最好包装在您自己的结构中，该结构将提供查找界面。如果稍后分析告诉您这不够快，您可以在此类数据之上构建自己的索引。您甚至不必手动执行此操作，boost::multi_index 是专为多标准查找而设计的通用容器。

Answer 2

我会使用 vector 或简单的数组来存储实际数据。并有一些 maps 将带有指针的键映射到实际数据。

这会增加内存使用量，但如果经常需要通过不同的索引进行搜索，您可能会牺牲一些内存。

Answer 3

散列 table（std::unordered_map 是）为一个键（键值对）提供恒定时间查找。但是，它的常数因子 总是 比简单数组（它为整数索引提供常数时间查找）更高（即查找速度较慢）。

如果您需要根据某些条件过滤一组元素，则需要检查每个单独的元素。在这种情况下，哈希 table 在性能方面 比 array/vector 严格地差 ，因为它的计算复杂度与数组索引相同，但是常数因子更差。

所以不，在这种情况下您没有理由要使用 unordered_map。