Previous Next ua

Laboratory Training 5

Use of the Standard Template Library

1 Training Tasks

1.1 Presentation and Processing of Data about Students using the Standard Template Library

Complete task 1.3 of the third laboratory training (Classes for Representing Students and Groups).

In the "Student" class, use a std::string of type to store the last name. Store grades for the last session in a vector of integers std::vector<int>). In addition to the functions listed in task 1.3 of the second laboratory training, you should implement functions that perform:

calculating the value that is used for sorting according to individual task;
test conditions used for searching data according to individual task.

In the "Group of students" class, place a vector of objects that represents a student. Implement the functions defined in task 1.3 of the second laboratory training for this class. To sort the array according to the criteria specified in the individual task, use the sort() algorithm. To find data about students that meet the condition given in the individual task, apply the for_each() algorithm.

Additionally, place objects of" "Student" class into priority queue and obtain objects in descending order of the average score.

1.2 The Vector of Vectors for Representation of Two-Dimensional Array

Complete task 1.4 of the previous laboratory training (Class for Representing a Two-Dimensional Array) by creating a class whose field is a vector of vectors of the Standard template library. The created class does not require a copy constructor, destructor and overloaded assignment operator, because data is not placed into free store (vectors are responsible for this).

1.3 Counting the Number of Repetitions of Values (Additional Task)

Develop a program in which integer values are read and the number of repetitions of each value is counted, except for the numbers given in some list. Counting the repetitions of a number should be implemented using map, the list of numbers for exclusion should be implemented using a set. Each time a number from the list is encountered, output message.

2 Instructions

2.1 The Overall Structure of the Standard C++ Library

The Standard C++ Library is a collection of classes and functions for solving complex and low-level programming tasks. The Library includes the following components:

tools for working with I / O streams;
a set of structured data and algorithms formerly known as the Standard Template Library (STL)
means of localization (adaptation to national languages and standards)
parameterized class string
parameterized class complex for representing complex values
the valarray class that is optimized for processing numeric arrays
parameterized class numeric_limits and specialization for each base data type
memory management tools
great support for national character sets
exception handling means.

Tools provided by the Standard C++ Library are defined in std namespace and presented by a large set of header files.

The main building blocks provided by STL include containers, iterators and algorithms. A container is a class that stores a collection of other objects and includes basic functions to support the use of common algorithms. Standard containers are not derived from some common base class. Instead, each container provides a set of standard operations with standard names and meaning.

There are main groups of containers:

sequences: vector, list, deque
container adapters: stack, queue, priority_queue
associative containers: associative arrays (map, multimap) and sets (set, multiset).

A special group includes classes built on standard containers and adapted for specific use: strings (string), value arrays (valarray) and bit sets (bitset).

Most containers are defined in header files with the same names. The multimap class is defined in the header file <map>. The multiset class is defined in the header file <set>.

2.2 Standard Sequential Containers

2.2.1 Overview

The Standard Library provides two types of containers: sequences and associative containers. Sequences include containers such as vector, list, and deque.

There are also sequence adapters, such as stack, queue, and priority_queue. They are built on use inside existing standard containers.

To work with indexes, there is the size_t type, a synonym for the unsigned int type, defined using the typedef.

The following types are defined for all sequences:

value_type - item type,
size_type - type of indices, sizes, and counters (unsigned int),
difference_type - type of difference between iterators,
reference and const_reference - reference to item.

The string type, which is actually a character vector, is very useful.

2.2.1 Use of Vectors

The vector (vector class) is in many respects similar to the traditional one-dimensional array. To use vectors, you must include the <vector> header file. The item type is indicated in angle brackets ("<" and ">"). In the example below, the variable v1 is defined as a vector containing n real numbers:

#include <vector>
using std::vector;

vector<double> v1(n);

where n can be either constant or variable.

You can also create a vector while filling the elements with initial values:

vector<int> v2(10, 1000); // Ten items with values 1000

Thanks to the new type std::initializer_list, as well as new syntactic features of the language in version C++11 and an additional constructor, vectors can be initialized as arrays:

vector<int> v3 = { 1, 2, 4, 8 };

The advantage of a vector over a conventional array is that it keeps its size. The size() member function returns the count of items. A similar function is implemented for all sequential containers.

You can refer to the individual items by index, like array items, for example:

#include <iostream>
#include <vector>

using std::vector;
using std::size_t;
using std::cout;
using std::endl;

