padraic.xyz

Standard Library and Templates

Templates

Templates allow functions and classes that can act on or define generic types (respectively). This allows for parametric polymorphism, also called generic programming. The tempalte pattern is required in any strongly-typed language that does not use duck-typing.

Perhaps the most common example is std::vector<int> , where vector is a template and we have told it to act with the type int .

Templates are compiled, making them stronger than C++ macros. At the same time, it requires a lot of thought to abstract the algorithm away from the type. These tricks are called Template Meta-Programming.

Below is an example of a template definition: :::C template // keyword class, then the placeholder name T sum (T a, T b) { T result; result = a+b; return result; }

In the above example, T is a placeholder for the class the template acts on; it returns a variable of type T , and takes two instances of type T as input.

To use it, we might then call it as sum<int>(i,j) . At compile time, the compiler will check that the class specified implements the operations called in the template. It won't check that they make sense, however: e.g if your + operator is overloaded to subtract the two elements, C++ won't catch that.

The templated function should be thought of as not 'existing' until compile time, at which time the programme will create a version of the function acting on the requisite types. In the above example, if i and j are both ints, then the type definition could be left implicit. You should be aware of this as obviously the type passed to the template will alter its function.

Caution: The template functions not being compiled unless instantiated is a caveat that can create significant problems when compiling a templated library. Unless the template is used, all you have done is verify the template is synatically valid C++. This makes unit testing templates REALLY important.

Instantiation and Use of Templates

Templates can be distributed as either a simple header file, or in a header file with explicit instantiation. The latter is more complicated. Namely, there will be a separate header file including the template prototype, and a .cpp file that includes the header file, defines the template and often specifies certain instantiated types for compile time or platform advantages. To use these libraries, you must include the header and link against the implementation.

If there is no explicit instantiation, we are then distributed simply a header file which includes the template definition.

Class Templates

These function similarly to function templates, and allow us to define classes derived from different base classes and reuse code.

Template Specialisation

This is distinct from explicit instantiation, where we define some special cases of our tempalte. This can be full specialisation, where we refer to a single type, or partial, where we refer to a different templated type. This is how parametric polymorphism works.

We can initialize variables in templates (with a default variable) as a form of template specialisation, e.g. specifying templates for 2 or 3D vectors.

Typedef

This is a shorthand for some elements of the template syntax. This is used to alias template variables or classnames in other templates. It allows us to condense the syntax down by using shorthands.

Error Handling

In C, error handling is done using error codes in return values. The programme then has to have large control structures to manage these exceptions. In C++, however, error handling works a lot more like we are used to from python: we throw an exception object.

The exception travels back up the 'call stack' of functions until it is either caught in a try/catch block, or until it reaches main at which point the programme exits with the error. The exception can also contain information about what caused the exception, and this information can be e.g. logged to debug or used for error handling.

Side Effects

This is a jargon term to describe an aspect of programme function we need to keep in mind whenever we move between levels in the call stack (e.g. by throwing exceptions). Consider for example a function that modifies a pair of variables, checking each one to see if they're valid. Your class should not be between valid states when an exception is thrown.

STL

The standard templating library is a way to avoid reinventing the wheel and can save huge amounts of time while still allowing you the promise of well optimised code. For example, consider the example of sorting two sets of numbers. We don't know how many numbers there are, so we need to code a way to determine this and allocate memory accordingly. We then need to code a comparison function by hand to call quick-sort with. By comparison, the STL enables us to use dynamic sequences called vectors, etc.

The standard library provides a large number of well optimsied templates and containers that allow us to write fast code more quickly.

STL Sequences

These allow for collections of data that can be fixed size (much like we would allocate arrays), or dynamic, as in vectors and lists. They can also be either contiguous or non-contiguous in memory. Non-contiguous requries we store additional information, links between memory locations, where as contiguous has sequently elements but is slower to extend because it involves moving data around or even reallocating elements.

There are 5 common types, which are summarised below.

