This question already has answers here:
Closed 6 years ago.
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.