int main()
{
    vector<int> v = { 10, 20, 40, 80 };
    for (size_t i = 0; i < v.size(); i++)
    {
        cout << v[i] << endl;
    }
}

Note. You can use int to represent the index, but this will generate a compiler warning "signed/unsigned mismatch". It is recommended to use size_t.

You can also refer to items using at() member function (both for reading and for writing, because this function returns a reference):

for (size_t i = 0; i < v.size(); i++)
{
    v.at(i) = v.at(i) + 9;
}

The difference between [] and at() is that the function at() generates an exception if the index specified as an argument is out of range.

You can use range-based loops for working with vectors. For example, this way you can display all the items of the vector:

for (int &k : v)
{
    cout << k << ' ';
}

Unlike arrays, such loops can be applied anywhere in the program, not just in the block in which the vector is defined. The range-based for loop can be used to iterate types that support iterators and begin() / end() functions. It's almost all C++ Standard Library containers.

You can create an "empty" vector (length 0), and then add items to the end using the push_back() member function. This way you can obtain a vector whose items are 0, 1, 2, 3 and 4:

vector<int> v4;
for (int i = 0; i < 5; i++)
{
    v4.push_back(i);
}

Using pop_back() function, you can remove the last item. The push_back() and pop_back() functions can be applied to all sequence containers.

The empty() member function returns true if the container is empty.

The vector may contain vectors. This way you can imitate a two-dimensional array.

2.2.2 Iterators

Iteration through the container is performed by defining an iterator class suitable for a particular kind of container. An iterator is an object that abstracts the notion of a pointer to an item and allows you to bypass the items of a sequence in a certain direction. Each container class in the Standard C++ Library is able to generate an iterator that implements optimal mechanisms for passing items.

The iterator object must support the following operations:

get the current item (implemented by overloaded operators * and ->)
increment (implemented by overloaded operator ++);
equality check (implemented by overloaded operator ==);

There are unidirectional iterators (for writing and reading), bidirectional iterators, and random access iterators. They differ in the number of operators defined for them. The bidirectional iterator supports the operation --, the random access iterators support the operations +, -, +=, -=, <, >, <=, >=, and also [].

The vector container can provide the following iterators:

vector<T>::iterator - an iterator that implements a direct path through the container;
vector<T>::reverse_iterator - an iterator that implements a reverse pass through the container;
vector<T>::const_iterator - an iterator that cannot be used to change the container items;
vector<T>::const_reverse_iterator - a constant iterator that implements a reverse pass through the container.

Vector iterators are random access iterators (not only sequential ones). For them, the operations of adding integers and subtracting integers are implemented.

The container does not contain an iterator object, just its type defined there. You should create an iterator object manually:

vector<int> v(4);
vector<int>::iterator vi; 
// v.begin() and v.end() return iterators,  
// indicating the beginning and the end of the vector
// Change the value through the iterator:
for (vi = v.begin(); vi != v.end(); vi++)
{
    *vi = 200;
}

Using the reverse_iterator object, you can bypass the vector from end to beginning:

vector<int>::reverse_iterator ri; 
// v.rbegin() returns an iterator for the back pass,
//            pointing to end of the vector
// v.rend()   points to the position before the vector
// ri++       moves the iterator to the previous element
for (ri = v.rbegin(); ri != v.rend(); ri++)
{
    cout << *ri; // bypass from end to begin
}

The iterator const_iterator works similarly to the usual one, except that you cannot change array items through it.

One of the constructors of the vector (and other sequences) fills the elements with values from another sequence using two iterators:

vector<int> v1 = { 0, 1, 2, 3 };
vector<int> v2(v1.begin() + 1, v1.end() - 1); // 1, 2

The member function

insert(iterator pos, const T& x);

inserts x before pos. The member function

erase(iterator first, iterator last);

removes a subsequence from the vector.

In addition to using iterators, the first and last elements can be accessed using the front() and back() member functions.

2.2.3 Working with Lists and Double Ended Queues

List (the list class) is a sequence optimized for inserting and deleting items. This container is implemented with classic doubly-linked list. The most common operations for working with the list are:

insert(p, x) - adding x before p;
insert(p, n, x) - adding n copies of x before p;
insert(p, first, last) - adding before p elements of the sequence specified by the iterators first and last;
erase(p) - deleting item at position p;
erase(first, last) - deleting the sequence specified by the iterators;
clear() - removal of all items.

