Lab 3 - templates, C++ standard library containers, iterators

Function templates

Function templates allow reuse of a function for several different types of data. Let's look at an example that returns the smaller of two given elements.

template <typename T>
T getMin (T a, T b) {
      return ((a < b) ? a : b );
}

In this example, a function is defined that finds the smaller of the two given values. The only requirement for the data type is to have operator < defined for it. If, for example, for Line2 (known from our homework) such a comparison were defined (for example, by length), the function getMin could be given two straight lines as arguments and a shorter one would be returned. The function would then be called as follows:

Line2 l1, l2;
Line2 theShorterOne = getMin <Line2> (l1, l2);

Note that the template parameter is not limited to data types. Functions and classes can be initialized with other values. For example, we can write a function that multiplies the inputs by predefined integers.

template <int multiplier>
int doMultiplication (int a) {
      return (a * multiplier);
}
int a = 6;
int b = doMultiplication<7> (a); // b väärtuseks saab 42

The example above is given to show the intuitiveness of templates. In reality it is suggested to use templates to create abstractions and to avoid code duplication. Remember that in templates you can mix the use of values and data types.

NB! Note that when using templates, implementations are written in the headers! The compiler generates specific implementations based on a predefined template at compile time. If it turns out that a template is parameterized with a data type that does not meet the requirements of the class, for example, we try to use a function getMin on a data type that does not have a comparison operation, the compiler returns an error message. Also, please note that headers do not need to be compiled! Finally, if all the code can be placed in the headers (possible sometimes in the case of templates), you don't have to create a library file.

Read more about templates: http://www.cplusplus.com/doc/tutorial/functions2/

Class templates

Class templates allow you to customize the class code to handle different types of objects. We illustrate this with two examples from the standard C ++ library. The container class vector stores a variable number of data of a given type. The class stack implements the stack data structure.

std::vector<std::string> laused;     // define a vector of strings
std::string la = "Aias sadas saia.“;
laused.push_back (la);               // store laat end of vector
std::string rida = laused[0];        // retrieve vector’s first element
std::stack<int> arvudepinu;          // define stack of ints
int a = 7;
arvudepinu.push(a);                  // push integer to stack
int b = arvudepinu.top ();           // compiler knows the type

The data type in parentheses determines which data type the instance of a given container works with. For example, you can't add string to an integer stack. The compiler learns the data type from the definition and uses it to generate e. g. an integer version of the class model. When working with such a container, no type conversions are required because the compiler knows which data type to use. The following is an example of a class model with a type parameter.

template <class T>          // T represents the class parameter
class Line {                // we define a line
public:
     T p1;                  // attribute of type T
     T p2;                  // another attribute of type T
     Line () = default;     // default constructor
     Line (T np1, T np2)    // a parametrized constructor
           : p1 (np1)
           , p2 (np2)
     {}
     float length () {      // calculating length

           return p1.distanceFrom (p2); // distanceFrom must exist in T
     }
};

This template sets the following requirements for a type used as type parameter: It must have a default constructor and a method distanceFrom that returns the distance between two Ts. The template could be used, for example, like this:

Line<Point2> l = Line<Point2>{p1, p2}; // a straight line in two - dimensional space.

Read about class templates: http://www.cplusplus.com/doc/tutorial/templates.html

Iterators in the C ++ standard library

An iterator in C++ is an object that refers to an object inside a container (containers are, for example, vector, map etc.). An iterator wraps a container and a position in that container. The iterator can be moved back and forth over the elements of the container, which provides additional possibilities for processing the elements in the container. The C++ 11 standard makes our lives easier by automatically deriving a type using the @@auto22 keyword. Using an iterator in a for loop would look like this:

vector<float> polynoomiKordajad;    // vektor of floats
polynoomiKordajad.push_back (1.7);  // add some floats
...                                 
polynoomiKordajad.push_back (-5.1); // push_back adds them to the end

for (float kordaja : polynoomiKordajad) {  // loop over container (C++11)
    ...                         // do something with the element
}

auto it = polynoomiKordajad.begin ();     // type of the iterator is auto
while (it != polynoomiKordajad.end ()) {  // while not at the end
    float kordaja = *it;   // read float at the current position
    ...                    // do soemthnin
    it++;                  // move on
}

Note that the asterisk is an operator of iterator. The iterator class defines an operation * that returns the object that the iterator is currently "on".

Containers usually have at least two methods - the method begin() returns an iterator that points to the first element in the container and end() that points to the end of the container. The iterator defines one or both motion operations, + and -. The command it += 7 advances the iterator by seven items. It should be noted that even when using iterators, nothing stops the programmer from going "over the edge" - the iterator can be moved beyond the container boundary.

