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.