The following example demonstrates the use of some list member functions:

std::list<int> list = { 1, 2, 4, 8, 16 }; // initialization with a list of values is available in C++11
list.insert(++++list.begin(), 3); // 1, 2, 3, 4, 8, 16
list.insert(--list.end(), 2, 12); // 1, 2, 3, 4, 8, 12, 12, 16
list.erase(--list.end()); // 1, 2, 3, 4, 8, 12, 12

The "Double Ended Queue" (deque) class is similar to vector, but with the ability to insert and remove elements at both ends. The class is implemented quite effectively. Consider an example:

std::deque<int> deque = { 1, 2, 4, 8, 16 };
std::cout << deque[0] << std::endl; // 1
deque.push_front(0);
std::cout << deque[0] << std::endl; // 0
deque.push_back(32); // 0, 1, 2, 4, 8, 16, 32
deque.pop_front();
std::cout << deque[0] << std::endl; // 1
deque.pop_front();
std::cout << deque[0] << std::endl; // 2
deque.pop_back();
deque.pop_back(); // 2, 4, 8

The deque class is used, in particular, for the internal implementation of sequence adapters (will be discussed below).

2.2.4 Strings

To work with sequences of characters (strings) Standard C++ Library offers a special type: std::string. It is defined using typedef as the instantiated class of the template class basic_string:

typedef basic_string<char> string;

The basic_string template is a specialized vector optimized for storing strings. This template can be used to create specific types of strings that differ in the representation of characters. In particular, the wstring type works with 16-bit characters.

To work with strings, you must include the <string> header file. The constructor without parameters creates an empty string. A string can be initiated by a chain of characters or by another string of the type std::string:

string s1;
string s2("a string");
string s3 = "initial value";
string s4(s3);
string s5 = s4;

The total number of characters is returned by the length() function, which is a synonym for the size() member function. You can access individual characters by index or by using the at() function. For example, all characters of the string s in the following example are replaced by the character 'a':

for (size_t i = 0; i < s.length(); i++)
{
    s[i] = 'a';
}

The class provides a number of useful member functions that implement searching, replacement, pasting, exchanging content, etc. In particular, using the resize() function, the current string length can be changed. The second parameter of the function can be a symbol inserted into new positions:

s7.resize(15, '\t'); // inserting tabs

The empty() member function returns true if the string does not contain symbols. The + operator stitches two lines:

s = s1 + s2;

You can also use +=. You can assign a string value, an array of characters, or a single character to another string:

s1 = s2;
s2 = "a new value";
s3 = 'x';

The += operator, as well as the + operator with the corresponding second operand, can be used for all three forms of assignment.

The member function c_str() returns a temporary pointer to an array of characters (null-terminated string). For example:

string s = "Text";
cout << s.length() << endl; // 4
cout << strlen(s.c_str()) << endl; // the same

Note. In the above example, the use of c_str() does not make much sense. Use makes sense when the corresponding function with a parameter of type string is absent.

To use standard algorithms, you can work with random access iterators and the corresponding functions begin() and end(). Reverse iterators are obtained using the rbegin() and rend() functions.

The insert() and erase() member functions are similar to the corresponding vector functions. For their work, it is necessary to define the parameters of the corresponding iterators. The replace() function is a combination of erase() and insert():

s2.replace(s2.begin()+3, s2.begin()+6, s3.begin(), s3.end());

An alternative implementation of functions is the use of integer positions and string constants:

s3.insert(3, "abc");     // insertion abc after position 3
s3.erase(4, 2);          // remove items 4 and 5
s3.replace(4, 2, "pqr"); // replacement positions 4 and 5 on pqr

The copy() member function copies the characters from the specified range into a character array:

string s = "abcdefg";
char c_arr[100] = "0123456";
s.copy(c_arr, 4);   // assigns 4 characters from the beginning of s3 to the first positions of c_arr
std::cout << c_arr << '\n'; // abcd456
s.copy(c_arr, 2, 3);// assigns 2 characters from position 3 of s3 to the first positions of c_arr
std::cout << c_arr << '\n'; // decd456

The substr() member function returns a substring. The substring is specified by a range of indices:

cout << s4.substr(3) << endl ;    // output from position 3 to the end
cout << s4.substr(3, 2) << endl ; // output characters on positions 3 and 4

