用于快速查找和检索的数据容器

实际上，我需要一个数据结构来帮助我减少查找和检索各个键值的时间。用于快速查找和检索的数据容器

现在我正在使用一个带键的地图容器作为结构，并且希望尽可能快地检索它的值。

我在Fedora 12上使用gcc。我也尝试过无序映射，但它不能与我的编译器一起工作。

另外，哈希映射在命名空间std中不可用。

你能详细说明你的键，键空间，值和值空间吗？ – perreal 2012-02-06 14:41:44

'unordered_map'以何种方式无效？ – 2012-02-06 14:42:50

为了得到'std :: unordered_map'，你需要为'C++ 11'编译。你可以通过指定'-std = C++ 0x'来实现。 – Grizzly 2012-02-06 15:22:34

如果您使用的是C++ 11，请使用std::unordered_map，定义见<unordered_map>。

否则，使用std::tr1::unordered_map，在<tr1/unordered_map>或boost::unordered_map中定义，在<boost/unordered_map.hpp>中定义。

如果您的密钥是用户定义的类型，那么您需要为该类型定义hash和operator==，或者提供合适的函数类型作为unordered_map的模板参数。

当然，你也应该测量性能相比std::map;在某些情况下可能会更快。

2012-02-06 14:42:07

非常感谢:)我想使用无序的地图。 – 2012-02-07 06:29:07

实际上要使用推动hashmap我将不得不下载很多库...我想要一些易于使用..无序的地图应该证明对我有帮助..我会试着回到这..谢谢很多。 – 2012-02-07 06:34:58

@ user1087895：如果您需要支持不提供''的编译器，则只需要Boost。如果你只使用GCC，那么你应该已经有了。 – 2012-02-07 07:03:34

哈希映射称为unordered_map。你可以从boost得到它，即使你不能得到一个std/tr1工作，也可能工作。通常，查找时间是“不变的”，这意味着它不会随着元素的复杂性而增加。但是，您必须更详细地看一下：

“常量”假定您永远不会有超过固定数量的“冲突”。这是不可能的，你不会有任何，然后你必须衡量会有一些碰撞的事实。
“常量”包括散列密钥所花费的时间。这是一个不变的时间，因为集合中有多少其他元素没有什么区别，但是它仍然是一个需要完成的任务，到那时候你的std :: map可能已经找到了你的元素。

如果密钥的哈希速度非常快并且分布很好，所以发生很少的碰撞，那么哈希确实会更快。

我总是在使用哈希映射时发现的一件事情是，为了获得最佳性能，您几乎总是通过编写自己的实现而不是使用标准实现而获胜。这是因为您可以为您知道要处理的数据自定义自己的数据。也许这就是为什么他们没有把散列图加入原始标准。

写我自己的时候做的一件事是用密钥存储实际的哈希值（最初生成的哈希值）。这是第一个比较点（通常比比较键快，因为它只是一个int），也意味着如果调整了散列表的大小，则不需要重新生成它。

请注意，如果您从不删除任何内容，即加载和只读，则散列表更容易实现。

2012-02-06 15:42:24 CashCow

是的，这是我想确认散列密钥的时间开销会导致比std :: map更多的时间。 – 2012-02-07 06:32:33

我认为这个我可以用数字帮助确认.. – 2012-02-07 06:33:05

这通常取决于你的地图大小和每个节点的比较时间。请记住，您在散列图上也会进行一些比较，因为碰撞（具有重新分配的碰撞的平坦表是最常见的实施方式）。 – CashCow 2012-02-07 10:53:50

回答