Enumerate like Python in C++17 range based for loops

I’m a fan of range based for loops however sometimes access to only the element value is not enough, certain algorithms require the element value and its index. Python has your back in this situation with the enumerate builtin which returns a tuple for each iteration through the container.

for index, value in enumerate(values):
    # ...

Since the addition of structured bindings or decomposition declarations to C++17 I wanted to find out if it was possible to implement an analogous construct using range based for loops.

Enumerate Algorithm

Previously I’ve used a std::for_each like algorithm as suggested on Stack Overflow to solve this problem, it looks like this to use.

enumerate(values.begin(), values.end(), 0,
          [](auto &index, auto &value) {
            // ...
          });

And is implemented as follows, slightly modified for clarity.

template <typename Interator, typename Function>
Function enumerate(Interator first, Interator last, std::size_t initial,
                   Function function) {
  for (; first != last; ++first, ++initial) {
    function(initial, *first);
  }
  return function;
}

The problem I have with this solution is readability, in most cases I find C++ algorithms easier to read because the programmers intent is spelled out in plain English. I don’t feel the same way about std::for_each due to the indentation which clang-format applies to the code. Compared this to a range based for loop which looks like the natural form of a loop to my eyes.

std::for_each(values.begin(), values.end(),
              [](auto &value) {
                // ...
              });

for (auto &value : values) {
  // ...
}

More practically, with std::for_each the lambda function must capture any state it requires from the surrounding scope which ranged based for loop are not limited by. The enumerate algorithm above has the same drawbacks but since this is the closest I’ve been able to get I will use this as the baseline. Here is the code in Matt Godbolt’s compiler explorer with optimizations turned on.

Range Based Enumerate

Begin with the usage code and work backwards.

This is of the best advice I’ve come across when designing API’s, I can’t remember where I heard it first but I’m pretty sure Casey Muratori said it early on in the Handmade Hero series. So here’s what I want the code to look like.

for (auto [index, value] : enumerate(values)) {
  // ...
}

Compare this to the Python snippet from the beginning of the post I believe this is as close as its possible to get using C++17.

for index, value in enumerate(values):
    # ...

Enumerate Iterator

Now that we have the usage code we need to figure out how to actually implement the design. When the compiler finds a range based for loop in your code it essentially turns it into a regular iterator for loop and declares value. The iterator first only exists in the eye of the compiler and has no real name.

for (auto first = std::begin(values), last = std::end(values);
     first != last; ++first) {
  auto &value = *first;
  // ...
}

We can glean three things which are required of the iterator type here.

With this information we can implement the enumerate iterator type.

template <class Iterator>
struct enumerate_iterator {
  using iterator = Iterator;
  using index_type = typename std::iterator_traits<iterator>::difference_type;
  using reference = typename std::iterator_traits<iterator>::reference;

  enumerate_iterator(index_type index, iterator iterator)
      : index(index), iter(iterator) {}

  enumerate_iterator &operator++() {
    ++index;
    ++iter;
    return *this;
  }

  bool operator!=(const enumerate_iterator &other) const {
    return iter != other.iter;
  }

  std::pair<index_type &, reference> operator*() { return {index, *iter}; }

 private:
  index_type index;
  iterator iter;
};

The main point of note is the return type of operator* which is a std::pair of references to the index and iter member variables. This pair is the object with will partake in the decomposition declaration and is analogous to the tuple returned on each iteration by Python’s enumerate builtin.

auto [index, value] = *enumerate_iterator(0, std::begin(values));

My original implementation did not make use of std::pair but instead made use of the excellent guide to Adding C++17 structured binding support to your classes which is the best resource I found on the topic.

Enumerate Range Container

Now that we have an iterator which tracks both the current index and the iterator pointing to the elements value we need a pair of them to demarcate the extent of the range. Essentially we need a container with begin and end member functions and holds the index, first and last iterators from the container being enumerated.

template <class Iterator>
struct enumerate_range {
  using index_type = typename std::iterator_traits<Iterator>::difference_type;
  using iterator = enumerate_iterator<Iterator>;

  enumerate_range(Iterator first, Iterator last, index_type initial)
      : first(first), last(last), initial(initial) {}

  iterator begin() const { return iterator(initial, first); }

  iterator end() const { return iterator(0, last); }

 private:
  Iterator first;
  Iterator last;
  index_type initial;
};

This can be used directly in a range based for loop by explicitly specifying the Iterator template type.

for (auto [index, value] :
     enumerate_range<typename std::vector<float>::iterator>(
         std::begin(values), std::end(values), 0)) {
  // ...
}

Enumerate Functions

The final piece of the puzzle is to use a function template to deduce the type of the iterator which needs to be passed to the enumerate_range class template.

template <class Iterator>
decltype(auto) enumerate(
    Iterator first, Iterator last,
    typename std::iterator_traits<Iterator>::difference_type initial) {
  return enumerate_range(first, last, initial);
}

template <class Container>
decltype(auto) enumerate(Container &content) {
  return enumerate_range(std::begin(content), std::end(content), 0);
}

The first function template implements the general case which allows the user to specify a partial range and the second acts upon the entire range of the container. Here is the entire implementation.

Note the use of non-member begin and end here, this ensures that values can be a C array, thanks to my colleague Simon Brand for pointing this out.

Conclusion

I really enjoyed coming up with this solution especially in conjunction with the compiler explorer, many thanks to Matt Godbolt. If you take the time to compare the generated assembly for enumerate algorithm and my range based enumerate you will see they produce almost identical code at -O1. If you find any bugs or have any suggestions on how it could be improved please get in touch on Twitter using the buttons below.

Disclaimer: I’ve not actually executed any of the range based enumerate code since I don’t have a local C++17 compiler tool-chain handy but would suggest it works when comparing the generated assembly with the enumerate algorithm.