Feedback form for Lecture 4

Please fill in the feedback form for lecture 4 here.

1 A brief overview of the standard algorithms library

Take a look at the algorithms library on C++ Reference. There are many algorithms available, but there is one thing that these algorithms have in common — they all operate on iterators. This (somewhat) decouples containers from the algorithms that you can do on them — container designers write the iterators for them, and these algorithms can operate on iterators from any container (well… sometimes you need certain kinds of iterators with more abilities, but we’ll talk about them later).

We’ll just pick out one or two algorithms from each section on the C++ Reference page, discuss them, and attempt implementing them. From there you should get an idea of how most of the other algorithms are implemented, and at the same time we introduce the syntax for template functions.

1.1 std::find (and an introduction to template functions)

std::find takes in three arguments — a pair of iterators and the value you want to find. It then searches through the iterator range to find an iterator to an element that is equal to the one you have supplied (or returns the end iterator if the element cannot be found).

For example:

std::vector<int> v{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

auto it =
    std::find<std::vector<int>::iterator, int>(v.begin(), v.end(), 17);
if (it != v.end()) {
  std::cout << "Found " << *it << "." << std::endl;
  // Prints "Found 17."

  ++it;

  if (it != v.end()) {
    std::cout << "The following element is " << *it << "." << std::endl;
    // Prints "The following element is 19."
  }
}

How is std::find implemented? In this case it is clear, but in other more complicated algorithms we can take a look at the time complexity that the standard requires this algorithm to have, as well as the kind of iterators that are allowed (this will be covered later).

1.1.1 Implementing std::find

We have already seen template classes, which are not classes in themselves — they are more like blueprints of classes that are used to generate classes when someone instantiates them (i.e. writes something like std::vector<int>).

Similarly, template functions are not functions in themselves, but they are blueprints of functions that are used to generate functions when they are instantiated. For example,

// By doing this
std::find<std::vector<int>::iterator, int>(v.begin(), v.end(), 17);
// We instantiate std::find with the template arguments
         <std::vector<int>::iterator, int>

Let’s try implementing std::find.

The declaration, as we can see on C++ Reference has two template parameters, and looks like this:

template <typename It, typename T>
It find(It first, It last, const T& value);

There are two template parameters since this template function is parameterised on both the iterator type and the value type.

Template functions almost always should be defined inline (i.e. in a header file), even though they are used by multiple translation units. Here is an example (though the inline specifier is optional for template functions — the One Definition Rule does not apply to template functions):

template <typename It, typename T>
inline It find(It first, It last, const T& value) {
  // implementation goes here
}

// find.hpp

template <typename It, typename T>
It find(It first, It last, const T& value);

// find.cpp

#include "find.hpp"

template <typename It, typename T>
It find(It first, It last, const T& value) {
  // implementation goes here
}

// main.cpp

#include <vector>

#include "find.hpp"

int main() {
  std::vector<int> v{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

  auto it = find<std::vector<int>::iterator, int>(v.begin(), v.end(), 17);
  if (it != v.end()) {
    std::cout << "Found " << *it << "." << std::endl;
    // Prints "Found 17."

    ++it;

    if (it != v.end()) {
      std::cout << "The following element is " << *it << "." << std::endl;
      // Prints "The following element is 19."
    }
  }
}

// find.hpp

template <typename It, typename T>
It find(It first, It last, const T& value) {
  // implementation goes here
}

// main.cpp

#include <vector>

#include "find.hpp"

int main() {
  std::vector<int> v{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

  auto it = find<std::vector<int>::iterator, int>(v.begin(), v.end(), 17);
  if (it != v.end()) {
    std::cout << "Found " << *it << "." << std::endl;
    // Prints "Found 17."

    ++it;

    if (it != v.end()) {
      std::cout << "The following element is " << *it << "." << std::endl;
      // Prints "The following element is 19."
    }
  }
}

Here’s a possible implementation (and more or less the only sane one) of std::find:

template <typename It, typename T>
It find(It first, It last, const T& value) {
  while (first != last) {
    if (*first == value) return first;
    ++first;
  }
  return first;
}

1.1.2 Type deduction of template parameters

Writing

auto it =
    std::find<std::vector<int>::iterator, int>(v.begin(), v.end(), 17);

every time we want to use std::find is quite a mouthful. Thankfully, in most situations the template arguments can be inferred from the types of the function arguments, so we can instead write:

auto it = std::find(v.begin(), v.end(), 17);

We will talk about how this works in more detail in a future lecture, but for now just know that it usually works for most unambiguous situations.

1.2 std::find_if

In the same C++ Reference page as std::find, we also see std::find_if, which takes in a unary predicate in place of a value to compare with. std::find_if returns an iterator to the first element that matches the predicate, or the end of the range otherwise.

Its declaration looks like this:

template <typename It, typename UnaryPredicate>
It find_if(It first, It last, UnaryPredicate p);

p is a function object (an object that overloads operator()), and is similar to those that you have seen in the last lecture like std::less.

This is a possible implementation of std::find_if:

template <typename It, typename UnaryPredicate>
It find_if(It first, It last, UnaryPredicate p) {
  while (first != last) {
    if (p(*first)) return first;
    ++first;
  }
  return first;
}

We’ve followed essentially the same logic as std::find, except that we changed the value being sought to the predicate.

(Note that it is possible to implement std::find with std::find_if — think about how you might implement that in C++.)

1.3 Aside: Lambda expressions

How would you actually write a call to std::find_if?

Suppose, for example, we want to find the first element that is at least 10. Just like how we wrote custom comparators, we could write something like this:

std::vector<int> v{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

struct Pred {
  bool operator()(int x) const { return x >= 10; }
};
auto it = std::find_if(v.begin(), v.end(), Pred{});
if (it != v.end()) {
  std::cout << "Found " << *it << "." << std::endl;
  // Prints "Found 11."
}

It works! Wonderful!

The only minor issue is that it looks horrible. Luckily, C++ has lambda expressions (since C++11), which are syntactic sugar to define and instantiate a function object. Instead of the above eyesore, we can write the following:

std::vector<int> v{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

auto it = std::find_if(v.begin(),  //
                       v.end(),
                       [](int x) { return x >= 10; });
if (it != v.end()) {
  std::cout << "Found " << *it << "." << std::endl;
  // Prints "Found 11."
}

The code [](int x) { return x >= 10; } defines a new struct with an operator() as given.

Note that while our lambda expression takes in x by value, it is common to pass x by const reference (i.e. const int& x), especially when x could be expensive to copy.

1.3.1 Captures

What if we want to find the first element that is at least y, where y is a variable that comes from somewhere else? In other words, we want our lambda expression to “capture” y from some outer scope, so that we can use it in our lambda expression.

We capture y be writing the following:

int y = /* stuff */;
std::vector<int> v = /* stuff */;

auto it = std::find_if(
    v.begin(), v.end(), [y](int x) {  // <-- notice the captured `y`
      return x >= y;                  // <-- use of the captured `y`
    });

This is semantically equivalent to the following code:

int y = /* stuff */;
std::vector<int> v /* stuff */;

struct Pred {
  int y;
  bool operator()(int x) const { return x >= y; }
};
auto it = std::find_if(v.begin(), v.end(), Pred{y});

Note that this is equivalent in terms of memory layout, but the field is not actually named y, and so cannot be accessed directly by std::find_if or any other code that has access to the function object. Writing this in a lambda expression also refers to the outer object instead of the generated object itself.

From C++14, it is also possible to write any expression in the capture list, such as [z = y + 100](int x) { return x >= z; }. This is equivalent to doing Pred{y + 100}.

1.3.2 Capture by value vs capture by reference

Notice that in the previous example y was copied into the Pred struct. This is fine since y is just a plain int and we are not modifying it, but what if we want to capture something bigger (where copies are expensive) or something non-copyable? We’d want to generate code that looks like this (say, if we wanted to return true if the number is some std::set<int>):

std::set<int> s = /* stuff */;
std::vector<int> v = /* stuff */;

struct Pred {
  const std::set<int>& s;
  bool operator()(int x) const { return s.contains(x); }
};
auto it = std::find_if(v.begin(), v.end(), Pred{s});

To generate that kind of code, we write &s instead of s in the capture list:

std::set<int> s = /* stuff */;
std::vector<int> v = /* stuff */;

auto it = std::find_if(v.begin(),  //
                       v.end(),
                       [&s](int x) { return s.contains(x); });

Note that there’s actually a slight semantic difference — &s captures the set by non-const reference, so it’s equivalent to having a std::set<int>& s field instead of a const std::set<int>& s field. C++ unfortunately doesn’t have a language feature to capture by const reference in a lambda expression, so the best we can do is something like:

[&s = std::as_const(s)](int x) { ... }

1.3.3 Mutable lambda functions

Notice how in the desugaring we always marked operator() as a const member function. A lambda expression by default cannot mutate any of its by-value captures. (By-reference captures may be mutated, since the reference itself doesn’t change, just like how non-const references in a const struct may still mutate the objects they refer to.)

To generate a non-const operator(), we write mutable after the parameters of the lambda expression. For example, this lambda expression returns true when the current element is at least 4 more than the previous element:

[y = numeric_limits<int>::max()](int x) mutable {
  bool ret = x >= y;
  y = x + 4;
  return ret;
}

template <typename It>
It find_if_funcref(
    It first,
    It last,
    bool (&p)(typename std::iterator_traits<It>::value_type)) {
  while (first != last) {
    if (p(*first)) return first;
    ++first;
  }
  return first;
}

1.4 std::copy

Now let’s look at a different and probably simpler algorithm: std::copy. std::copy copies the elements of one range into another range, and returns an iterator to the end of the second range.

std::set<int> s{5, 12, 15, 22, 25, 32};

std::vector<int> v;
v.resize(s.size());

std::copy(s.begin(), s.end(), v.begin());
assert(v == std::vector<int>{5, 12, 15, 22, 25, 32});

Note that the input iterator and the output iterator need not be from the same container — in the above example, our input iterator is std::set<int>::iterator while our output iterator is std::vector<int>::iterator.

Again, there’s really only one good way to do this in terms of operator++ and operator*:

template <typename InIt, typename OutIt>
OutIt copy(InIt first, InIt last, OutIt d_first) {
  while (first != last) {
    *d_first = *first;
    ++first;
    ++d_first;
  }
  return d_first;
}

Notice that OutIt is used slightly differently from InIt. In particular, the elements pointed to be OutIt must be writable. It’s similar to the difference between T* and const T*. Iterators, being modelled after pointers, have both const and non-const versions. InIt is allowed to be a const iterator, while OutIt must be non-const.

Every standard library container Container has two kinds of iterators — Container::iterator (non-const, like a T*) and Container::const_iterator (const, like a const T*). The begin member function is overloaded for the const and non-const versions of the container, in order to propagate the const-ness of the container to its iterator. For example:

// Good:
//   container is non-const
//   so iterators are non-const
void f(std::vector<int>& v) {
  std::set<int> s{5, 12, 25, 32};

  // `v.begin()` and `v.end()`
  // have type
  // `std::vector<int>::iterator`
  std::copy(s.begin(),  //
            s.end(),
            v.begin());
}

// Bad: container is const
//      so iterators are const
void f(const std::vector<int>& v) {
  std::set<int> s{5, 12, 25, 32};

  // `v.begin()` and `v.end()`
  // have type
  // `std::vector<int>::const_iterator`
  std::copy(s.begin(),  //
            s.end(),
            v.begin());
}

Iterators can be implicitly converted to their const versions, as one might expect. In addition, we can get const begin and end iterators from a non-const standard library containers by using cbegin and cend.

1.5 std::reverse

std::reverse reverses the elements in the range.

std::vector<int> v{5, 12, 15, 22, 25, 32};

std::reverse(v.begin(), v.end());
assert(v == std::vector<int>{32, 25, 22, 15, 12, 5});

The typical way to reverse a range is to maintain two pointers — one from the beginning and one from the end — and swap pairs of elements as the pointers move towards the middle of the range.

Notice that this requires iterators that have additional functionality on top of operator++ and operator* — the ability to go backward one step at a time (i.e. operator--). We’ll formalise the different levels of requirements for iterators later in this lecture.

A possible implementation is as follows (note the need for operator--):

template <typename It>
void reverse(It first, It last) {
  while (true) {
    if (first == last) return;
    --last;
    if (first == last) return;
    std::iter_swap(first, last);
    ++first;
  }
}

std::iter_swap swaps the elements pointed to by the two iterators.

1.6 Binary searching with std::binary_search

Let’s revisit the situation in std::find where we wanted to find an element from a range.

If the range is sorted, there are better ways to find some element than to look through every element in the range. Performing a binary search takes O(logN) time, instead of O(N) required for a linear search (std::find).

Using the same as example as previously, let’s test if the number 17 is in the vector:

std::vector<int> v{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

bool exists = std::binary_search(v.begin(), v.end(), 17);
if (exists) {
  std::cout << "Found 17." << std::endl;
  // Prints "Found 17."
} else {
  std::cout << "Not found." << std::endl;
}

Instead of using operator== to compare elements, std::binary_search uses operator<, because it needs to test if the given element is too large or too small for each position. Hence, if the elements are sorted in a different order from normal, we will pass in a custom comparator that takes two parameters (something like our custom comparator for std::priority_queue). For example:

std::vector<int> v{30, 25, 20, 15, 10, 5, 0};

bool exists = std::binary_search(v.begin(),  //
                                 v.end(),
                                 20,
                                 std::greater<int>{});
if (exists) {
  std::cout << "Found 20." << std::endl;
  // Prints "Found 20."
} else {
  std::cout << "Not found." << std::endl;
}

// sorted by increasing number of set bits
std::vector<unsigned> v{0, 1, 2, 4, 3, 5, 6, 7};

bool exists =
    std::binary_search(v.begin(),  //
                       v.end(),
                       9,
                       [](unsigned a, unsigned b) {
                         return std::popcount(a) < std::popcount(b);
                       });
if (exists) {
  std::cout << "Found an element with " << std::popcount(9u)
            << " set bits." << std::endl;
} else {
  std::cout << "Not found." << std::endl;
}

1.6.1 std::lower_bound and std::upper_bound

std::binary_search returns only a boolean, that tells us whether an element is in the range, but just that information may be insufficient. For example, we might want to find, say, the smallest element larger than 15. We then want an iterator to the element found in the range (or a nearby element if the exact value cannot be found). std::lower_bound and std::upper_bound do just that — they return an iterator to the position where the given element could be inserted to ensure that the elements remain in ascending order. They differ when there are existing element(s) that are equal to the given element — std::lower_bound returns the first possible position, while std::upper_bound returns the last possible position.

std::vector<int> v{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int x = /* stuff */;

// Returns the earliest iterator that points to a value at least `x`
auto it = std::lower_bound(v.begin(), v.end(), x);

if (it != v.end()) {
  if (*it == x) {
    std::cout << "Found " << x << "." << std::endl;
  } else {
    std::cout << "The smallest element at least " << x << " is " << *it
              << "." << std::endl;
  }
} else {
  std::cout << x << " is bigger than all elements." << std::endl;
}

The example with popcount can also be written more nicely with std::lower_bound:

// sorted by increasing number of set bits
std::vector<unsigned> v{0, 1, 2, 4, 3, 5, 6, 7};

auto it = std::lower_bound(
    v.begin(),  //
    v.end(),
    2,
    [](unsigned x, int bits) { return std::popcount(x) < bits; });
if (it != v.end() && std::popcount(*it) == 2) {
  std::cout << *it << " has 2 set bits." << std::endl;
} else {
  std::cout << "Not found." << std::endl;
}

std::equal_range is the combination of both std::lower_bound and std::upper_bound:

std::vector<std::pair<int, std::string>> v{
    {1, "a"}, {3, "the"}, {3, "int"}, {4, "auto"}};

auto [first, last] =
    std::equal_range(v.begin(),
                     v.end(),
                     std::pair(3, std::string()),
                     [](const std::pair<int, std::string>& a,
                        const std::pair<int, std::string>& b) {
                       return a.first < b.first;
                     });
// Prints "the" and "int":
for (auto it = first; it != last; ++it) {
  std::cout << it->second << std::endl;
}

1.6.2 Implementing std::lower_bound

Here’s a possible implementation of std::lower_bound:

template <typename It, typename T, typename Compare = std::less<>>
It lower_bound(It first, It last, const T& value, Compare comp) {
  ptrdiff_t low = -1;
  ptrdiff_t high = std::distance(first, last);  // roughly `last - first`
  // Loop invariants:
  //     low == -1 || comp(*(first + low), value)
  //     high == last - first || !comp(*(first + high), value)
  while (low + 1 < high) {
    ptrdiff_t mid = low + (high - low) / 2;
    auto it = first;
    std::advance(it, mid);  // roughly `it += mid`
    if (comp(*it, value)) {
      first = mid;
    } else {
      last = mid;
    }
  }
  return high;
}

Over here we’ve used std::distance(first, last) which is equivalent to last - first if the iterator supports operator-. Otherwise, it figures out the distance between first and last using a loop. Similarly. std::advance(it, mid) is equivalent to it += mid where operator+= is available, otherwise it uses a loop to advance the iterator. Even though it’s technically possible to use iterators that do not support operator- and operator+= quickly, it defeats the purpose of binary search. Whether using std::binary_search and friends is worthwhile depends on the properties of your iterator.

1.7 std::sort and std::stable_sort

std::sort is one of the more complicated algorithms in the standard library. It sorts a range, either using the default operator< or using a custom comparator:

std::vector<int> v1 = /* stuff */;
// sorts using `operator<` (i.e. in ascending order)
std::sort(v1.begin(), v1.end());

std::vector<int> v2 = /* stuff */;
// sorts using `operator>` (i.e. in descending order)
std::sort(v2.begin(), v2.end(), std::greater<int>{});

std::vector<Point> v3 = /* stuff */;
// sorts using custom comparator, by x-coordinate then by y-coordinate
std::sort(v3.begin(), v3.end(), [](const Point& a, const Point& b) {
  if (a.x != b.x) return a.x < b.x;
  return a.y < b.y;
});

1.7.1 What sorting algorithm does std::sort use?

Being a very commonly used algorithm, standard library implementers pay a lot of attention to the performance of std::sort.

Quicksort is a really quick sorting algorithm, and can be made even faster when implementations use highly-optimised versions of the Hoare partition scheme. It is one of the fastest general-purpose sorting algorithms available, because it often uses a smaller number of swaps than other algorithms, and it also requires no additional heap memory (i.e. quicksort is an in-place swap).

The main problem of quicksort is that it has O(N²) time complexity in the worst case scenario, but std::sort is required to have O(NlogN) time complexity in all cases from C++11 onwards (see the details on the C++ Reference page). Hence, a std::sort implemented by quicksort alone is not standard-compliant.

All major implementations hence implement a hybrid algorithm — quicksort for most cases, and then a fallback to some guaranteed O(NlogN) algorithm if some condition is met. This allows us to heap the performance benefits of quicksort, but yet have a worst case time complexity of O(NlogN).

GCC’s std::sort implementation starts of with quicksort, but if the recursion depth goes beyond 2log N, it falls back to heapsort (which is an in-place guaranteed O(NlogN) sorting algorithm). This combination of quicksort and heapsort is known as introsort. GCC’s introsort however only places elements nearby to their correct positions (i.e. within some constant number of positions away from its correct position). The positions are then finalised by an insertion sort routine at the end, which is more efficient when elements near to their correct positions because of cache efficiency considerations.

1.7.2 Stability of a sorting algorithm

A sorting algorithm is stable if equal elements retain their relative positions. This is not important when equivalence implies equality (as in the case of sorting ints using operator<). However, when there could be multiple equivalent elements that are not equal, stability of the sorting algorithm might be something desirable to have.

std::vector<Point> v3 = /* stuff */;
// sorts using custom comparator,
// by the sum of the x-coordinate and y-coordinate
std::sort(v3.begin(), v3.end(), [](const Point& a, const Point& b) {
  return a.x + a.y < b.x + b.y;
});

As std::sort is not guaranteed to be stable, the above code may have different output on different standard library implementations if there are two equivalent but different points (for example, Point{3, 5} is equivalent to Point{4, 4} in this custom comparator). In practice, since quicksort is unstable, std::sort is unstable in all major standard library implementations.

In situations where we want to perform a stable sort, we can use std::stable_sort.

Notice how the C++ standard says that std::stable_sort is required to take O(NlogN) time if additional memory is available (i.e. not an in-place sort), and O(Nlog²N) time otherwise. This is because there is no known good general purpose in-place stable sorting algorithm that runs in O(NlogN) time. Implementations usually use merge sort to implement std::stable_sort, and since linear time merging of two sorted arrays needs a separate buffer for the output array, std::stable_sort needs additional memory to sort the elements in O(NlogN) time. Without additional memory, we can merge two sorted arrays in O(NlogN) time.

1.8 The erase-remove idiom

There are some algorithms, such as std::remove/std::remove_if and std::unique, that “removes” some of the elements in the range. Of course, this can’t actually erase elements from the backing container, since you can’t erase an element without having a reference to the container itself. These algorithms instead returns an iterator to the “logical” end of the modified array — elements between the logical end and the real end may have arbitrary values.

std::vector<int> v{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
auto new_end = std::remove_if(v.begin(),  //
                              v.end(),
                              [](int x) { return x % 10 == 3; });

// Now, the range [v.begin(), new_end) contains {2, 5, 7, 11, 17, 19, 29}
// and the range [new_end, v.end()) contains unspecified values.
// So `v` contains {2, 5, 7, 11, 17, 19, 29, ?, ?, ?}.

// Actually erase the trailing values:
v.erase(new_end, v.end());

// Now, `v` contains {2, 5, 7, 11, 17, 19, 29}.

This is actually so common that it is an idiom in C++, usually written in a single statement like this:

std::vector<int> v{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
v.erase(std::remove_if(v.begin(),
                       v.end(),
                       [](int x) { return x % 10 == 3; }),
        v.end());

// Now, `v` contains {2, 5, 7, 11, 17, 19, 29}.

In C++20, the std::remove/std::remove_if case may be expressed more succinctly using std::erase/std::erase_if, which are implemented by standard library containers that implement uniform container erasure:

std::vector<int> v{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
std::erase_if(v, [](int x) { return x % 10 == 3; });

// Now, `v` contains {2, 5, 7, 11, 17, 19, 29}.

However uniform container erasure only works with std::remove/std::remove_if, and there is no equivalent for std::unique.

1.9 Other algorithms

There are many other algorithms in the algorithms library, and we encourage you to think about how these algorithms are implemented, and why their time complexities match those specified by the standard (on C++ Reference). It’s also useful to try implementing some of them on your own.

2 Iterators in depth

Let’s now crack open the hood and see how iterators actually work.

We know from L4 that different containers have to implement iterators differently. For example, when we implement a std::vector iterator, we want a simple raw pointer, but when we implement a std::deque iterator, we actually want to store multiple pieces of state so that the iterator knows how to find the next element.

We also know that for some containers, their iterators literally cannot implement certain traversal patterns efficiently. For example, while std::list allows us to either increment or decrement iterators to move forwards or backwards in the list, a std::forward_list can only be traversed in one direction. Similarly, std::vector allows us to add or subtract large steps using it + 420, but this cannot be done efficiently for trees or linked lists like std::map.

To communicate these nuances to the developers, C++ defines 5 iterator categories. Iterator categories are conceptually just a specification of how much an iterator is able to do with regards to traversal, to allow documentation to communicate the aforementioned nuances to users.

While this is great language to use for documentation to communicate to developers, we will also cover how C++ specifies additional type-level requirements that will allow types to convey information to templated code using metaprogramming techniques.

2.1 Iterator categories

2.1.1 Overview

The 5 iterator categories are:

• InputIterator
• ForwardIterator
• BidirectionalIterator
• RandomAccessIterator
• ContiguousIterator

These iterator categories describe readable iterators that support certain traversal patterns.

Iterators that are writable are called OutputIterators.

Finally, an iterator that can be both written to and read from are called mutable iterators, and are described as satisfying some readable iterator category, as well as OutputIterator.

The (readable) iterator categories range from the most restricted (InputIterator) to the most pointer-like (ContiguousIterator). In fact, ContiguousIterators are functionally identical to pointers, but its definition is subtly more nuanced in case container classes wish to use a wrapper type for debugging purposes / other reasons.

Here is a table that summarises the iterator categories.

Note the way that the categories only ever increase in power. For example, BidirectionalIterators are also ForwardIterators and InputIterators.

2.1.2 ForwardIterator

Let’s start with ForwardIterators. We will cover InputIterators next, as a more restricted ForwardIterator.

Iterators in this category are allowed the following operations:

• Dereferenceable (shared with InputIterator)
• Incrementable (shared with InputIterator)
• Equality-comparable (shared with InputIterator)
• Multi-pass
• Dereference returns true reference

Specifically, this means that the following operations are allowed:

// ForwardIt it, it2;

const T& ref = *it;  // Reading from the iterator
it->m;               // Really the same as *(it.m),
                     // but listed because it's technically not the same

++it;           // Pre-incrementing the iterator
old_it = it++;  // or post-incrementing the iterator

it == it2;  // Comparing for equality...
it != it2;  // or for inequality

This is quite natural, and it means that code like std::find_if will work on ForwardIterators.

One way to notate that in code is to use the term ForwardIterator as the type name.

template <typename ForwardIt, typename T>
It find(ForwardIt first, ForwardIt last, const T& value) {
  /* implementation goes here */
}

You’ll see this kind of documentation style in cppreference, for example the docs for std::find:

template< class InputIt, class T >
constexpr InputIt find( InputIt first, InputIt last, const T& value );

2.1.3 InputIterator

Notice that std::find actually only requires an InputIterator, rather than a ForwardIterator. InputIterators are only allowed the following operations:

• Dereferenceable
• Incrementable
• Equality-comparable

In other words, they are ForwardIterators where multi-pass is not allowed, and dereference doesn’t have to returns a true reference (as in, its return type might not end in &).

Multi-pass refers to the following guarantees:

• a == b implies ++a == ++b

• Incrementing a copy does not change the value you would have read from the original iterator:

  ForwardIterator it;
  ForwardIterator it2 = it;
  const T& ref = *it;  // returns reference to X
  ++it2;
  const T& ref2 = *it;  // also returns reference to X

• Other esoteric details

Removing these two conditions means that the API is similarly limited. Specifically, this means that the following operations are allowed:

// InputIt it, it2;

*it;        // Reading from the iterator, not necessarily a reference
T v = *it;  // Whatever dereference returns, we should be able to use it
            // like a T
it->m;      // Really the same as *(it.m),
            // but listed because it's technically not the same

++it;  // Pre-incrementing the iterator
// Post-incrementing is only allowed in certain cases:
(void)it++;  // either we don't use the result
*it++;       // or we immediately dereference it

it == it2;  // Comparing for equality...
it != it2;  // or for inequality

So the reason std::find works not only on ForwardIterators but also on InputIterators is because it doesn’t require multi-pass traversal, or even post-increment.

template <typename It, typename T>
It find(It first, It last, const T& value) {
  while (first != last) {
    if (*first == value) return first;
    ++first;
  }
  return first;
}

2.1.4 BidirectionalIterator

Moving on to the more powerful iterator categories, we have BidirectionalIterator which just does what it says on the tin: it allows bidirectional traversal.

• Dereferenceable (shared with ForwardIterator)
• Incrementable (shared with ForwardIterator)
• Equality-comparable (shared with ForwardIterator)
• Multi-pass (shared with ForwardIterator)
• Dereference returns true reference (shared with ForwardIterator)
• Decrementable

If we wanted to find the number immediately preceding a 5, we could do the following:

std::vector<int> v{1, 2, 3, 4, 5, 6};
auto it = std::find(v.begin(), v.end(), 5);

// decrement! wheee
--it;
// prints 4
std::cout << *it << std::endl;

++it;
// it is now equal to before we decremented,
// so this prints 5
std::cout << *it << std::endl;

As we showed earlier, std::reverse is an STL algorithm that requires at least BidirectionalIterator and above.

// BidirIt it, it2;

const T& ref = *it;  // Reading from the iterator
it->m;               // Really the same as *(it.m),
                     // but listed because it's technically not the same

++it;                 // Pre-incrementing the iterator
old_it = it++;        // or post-incrementing the iterator
--it;                 // Pre-decrementing the iterator
old_it = it--;        // or post-decrementing the iterator
++(--copy_it) == it;  // Decrementing is actually semantically
--(++copy_it) == it;  // the opposite of incrementing
                      // *given that at no point we created an illegal
                      // iterator, e.g. iterating past the end

it == it2;  // Comparing for equality...
it != it2;  // or for inequality

2.1.5 RandomAccessIterator

Next up is RandomAccessIterator. Intuitively, these iterators have “index” semantics — they behave like indices into a data structure, and we can dereference them to obtain the corresponding object in that data structure.

Just like indices, we can not only increment / decrement (which is like it += 1), but also skip ahead and backwards by a certain amount (it += n).

We’re also allowed to measure the distance between iterators (it2 - it1) and then use this distance to skip ahead / backwards (it1 + (it2 - it1) == it2).

Finally, we can also compare iterators just like we can compare indices (it2 < it1).

// RandomIt it, it2;

const T& ref = *it;  // Reading from the iterator
it->m;               // Really the same as *(it.m),
                     // but listed because it's technically not the same

++it;           // Pre-incrementing the iterator
old_it = it++;  // or post-incrementing the iterator
--it;           // Pre-decrementing the iterator
old_it = it--;  // or post-decrementing the iterator

it += n;  // Skipping ahead / behind
it -= n;
it + n;  // Skipping ahead / behind on a copy
it - n;

it[n];  // Note: this is just syntax sugar for *(it + n)

it2 - it;               // Taking distances
it + (it2 - it) == it;  // Distances actually correspond to
                        // semantics of skipping ahead / behind

it == it2;  // Comparing for equality...
it != it2;  // or for inequality
it < it2;   // or any other comparison

An example of an STL algorithm that requires RandomAccessIterators is std::shuffle. Hopefully it’s obvious why this algorithm needs random access to be implemented efficiently :P

Another example is std::{lower,upper}_bound, which runs binary search on a sorted range. Since binary search requires us to be able to split the range in halves repeatedly, we need to be able to take distances, and skip the iterator to the midpoint. We also need to be able to compare iterators to be able to determine when the range is too small or has shrunk to a negative size.

However, if we look at the actual documentation for std::lower_bound, we see that it only requires ForwardIterator. In such cases, it’ll use O(N) traversal to skip ahead / behind the iterators, but still use binary search to actually find the element, so the number of dereferences and comparison operations is only O(logN). Obviously, this is not ideal, but sometimes, this is actually the trade-off you want.

template <typename RandomIt>
void random_shuffle(RandomIt first, RandomIt last) {
  // Implements the Fisher-Yates shuffle
  // Taken from libstdc++ and cleaned up
  if (first != last) {
    for (RandomIt i = first + 1; i != last; ++i) {
      // XXX rand() % N is not uniformly distributed
      RandomIt j = first + std::rand() % ((i - first) + 1);
      if (i != j) std::iter_swap(i, j);
    }
  }
}

2.1.6 ContiguousIterator

Finally, the most powerful (readable) iterator is ContiguousIterator. These iterators not only have “index” semantics, they have “pointer” semantics, and require that all the objects pointed to by the iterator are contiguous in memory, so the iterator’s operator++ is really the same as the pointer’s operator++.

Specifically, this means that it shouldn’t matter whether you first dereference an iterator to get an object, then increment the address, or if you increment the iterator first, and then dereference it. Or in fancy math terms, dereferencing the iterator commutes with iterator / pointer increment.

// ContiguousIt it;
*it;                       // Reference to an object
&*it;                      // Address of that object
&*(it + n) == &*it + n;    // Iterator +n is the same as pointer +n
*(it + n) == *(&*it + n);  // The wording for the actual requirement

But in terms of the operations allowed, they are exactly the same as a RandomAccessIterator.

As far as I know, no algorithms require ContiguousIterators, and they usually require up to RandomAccessIterator. However, some algorithms such as std::copy perform much better when the iterator is contiguous and the pointed to elements are trivial types. In such cases, std::copy may be implemented as a memcpy.

2.1.7 OutputIterator

This brings us to the last kind of iterators, OutputIterators.

At the minimum, such iterators allow writing and not much else.

// OutputIt it;

*(it++) = v;  // Writing to the iterator

// Technically, the specification describes a different set of operations,
// but this is roughly the right idea.

An example OutputIterator is the return type of std::back_inserter, which gives us an iterator that just calls push_back when written to. This is useful for doing stuff like appending containers together.

// Container c;
// Container c1, c2, c3;
auto output_it = std::back_inserter(c);
std::copy(c1.begin(), c1.end(), output_it);
std::copy(c2.begin(), c2.end(), output_it);
std::copy(c3.begin(), c3.end(), output_it);

Note: Most of the time, this is a terrible way of using std::back_inserter, because better alternatives exist if you know the proper type. For example, if Container was a std::vector<int>, the following would be much preferred.

// std::vector<int> c;
// std::vector<int> c1, c2, c3;
c.insert(c.end(), c1.begin(), c1.end());
c.insert(c.end(), c2.begin(), c2.end());
c.insert(c.end(), c3.begin(), c3.end());

2.2 Mutable iterators

As mentioned before, mutable iterators are simply readable iterators that can be written to, i.e. the expression *it = v is allowed.

Most of the time, containers will expose different APIs for you to access the mutable iterator and immutable iterators. On a non-const container, these are usually called .begin/.end() and .cbegin/.cend(). For const containers, they usually both return immutable iterators.

Here are some examples:

• mutable ForwardIterator: return type of .begin() of non-const std::unordered_set<T>
• mutable BidirectionalIterator: return type of .begin() of non-const std::set<T>
• mutable RandomAccessIterator: return type of .begin() of non-const std::deque<T>
• mutable ContiguousIterator: return type of .begin() of non-const std::vector<T>

I’ve never seen a mutable InputIterator, but I think it is theoretically possible. I’m not sure why you would ever want one, though.

2.3 Member type requirements (and differences with C++20)

So far, we’ve described the traversal operations that each category of iterators expose. A keen eye would have noticed that this entire time, we’ve been linking to “Legacy” pages. Furthermore, if we read the actual cppreference page, we see an interesting requirement:

std::iterator_traits<It> has member typedefs value_type (until C++20), difference_type, reference, pointer, and iterator_category,

cppreference

What does this actually mean? Long story short, it means that if we’re defining our own iterator type, we need to make sure that we have member types for the things named above defined.

For example, even though we defined all the required traversal operations, the following is not sufficient to define a (Legacy)InputIterator:

struct NotInputIterator {
  int* i;

  NotInputIterator& operator++() {
    ++i;
    return *this;
  }
  NotInputIterator operator++(int) {
    ++i;
    return NotInputIterator{i - 1};
  }

  int& operator*() {
    return *i;
  }
  int* operator->() {
    return i;
  }

  bool operator==(const NotInputIterator& other) const {
    return i == other.i;
  }
  bool operator!=(const NotInputIterator& other) const {
    return i != other.i;
  }
};

Trying to use and compile it (on C++17, with clang 13.0.1 and libstdc++ 12.1.0), it explodes:

int main() {
  int x[3] = {1, 2, 3};
  NotInputIterator start{x};
  NotInputIterator end{x + 3};
  std::copy(start, end, std::ostream_iterator<int>{std::cout});
}

$ make not-an-iterator.cxx17.out
clang++ -g -std=c++17 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable -fsanitize=address   -c -MMD -o not-an-iterator.cxx17.o not-an-iterator.cpp
In file included from not-an-iterator.cpp:1:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/algorithm:61:
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_algobase.h:395:46: error: no type named 'value_type' in 'std::iterator_traits<NotInputIterator>'
      typedef typename iterator_traits<_II>::value_type _ValueTypeI;
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_algobase.h:441:8: note: in instantiation of function template specialization 'std::__copy_move_a<false, NotInputIterator, std::ostream_iterator<int>>' requested here
                std::__copy_move_a<_IsMove>(std::__niter_base(__first),
                     ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_algobase.h:473:19: note: in instantiation of function template specialization 'std::__copy_move_a2<false, NotInputIterator, std::ostream_iterator<int>>' requested here
      return std::__copy_move_a2<__is_move_iterator<_II>::__value>
                  ^
not-an-iterator.cpp:39:8: note: in instantiation of function template specialization 'std::copy<NotInputIterator, std::ostream_iterator<int>>' requested here
  std::copy(start, end, std::ostream_iterator<int>{std::cout});
       ^
In file included from not-an-iterator.cpp:1:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/algorithm:61:
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_algobase.h:397:46: error: no type named 'iterator_category' in 'std::iterator_traits<NotInputIterator>'
      typedef typename iterator_traits<_II>::iterator_category _Category;
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
2 errors generated.
make: *** [Makefile:57: not-an-iterator.cxx17.o] Error 1

However, if we add the required member types, it will now work:

struct IsInputIterator {
  using value_type = int;
  using difference_type = std::ptrdiff_t;
  using reference = int&;
  using pointer = int*;
  using iterator_category = std::input_iterator_tag;

  int* i;

  IsInputIterator& operator++() {
    ++i;
    return *this;
  }
  IsInputIterator operator++(int) {
    ++i;
    return IsInputIterator{i - 1};
  }

  int& operator*() {
    return *i;
  }
  int* operator->() {
    return i;
  }

  bool operator==(const IsInputIterator& other) const {
    return i == other.i;
  }
  bool operator!=(const IsInputIterator& other) const {
    return i != other.i;
  }
};

$ make is-an-iterator.cxx17.out
clang++ -g -std=c++17 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable -fsanitize=address   -c -MMD -o is-an-iterator.cxx17.o is-an-iterator.cpp
clang++ -g -std=c++17 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable -fsanitize=address    is-an-iterator.cxx17.o   -o is-an-iterator.cxx17.out

Alternatively, compiling with C++20 works (again, with clang++ 13.0.1 and libstdc++ 12.1.0).

int main() {
  int x[3] = {1, 2, 3};
  NotInputIterator start{x};
  NotInputIterator end{x + 3};
  std::copy(start, end, std::ostream_iterator<int>{std::cout});
}

$ make not-an-iterator.out
clang++ -g -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable -fsanitize=address   -c -MMD -o not-an-iterator.o not-an-iterator.cpp
clang++ -g -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable -fsanitize=address    not-an-iterator.o   -o not-an-iterator.out

How does this work? Let’s look at the pre-C++20 rules first.

In order to fulfil the (legacy) requirement, we need to somehow ensure that the member types std::iterator_traits<It>::stuff is defined for the various stuff, like value_type, iterator_category, and so on.

Following the trail, in order to ensure std::iterator_traits<It>::stuff is defined, we see that std::iterator_traits simply defines the member types exactly according to what we put in our iterator type It.

There is some magic that says that if we don’t define all five member types, then std::iterator_traits won’t define any of them, but the point is that all it does is to “forward” the member types.

This sounds quite pointless at first glance. However, it makes more sense once you realise that std::iterator_traits is actually defined for pointer types such as int*. For example, std::iterator_traits<int*>::value_type is int, as expected.

This pattern of having std::*_traits classes is common in the C++ standard library and is meant for metaprogramming use, in order to bridge the gap between non-customizable primitive types and customizable user-defined types.

Post-C++20, the rules change slightly so that one no longer needs to define all five member types in order to qualify as an iterator, so long as sufficiently many other conditions hold. In the example we showed above, we happen to fulfil the requirements needed to count as an iterator in C++20. However, the rules are kind of annoying to cover, and it’s not very difficult to simply define the member types, so we will simply define all the member types from now on.

Later, we will briefly show how we can make use of std::iterator_traits in order to write templated functions that can change their implementation depending on the strength of the iterator that’s been passed into the function.

2.4 Implementing {,reverse_}iterator for SimpleVector

Full godbolt link for this section

Let’s now implement a bunch of iterators to get a feel for it!

2.4.1 Normal iterators

The easiest iterator to implement are the (normal) iterators for SimpleVector.

Believe it or not, this suffices:

  ElemTy* begin() {
    return m_buffer;
  }
  ElemTy* end() {
    return m_buffer + m_size;
  }
  const ElemTy* begin() const {
    return m_buffer;
  }
  const ElemTy* end() const {
    return m_buffer + m_size;
  }
  const ElemTy* cbegin() const {
    return m_buffer;
  }
  const ElemTy* cend() const {
    return m_buffer + m_size;
  }

This is because normal pointers already count as ContiguousIterators! Not only do they support the highest level of traversal, they also have std::iterator_traits defined since pointer types get special treatment and their traits types are auto-detected.

2.4.2 Reverse iterators 1: Nested struct

However, this doesn’t work when the data structure is not contiguous in memory, with no gaps or jumping around in address space.

This is the case for if we want to implement the reverse iterators .rbegin() and .rend(). In this case, although the objects themselves are contiguous, the traversal order needs to jump around — the pointer for the next iterator is not simply the end of the current pointer, but rather we need to do some fancy pointer arithmetic to figure it out.

We can start by implementing a nested struct inside SimpleVector and using that as the iterator type. We’ll also start by only implementing an InputIterator, for simplicity.

  struct RevIter {
    using post_increment_t = int;

    using difference_type = ptrdiff_t;
    using value_type = ElemTy;
    using pointer = ElemTy*;
    using reference = ElemTy&;
    using iterator_category = std::input_iterator_tag;

    ElemTy* m_ptr;

    bool operator==(const RevIter& other) const {
      return m_ptr == other.m_ptr;
    }
    bool operator!=(const RevIter& other) const {
      return m_ptr != other.m_ptr;
    }

    reference operator*() const {
      return *(m_ptr - 1);
    }
    pointer operator->() const {
      return m_ptr - 1;
    }

    RevIter& operator++() {
      m_ptr--;
      return *this;
    }
    RevIter operator++(post_increment_t) {
      return {m_ptr--};
    }
  };

Now, we can implement .rbegin() and .rend() by getting them to return instances of our newly defined RevIter class.

  RevIter rbegin() {
    return {end()};
  }
  RevIter rend() {
    return {begin()};
  }

However, notice that we haven’t, and in fact cannot, implement the const iterator versions. This is because all our types are not const-correct — a const iterator needs to make sure that the reference returned by operator* is a const reference, for example.

2.4.3 Reverse iterators 2: Templated struct

In order to implement the const versions, one way we could do it is to simply copy paste the entire RevIter class and make a const version, like so:

  struct ConstRevIter {
    using post_increment_t = int;

    using difference_type = ptrdiff_t;
    using value_type = ElemTy;
    using pointer = const ElemTy*;
    using reference = const ElemTy&;
    using iterator_category = std::input_iterator_tag;

    const ElemTy* m_ptr;

    bool operator==(const ConstRevIter& other) const {
      return m_ptr == other.m_ptr;
    }
    bool operator!=(const ConstRevIter& other) const {
      return m_ptr != other.m_ptr;
    }

    reference operator*() const {
      return *(m_ptr - 1);
    }
    pointer operator->() const {
      return m_ptr - 1;
    }

    ConstRevIter& operator++() {
      m_ptr--;
      return *this;
    }
    ConstRevIter operator++(post_increment_t) {
      return {m_ptr--};
    }
  };

But this is slightly unsatisfying. Instead, let’s make a templated class for the reverse iterator that wraps over another iterator type. In order to make it easy to make both the const and non-const versions, we’ll have our templated class make use of std::iterator_traits to set the member types to correspond exactly to the member types of the iterator we’re wrapping over.

template <typename Iter>
struct RevIterUnconstrained {
  using post_increment_t = int;

  using Traits = std::iterator_traits<Iter>;
  using difference_type = typename Traits::difference_type;
  using value_type = typename Traits::value_type;
  using pointer = typename Traits::pointer;
  using reference = typename Traits::reference;
  using iterator_category = std::input_iterator_tag;

  Iter m_iter;

  bool operator==(const RevIterUnconstrained& other) const {
    return m_iter == other.m_iter;
  }
  bool operator!=(const RevIterUnconstrained& other) const {
    return m_iter != other.m_iter;
  }

  reference operator*() const {
    return *(m_iter - 1);
  }
  pointer operator->() const {
    return m_iter - 1;
  }

  RevIterUnconstrained& operator++() {
    m_iter--;
    return *this;
  }
  RevIterUnconstrained operator++(post_increment_t) {
    return {m_iter--};
  }
};

Note that we did NOT simply copy iterator_category as well. That would be wrong, since we did not in fact implement the traversal operations for anything higher than input iterator so far.

However, this is not ideal, because we are allowed to do silly things like this:

void silly(std::unordered_set<int> s) {
  // This compiles, even though it will break later
  auto rev_begin =
      RevIterUnconstrained<std::unordered_set<int>::iterator>{s.end()};
  auto rev_end =
      RevIterUnconstrained<std::unordered_set<int>::iterator>{s.begin()};

  // Trying to use it results in a compile error, and a bad error message
  // ++rev_begin;
}

Trying to use it results in the following rather low-level error message:

$ make bad-error.out
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable -fsanitize=address   -c -MMD -o bad-error.o bad-error.cpp
bad-error.cpp:32:11: error: cannot decrement value of type 'std::__hash_const_iterator<std::__hash_node<int, void *> *>'
    m_iter--;
    ~~~~~~^
bad-error.cpp:48:3: note: in instantiation of member function 'RevIterUnconstrained<std::__hash_const_iterator<std::__hash_node<int, void *> *>>::operator++' requested here
  ++rev_begin;
  ^
1 error generated.
make: *** [Makefile:32: bad-error.o] Error 1

A user of our class might be confused why ++rev_begin is an issue, because we claimed to be an InputIterator. Is it their fault for misusing our class? Or was the class somehow malformed? Or maybe it was just a bug in our code?

2.4.4 Reverse iterators 3: Constrained templated struct

We can significantly improve error messages by using C++20 concepts, or using slightly fancier techniques (covered in a future lecture) if you’re still on C++17 or below.

If we add a requires clause just before the class definition, we can cause the compiler to error out early, during class template instantiation, rather than at the last minute when it is used.

template <typename Iter>
requires std::random_access_iterator<Iter>
struct RevIter1 {

Trying to instantiate it gives us much better error messages immediately.

void silly(std::unordered_set<int> s) {
  // This no longer compiles, which is great
  auto rev_begin = RevIter1<std::unordered_set<int>::iterator>{s.end()};
  auto rev_end = RevIter1<std::unordered_set<int>::iterator>{s.begin()};
}

$ make good-error.out
clang++ -g -stdlib=libc++ -std=c++20 -Wpedantic -Wall -Wextra -Wconversion -Wno-unused-variable -Wno-unused-but-set-variable -fsanitize=address   -c -MMD -o good-error.o good-error.cpp
good-error.cpp:44:20: error: constraints not satisfied for class template 'RevIter1' [with Iter = std::__hash_const_iterator<std::__hash_node<int, void *> *>]
  auto rev_begin = RevIter1<std::unordered_set<int>::iterator>{s.end()};
                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
good-error.cpp:5:15: note: because 'std::__hash_const_iterator<std::__hash_node<int, void *> *>' does not satisfy 'random_access_iterator'
requires std::random_access_iterator<Iter>
              ^
/usr/lib/llvm-13/bin/../include/c++/v1/__iterator/concepts.h:156:3: note: because 'std::__hash_const_iterator<std::__hash_node<int, void *> *>' does not satisfy 'bidirectional_iterator'
  bidirectional_iterator<_Ip> &&
  ^
/usr/lib/llvm-13/bin/../include/c++/v1/__iterator/concepts.h:148:3: note: because 'derived_from<_ITER_CONCEPT<std::__hash_const_iterator<std::__hash_node<int, void *> *> >, std::bidirectional_iterator_tag>' evaluated to false
  derived_from<_ITER_CONCEPT<_Ip>, bidirectional_iterator_tag> &&
  ^
/usr/lib/llvm-13/bin/../include/c++/v1/concepts:161:3: note: because 'is_base_of_v<std::bidirectional_iterator_tag, std::forward_iterator_tag>' evaluated to false
  is_base_of_v<_Bp, _Dp> &&
  ^
good-error.cpp:45:18: error: constraints not satisfied for class template 'RevIter1' [with Iter = std::__hash_const_iterator<std::__hash_node<int, void *> *>]
  auto rev_end = RevIter1<std::unordered_set<int>::iterator>{s.begin()};
                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
good-error.cpp:5:15: note: because 'std::__hash_const_iterator<std::__hash_node<int, void *> *>' does not satisfy 'random_access_iterator'
requires std::random_access_iterator<Iter>
              ^
/usr/lib/llvm-13/bin/../include/c++/v1/__iterator/concepts.h:156:3: note: because 'std::__hash_const_iterator<std::__hash_node<int, void *> *>' does not satisfy 'bidirectional_iterator'
  bidirectional_iterator<_Ip> &&
  ^
/usr/lib/llvm-13/bin/../include/c++/v1/__iterator/concepts.h:148:3: note: because 'derived_from<_ITER_CONCEPT<std::__hash_const_iterator<std::__hash_node<int, void *> *> >, std::bidirectional_iterator_tag>' evaluated to false
  derived_from<_ITER_CONCEPT<_Ip>, bidirectional_iterator_tag> &&
  ^
/usr/lib/llvm-13/bin/../include/c++/v1/concepts:161:3: note: because 'is_base_of_v<std::bidirectional_iterator_tag, std::forward_iterator_tag>' evaluated to false
  is_base_of_v<_Bp, _Dp> &&
  ^
2 errors generated.
make: *** [Makefile:32: good-error.o] Error 1

… okay, maybe I oversold it a little, because this error message is significantly longer. However! I would personally prefer a long error message that exactly explains my problem than a cryptic one. Here, it is clear that the issue is the iterator I’m trying to wrap over is not sufficiently powerful. RevIter1 wants a RandomAccessIterator, but I’ve provided it with a ForwardIterator.

2.4.5 Reverse iterators 4: Finishing up the iterator

Let’s go ahead and implement the rest of the traversal operations. Here, I’ve decided to implement a RandomAccessIterator, because that’s what we need for SimpleVector.

template <typename Iter>
requires std::random_access_iterator<Iter>
struct RevIter4 {
  using post_increment_t = int;

  using Traits = std::iterator_traits<Iter>;
  using difference_type = typename Traits::difference_type;
  using value_type = typename Traits::value_type;
  using pointer = typename Traits::pointer;
  using reference = typename Traits::reference;
  using iterator_category = std::random_access_iterator_tag;

  Iter m_iter;

  reference operator*() const {
    return *(m_iter - 1);
  }
  pointer operator->() const {
    return m_iter - 1;
  }

  RevIter4& operator++() {
    m_iter--;
    return *this;
  }
  RevIter4& operator--() {
    m_iter++;
    return *this;
  }
  RevIter4 operator++(post_increment_t) {
    return {m_iter--};
  }
  RevIter4 operator--(post_increment_t) {
    return {m_iter++};
  }

  RevIter4& operator+=(difference_type n) {
    m_iter -= n;
    return *this;
  }
  RevIter4& operator-=(difference_type n) {
    m_iter += n;
    return *this;
  }

  RevIter4 operator+(difference_type n) {
    return {m_iter - n};
  }
  RevIter4 operator-(difference_type n) {
    return {m_iter + n};
  }
  friend RevIter4 operator+(difference_type n, RevIter4 it) {
    return {it.m_iter - n};
  }
  friend RevIter4 operator-(difference_type n, RevIter4 it) {
    return {it.m_iter + n};
  }

  difference_type operator-(RevIter4 other) {
    return -(m_iter - other.m_iter);
  }

  bool operator==(const RevIter4& other) const = default;
  bool operator<(const RevIter4& o) const {
    return m_iter > o.m_iter;
  }
  bool operator<=(const RevIter4& o) const {
    return m_iter >= o.m_iter;
  }
  bool operator>(const RevIter4& o) const {
    return m_iter < o.m_iter;
  }
  bool operator>=(const RevIter4& o) const {
    return m_iter <= o.m_iter;
  }
  std::strong_ordering operator<=>(const RevIter4& o) const {
    static_assert(std::is_same_v<std::strong_ordering,
                                 decltype(m_iter <=> o.m_iter)>);

    // Instead of the following, we should be using
    //
    // std::compare_strong_order_fallback
    // https://en.cppreference.com/w/cpp/utility/compare/compare_strong_order_fallback
    //
    // but unfortunately as of libc++ 13.0.1, this is not included.
    // (It's probably included in libc++ 14.0.0,
    //  since it only barely missed the merge window for 13.0.1)
    auto cmp = m_iter <=> o.m_iter;

    // https://stackoverflow.com/questions/60087254/how-do-you-reverse-a-strong-ordering
    return 0 <=> cmp;
  }
};

Honestly, it’s not that interesting if you know what you need to implement, and mainly consists of writing a lot of simple code. You might want to peruse the full godbolt link if you want to look at the interim revisions, where I’ve progressively added more traversal operations that correspond to each iterator category between InputIterator and RandomAccessIterator.

Now we can make use of this templated class inside our SimpleVector.

  ElemTy* begin() {
    return m_buffer;
  }
  ElemTy* end() {
    return m_buffer + m_size;
  }
  const ElemTy* begin() const {
    return m_buffer;
  }
  const ElemTy* end() const {
    return m_buffer + m_size;
  }
  const ElemTy* cbegin() const {
    return m_buffer;
  }
  const ElemTy* cend() const {
    return m_buffer + m_size;
  }

  RevIter4<ElemTy*> rbegin() {
    return {end()};
  }
  RevIter4<ElemTy*> rend() {
    return {begin()};
  }
  RevIter4<const ElemTy*> rbegin() const {
    return {end()};
  }
  RevIter4<const ElemTy*> rend() const {
    return {begin()};
  }
  RevIter4<const ElemTy*> crbegin() const {
    return {end()};
  }
  RevIter4<const ElemTy*> crend() const {
    return {begin()};
  }
};

2.4.6 Reverse iterators 5: Possible future work

Of course, if we want our templated struct to be fully generic, we might also want to consider writing a weaker BidirectionalIterator for wrapping over iterators that are bidirectional but not random access. But we won’t cover that here.

2.5 Implementing back_inserter

This time, let’s try writing an OutputIterator!

For a start, we’ll keep a reference to the container we want to insert into in the iterator. That will allow us to call push_back on it later.

template <typename Container>
struct BackIns {
  Container& c;

  ...

Our iterator_category will be std::output_iterator_tag because we don’t support any reading at all. Since all we need to do is make the write operation *(it++) = v perform a push_back, we can overload the assignment operator operator= to do what we need it to do.

We still need to overload operator* and operator++ to make it support the bare minimum iterator API, but they don’t need to do anything. However, note that we can make them do fancier things if we wanted them to.

template <typename Container>
struct BackIns {
  Container* c;  // Pointer not reference, so that this class is Swappable

  using post_increment_t = int;

  using difference_type = void;
  using value_type = void;
  using pointer = void;
  using reference = void;
  using iterator_category = std::output_iterator_tag;

  auto operator*() const {
    return *this;
  }
  auto operator++() {
    return *this;
  }
  auto operator++(post_increment_t) {
    return *this;
  }

  BackIns& operator=(const auto& v) {
    c->push_back(v);
    return *this;
  }
};

template <typename Container>
BackIns<Container> back_inserter(Container& c) {
  return {&c};
}

2.6 Implementing range-based insert_back for SimpleVector

To end things off, let’s show how std::iterator_traits can be used to implement fancy metaprogramming things.

The basic range-based insert_back is the following:

  template <typename InputIt>
  void insert_back_1(InputIt begin, InputIt end) {
    // for (; begin != end; ++begin) {
    //   push_back(*begin);
    // }

    // Conceptually equivalent to
    // std::copy(begin, end, std::back_inserter(*this));
    // But does not work as we don't have the container member types

    // However, our own back_inserter is not so advanced,
    // so we can actually use it

    std::copy(begin, end, back_inserter(*this));
  }

This is great, but the repeated push_back means that we’re performing N memory reallocations! It would be great if we could know how many elements we need to insert, allocate, then copy all in one go.

We rarely actually encounter InputIterators in the real world. Usually, they’re at least ForwardIterators, if they’ve come from some container type, so let’s implement an insert_back in that case.

  template <typename ForwardIt>
  void insert_back_2(ForwardIt begin, ForwardIt end) {
    // We first compute the size
    size_t num_elems = 0;
    for (auto it = begin; it != end; ++begin) {
      ++num_elems;
    }

    // Now we can allocate the new buffer that we know is large enough
    ElemTy* new_buffer = new ElemTy[m_size + num_elems];
    for (size_t i = 0; i < m_size; i++) {
      new_buffer[i] = m_buffer[i];
    }
    // And copy!
    auto it = begin;
    for (size_t i = m_size; i < m_size + num_elems; i++) {
      new_buffer[i] = *it;
      ++it;
    }
    m_size += num_elems;

    delete[] m_buffer;
    m_buffer = new_buffer;
  }

If we had RandomAccessIterators as input, we can do even better and simply compute the size given to us! This avoids an unnecessary O(N) step and decreases the constant factor of our algorithm.

  template <typename RandomIt>
  void insert_back_3(RandomIt begin, RandomIt end) {
    // With RandomIt, it's easier to compute the size
    size_t num_elems = static_cast<size_t>(end - begin);
    // ... the same after this

Now here’s the cool part. We have different algorithms that are best suited for different iterator categories. Using C++20 constraints and std::iterator_traits, we can actually implement all three overloads with the same name, and C++ will pick the correct one for us!

  template <typename InputIt>
  requires std::input_iterator<InputIt>
  void insert_back(InputIt begin, InputIt end) {
    // ...
  }

  template <typename ForwardIt>
  requires std::forward_iterator<ForwardIt>
  void insert_back(ForwardIt begin, ForwardIt end) {
    // ...
  }

  template <typename RandomIt>
  requires std::random_access_iterator<RandomIt>
  void insert_back(RandomIt begin, RandomIt end) {
    // ...
  }

But before we do that, we can actually make our algorithm more succinct by using STL algorithms. As shown earlier, using std::distance, we can measure the distance between ForwardIterators and RandomAccessIterators. We can also use std::copy to make the copying code much shorter.

  template <typename ForwardIt>
  void insert_back_4(ForwardIt begin, ForwardIt end) {
    // For RandomAccessIterators, std::distance just uses operator-
    auto num_elems = static_cast<size_t>(std::distance(begin, end));

    ElemTy* new_buffer = new ElemTy[m_size + num_elems];
    std::copy(m_buffer, m_buffer + m_size, new_buffer);
    std::copy(begin, end, new_buffer + m_size);
    m_size += num_elems;

    delete[] m_buffer;
    m_buffer = new_buffer;
  }

Now we only need to combine two constrained implementations together :)

  template <typename InputIt>
  requires std::input_iterator<InputIt>
  void insert_back_5(InputIt begin, InputIt end) {
    std::copy(begin, end, back_inserter(*this));
  }
  template <typename ForwardIt>
  requires std::forward_iterator<ForwardIt>
  void insert_back_5(ForwardIt begin, ForwardIt end) {
    auto num_elems = static_cast<size_t>(std::distance(begin, end));

    ElemTy* new_buffer = new ElemTy[m_size + num_elems];
    std::copy(m_buffer, m_buffer + m_size, new_buffer);
    std::copy(begin, end, new_buffer + m_size);
    m_size += num_elems;

    delete[] m_buffer;
    m_buffer = new_buffer;
  }

int main() {
  SimpleVector7<int> v1{1, 2, 3};
  SimpleVector7<int> v2{4, 5, 6};
  // Demonstrates:
  //   - insert_back
  //     - which uses back_inserter
  //   - const and reverse iterators
  v1.insert_back_5(v2.crbegin(), v2.crend());
  std::cout << v1 << std::endl;
  return 0;
}

$ ./simple-vector.out
[1, 2, 3, 6, 5, 4]

© 27 June 2022, Tan Chee Kun Thomas, Bernard Teo Zhi Yi, All Rights Reserved

dummy