stl - What is the difference between set vs map in C++?

Question

I am still confused by the differences between the map and set datastructures in STL. I know set is storing the values in a sorted way, what about map? Does it store the values in sorted order? Map stores pairs of values (key,value), what is the advantage of this feature?

question from:https://stackoverflow.com/questions/22088607/what-is-the-difference-between-set-vs-map-in-c

Answer 1

At least for the ordered versions (std::map and std::set), a map facilitates use-cases of a set by allowing you to introduce an external key (map::key_type) to determine ordering of the elements that otherwise can't be derived from map's data type (map::mapped_type). If the ordering can be wholly derived (by comparing 2 elements) from map::mapped_type, then you're typically better off using a set, in which case you'll avoid duplicating the key as map::key_type.

In a way, std::map is redundant and you can always use std::set instead by introducing a new element type which aggregates keys with data while providing the necessary comparison function. However, this is cumbersome and typically inelegant.

To clarify why a set may be cumbersome over a map; A set will store the <key, data> pair as an element while map will maintain a separation between the 2. This means, for instance, that for a find operation on a set where find's parameter is constructed on-the-spot, an entire <key, data> element will have to be constructed while it's really on the key that's needed for the find operation. The construction of the data members of a set's element is then redundant, and can be rather inefficient if, for instance, data members represent disk storage or involve some other complex or else time consuming construction operation. map alleviates this by only having to construct the actual key required for find.

To summarize, consider an element <key, data> for which you're wondering whether to use a map or a set to store multiple ordered elements. If key spans the entire data (meaning data is empty or else key == data) then you're better off using a set in which case you'll avoid a) duplicating key storage and b) likely having to keep 2 keys synchronized. If key is not contained in data then (you have to) use a map. The tricky part is when key is a (proper) subset of data. You then have to trade-off the cost of maintaining duplicate keys (for a map) vs the cost of constructing data that doesn't overlap with key (for a set), the latter which may occur for find operations.