Session 4 Summary

Code Examples for Session 04

A talk at ACCU has just been published on YouTube that summarizes the relevance of STL algorithms and explains the mental model behind them really well:

Everything in this talk agrees with the discussion of STL algorithms in our lab sessions, and the presentation is stellar.

There is a trap that lies right at the beginning of the path to STL algorithms, and this trap is called for_each.

In another talk, Marshall Clow gives an introduction and some hints on how to implement good STL algorithm abstractions:

Rule of Zero

We do not need to follow the Rule of Three in class template Measurements in assigment 3 because all resource management is encapsulated in the std::vector member.

As std::vector respects the Rule of Five which includes the Rule of Three, we can safely assume that its resources will be acquired and released automatically and correctly.

We will discuss the Rule of Zero and move assignment in an upcoming lab session.

Default Definitions

Every class has default/copy constructor, assignment operator and destructor defined unless they are explicitly marked as delete.

If no implementation is specified explicitly, default definitions are generated by the compiler. These are usually based on member-wise operations.

This example shows a minimal implementation of a class with default operations specified by the compiler.
Note that there is no default definition of comparison operators.

Iterator Concepts

Algorithms and containers are entirely decoupled concepts in the C++ Standard Template Library. That is: algorithms are agnostic of containers and are implemented against iterator ranges, not for specific container types.

You should follow this approach as strictly as possible in your own implementations.

As an example, the std::fill algorithm works for any range (first, last[ specified by any iterator implementation that satisfies the ForwardIterator concept:

val_t                      c_arr[NElem];
std::array<val_t, NElem>   stl_arr;
std::vector<val_t>         stl_vec(NElem);
std::list<val_t>           stl_lst(NElem);

std::fill(c_arr,           c_arr + NElem, 1.23);
std::fill(stl_arr.begin(), stl_arr.end(), 2.34);
std::fill(stl_vec.begin(), stl_vec.end(), 3.45);
std::fill(stl_lst.begin(), stl_lst.end(), 4.56);

Iterator Categories

Iterators are classified into categories as illustrated in this overview.

Don’t let the formal vocabulary confuse you, it is actually really simple:

When you write an algorithm that operates on iterators, you have to consider which methods of an iterator you actually require to call. The operations you can always rely on are those in the InputIterator category:

Operation Name Category
++it prefix increment InputIterator
(void)it++ postfix increment (with unused return value) InputIterator
*it dereference InputIterator
it->m member dereference InputIterator
it != it2 inequality comparison InputIterator

full reference

So if your code doesn’t use operations apart from these: great! Your code will work with just any iterator.

The next category is ForwardIterator. It includes all operations of the InputIterator category and also provides:

Operation Name Category
it++ postfix increment ForwardIterator
*it++ dereference ForwardIterator

full reference

… and so on. Note that it += n or it[n] are still missing. These are only defined in the most ‘powerful’ RandomAccessIterator category.

So instead of writing it += 2 in your algorithm, it is better to use ++(++it) as it this operation would work for any iterator.

Even better, use std::advance. It always resolves to the most effcient increment operation for any iterator.

Some examples:

The container std::list provides iterators in the BidirectionalIterator category:

std::list<int> lst;
// ... initialize lst with some values ...
auto it = lst.begin();
++it;                 // <- move forward
--it;                 // <- move backwards (bidirectional)
int v = i[0];         // <- fails! Random access (operator[]) is not supported by
                      //    bidirectional iterators
it += 10              // <- fails! Corresponds to random access
std::advance(it, 10); // <- works! Programmer requested "manual" advance of the
                      //    iterator. Corresponds to invoking ++it 10 times i.e.
                      //    O(k = 10) complexity

The container std::vector provides iterators in the RandomAccessIterator category:

std::vector<int> vec;
// ... initialize vec with some values ...
auto it = vec.begin();
int v   = it[10];      // <- works! Random access is provided
it     += 10;          // <- works! Corresponds to random access
std::advance(it, 10);  // <- works! Corresponds to it += 10 i.e. O(1) complexity

STL Algorithms

First, have a look a the complete overview of all algorithm interfaces defined in the STL. Every algorithm interface specifies the required cateogory of its iterator arguments.

For example:

  • std::min_element (reference) expects iterators in the ForwardIterator category
  • std::sort (reference) requires random access iterators.

How algorithms check iterator categories at compile time:

Yes, looks insane, but it’s actually not as complicated as it looks at first

// Iterator class provides public type `iterator_category`:
template <typename Something>
class MyIterator {
public:
   using iterator_category = std::forward_iterator_tag;
// ...
};

Assuming we have an algorithm algo that should provide different implementations depending on the category of the iterators passed as arguments.

The best practice approach is a technique called tag dispatching.
It works like this:


// Non-public implementation detail
//
namespace detail {
   template <typename Iter>
   Iter algo_impl(Iter first, Iter last, std::random_access_iterator_tag) {
      // Implementation for random access iterators
   }

   template <typename Iter>
   Iter algo_impl(Iter first, Iter last, std::forward_iterator_tag) {
      // Implementation for forward iterators
   }
}

template <typename Iter>
Iter algo(Iter first, Iter last) {
   return detail::algo_impl(
            first,
            last,
            // value of this parameter is irrelevant,
            // we only need it to select the matching
            // overloaded function definition:
            typename first::iterator_category());
} 

You could also exploit SFINAE to enable / disable variants of an algorithm, for example using std::enable_if:

template <typename FwdIter>
std::enable_if<
  // condition:
  std::is_same< std::iterator_traits<FwdIter>::iterator_category,
                std::forward_iterator_tag >,
  // return value if condition is met:
  FwdIter >::type
my_algorithm(FwdIter first, FwdIter last) {
  // ...
}

Further references:

Custom Iterators

Most custom containers require custom iterators that comply to the STL’s iterator concept.

We discussed the example BucketHeap (source) which implements an Unrolled List in principle.

  • All STL algorithms are compatible, no need to reinvent +50 algorithms for the user-defined class template BucketVector

  • What if we wanted to specify a user-defined variant of an algorithm? \(\Rightarrow\) template specialization