| Name | size | access | memory | efficient insert/remove | | ------ |:----:|:------:|:------:|:-----------------------:| | array |fixed | random |contiguous| - | | vector |dynamic|random |contiguous| at end only | | deque |dynamic|random |non-contiguous| both ends | | list|dynamic|sequential|non-contiguous| anywhere | |forward_list|dynamic|sequential, only forward|non-contiguous| anywhere |

Note: In C++11, we have access to the emplace method, which is preferable to insert as it does not create a copy of the element you add to the container. This is not available on older compilers though.

Associative Containers are a seperate class of sequence; they can be 'key-value' pairs (maps) or just keys (sets). By default these types are unique for keys but there also exists multimap and multiset. They can also be ordered or unordered; ordered containers are faster to iterate over, and unordered elements are faster to modify.

Unique maps allow us to access elements using the square-bracket notation, similar to dictionaries in Python. This method is NOT implemented for multimap elements because it would be abiquous which element we are referring to. Similarly, we can use this notation to add to maps but must call the inset method for multimap. Finding given elements in a multimap is harder, but can be achieved using an iterator method called equal_range.

| | ordered | unordered | |-------------|:-------:|:---------:| | unique | map | unordered_map| | non-unique| multimap |unordered_multimap|

| | ordered | unordered | |-------------|:-------:|:---------:| | unique | set | unordered_set| | non-unique| multiset |unordered_multiset|

Aside: Functors

These are classes which implement the operator (), and thus can behave like a function. For example, consider this example :::C class compMass { public: compMass() : m_particlesOrdered({"neutrino", "electron", "muon", "pion", "kaon", "proton"}) {}; bool operator() (const std::string& s1, const std::string& s2) const { int index1=-1, index2=-1; for (int i=0;i m_particlesOrdered; };

which could be used to sort particles based on their mass which is hard-coded in as the list m_particlesOrdered.

Pairs and Tuples

These are defined in a seperate header file, <utility>. Pairs can be defined using syntax format, or by using the function make_pair with the auto keyword. A tuple is like a pair, but with as many as n members allowed.

Iterators

This is a tempalated type that returns holds a pointer to an element in the container. We can do arithmetic with iterators, e.g. incrementing them to move through the container, which makes them a useful way to iterate over containers. More information is available in the

Extending STL Structures

Inhereting from STL datatypes is a bad idea as they are not meant to be polymorphic; for examople, they do not have virtual destructors and thus will begin to behave weirdly if extended. There are thus two ways for us to extend them 1. Composition: We define a class which contains a container as a private member 2. Funciton: We define a function that takes a reference to the container and the data, and does the desired implementation.

Other STL Types

There are a number of different things defined in the STL, and we will briefly review a few here

  1. Streams:

    These include iostream, fstream and sstream, which are used for std I/O, file I/O and string manipulation respectively

  2. Function Objects: Unlike the functor example given above, we can instead use std::function to define functions and function pointers, functors and lambdas. All three are shown in the example below.

  3. Algorithms: These define a collection of functions that are highly optimised and designed to act on collections of elements.

    :::C

    include // std::function, std::negate

    // a function: int half(int x) {return x/2;} // a function object class: struct third_t { int operator()(int x) {return x/3;} }; // a class with data members: struct MyValue { int value; int fifth() {return value/5;} }; int main () { std::function fn1 = half; // function std::function fn2 = ½ // function pointer std::function fn3 = third_t(); // function object std::function fn4 = {return x/4;}; // lambda expression std::function fn5 = std::negate(); // standard function object
    std::cout << "fn1(60): " << fn1(60) << '\n'; std::cout << "fn2(60): " << fn2(60) << '\n'; std::cout << "fn3(60): " << fn3(60) << '\n'; std::cout << "fn4(60): " << fn4(60) << '\n'; std::cout << "fn5(60): " << fn5(60) << '\n'; // stuff with members: std::function value = &MyValue::value; // pointer to data member std::function fifth = &MyValue::fifth; // pointer to member function MyValue sixty {60}; std::cout << "value(sixty): " << value(sixty) << '\n'; std::cout << "fifth(sixty): " << fifth(sixty) << '\n' }