Unique and Ordered Containers in C++

6, 10, 2, 8, 4 is a set; 2, 4, 6, 8, 10 is a set of the same integers, arranged in ascending order. In Mathematics, a set has unique elements (distinct elements), and that is, no element occurs more than once. Furthermore, a multiset is a set, where any element can occur more than once. 6, 6, 10, 2, 2, 8, 4, 4, 4 is a multiset. 2, 2, 4, 4, 4, 6, 6, 8, 10 is the same multiset, but with the elements arranged in ascending order. This article does not deal with multiset. It deals with the C++ data structure called, set.

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
#include
using namespace std;

Note the directive “#include ”, 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
#include
using namespace std;

Note the directive “#include ”, 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:

set objectName

Example:

set setObj;

An example to create a set with content is:

set setObj(6, 10, 2, 8, 4);

The syntax to create an empty map is:

map objectName

Example:

map mapObj;

An example to create a map with content is:

map mapObj('c',30,'b',20,'d',30,'e',40,'a',10);

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 setObj(6, 10, 2, 8, 4);
set::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 mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
map::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:

const set setObj(6, 10, 2, 8, 4);
set::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:

const map mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
map::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 setObj(6, 10, 2, 8, 4);
set::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 mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
map::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:

const set setObj(6, 10, 2, 8, 4);
set::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:

const map mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
map::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 setObj(6, 10, 2, 8, 4);
set::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:

map mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
cout << mapObj['b'] << '\n';
mapObj['b'] = 55;
cout << mapObj['b'] << '\n';

The output is:

20
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:

set > setObj(6, 10, 2, 8, 4);

So, after the type, e.g., int, for the template, there is a comma, followed by “greater” 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:

map > mapObj('c',30,'b',20,'d',30,'e',40,'a',10);

So, after the type pair, e.g., “char, int”, for the template, there is a comma, followed by “greater” 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:

set > setObj(6, 10, 2, 8, 4);
for (set::iterator iter = setObj.begin(); iter != setObj.end(); ++iter)

cout << *iter << ";

The output is:

10 8 6 4 2

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:

map > mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
for (map::iterator iter = mapObj.begin(); iter != mapObj.end(); ++iter)

cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

The output is:

e, 40, d, 30, c, 30, b, 20, a, 10,

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:

set > setObj(6, 10, 2, 8, 4);
cout << setObj.size() << '\n';

The output is 5.

Map example:

map > mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
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:

set setObj(6, 10, 2, 8, 4);
setObj.insert(6);
setObj.insert(9);
setObj.insert(12);
for (set::iterator iter = setObj.begin(); iter != setObj.end(); ++iter)

cout << *iter << ";

The output is:

2 4 6 8 9 10 12

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:

map mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
mapObj.insert('e',80);
mapObj.insert('f',50);
mapObj.insert('g',60);
for (map::iterator iter = mapObj.begin(); iter != mapObj.end(); ++iter)
cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

The output is:

a, 10, b, 20, c, 30, d, 30, e, 40, f, 50, g, 60,

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:

set setObj(6, 10, 2, 8, 4);
bool ret = setObj.empty();
cout << ret << '\n';

The output is 0 for false, meaning the set here is not empty.

Map example:

map mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
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 setObj(10, 20, 30, 40, 50);
set::iterator iter = setObj.begin();
set::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:

new size: 4
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 mapObj('a',10,'b',20,'c',30,'d',40,'e',50);
map::iterator iter = mapObj.begin();
map::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:

new size: 4
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:

set setObj(6, 10, 2, 8, 4);
setObj.clear();
cout << setObj.size() << '\n';

The output is 0.

map example:

map mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
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.