C++

# Set vs Map in C++

The aim of this article is to give the similarities and differences between a set and a map. “vs” in the title means “versus”. First of all, what is a set? – A set in C++ is like the set in Mathematics. In C++, a set is a group of not necessarily unrelated values, but of the same type. The values of a set are called keys in C++.

What then is a map? – A map is a set of key/value pairs. In C++, the keys are of the same type, and the values are also of the same type. There is multiset and there is multimap. A multiset is a set where the values are not unique; that is, there can be more than one of the same values. Do not forget that the values of the set are called keys in C++. In a map, some of the values may be the same, but the keys must be different (unique). In a multimap, there can be more than one key, which are the same.

Each time a key is inserted into a set, the set is re-sorted. Note: a set in C++ can also have key/value pairs; and this is not a mathematical view of the set. – Still, in C++, a set can have key/value pairs. So, each time a key/value pair is inserted into a set, the set is re-sorted by keys. On the other hand, a map by definition consists of key/value pairs where the keys have no duplicate. With the map too, each time a key/value pair is inserted into the map, the map is re-sorted by keys. The set and the map are the same in this regard.

Both the set and the map each has the Compare template specialization. Both of them are associative containers. For either of them, in order to have the data structure sorted ascending, use the Compare template specialization, less<Key>, replacing “Key”, with the key type. For either of them, in order to have the data structure sorted descending, use the Compare template specialization, greater<Key>, replacing “Key”, with the key type. For both of them, less<Key> is the default.

For both data structures, member functions are categories in the following categories: constructions (including copy and assignment), iterators, modifiers, observers, operations, and swap. In all these categories, the member functions for both the set and the map are similar.

The set data structure does not have the Element Access Category, but the map does. The element access category consists of the square brackets operators and the at() member functions which are used like the counterparts for the vector. They are used to access (scan) each of the element in the map. The set does not have these operators or functions. For the set, elements are accessed using iterators. Elements can also be accessed for the map using similar iterators.

Above are the main similarities and differences for the set and the map. The peculiarity in this comparison is with the use of key/value pairs. Key/value pair is of the structure called pair in the C++ utility library. The rest of this article gives a brief description of how the pair is employed in both the set and the map, beginning with what a pair is:

## Pair

The syntax of a pair literal is:

{key, value}

A series of such pairs that would consist of a set or map is:

{"lemons", 8}
{"oranges", 5}
{"pears", 12}

This represents a data structure of fruits and their numbers found in a basket. The key for each pair is the string type; and the value for each pair is the integer type. The following program constructs three different pairs of the same value_type, string/int :

#include <iostream>
#include <utility>
using namespace std;
int main()
{
pair<string, int> pr1 = {"lemons", 8};
pair<string, int> pr2 = {"oranges", 5};
pair<string, int> pr3 = {"pears", 12};
return 0;
}

Note that the utility library was included. The names of the pairs are pr1, pr2 and pr3. They are of the same value_type, string/int.

The key/value of a pair must not necessarily be string/int. It can be iterator/bool with the literal syntax:

{iterator, bool}

In a pair object, bool is either true or false, and iterator is the name of the iterator. It is this kind of pair that is returned when a key/value pair, such as a string/int pair, is inserted into a set or a map. The bool component is true, if and only if insertion of the pair took place. The iterator component points to the particular inserted element (key and value) as a whole.

The key of a pair is named “first” in C++; and the value of the pair is named “second”.

## Set and Map Constructions

Set
An empty set of string/int pairs would be constructed as follows:

#include <iostream>
#include <utility>
#include <set>
using namespace std;
int main()
{
set<pair<string,int>> st;
return 0;
}

The Key template specialization is “pair<string,int>”, and it is considered as one component. The one component refers to the pair (of key/value).

Map
An empty map of string/int pairs would be constructed as follows:

#include <iostream>
#include <utility>
#include <map>
using namespace std;
int main()
{
map<string,int> mp;
return 0;
}

Here, template specialization begins with Key and then Value. The Key template specialization is “string” and the Value template specialization is “int”. There are two components for the map, which are the key and value. For the set, there is one component which consists of two internal components. Note the difference.

## Insertion

Set
The following C++ main() function code shows how pairs can be inserted into a set and printed out (displayed on screen):

pair<string, int> prA = {"pears", 12}, prB = {"oranges", 5}, prC = {"lemons", 8};
set<pair<string,int>> st;

st.insert(prA); st.insert(prB); st.insert(prC);

for (set<pair<string,int>>::iterator iter = st.begin(); iter != st.end(); iter++)
cout << iter->first << " => " << iter->second << endl;

The output is:

lemons => 8
oranges => 5
pears => 12

Note that though the key/value pairs were not inserted in ascending order by keys, the elements where internally sorted by keys. The set will always sort its elements by keys, whether they are pairs or not.

Map
The following main() function code shows how pairs can be inserted into a map and printed out (displayed on screen):

pair<string, int> prA = {"pears", 12}, prB = {"oranges", 5}, prC = {"lemons", 8};
map<string,int> mp;

mp.insert(prA); mp.insert(prB); mp.insert(prC);

for (map<string,int>::iterator iter = mp.begin(); iter != mp.end(); iter++)
cout << iter->first << " => " << iter->second << endl;

The output is:

lemons => 8
oranges => 5
pears => 12

Though the key/value pairs were not inserted in ascending order by keys, the elements where internally sorted by keys. The map will always sort its elements by keys.

## Conclusion

The similarities and differences between a set and a map in C++ are easily appreciated from their different definitions. The peculiarity comes up when dealing with pairs. In C++, a set can have pairs which is not really what mathematics suggests. Even so, the programmer needs to know how to handle pairs for a set and for a map. 