The compare() member function is used to lexicographically compare strings. Optional arguments can specify different starting positions for comparison. The function returns a negative value if the receiver is less than the argument, zero if they are equal, and positive otherwise. More often used operations of comparison <, <=, ==, !=, >=, and >, which can also be used for comparison with null-terminated strings.

The find() member function determines the first inclusion of an argument in the current string. An optional integer argument specifies the starting position for the search. The function returns the found position or value outside the index. The rfind() function searches from the end in the reverse direction.

string s1 = "Mississippi";
cout << s1.find("ss") << endl;     // returns 2
cout << s1.find("ss", 3) << endl;  // returns 5
cout << s1.rfind("ss") << endl;    // returns 5
cout << s1.rfind("ss", 4) << endl; // returns 2

2.2.5 Sequence Adapters

The classes stack, queue and priority_queue are defined not as separate containers, but as adapters for the basic containers. Container adapters provide a limited interface to the container. In particular, they do not provide iterators. Standard containers are stored as data items in the adapter classes in the private section.

The stack adapter is defined in the <stack> header file. A stack is a dynamic data structure, consisting of a variable number of items. Adding new and deleting items is done from one end of the stack according to the principle of LIFO (Last In - First Out). A standard implementation involves storing items in a deque, but you can use any sequence by specifying it as the second template parameter. To work with the stack, you should use the functions top() (get the item from the top), push() (add item) and pop() (remove the item).

The queue class is defined in the <queue> header file. The push() member function adds an item to the end of the queue. The pop() member function removes an item from the beginning of the queue, The front() and back() functions receive items from the beginning and end of the queue. In both classes, the functions empty() and size() are implemented.

The following example demonstrates the creation of a queue of integers based on the list:

#include <iostream>
#include <queue>   
#include <list>

using std::cout;
using std::endl;
using std::list;
using std::queue;

int main()
{
    // Instead deque, you can use list:
    queue<int, list<int> > q;
    q.push(2);
    q.push(3);
    // You can get the value of the last item:
    cout << q.back() << endl;
    // Obtain items from the queue:
    while (q.size()) // or while (!q.empty())
    {
        cout << q.front() << endl;
        q.pop();
    }
    return 0;
}

To represent queues and lists, you cannot use vector because it does not implement the pop_front() function.

The Standard C++ Library defines a sequence adapter called Priority queue (priority_queue class). Each item of such a queue is assigned a priority that determines the order in which the items are obtained from the queue. The priority_queue declaration is allocated in the <queue> header file. In the default case, the items are compared using the < operator, so the top() function returns the largest item.

The size() function returns the number of items in the queue. The empty() function with a result value of type bool returns true if the queue is empty. The pop() function removes the item with the highest priority from the queue. Using a special constructor, you can initialize a priority queue by specifying two iterators from an existing sequence. Instead of using the operator < to organize the comparison, you can use a class containing the function bool operator()(), which takes two arguments (constant references to the type of the item of the queue).

Priority queues are often used to simulate the queue of events and their processing. To represent an event, you can use a structure or class with the overloaded operator <.

2.3 Associative Arrays and Sets

2.3.1 Associative Arrays

The associative array (map, sometimes called a dictionary) stores pairs of values. Having one of the values (key), you can access the other (value). An associative array can be treated as an array, in which the index is not necessarily an integer.

To implement such an array in the Standard Library, there are two classes: map and multimap. They differ in that the map keys must be unique, and the multimap keys can be repeated. To work with map and multimap, you need to include the <map> header file.

The map class is a template whose two parameters are the type of the key and the type of the value. To create an array item, you only need to assign an element a new value, and the index is the key. If the key is not found, then the "key" - "default value for value type" is placed in the array. For example, if the key is a string and the value is an integer, you can create such a variable:

map<string, int> m;

A new item is included by assigning:

m["string1"] = 7;

You can read the value in the same way:

int i = m["string1"];

This operation always gives some correct result. It returns either the value entered (if the key was found), or the default value for the value type.

The map object contains objects of the pair structure, which consists of two items: first and second. Using the insert function and the make_pair function defined in the Standard Library, you can insert a new pair into an associative array without using the [] operator:

m.insert(make_pair(string("string1"),8));

Using the count() function, you can determine how many times how many times an associative array includes a pair with a given key (in the case of using map container, count() returns 0 or 1).

if (m.count("string1") != 0) // the item with this key is present in the array

The find() member function allows you to retrieve a value for a given key. It returns an iterator pointing to the found element (a pair object), if it is present, or result of end() function if the item with the given key is not found. Inserting new items is not carried out (in contrast to the [] operation).

