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?

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.

Answer 2

Conceptually, a set is a collection of things, whereas a map is a mapping of keys to values.

Answer 3

A map stores keys sorted. It maps keys to values. Usually it is implemented as a binary search tree (red-black tree) for keys. A set is a map where values are irrelevant. unordered_map and unordered_set (new in C++11) store keys unsorted and use hash table for search.

Answer 4

std::map and std::set are extremely similar. They both have a sorted collection of unique keys. Additionally, map has a value associated with each key.