What is the difference between set vs map in C++?
What is the difference between set vs map in C++?
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?
They are both associative containers, are they not? By default, they use
std::less as a comparator, and they follow strict ordering.– user1508519
Feb 28 '14 at 7:15
std::less
You can kind of think of a set as a hash where only the key is used and the value not utilized.
– seand
Feb 28 '14 at 7:17
In the context of STL it is better not to thing that set is a hash. unordered_set is implemented with hash, set is not.
– Alexey Voytenko
Feb 28 '14 at 7:33
5 Answers
5
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::data_type). If the ordering can be wholly derived (by comparing 2 elements) from map::data_type, then you're typically better off using a set, in which case you'll avoid duplicating the key as map::key_type.
std::map
std::set
map
set
map::key_type
map
map::data_type
map::data_type
set
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.
std::map
std::set
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.
set
map
set
<key, data>
map
find
set
find
<key, data>
key
find
data
set
data
map
key
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.
<key, data>
map
set
key
data
data
key == data
set
key
key
key
data
map
key
data
key
map
data
key
set
find
A major point is that the elements in a Set cannot be changed once they're placed in the set [cplusplus.com/reference/set/set/] If you're storing a collection of simple data items in an ordered way, then a set can work. If you're storing structs ordered by one data member, and you want to be able to change the other data in the struct, take the ordering data member out to be a key and use a map.
– cvanbrederode
Jul 23 '15 at 17:46
Conceptually, a set is a collection of things, whereas a map is a mapping of keys to values.
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.
map
set
unordered_map
unordered_set
std::map is an associative container storing pairs of key-values with unique keys. std::set is also an associative container that stores a sorter set of objects (or keys).
std::map
std::set
You should have a look at std::map and std::set.
In which way the map storing the values? based upon the key? If it is stores based upon the key, is key sorted?
– SheikCode
Feb 28 '14 at 7:21
sets aren't really associative -- the contents of the set don't "associate" to anything else.
– seand
Feb 28 '14 at 7:22
@sheik Did you even look at the link? Or read my comment?
– user1508519
Feb 28 '14 at 7:23
the elements in a map are always sorted by its key following a specific strict weak ordering criterion indicated by its internal comparison object
– Marius Bancila
Feb 28 '14 at 7:24
@seand
sets are considered "associative containers" in the C++ standard. It may be counter-intuitive, and could be derived from the fact that the implementation is similar to that of a map, except that only keys are stored. But that is the terminology we are stuck with now.– juanchopanza
Feb 28 '14 at 8:06
sets
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.
std::map
std::set
map
Thanks for contributing an answer to Stack Overflow!
But avoid …
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
But avoid …
To learn more, see our tips on writing great answers.
Required, but never shown
Required, but never shown
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
Semantically, set and map are totally different data structures. You should go through a good tutorial to study when to use which.
– Abhishek Bansal
Feb 28 '14 at 7:14