<分区>
昨天有人告诉我，有序映射的底层结构是二叉搜索树。这对我来说没有意义，因为如果是这种情况，您将无法进行 O(1) 检索。谁能解释一下？
此外，如果要在不使用标准库的情况下用 C++ 实现哈希表，最好的方法是什么？
<分区>
昨天有人告诉我，有序映射的底层结构是二叉搜索树。这对我来说没有意义，因为如果是这种情况，您将无法进行 O(1) 检索。谁能解释一下？
此外，如果要在不使用标准库的情况下用 C++ 实现哈希表，最好的方法是什么？
最佳答案
std::map 查找时间不是 O(1) 而是 O(log(n))。
std::unordered_map 的查找时间为 O(1) 分摊。
std::unordered_map 和 std::unordered_set 是哈希表。
关于c++ - std::map 的底层结构是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42273800/