昨天有人告诉我,有序地图的底层结构是二叉搜索树。这对我来说没有意义,因为如果情况是这样的话,你不能有O(1)检索。谁能解释一下?另外,如果有人在不使用stdlib的情况下在C++中实现哈希表,那么最好的方法是什么?std :: map的底层结构是什么?
0
A
回答
0
底层数据结构是实现定义的。它通常被实现为红黑树,它是一个自平衡二叉搜索树。获取元素的时间复杂度为O(logn)(请参阅this)
我只是阅读
std::unordered_map
的实现作为起点。我认为这是学习活动,所以阅读和理解工作STL实施将是一个很好的练习。如果它不是练习,那么使用std::unordered_map
0
std :: map使用红黑树,因为它在节点插入/删除和搜索的复杂性之间取得了合理的折衷。
+0
对于当前的实现,这是正确的,但它不是标准所要求的。 (目前没有人知道可以满足要求的另一个数据结构 - 但明天可能会发现一个。) –
1
std :: map查找时间不是O(1)它的O(log(n))。
std :: unordered_map的查找时间为O(1)摊销。
std :: unordered_map和std :: unordered_set是哈希表。
相关问题
- 1. 什么是ZeroMQ底层设计架构
- 2. Python列表的底层数据结构是什么?
- 3. C#集合的一般区别是什么?底层数据结构是什么?
- 4. WCMS的层次结构是什么?
- 5. 什么是UICollectionView的层次结构?
- 6. std :: map的作用是什么?
- 7. std :: map - 里面有什么数据结构
- 8. android - 什么是视图层次结构?
- 9. 什么是“类层次结构:。
- 10. Scala中的“底层类型”是什么?
- 11. `mkvirtualenv`命令的底层是什么?
- 12. graphql的底层后端是什么?
- 13. 是什么分层架构
- 14. Java,什么是底层文档
- 15. 构建类层次结构的最佳方法是什么?
- 16. 访问PyObject的底层结构
- 17. 为什么boost :: ptr_list使用底层void *?
- 18. 什么是此层次结构的基于对象的最佳数据结构?
- 19. 用什么来代替std :: map :: emplace?
- 20. JavaScript中的类的层次结构是什么?
- 21. IQueryable的结构是什么?
- 22. 什么是Eclipse的结构?
- 23. Resolv.conf的结构是什么?
- 24. AppxSignature.p7x的结构是什么?
- 25. 什么是C++的std :: map的Swift等价物?
- 26. 为什么std :: map是红黑树而不是哈希表?
- 27. 正则表达式当底层结构是不同的R
- 28. 在SSAS中创建层次结构的优点是什么?
- 29. 使用类加载器层次结构的好处是什么?
- 30. Encoding.UTF8.GetBytes(“hag”)中的类层次结构/调用链是什么?
你从哪里得知检索是O(1)?首先阅读[文档](http://en.cppreference.com/w/cpp/container/map),其次它们通常以[红黑树](https://en.wikipedia.org/wiki /红色%E2%80%93black_tree),第三你的其他问题太宽 – EdChum
也试图限制自己每个问题的一个问题。 – nwp