Iterator for templated list

C++ Standard Template Library Part II - Iterators

Now that we've discussed STL Containers, it is time to turn our attention to iterators. Iterators are objects that can navigate or iterate over elements in a container. They are essentially a generalisation of pointers and provide similar, but more advanced, behaviour. Their main benefit is that they allow the decoupling of the implementation of a container with an algorithm that can iterate over it.

Iterators are often tricky for beginning C++ programmers to get to grips with as there are many different categories and adaptors that can be applied to modify their behaviour. In this article I want to describe the taxonomy that exists to help you choose the correct iterator type for your quantitative finance algorithm implementations.

Iterator Categories

Iterators are grouped according to their category. There are five separate iterators categories in C++: Input, Output, Forward, Bidirectional and Random Access:

Input - An input iterator is a single-pass read-only iterator. In order to traverse elements, the ++ increment operator is used. However, elements can only be read once. Input iterators do not support the -- decrement operator, which is why they are termed single-pass. Crucially, an input iterator is unable to modify elements. To access an element, the * pointer dereference operator is utilised.
Output - An output iterator is very similar to an input iterator with the major exception that the iterator writes values instead of reading them. As with input iterators, writes can only occur once and there is no means of stepping backwards. Also, it is only possible to assign a value once to any individual element.
Forward - A forward iterator is a combination of an input and output iterator. As before the increment operator ( ++ ) allows forward stepping, but there is no decrement operator support. To read or write to an element the pointer derefernce operator ( * ) must be used. However, unlike the previous two iterator categories, an element can be read or written to multiple times.
Bidirectional - A bidirectional iterator is similar to a forward iterator except that it supports backward stepping via the decrement operator ( -- ).
Random Access - A random access iterator is the most versatile iterator category and is very much like a traditional C-style pointer. It possesses all the abilities of a bidirectional iterator, with the addition of being able to access any index via the [] subscript operator. Random access iterators also support pointer arithmetic so integer stepping is allowed.

Iterators are divided into these categories mainly for performance reasons. Certain iterators are not supported with certain containers when C++ deems it likely that iteration will lead to poor performance. For instance, random access iteration is not supported on the std::list as access to a random element would potentially require traversal of the entire linked-list used to store the data. This is in contrast to a std::vector where pointer arithmetic can be used to step directly to the desired item.

Iterator Adaptors

Iterator adaptors allow iterators to be modified to allow special functionality. In particular, iterators can be reversed, they can be modified to insert rather than overwrite and can be adapted to work with streams.

Reverse Iterators

Reverse iterator adaptors essentially "swap" the increment ( ++ ) and decrement ( -- ) operators so that any algorithms making use of these iterators will be carried out in reverse. Every STL container allows reverse iteration. It is possible to convert standard iterators to reverse iterators, although any converted iterator must support both increment and decrement (i.e. it must be bidirectional).

Insertion Iterators

Insertion iterators adapt normal output iterators to perform insertion instead of overwriting. They only allow writing, as with normal output iterators. There are three separate insertion iterators in the STL: back, front and general. They all behave differently with regards to the position of the inserted element:

Back inserters utilise the push_back method of the container it is acting upon and so will append values at the end. Hence they only work on a subset of containers that support the method (strings, lists, deques and vectors).
Front inserters utilise the push_front method of the container and is only available for two containers in the STL - the deque and the list.
General inserters utilise the insert method of the container being acted upon, which is supported by all STL containers.

Stream Iterators

Stream iterators are adapted iterators that permit reading and writing to and from input and output streams. istream iterators are used to read elements from an input stream, making use of the >> operator. ostream iterators are the writing counterpart and can write to an output stream via the

Const Iterators

Containers allow both iterator and const_iterator types. const_iterators are returned by certain container methods (such as begin or end ) when the container itself is const .

One must be careful to distinguish between const_iterator and const iterator (notice the lack of underscore!). The former is a non-const object with iterator type, so that it returns objects which cannot be modified. The latter is a constant iterator (i.e. it cannot be incremented!). It is possible to convert an iterator to a const_iterator , but going the other way is not possible.

const_iterators are preferred (if possible) because they aid readability. They let programmers know that the iterator is only iterating over the container and not modifying it.

Iterator Traits

A common requirement is to be able to use pointers in place of iterators when carrying out an algorithm. Since they have nearly identical behaviour, it makes sense to allow this. The way this is achieved is through iterator traits. The iterators_traits class template provided by the STL is designed to allow a common interface for any type of iterator.

When creating algorithms that iterate over a container it is possible to make use of the iterator traits to obtain the underlying type being referred to by the presented iterator (or pointer), without the need to know whether an iterator or pointer is actually being presented. This makes the code more maintainable and versatile.

In the next article we will discuss STL Algorithms in detail and show how iterators can bridge the gap between the containers and the algorithms that operate upon them.

If you haven't done so already, please take a look at the previous article on STL Containers.

QSAlpha

Join the QSAlpha research platform that helps fill your strategy research pipeline, diversifies your portfolio and improves your risk-adjusted returns for increased profitability.

The Quantcademy

Join the Quantcademy membership portal that caters to the rapidly-growing retail quant trader community and learn how to increase your strategy profitability.

Successful Algorithmic Trading

How to find new trading strategy ideas and objectively assess them for your portfolio using a Python-based backtesting engine.

Advanced Algorithmic Trading

How to implement advanced trading strategies using time series analysis, machine learning and Bayesian statistics with R and Python.