Iterators are also used to determine ranges. Suppose we want to delete the first 5 elements from the multiplier vector. To do this, we can use a vector command erase whose parameter is the range specified by the iterators.

polynoomiKordajad.erase(polynoomiKordajad.begin(), polynoomiKordajad.begin()+5);

Such possibility to work with ranges makes using containers rather comfortable. For example if we want to get a part of vector we do not have to copy elements one by one. It suffices to define a range:

vector<float> esimesedViis;
esimesedViis.assign (polynoomiKordajad.begin(), polynoomiKordajad.begin()+5);

Different containers offer different options. Some containers are iterative in both directions (vector), some are not (list). All this must be taken into account when writing programs.

You can read more about containers here: http://en.cppreference.com/w/cpp/container

Algorithms in C++ Standard Library

The C++ Standard Library contains many algorithms, which simplify the work with containers. Algorithms are not bound to specific containers (they are not methods of classes), but are based on iterators. Algorithms are defined in the header <algorithm> and are in namespace std. A good overview of the algorithms and examples of using them can be found on the site: http://en.cppreference.com/w/cpp/algorithm

Function objects (functors)

Before looking at specific algorithms it is useful to know about another C++ structure. Classes, which have defined operator () with some set of parameters are function objects. Function objects are used to adjust algorithms to specific needs. Example of one function object, which can be used to split integers to even and odd:

class OddEvenPredicate { // define a class, which divides integers
   public: bool operator() (int i) { // into odd and even integers
      if ((i % 2) == 0) return true; // ahead when odd number
      else return false;
   }
};

If during solving a task you do not need a function object to have a state, it can often be replaced with a normal function. Function objects gives us more possibilities; e.g. you can not save state over several function calls. The last property might be required to use several Standard Library algorithms (such as for_each).

Example of algorithms in use: sorting and partitioning

Sorting is a frequently needed operation. C++ offers us several algorithms to do that. The most common algorithms that are used are sort and stable_sort. The difference is that if the objects are equal then with stable_sort the order between them will be kept. E.g.:

vector<int> numbervector {32,71,12,45,26,80,53}; // define vector with numbers

If we want to sort that vector then we can do the following:

sort(numbervector.begin(), numbervector.end()); // result: 12,26,32,45,53,71,80

The algorithm’s third (optional) parameter is a function object (or function), which can compare the objects which are to be sorted.

Let’s try to use the function object OddEvenPredicate. We want to partiation the vector so that even numbers are before odd numbers:

partition(numbervector.begin(), numbervector.end(), OddEvenPredicate ()); // result: 12,26,32,80,45,53,71

Example of using λ expressions (C++11)

C++11 also enables us to use anonymous functions. With that is possible to avoid creating separate function objects for algorithms. E.g.:

partition(numbervector.begin(), numbervector.end(),[](int x) {return (x % 2 == 0); } ); // result: 12,26,32,80,45,53,71

Example of using exceptions in C++

The reason to use exceptions is to let user know that something is wrong/broken. For example when using a library we could put a creation of an object and using in a try block . C++ exceptions system is somewhat more difficult than Java’s counterpart. In this material we provide only one example, what you could use in your homework to display errors in a constructor. First throwing an exception:

Klass::Klass(int n) {
if (n <1) {
throw string ("Parameter n was negative!");
}
...
}

And now catching:

int n = -1;
try {
Klass k (n);
} catch (string& str) {
cout << "Creation of class was unsuccessful. Error message was: " <<
str << endl;
}

Constructor note – () vs {}

If type has a separate constructor with member initializer list, then creating objects with a braces and parentheses can have different results. E.g.

vector<int> x (5); // result {0, 0, 0, 0, 0}
vector<int> y {5}; // result {5}

Read more about vector at: http://en.cppreference.com/w/cpp/container/vector

Note on looping over a container

We have defined:

for (float coefficent: polynomCoefficents) { // does nothing
 coefficent += 5;
}

The change of coefficient does not change the values of objects inside the container, because a copy of coefficient is made. If we want to change the values of container objects we can do:

for (float &coefficent : polynomCoefficents) { // change values of objs
 coefficent += 5;
}

Symbol ‘&’ here means reference to the variable, so no copy is made but points to original variable. More about it in the 4th lab.

Using random numbers (C++11)

#include <random>
ˇ
#include <iostream>
int main()
{
   std::mt19937 gen; // Create a RNG
   std::random_device rd; // to create non-deterministic RNG
   gen.seed(rd()); // if we initialize generator with same seed, then we
   // always get the same list of random numbers. To test comment out this line
   std::uniform_int_distribution<short> dis{1, 5}; // Uniform distrib.[1,5]
   for (int n = 0; n < 10; ++n) {
      std::cout << dis(gen) << ' '; // create random number from [1, 5]
   }
   std::cout << std::endl;
}