map<string, int>::iterator mi;
if ((mi = m.find("key1")) != m.end())
{
    cout << "value=" << mi->second << endl;
}

All items of an associative array can be bypassed using an iterator:

map<string, int>::iterator mi;
for (mi = m.begin(); mi != m.end(); mi++)
{
    cout << "key=" << mi->first << " value=" << mi->second << endl; 
}

Items are stored in an associative array in ascending order of the key. The < operation is usually used. Instead of using the < comparison, you can create the class that contains the function bool operator()(), which takes two arguments of type constant reference to the type of the key.

The erase() member function allows you to delete the specified items. There are three options for deleting:

m.erase(4);            // By the value of the key
m.erase(iter);	     // Using iterator
m.erase(iter1, iter2); // Using a pair of iterators

Unlike the map class, the value of the key can be repeated in objects of the multimap class. Therefore, the indexing operation [] does not make sense, and it is not defined for multimap. To receive all items with a certain key, the member functions equal_range(), lower_bound() and upper_bound() are used. The first of these functions takes the value of the key and returns a pair of two iterators, the first of which points to the first item with the given key, and the second points after the last item. These iterators can be obtained separately using the functions lower_bound() and upper_bound()::

multimap<string, int> mm;
typedef multimap<string, int>::iterator MmIter;
pair<MmIter, MmIter> p = mm.equal_range("abc");
for (MmIter mmi = p.first; mmi != p.second; mmi++)
    // Bypass items with the same key

for (MmIter mmi = mm.lower_bound("abc"); mmi != mm.upper_bound("abc"); mmi++)
    // The same

Pairs are inserted using the insert() member function. Checking the elements with the given keys is done using the count() function, which can return a value greater than one.

2.3.2 Sets

A set can be considered as a variant of an associative array, in which only the keys are present. The items of the set are automatically sorted. For sets, the indexing operation is not implemented. The most common operations with sets are insert(), erase(), find(), and count().

An ordinary set (the set type) can contain only unique items. A special type multiset allows the repetition of items of a set. To work with both sets, you must include the <set> header file. When defining variables of the type of set, you need to specify only one type: the type of the item of the set. For example:

set<string> words;

Adding elements is done using the insert() member function:

words.insert("word1");

The definition of the number of occurrences of an item and the search for an item are similar to map. Determining the number of occurrences:

if (words.count("word1") != 0) 
{
    // this item presents in the set
}

The search:

set<string>::iterator si;
if ((si = words.find("word1")) != words.end()) 
{
    // this item presents in the set
    cout << "item=" << *si << endl;
}

The items of the set are traversed by using iterators:

// output set
for (si = words.begin(); si != words.end(); si++)
{
    cout << *si << " ";
}

2.4 Algorithms of the Standard Library

2.4.1 Overview of Algorithms

Algorithms are template functions (sets of template functions) that operate on sequences through their iterators. Most algorithms are defined in the <algorithm> header file. Several numerical algorithms are defined in the <numeric> header file.

All algorithms are separated from the details of the implementation of data structures and use iterators as parameters. Therefore, they can work with user-defined data structures if these data structures provide iterator types that satisfy the standard requirements. Template algorithms of the Standard Library work not only with Library data structures, but also with C++ arrays.

It should be remembered that the result of applying algorithms to unacceptable ranges is not defined. There are no mechanisms for checking the correctness of the range at runtime. The programmer is responsible for the correctness of the range.

There are several groups of algorithms:

Groups of Algorithms	Examples
algorithms that do not modify the sequence	`for_each()`, `find()`, `find_if()`, `count()`
algorithms for modifying the sequence	`transform()`, `copy()`, `replace()`, `fill()`, `swap()`, `random_shuffle()`
sorting algorithms	`sort()`, `partial_sort()`, `stable_sort()`
algorithms for working with sets	`includes()`, `set_union()`, `set_intersection()`
algorithms for finding maxima and minima	`min()`, `max()`, `min_element()`, `max_element()`
permutation algorithms	`next_permutation()`, `prev_permutation()`

2.4.2 Use of for_each

Consideration of general features of algorithms and the use of helper objects can be done using a simple algorithm that does not change the sequence: the for_each() algorithm. This algorithm specifies the operations with each element of the sequence.

The algorithm for_each(InputIterator first, InputIterator last, Function f) applies f to the result of dereferencing each iterator in the range [first, last). If f returns some result, the result is ignored.

