std::set 和 std::map 有什么区别 [英] What is the difference between std::set and std::map

问题描述

我对 c++ 编程比较陌生，想知道是否有人可以帮助我澄清一些问题.

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/

我一直在阅读有关如何实现 STL 二叉搜索树的文章，并且一直注意到 std::set 和 std::map 经常被提及作为完成此类任务的方法.然而，两者之间究竟有什么区别?对我来说，两者看起来几乎相同，我不确定是否有一些我没有注意到的东西让一个在特定任务上比另一个更好.使用 std::set 而不是 std::map 来实现从数组或向量中获取值的 STL 二叉搜索树有什么优势(例如速度)?

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!

推荐答案

std::set和std::map都是关联容器.不同的是 std::sets 只包含键，
而在 std::map 中有一个关联的值，即 if A ->;B ，然后 map[A]=B ，这类似于 hashing 但不是 O(1) ，而是 O(log N).

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).

您可以进一步查看 unordered_map，它提供了 O(1) 时间的操作.

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

std::set 以排序格式保存数据.
两者的实现都是通过平衡树(如 AVL 或红黑树)完成的，时间复杂度为 O(logN).

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.

但需要注意的重要一点是，两者都可以存储唯一值.为了克服这个问题，您还必须查看 multimap 和 multiset .

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

希望这会有所帮助！

更新:在红黑树重新平衡旋转的情况下，是一个 O(1) 操作，而对于 AVL，这是一个 O(logn) 操作，使得红黑树在再平衡阶段这方面的效率更高，也是它被更常用的可能原因之一.

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屋！