c++ - C++ 中的 O(1) 查找

Question

C++ 中是否有带有O(1)查找功能的数据结构？

Astd::map有O(log(n))查找时间（对吗？）。

我正在寻找std最好的东西（所以不是Boost pls）。另外，如果有，它是如何工作的？

编辑：好的，我猜我还不够清楚。我想关联值，有点像map. 所以我想要一些类似的东西std::map<int,string>，find并且insert应该采取O(1)。

Answer 1

数组具有 O(1) 查找。c++11 的哈希表 (std::unordered_map) 具有 O(1) 查找。（摊销，但或多或​​少是恒定的。）

我还想提一下，像地图这样的基于树的数据结构具有很大的优势，并且只有 log(n)，这往往是不够的。

回答您的编辑 - >您可以将数组的索引与其中一个值相关联。哈希表也是关联的，但完美的哈希（每个键映射到恰好 1 个值）确实很难获得。

值得一提的另一件事是：数组具有出色的缓存性能（由于局部性，也就是元素彼此相邻，因此它们可以被 prefecting 引擎预取到缓存）。树，不多。在元素数量合理的情况下，哈希性能可能比渐近性能更为关键。

Answer 2

具有O(1)查找（忽略键的大小）的数据结构包括：

• 数组
• 哈希表

对于复杂类型，平衡树在O(log n)时会很好，或者有时你可以在O(k)时使用帕特里夏树。

供参考：搜索结构的复杂性

Answer 3

数组有O(1)查找。