In most cases, it is advisable to use other algorithms instead of for_each(). However, as an example, you can display the values of integers using the for_each() algorithm:

#include <iostream>
#include <algorithm>
#include <vector>

using std::cout;
using std::endl;
using std::vector;
using std::for_each;

void writeInt(const int& i)
{
    cout << i << endl;
}

int main()
{
    vector<int> a = { 1, 2, 3, 4 };
    . . .
    // vector output:
    for_each(a.begin(), a.end(), writeInt);
    return 0;
}

If you want to use the for_each() function to perform certain actions on an array, you should use the pointer to the array and to the non-existing item after the array instead of the iterator. For example:

#include <iostream>
#include <algorithm>

using std::cout;
using std::endl;
using std::for_each;

void writeInt(const int& i)
{
    cout << i << endl;
}

int main()
{
    const int n = 6;
    int a[] = { 1, 2, 4, 8, 16, 32};
    // array output:
    for_each(a, a + n, writeInt);
    return 0;
}

2.4.3 Examples of use transform

The transform() algorithm takes two sequences: the source sequence(defined by two iterators) and the resulting (defined by one iterator), performs an action on the elements of the first sequence, defined by the function (last parameter) and fills the second sequence. In some cases, this function may be standard. In the following example, for each of the strings stored in the array, you can get the length and write it to the array of integers:

#include <cstring>
#include <algorithm>

using std::transform;
using std::strlen;

void main()
{
    const char* words[] = { "first", "second", "third" };
    int sizes[3];
    transform(words, words + 3, sizes, strlen); // 5, 6, 5
    // ... use an array 
}

If you create an array of strings of type std::string instead of an array of pointers to a character, you will have to create a separate function for the transform() algorithm, because you cannot use the length() member function as an argument:

#include <string>
#include <algorithm>

using std::transform;
using std::string;

int len(string s)
{
    return s.length();
}

void main()
{
    string words[] = { "first", "second", "third" };
    int sizes[3];
    transform(words, words + 3, sizes, len); // 5, 6, 5
    // ... use an array
}

Working with vectors involves using iterators instead of pointers. You can pre-create an empty vector of the required length, but you can also use the back_inserter() function, which in turn returns a special iterator object of type back_insert_iterator, whose job is to add elements to the end of the container using the push_back() function. The previous example can be implemented using vectors:

#include <vector>
#include <string>
#include <algorithm>

using std::transform;
using std::string;
using std::vector;
using std::back_inserter;

int len(string s)
{
    return s.length();
}

int main()
{
    vector<string> words = { "first", "second", "third" };
    vector<int> sizes;
    transform(words.begin(), words.end(), back_inserter(sizes), len); // 5, 6, 5
    // ... use a vector
    return 0;
}

There is an alternative form of the transform() algorithm for working with two source sequences. This algorithm will be discussed later.

2.4.4 Sorting Sequences

Using the sort() algorithm, you can sort random access containers. The quick sort algorithm is used. For example, you can organize the sorting of a vector of integers in ascending order of values:

vector<int> v;
v.push_back(3);
v.push_back(4);
v.push_back(1);
sort(v.begin(), v.end()); // 1, 3, 4

You can also use the sort() function to sort arrays. As for other algorithms, instead of iterators, a pointer (array name) is used:

const int n = 3;
int a[n] = { 3, 4, 1 };
sort(a, a + n); // 1, 3, 4

In the case of more complex types for which the "greater" and "less" relations are not defined, the sort() function must be called with three parameters. The third parameter, the predicate function, is a function that returns a bool result. The corresponding function for the sort() algorithm must take two parameters of the sequence element type and return true if the elements do not need to be swapped, or false otherwise. You can also change the sort criteria. In this way, you can sort the vector of integers in descending order:

#include <algorithm>
#include <vector>

using std::vector;
using std::sort;

bool decrease(int m, int n)
{
    return m > n;
}

int main()
{
    vector<int> v = { 1, 11, 7, 4, 8 };
    sort(v.begin(), v.end(), decrease);
    // ... use of sorted vector
    return 0;
}

Note: the sort() function does not allow sorting lists (std::list), because the corresponding class does not provide the necessary iterators.

2.5 Function Objects. Predicate Functions. Function Adaptors

