我是C ++编程的新手,想知道是否有人可以为我澄清一些问题。
http://www.cplusplus.com/reference/set/set/
http://www.cplusplus.com/reference/map/map/
我一直在阅读有关如何实现STL二进制搜索树的信息,并且我不断注意到std :: set和std :: map被不断提及作为完成此类任务的方法。两者之间到底有什么区别?在我看来,两者似乎几乎完全相同,我不确定在某些特定任务上我是否没有注意到使某一项比另一项更好。使用std :: set而不是std :: map来实现STL二进制搜索树有什么好处,该树从数组或向量中获取值(例如,速度)?
如果有人可以帮助我理解这个概念,我将不胜感激!
这两个std::set
和std::map
的associative containers
。不同之处在于,std::sets
仅包含键,
而其中包含std::map
一个关联的值,即if A -> B
,然后map [A] = B,其工作方式类似,hashing
但O(1)
不是O(log N)
。
您可以进一步查看unordered_map,它可以O(1)
及时提供操作。
std::set
使数据保持排序格式。
两者的实现都是通过平衡树(例如AVL或Red-Black树)来完成的,从而增加了O(logN)
时间复杂度。
但是要注意的重要一点是,两者都可以存储唯一值。为了克服这一点,您还必须看到multimap和multiset。
希望这可以帮助 !
更新:对于Red-Black树重新平衡旋转是一项O(1)
操作,而对于AVL来说,这是一项O(log n)
操作,这使得Red-Black树在重新平衡阶段的这方面效率更高,这是其可能的原因之一更常用。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句