std :: set和std :: map之间的区别是什么 [英] What is the difference between std::set and std::map

问题描述

我是c ++编程的新手，想知道是否有人能帮我澄清几个问题。

http：//www.cplusplus .com / reference / set / set /

http://www.cplusplus.com/reference/map/map/

我一直在阅读如何实现STL二叉搜索树，我不断注意到std :: set和std :: map是不断提到的完成这样的任务的方法。两者之间的区别究竟是什么？对我来说，两者看起来几乎相同，我不知道是否有一些我不注意，使一个比另一个更好的具体任务。使用std :: set over std :: map来实现从数组或向量中获取值的STL二叉搜索树有什么好处？（例如速度）？

如果有人可以帮助我理解这个概念，我会非常感谢。

解决方案 std :: set 和 std :: map 是关联容器。区别在于 std :: sets 只包含键，

而在 std :: map 有一个相关的值，即如果 A - > B ，那么map [A​​] = B，它的工作方式类似于散列，但不是 O（1），而不是 O（log N）。

您可以进一步查看提供操作的 unordered_map O（1）时间。

std :: set 将数据保存为排序格式。

两者的实现完成通过平衡树（如AVL或红黑树）给予 O（logN）时间复杂性。

但重要的是要注意两者都可以存储唯一值。要克服这一点，您还必须参见 multimap 和 multiset 。

希望这有助于！

更新：在红黑树的情况下，重新平衡旋转是 O（1） code>操作，而使用AVL这是一个 O（log n）操作，使Red-Black树在重新平衡阶段的这方面更有效率，它是更常用的一个可能的原因之一。

I'm relatively new to c++ programming and was wondering if someone could help clarify a few questions for me.

http://www.cplusplus.com/reference/set/set/

http://www.cplusplus.com/reference/map/map/

I've been reading on how to implement STL binary search trees and I keep noticing that std::set and std::map are constantly mentioned as the methods for accomplishing such a task. What exactly is the difference between the two however? To me both seem almost identical and I'm not sure if there's something I'm not noticing that makes one better than the other for specific tasks. Is there any advantage of using std::set over std::map for implementing a STL binary search tree that takes values from an array or vector (such as speed for example)?

If someone could help me understand this concept I'd greatly appreciate it!

解决方案

Both std::set and std::map are associative containers. The difference is that std::sets contain only the key,
while in std::map there is an associated value , that is if A -> B , then map[A]=B , this works like hashing but not O(1) , instead O(log N).

You can further look unordered_map which provides the operation in O(1) time.

std::set keeps data in sorted format .
Implementation of both is done by balanced trees (like AVL or Red-Black trees ) giving O(logN) time complexity.

But important point to note is that both can store unique values . To overcome that you must see also multimap and multiset .

Hope this helps !

update: In the case of Red-Black tree re-balancing rotation is an O(1) operation while with AVL this is a O(log n) operation, making the Red-Black tree more efficient in this aspect of the re-balancing stage and one of the possible reasons that it is more commonly used.

这篇关于std :: set和std :: map之间的区别是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！