More STL containers¶

Examples on STL set¶

We will now define a set where you can store strings:

set<string> ship_has_been_loaded;

After the definition, the set is automatically empty.

A set has no separate search key, but its elements act as keys. Therefore, the type of the elements of a set must have an order.

The set can be initialized with another set of the same type, or another set of the same type can be assigned into it:

set<int> lottery_numbers_1;
...
set<int> lottery_numbers_2(lottery_numbers_1);
...
lottery_numbers_1 = lottery_numbers_2;

You can also initialize and assign your set with a curly bracket list:

set<int> prime_numbers = {2, 3, 5, 7, 11, 13, 17};
...

set<string> friends;
...
friends = { "Matti", "Maija", "Teppo" };

You can add a new element into the set with the method insert:

ship_has_been_loaded.insert("dogs");

The addition works also if the element is already included in the set but will not do anything.

The amount of elements in the set can be found out with the method size:

// Amount of friends
cout << friends.size() << endl;

You can examine whether an element is included in the set by using the method find:

// The word is not included in the set, let's add it.
if ( ship_has_been_loaded.find(word) == ship_has_been_loaded.end() ) {
    ship_has_been_loaded.insert(word);
    cout << "Ok!" << endl;

// The word was already included in the set.
} else {
    cout << "You lost, " << word << " has already been loaded!" << endl;
}

A single element can be removed from the set with the method erase:

// Teppo is not a friend anymore.
friends.erase("Teppo");

The method clear empties the set (removes all the elements):

ship_has_been_loaded.clear();

The relational operators can be used on sets with the same element type:

if ( lottery_numbers_1 == lottery_numbers_2 ) {
    // Both of the sets include exactly the same elements.
    ...
} else {
    // The contents of the sets differ.
    ...
}

The method empty returns the value true only if the set is empty:

if ( not friends.empty() ) {
    // There is at least one friend.
}

Examples on STL map¶

Unlike other STL structures, the definition of the map includes both the types of the key and the mapped value:

map<string, double> prices;

After the definition, the uninitialized map container is empty.

As with other containers, the map can be initialized from another map of the same type, and you can assign a map of a similar type into it:

map<string, string> dictionary_1;
...
map<string, string> dictionary_2(dictionary_1);
...
dictionary_1 = dictionary_2;

You can also use the curly bracket list for initializing or assigning:

map<string, double> prices_2 = {
    { "milk",   1.05 },
    { "cheese", 4.95 },
    { "glue",   3.65 },
};
...
prices_2 = {
    { "pepper",    2.10 },
    { "cream",     1.65 },
    { "chocolate", 1.95 },
};

The data related to a search key can be accessed with the method at:

cout << prices_2.at("cream") << endl;  // 1.65
prices_2.at("cream") = 1.79;

However, you should remember a possible problem when using the at method: If the key cannot be found in the map, the result is an exception and the program will terminate. So please note: you cannot add new elements to map with the method at.

You can avoid the problematic situation by checking if the search key is located in map before calling at, just like the code below shows you.

if ( dictionary_3.find(word) != dictionary_3.end() ) {
    // The word was found in the map.
    cout << dictionary_3.at(word) << endl;
} else {
    // The word was not found in the map.
    cout << "Error, an unknown keyword!" << endl;
}

It uses the previously known fact that find returns the iterator end() if it does not find what it was searching for.

You can remove a key-value pair from the map by giving the search key you want to be removed as a parameter to the method erase:

if ( prices_2.erase("chocolate") ) {
    // The erasing was successful, "chocolate"
    // is not in the pricelist anymore.
    ...
} else {
    // The erasing was not successful, "chocolate"
    // was not in the pricelist to start with.
    ...
}

Even though it is not an error to remove a key-value pair that does not exist, you can check their existence with find before the removal if you want.

You can add a new key-value pair with the insert method:

dictionary_1.insert( { word, word_in_finnish } );

If word is already in dictionary_1 as a search key, insert will have no effect.

The method size returns the amount of key-value pairs stored in map:

cout << "Dictionary contains " << dictionary_2.size()
     << " pairs of words." << endl;

The action of going through the elements of map has also been implemented with iterators. It is, however, not as straightforward as with other STL containers, because each element now contains two parts: a key value and a mapped value. It has been implemented by making the elements of map structs (see the material on data driven programming on the previous round). Therefore, suppose a map structure defined like this:

map<int, string> students = {
    // id, name
    { 123456, "Teekkari, Teemu" },
    ...
};

then the elements stored in the structure would be of the following struct:

struct {
    int    first;
    string second;
};

where the field of the search key is actually named first, and the field of the mapped value, second.

Therefore you can go through the elements of map with an iterator like this:

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
    map<int, string> students = {
        { 200001, "Teekkari, Tiina" },
        { 123456, "Teekkari, Teemu" },
        // ···
    };

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

It is worth noting in the code that the struct fields pointed by the iterator are handled with the operator ->, instead of ., used usually.

If you want to avoid direct use of iterators, you can use for to go through the elements in map:

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
    map<int, string> students = {
        { 200001, "Teekkari, Tiina" },
        { 123456, "Teekkari, Teemu" },
        // ···
    };

    for ( auto data_pair : students ) {
        cout << data_pair.first << " "
             << data_pair.second << endl;
    }
}

Because data_pair in the previous loop is not an iterator but a real struct located in map, we have used the usual . operator to handle the fields first and second.

STL pair¶

Previously we considered map structure, the elements of which was said to be structs with two fields. Such a struct, consisting of two fields, can be defined as a pair.

It is possible to use pairs as such, and they can found from the library utility, and thus, you need to write at the beginning of the code the text:

#include <utility>

As can be concluded from its name, a pair consists of two elements. You can access the first one of them by writing first and the second one by writing second, as told in the context of map.

Below you can see different ways to declare and initialize pairs:

pair <int, char> pair1;
pair1.first = 1;
pair1.second = 'a';

pair <int, char> pair2 (1, 'a');

pair <int, char> pair3;
pair3 = make_pair(1, 'a');

auto pair4 = make_pair(1, 'a');

Unordered containers¶

The containers map and set introduced earlier have the property that their elements are ordered according to the key values. Therefore, a new element is inserted to such a location that the order is preserved.

Above you saw the example that traverses a map with an iterator or in a for loop. The output of the example code would print the elements in ascending order. This is useful in some situations. Most of the exercises (related to STL containers) on this course, the output is required to be in a certain order. Such a requirement makes it easier to implement automated tests.

In general, preserving the order makes some operations inefficient. Because of that, STL provides counterparts for map and set, called unordered_map and unordered_set. As you can conclude from the names, the elements in the latter containers are not in any specific order.

Since there is no need to keep the elements in order, it is possible to make searching, inserting, and removing elements more efficient on average than these operations are with ordered containers. You should use unordered containers, if the order of the elements does not matter, and you need not traverse the whole container element by element, but you only search for a certain element at a time.

The later course ”Data structures and algorithms” considers efficiencies of different containers more precisely, and especially for efficiency reasons it most often uses unordered_map and unordered_set, instead of map and set.

More examples¶

You can find a few larger examples on using the STL containers in the course materials: examples/05/cashier and examples/05/calendar.