std :: map的底层结构是什么？

昨天有人告诉我，有序地图的底层结构是二叉搜索树。这对我来说没有意义，因为如果情况是这样的话，你不能有O（1）检索。谁能解释一下？另外，如果有人在不使用stdlib的情况下在C++中实现哈希表，那么最好的方法是什么？std :: map的底层结构是什么？

来源

2017-02-16 John

你从哪里得知检索是O（1）？首先阅读[文档]（http://en.cppreference.com/w/cpp/container/map），其次它们通常以[红黑树]（https://en.wikipedia.org/wiki /红色％E2％80％93black_tree），第三你的其他问题太宽 – EdChum

也试图限制自己每个问题的一个问题。 – nwp

底层数据结构是实现定义的。它通常被实现为红黑树，它是一个自平衡二叉搜索树。获取元素的时间复杂度为O（logn）（请参阅this）
我只是阅读std::unordered_map的实现作为起点。我认为这是学习活动，所以阅读和理解工作STL实施将是一个很好的练习。如果它不是练习，那么使用std::unordered_map

来源

2017-02-16 12:31:10 mpiatek

std :: map使用红黑树，因为它在节点插入/删除和搜索的复杂性之间取得了合理的折衷。

来源

2017-02-16 12:23:36 Mero

对于当前的实现，这是正确的，但它不是标准所要求的。（目前没有人知道可以满足要求的另一个数据结构 - 但明天可能会发现一个。） –

std :: map查找时间不是O（1）它的O（log（n））。

std :: unordered_map的查找时间为O（1）摊销。

std :: unordered_map和std :: unordered_set是哈希表。

来源

2017-02-16 12:23:48 user3853544

std :: map的底层结构是什么？

回答

相关问题