STL algorithms¶

The STL library algorithm provides you with the most common operations you need to conduct on elements within a container. In order to use the algorithm library, here is an addition that you need to insert into the code:

#include <algorithm>

The ready-made algorithms are generic: They do not care about the type of the container, since they are able to operate with any container.

You relay the part of the container’s elements that you want to process to the algorithm function by using the iterator range. Every function has at least two iterator parameters.

For example, the algorithm (function) sort can sort the elements of the vector into an ascending order, as long as you use the iterators to tell to it the range that you want to sort:

vector<double> double_vector;
...
sort(double_vector.begin(), double_vector.end());

You should remember that you can replace the iterators begin and end with any pair of iterators representing the range:

vector<double>::iterator range_begin = double_vector.begin();
vector<double>::iterator range_end = double_vector.end();
++range_begin;   // Pointing now to the second element
--range_end;     // Pointing now to the last element

// Sorting all the elements within the vector
// excluding the first and the last one.
// The first and the last one stay in the same place.
sort(range_begin, range_end);

Important: the operations in the algorithm library do not have any effect on the target element of the second iterator parameter. Therefore, in the previous example, the last element of the vector was not sorted, because range_end was pointing to it.

Below you can find a short list of other useful functions from the algorithm library. We use the data structure vector in most of them because at this point, it is the only STL container type you know. However, unless otherwise mentioned, the functions will operate with other container types and strings as well.

count calculates the amount of elements of a certain value within the container:

vector<string> enemies;
...
// How many people by the name of Aki are there in the enemies vector?
cout << count(enemies.begin(), enemies.end(), "Aki")
     << " enemies by the name of Aki!" << endl;

The function count does not work with the map structure quite as straightforwardly.

min_element and max_element search the container for the element with the smallest or the greatest value, and return the iterator pointing at the element in question:
```
vector<int> amounts;
...
vector<int>::iterator smallest_it;
smallest_it = min_element(amounts.begin(), amounts.end());
cout << "Smallest amount: " << *smallest_it << endl;
```
The functions min_element and max_element do not work with the map structure quite as straightforwardly.

find searches the container for the chosen value and returns the iterator into the first element it finds or, if it cannot find the value, it returns the end iterator of the container:

vector<string> patients;
...
vector<string>::iterator iter;
iter = find(patients.begin(), patients.end(), "Kai");
if ( iter == patients.end() ) {
    // There is no Kai in the patient queue.
    ...
} else {
    // Kai was found and is located where iter points at
    // print it and delete it from the queue.
    cout << *iter << endl;

    // The container vector has the method erase. You can use it to
    // remove the element targeted by the iterator.
    patients.erase(iter);
}

You should remember that the string type and the types you will learn later, set and map, have a method function called find. It is worth using, because it is several times as fast as the find in the algorithm library, especially when used by the latter two types.

replace replaces all chosen values with a new value:
```
replace(text_vector.begin(), text_vector.end(), "TUT", "TUNI");
```
in which all elements with the value ”TUT” within the vector are replaced with the value ”TUNI”.

replace does not work with the set or map structures.

fill changes all elements within the iterator range into the given value:

string my_string = "";
...
// After the following fill operation, the
// string will be filled with question marks.
fill(my_string.begin(), my_string.end(), '?');

fill does not work with the set or map structures.

reverse reverses the order of the given range:

vector<Player> order_of_turns;
...
// On the next round of the game,
// the players take their turns in the opposite order.
reverse(order_of_turns.begin(), order_of_turns.end());

reverse does not work with the set or map structures at all.

shuffle shuffles the elements and puts them in a random order:
```
vector<Card> deck;
minstd_rand gen; // A random number generator called gen is created
...
shuffle(deck.begin(), deck.end(), gen);
```
shuffle does not work with the set or map structures at all.

C++ has several different random number generators, and you can find them in the random library. Using the data type minstd_rand, you can create a random number generator of a certain kind, and with the default_random_engine we saw above, a random number generator of another kind. At this point, it is enough for you to know how to create one (or both) of them. If you want, you can search the Internet to find out more about the different random number generators in C++.
copy copies the elements of the container into another container:
```
string word = "";
...
// Initialize the char_vector to have as many
// elements as there are characters in the word.
// Please note that this is, again, an initialization
// where you must use parentheses.
vector<char> char_vector(word.length());

// All the characters in the word are copied
// into the char_vector as elements.
copy(word.begin(), word.end(), char_vector.begin());
```
You must have free space at the target location of the copy action. At the start, the char_vector above is initialized to include as many elements as the word includes characters.

This concerns all STL algorithms storing results in a container: The target container must have space for all the elements you are going to store.

The element types of the source container and target container must be the same.

Several algorithm library functions have a version that you can adjust by using a function parameter. Let us take the sort function as an example.

Before getting into the details, it is important for you to understand that the sort function can sort data into order by magnitude only if the data has a defined magnitude relation (less/greater). It does not concern, for example, a vector with colors as its elements, because it is not known whether purple is less or greater than, say, lilac since you cannot sort colors by their magnitude.

This does not present a problem when the elements in the container to be sorted contain ordinary data for that language, such as strings or other predefined types of C++. However, as soon as you try to use classes implemented by yourself that cannot be compared automatically, you have a problem.

Here is a small example (irrelevant parts of the code are left out to save room):

class Student {
public:
    Student(string const& name, int student_id);
    string fetch_name() const;
    int fetch_student_id() const;
    void print() const; 
private:
    string name_;
    int    id_;
};

bool compare_ids(Student const& stud1, Student const& stud2) {
    return stud1.fetch_student_id() < stud2.fetch_student_id();
}

bool compare_names(Student const& stud1, Student const& stud2) {
    return stud1.fetch_name() < stud2.fetch_name();
}

int main() {
    vector<Student> students = {
        { "Teekkari, Tiina", 121121 }, 
        { "Arkkari, Antti",  111222 }, 
        { "Fyysikko, Ville", 212121 }, 
        { "Teekkari, Teemu", 100011 }, 
        { "Kone, Kimmo",     233233 }, 
    };

    // Let's order and print in the increasing order of student ids.
    sort(students.begin(), students.end(), compare_ids);
    for ( auto stud : students ) {
        stud.print();
    }

    cout << string(30, '-') << endl;

    // Let's order and print in the increasing order of names.
    sort(students.begin(), students.end(), compare_names);
    for ( auto stud : students ) {
        stud.print();
    }
}

The functions compare_ids and compare_names of the example are so-called comparison functions:

The parameters (2 pcs) are constant references to the elements of the data type your function is supposed to compare.
The type of the return value is bool.
The return value is true exactly when the first parameter is strictly smaller than the second one.

You can give the comparison function as an additional parameter to such functions of the algorithm library that work differently depending on the size of the elements in the processed container.

Therefore, you could search and print the student with the greatest student number from the function above:

vector<Student>::iterator iter;
iter = max_element(students.begin(),
                   students.end(),
                   compare_ids);

// Because the target of the next print method is
// the object the iterator is pointing to, you will use
// the operator -> instead of a period.
iter->print();

When you give the comparison function as a parameter to a function in the algorithm library, you use only the name of the function. If there were parentheses after the function, it would try to call the function and give the return value of the comparison function as the parameter, and this is not supposed to happen.

Functions with other functions as their parameter are called higher-order functions.