The criteria on the basis of which most algorithms work are calculated by applying the operation of calling a function to an object passed to this algorithm as a parameter. This parameter can be a pointer to a function or a function object. The main disadvantage of using the function pointer directly when working with algorithms is the impossibility of increasing the number of function parameters.

A function object (functor) is an instance of a class in which the "parentheses" (function call) operator is overloaded. Access to this operator is carried out whenever the function object is used as a function. A class describing the type of function object can have data members and a constructor in which these data members are initialized with the necessary values. These values are used in a function that overloads the operation "parentheses". In the example below, the function object stores a reference to the output stream:

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <functional>

using std::vector;
using std::ostream;
using std::ofstream;
using std::for_each;
using std::endl;

class WriteInteger
{
    ostream& out;
public:
    WriteInteger(ostream& strm) : out(strm) { }
    void operator () (const int& i) { out << i << endl; }
};

void main()
{
    vector<int> a({ 1, 2, 3, 4 }); // initialization by a list of values is available in C++11
    // output vector:
    ofstream out("result.txt");
    for_each(a.begin(), a.end(), WriteInteger(out));
}

A predicate is a function (or a function object) that returns a value of type bool. A number of predicates, corresponding relation operations and logical operations, are implemented in the Standard Library. To use them, you must include the <functional> header file. These predicates include the unary predicate logical_not (realizing !) and binary predicates:

equal_to (==)
not_equal_to (!=)
greater (>)
less (<)
greater_equal (>=)
less_equal (<=)
logical_and (&&)
logical_or (||).

Each such predicate is a template that takes as the parameter the type of the value for which the operation is performed. The following example uses the logical_not() predicate in the transform() algorithm. This algorithm takes two sequences: the input sequence (defined by two iterators) and the result (defined by one iterator):

vector<int> a = { 0, 1, 0, 2, 0, 3 };
vector<int> b(6); // result sequence
transform(a.begin(), a.end(), b.begin(), logical_not<int>());
// b: 1 0 1 0 1 0

The <functional> header file of the Standard Library defines arithmetic functions available as function objects. You can use the following operations:

plus (x + y)
minus (x - y)
multiplies (x * y)
divides (x / y)
modulus (x % y)
negate (-x).

Using arithmetic functional objects, you can perform the specified actions on all items of one or two sequences. For example, you can use another version of the transform() algorithm. This variant of the algorithm takes two input sequences defined by three iterators, and the resulting sequence (defined by one iterator):

int main()
{
    vector<int> a = { 0, 1, 2, 3, 4, 5 };
    vector<int> b = { 5, 4, 3, 2, 1, 0 };
    vector<int> c;
    transform(a.begin(), a.end(), b.begin(), back_inserter(c), plus<int>());
    // The WriteInteger was implemented before:
    for_each(c.begin(), c.end(), WriteInteger(cout)); // 5 5 5 5 5 5
    return 0;
}

The back_inserter() function adds items to the end of the container, increasing it to the required size.

Function adaptors are available through the <functional> header file.

A binder allows you to use a function object with two arguments as a function with one argument by binding one argument to a value. The bind1st() and bind2nd() functions get binary function (function object) f and x value as arguments and return the binder1st and binder2nd classes respectively. A function object must be a class derived from the binary_function class. The binder1st class binds the value to the first argument of the binary function, and binder2nd does the same for the second argument.

For example, to find the first vector item less than 10, you can use

find_if(vi.begin(), vi.end(), bind2nd(less<int>(), 10));

The member function adaptor allows you to use the member function pointer as the algorithm argument. To do this, template functions mem_fun, and mem_fun_ref are used. The first function is used to call member functions through a pointer to an object. The second function is used to refer to a method by reference to an object.

For example, if the vector contains pointers to geometric shapes (the Shape class that contains the draw() function), you can draw all the shapes using for_each():

for_each(vs.begin(), vs.end(), mem_fun(&Shape::draw));

The previous example of filling a vector with sizes of strings can be implemented without creating your own function:

vector<string> words = { "first", "second", "third" };
vector<int> sizes;
transform(words.begin(), words.end(), back_inserter(sizes), mem_fun(&string::length));

The negator allows us to express the opposite predicate. Functional adaptors not1 and not2 are used to invert the meaning of a unary and binary function object, respectively. In the following example algorithm sort() defined by the indication "not less than" as the condition that the sequence is sorted. Such a sequence will be sorted in descending order:

sort(a.begin(), a.end(), not2(less<int>()));

3 Sample Programs

3.1 The Use of Vectors

