A map in software is like an array, but it is an array with two columns instead of one. The first column has the keys and the second column has the values. Each row is one pair, making a key/value pair. A key is directly related to its value.
An example of a map is {{‘c’,30}, {‘b’,20}, {‘d’,30}, {‘e’,40}, {‘a’,10}}. The first key/value pair inserted here, is {‘c’,3}, where ‘c’ is the key and 30 is the value. This map is not ordered by keys. Ordering this map by keys produces {{‘a’,10}, {‘b’,20}, {‘c’,30}, {‘d’,30}, {‘e’,40}}. Notice that there can be duplicated values, but not duplicated keys. An ordered map is a map ordered by keys.
A multiset is to a set, as a multimap is to a map. This means that there are maps with duplicate keys. An example of a multimap is {{‘a’,10}, {‘b’,20}, {‘b’,20}, {‘c’,30}, {‘c’,30}, {‘d’,30}, {‘e’,40}}. And as stated above, this article does not deal with multimap, rather, it deals with the C++ data structure called, map.
In C++, a data structure is a structure with properties (data members) and methods (member functions). The data of the structure is a list; a set is a list; a map is a list of key/value pairs.
This article discusses the basics of sets and maps in C++, and to better understand this article, the reader should have had a basic knowledge of C++.
Article Content:
- Class and its Objects
- Creating a set or a map
- Iterator Basics
- Element Access for set and map
- Order of Elements in a set or map
- Other Commonly Used Member Functions
- Conclusion
Class and its Objects:
In C++, the set, the map, and other similar structures are called containers. A class is a generalized unit with data members, which are variables, and member functions that are related. When data members are given values, an object is formed. However, an object is formed in a process called, instantiation. As a class can lead to different values for the same data member variables, different objects can then be instantiated from the same class.
In C++, an unusable set is a class, as well as an unusable map. When an object is instantiated from the unusable set or the unusable map, the object becomes the real data structure. With the set and map data structures, the principal data member is a list. Well, the set and the map form a group of containers called, ordered associative containers. Unordered set and the unordered map also exist, but those are unfortunately not addressed in this article.
Creating a set or a map:
Instantiating a set from its set class is creating a set; instantiating a map from its map class is creating a map. The object so created is given a name of the programmer’s choice.
In order to create a set, the program should begin with:
#include <set>
using namespace std;
Note the directive “#include <set>”, which includes the set library that has the set class from which set data structures will be instantiated.
In order to create a map, the program should begin with:
#include <map>
using namespace std;
Note the directive “#include <map>”, which includes the map library that has the map class from which map data structures will be instantiated.
The syntax to create an empty set is:
Example:
An example to create a set with content is:
The syntax to create an empty map is:
Example:
An example to create a map with content is:
Iterator Basics:
An iterator is an elaborated pointer, which can be used to traverse the list of the data structure from the beginning to the end.
The begin() member Function
The begin() member function returns an iterator that points to the first element of the list. The following example illustrates this for the set:
set<int>::iterator iter = setObj.begin();
cout << *iter << '\n';
Note the way begin() has been used with setObj and the dot operator. iter is the returned iterator object. Also, note the way it has been declared. * is the indirection operator. As used with iter, it returns the first element of the set; the first element is 2 instead of 6 – see explanation below.
The following example illustrates the use of the begin() function for the map:
map<char,int>::iterator iter = mapObj.begin();
cout << "{" << (*iter).first <<',' << (*iter).second << "}\n";
Note the way begin() has been used with mapObj and the dot operator. iter is the returned iterator object. Also, note the way it has been declared. “first”, as used here, refers to the key. “second” refers to the value corresponding to the key. Observe how they have been used with iter to obtain the start element components of the list. The first element is {a,10} instead of {c,30} – see explanation below.
The “begin() const” member Function
The “begin() const” member function returns an iterator that points to the first element of the list when the declaration of the set begins with const (for constant). Under this condition, the value in the list, referred to by the iterator returned, cannot be changed by the iterator. The following example illustrates its use for the set:
set<int>::const_iterator iter = setObj.begin();
cout << *iter << '\n';
Note the way begin() has been used with setObj and the dot operator. No “const” has been typed just after begin(). However, “const” has preceded the declaration. iter here is the returned constant iterator object, which is different from the normal iterator. Also, note the way it has been declared. * is the indirection operator; as used with iter, it returns the first element of the set. The first element is 2 instead of 6 – see explanation below.
The following example illustrates the use of the “begin() const” function for the map:
map<char,int>::const_iterator iter = mapObj.begin();
cout << "{" << (*iter).first <<',' << (*iter).second << "}\n";
Note the way begin() has been used with mapObj and the dot operator. No “const” has been typed just after begin(). However, “const” has preceded the declaration. iter here is the returned constant iterator object, which is different from the normal iterator. Also, note the way it has been declared. “first”, as used here, refers to the key; “second”, as used here, refers to the value corresponding to the key. Observe how they have been used with iter to obtain the start element components of the list. The first element is {a,10} instead of {c,30} – see explanation below.
The end() member Function
The end() member function returns an iterator that points just after the end of the list. The following example illustrates this for the set:
set<int>::iterator iter = setObj.end();
cout << *iter << '\n';
Note the way end() has been used with setObj and the dot operator. iter is the returned iterator object. Also, note the way it has been declared. * is the indirection operator; as used with iter, it returns the last+1 element of the set. In the author’s computer, this last+1 element is 5, which is not on the list. So, careful not to use this element.
The following example illustrates the use of the end() function for the map:
map<char,int>::iterator iter = mapObj.end();
cout << "{" << (*iter).first <<',' << (*iter).second << "}\n";
Note the way end() has been used with mapObj and the dot operator. iter is the returned iterator object. Also, note the way it has been declared. * is the indirection operator; as used with iter, it returns the last+1 element of the map. In the author’s computer, this last+1 element is {,0}, which is not in the list. So, careful not to use this element.
The “end() const” member Function
The “end() const” member function returns an iterator that points just after the end of the list when the declaration of the set begins with const (for constant). Under this condition, the value in the list, referred to by the iterator returned, cannot be changed by the iterator. The following example illustrates its use for the set:
set<int>::const_iterator iter = setObj.end();
cout << *iter << '\n';
Note the way end() has been used with setObj and the dot operator. No “const” has been typed just after the end(). However, “const” has preceded the declaration. iter is the returned iterator object. Also, note the way it has been declared. * is the indirection operator; as used with iter, it returns the last+1 element of the set.
The following example illustrates the use of the “end() const” function for the map:
map<char,int>::const_iterator iter = mapObj.end();
cout << "{" << (*iter).first <<',' << (*iter).second << "}\n";
Note the way end() has been used with mapObj and the dot operator. No “const” has been typed just after the end(). However, “const” has preceded the declaration. iter is the returned constant iterator object, which is different from the normal iterator. Also, carefully observe the way it has been declared.
Element Access for set and map:
Set
With the set, the element is read using the indirection operator. The first two elements of a set are read in the following example:
set<int>::iterator iter = setObj.begin();
cout << *iter << '\n';
++iter;
cout << *iter << '\n';
The output is 2, then followed by 4 – see explanation below. To point at the next element of the list, the iterator is incremented.
Note: An element cannot be changed using the indirection operator for the set. For example, “*iter = 9;” is not possible.
map
A map consists of key/value pairs. A value can be read using the corresponding key, and changed using the same key. The following code segment illustrates this:
cout << mapObj['b'] << '\n';
mapObj['b'] = 55;
cout << mapObj['b'] << '\n';
The output is:
55
The dot operator has not been used here. Instead, it is the square brackets operator, which takes the key as content, that has been used.
Order of Elements in a set or map:
Elements can be inserted into a set, in any order. However, once inserted, the set rearranges its elements in ascending order. Ascending order is the default order. If descending order is needed, then the set has to be declared as in the following example:
So, after the type, e.g., int, for the template, there is a comma, followed by “greater<type>” in the angle brackets.
Elements can be inserted into a map in any order. However, once inserted, the map rearranges its elements in ascending order by key (only) while maintaining the relationship between each key and its value. Ascending order is the default order; if descending order is needed, then the map has to be declared as in the following example:
So, after the type pair, e.g., “char, int”, for the template, there is a comma, followed by “greater<type>” in the angle brackets.
Traversing a set
The while-loop or for-loop with the iterator can be used to traverse a set. The following example uses a for-loop to traverse a set that has been configured in descending order:
for (set<int>::iterator iter = setObj.begin(); iter != setObj.end(); ++iter)
{
cout << *iter << ' ';
}
The output is:
Incrementing an iterator points it to the next element.
Traversing a map
The while-loop or for-loop with the iterator can be used to traverse a map. The following example uses a for-loop to traverse a map that has been configured in descending order:
for (map<char,int>::iterator iter = mapObj.begin(); iter != mapObj.end(); ++iter)
{
cout << "{" << (*iter).first << ", " << (*iter).second << "}" << ", ";
}
The output is:
Incrementing an iterator points it to the next element. “first”, in the code, refers to the key and “second” refers to the corresponding value. Note how these values have been obtained for the output.
Other Commonly Used Member Functions:
The size() Function
This function returns an integer, which is the number of elements in the list. Set example:
cout << setObj.size() << '\n';
The output is 5.
Map example:
cout << mapObj.size() << '\n';
The output is 5.
The insert() Function
set
set does not allow duplicate. So, any duplicate inserted is silently rejected. With the set, the argument to the insert() function is the value to be inserted. The value is fitted into a position, in which the order in the set remains ascending or descending. Example:
setObj.insert(6);
setObj.insert(9);
setObj.insert(12);
for (set<int>::iterator iter = setObj.begin(); iter != setObj.end(); ++iter)
{
cout << *iter << ' ';
}
The output is:
Note: The insert() member function can be used to populate an empty set.
map
map does not allow duplicate by key. So, any duplicate inserted is silently rejected. With the map, the argument to the insert() function is the key/value pair in braces. The element is fitted into a position by key, in which the order in the map remains ascending or descending. Example:
mapObj.insert({'e',80});
mapObj.insert({'f',50});
mapObj.insert({'g',60});
for (map<char,int>::iterator iter = mapObj.begin(); iter != mapObj.end(); ++iter)
cout << "{" << (*iter).first << ", " << (*iter).second << "}" << ", ";
The output is:
Note: The insert() member function can be used to populate an empty map.
The empty() Function
This function returns true if the list is empty, and false if otherwise. Set example:
bool ret = setObj.empty();
cout << ret << '\n';
The output is 0 for false, meaning the set here is not empty.
Map example:
bool ret = mapObj.empty();
cout << ret << '\n';
The output is 0 for false, meaning the map here is not empty.
The erase() Function
set
Consider the following code segment:
set<int>::iterator iter = setObj.begin();
set<int>::iterator itr = setObj.erase(iter);
cout << "new size: " << setObj.size() << '\n';
cout << "next value: " << *itr << '\n';
itr = setObj.erase(itr);
cout << "new size: " << setObj.size() << '\n';
cout << "next value: " << *itr << '\n';
The output is:
next value: 20
new size: 3
next value: 30
The erase() function takes an iterator that points to an element as an argument. After erasing the element, the erase() function returns an iterator that points to the next element.
map
Consider the following code segment:
map<char,int>::iterator iter = mapObj.begin();
map<char,int>::iterator itr = mapObj.erase(iter);
cout << "new size: " << mapObj.size() << '\n';
cout << "next value pair: {" << (*itr).first <<',' << (*itr).second << "}\n";
itr = mapObj.erase(itr);
cout << "new size: " << mapObj.size() << '\n';
cout << "next value pair: {" << (*itr).first <<',' << (*itr).second << "}\n";
The output is:
next value pair: {b,20}
new size: 3
next value pair: {c,30}
The erase() function takes an iterator that points to an element as an argument. After erasing the element, the erase() function returns an iterator that points to the next element.
The clear() Function
The clear() function removes all the elements in the list. Set example:
setObj.clear();
cout << setObj.size() << '\n';
The output is 0.
map example:
mapObj.clear();
cout << mapObj.size() << '\n';
The output is 0.
Conclusion:
A set data structure in C++ is a structure in which the list of elements is stored in ascending order by default, or in descending order by programmer’s choice. All the elements of the set are unique. A map data structure in C++ is a structure in which the list is a hash of key/value pairs, stored in ascending order of keys by default, or in descending order of keys by programmer’s choice. The keys are also unique, and there can be duplicated values. The main data member of either of the structures is the list. Either structure has member functions, some of which are commonly used.