The following program creates vector of vectors of integers whose values are displayed:

#include <iostream>
#include <vector>

using std::cout;
using std::vector;

void main()
{
    vector<vector<int> > a = { vector<int>({ 1, 2 }), vector<int>({ 3, 4 }) };
    for (auto &row : a)
    {
        for (auto &x : row)
        {
            cout << x << "\t";
        }
        cout << "\n";
    }
}

3.2 Work with Priority Queue

Suppose there is a class for representation of the country:

#include <iostream>
#include <queue> 
#include <string>

using std::string;

class Country
{
private:
    string name;
    double area;
    long   population;
public:
    Country() : name(""), area(1), population(0) { }
    Country(string n, double s, long p) : name(n), area(s), population(p) { }
    string getName()       const { return name; }
    double getArea()       const { return area; }
    long   getPopulation() const { return population; }
    void   setName(string name)  { this->name = name; }
    void   setArea(double area)  { this->area = area; }
    void   setPopulation(long population) { this->population = population; }
    double density() const { return population / area; }
};

Now we can create priority queue, which will contain objects of Country type. Countries with greater population density will be obtained first. In order to allocate items of Country type in the priority queue, it is necessary for overload < operation. This operator can be overloaded by external function. This function may not even be a friend of the Country class:

bool operator<(const Country& c1, const Country& c2)
{
    return c1.density() < c2.density();
}

Now objects can be placed into a priority queue:

using std::priority_queue;
using std::cout;
using std::endl;

int main()
{
    Country c0("Ukraine", 603700, 42539000);
    Country c1("France", 544000, 57804000);
    Country c2("Sweden", 450000, 8745000);
    Country c3("Germany", 357000, 81338000);
    priority_queue<Country> cq;
    cq.push(c0);
    cq.push(c1);
    cq.push(c2);
    cq.push(c3);
    while (cq.size())
    {
        cout << cq.top().getName() << endl;
        cq.pop();
    }
    return 0;
}

An alternative to the use of overloaded operator is the use of functional object: the object of class has overloads operator (). The name of this class should be specified as the third parameter of the priority_queue constructor:

class Less
{
public:
    bool operator()(const Country& c1, const Country& c2) const
    {
        return c1.density() < c2.density();
    }
};

int main()
{
    . . .
    priority_queue<Country, std::vector<Country>, Less> cq;
    . . .	
}

3.3 Working with Map

Suppose we want to read integer values from the file "values.txt", count the number of each of the values and display the values and counts of repetitions.

#include <iostream>
#include <fstream>
#include <map>

using std::map;
using std::ifstream;
using std::cout;
using std::endl;

int main()
{
    map<int, int> m;
    int i;
    {
        ifstream in("values.txt");
        while (in >> i)
        {
            m[i]++;
        }
    }
    map<int, int>::iterator mi;
    for (mi = m.begin(); mi != m.end(); mi++)
    {
        cout << mi->first << " " << mi->second << endl;
    }
    return 0;
}

As the development of this example is to offer the use of a functional object that specifies the reverse sort logic.

4 Exercises

Present data about users in an associative array (username / password) with the assumption that all usernames are different. Display user information with a password length of more than 6 characters.
Enter information about the students of the group into the multimap container. The key is the surname, the group can have namesakes. Give a message if the group has namesake. Provide data about the students of the group by alphabet of names.
Develop a program in which a sequence is entered, and a new sequence is formed from the squares of the original values. Use the transform() algorithm and standard arithmetic functional objects.

5 Quiz

What are the main elements of the Standard C++ Library?
What is a Standard Library container?
What is the difference between sequential and associative containers?
What is iterator?
What are the requirements for the iterators of the Standard Library?
What are the advantages vectors compared with arrays?
How to create a vector object?
How to work with individual items of vectors?
What is the difference between the list and the array?
How the character strings are represented in the Standard Library?
What is a sequence adapter?
What is the difference between a queue and a stack?
What is associative array?
What is the difference between map and multimap?
Where are associative arrays used?
What sets are different from other containers?
What are the standard classes for representing a set?
What is the Standard Library algorithm?
What are groups of algorithms?
How does the algorithm relate to the type of container to which it is applied?
What is function object?
What is predicate function? What are the standard predicate functions?
What are function adaptors?

Previous Next

Programming Basics (Part 2)

Developed by Leo V. Ivanov

Laboratory Training 5 – Use of the Standard Template Library