Implementing Python's 'enumerate' in C++ // ${CLEVER

Python’s enumerate is handy for when you need both the index and value while iterating a sequence:

for index, value in enumerate(("my", "value", "sequence")):
  print(f'{index}: {value}')

0: my
1: value
2: sequence

However C++ doesn’t support this natively. This is no major revalation - Boost’s indexed does the same thing, and other implementations exist (plug python c++ enumerate into your favorite search engine). However let’s try to build our own, starting with a simple case and iteratively tweaking it to be more generic.

This isn’t trying to make a perfect enumerate clone - instead, this is exploring how to build something simple and then tweak it to support more cases.

Goal

Here is what we want to do:

std::vector<std::string> my_vec = {"enumerating", "all", "values"};
for (const auto& [index, value] : enumerate(my_vec)) {
  std::cout << index << ": " << value << "\n";
}

Conceptually this doesn’t seem too bad:

Create something called enumerate that takes a container
Implement an iterator for enumerate
Make dereferencing the iterator return both a value from the container and a ‘counter’

I mean really how hard could it be? We can do this live in front of an internet audience.

Supporting `std::vector<std::string>`

For our first trick, let’s start simple - make an enumerate that only works with std::vector<std::string> containers. We crack our knuckles and present this:

class enumerate {
 public:
  explicit enumerate(std::vector<std::string>& vec) : vec_(vec) {}

 private:
   std::vector<std::string>& vec_;
};

We want this to work in a range-based for loop. Per the docs , enumerate(my_vec) is the range-expression, which allows ‘objects for which begin and end member functions[…]are defined’. We can do that - we’ll add some members and just delegate to the iterator we already have:

... begin() { return vec_.begin(); }
... end() { return vec_.end(); }

A wrinkle - note the ... return type - what should we return? We can’t just return vec_’s iterator because we need to provide our own dereferencing behavior. Undeterred, we add own custom iterator:

class enumerate {
 public:
  explicit enumerate(std::vector<std::string>& vec) : vec_(vec) {}

  class iterator {
   public:
     explicit iterator(std::vector<std::string>::iterator it) : it_(it) {}

   private:
    std::vector<std::string>::iterator it_;
  };

  iterator begin() { return iterator(vec_.begin()); }
  iterator end() { return iterator(vec_.end()); }

 private:
   std::vector<std::string>& vec_;
};

Surely we’ve done it - let’s run the test program:

int main() {
  std::vector<std::string> string_vec = {"enumerating", "all", "values"};
  for (const auto& [index, value] : enumerate(string_vec)) {
    std::cout << index << ": " << value << "\n";
  }
}

…and:

$ clang++ -std=c++17 enumerate.cc && ./a.out
enumerate.cc:54:35: error: invalid operands to binary expression ('enumerate::iterator' and 'enumerate::iterator')
  for (const auto& [index, value] : enumerate(string_vec)) {
                                  ^
enumerate.cc:54:37: note: in implicit call to 'operator!=' for iterator of type 'enumerate'
  for (const auto& [index, value] : enumerate(string_vec)) {
                                    ^~~~~~~~~
enumerate.cc:45:12: note: selected 'begin' function with iterator type 'enumerate::iterator'
  iterator begin() { return iterator(vec_.begin()); }
           ^
1 error generated.

The crowd is not impressed. This means our iterator doesn’t support operator!=, which is required when comparing iterators. Simple fix - we’ll delegate to the underlying it_’s again:

class iterator {
 public:
   explicit iterator(std::vector<std::string>::iterator it) : it_(it) {}

   friend bool operator!=(const iterator& lhs, const iterator& rhs) {
     return lhs.it_ != rhs.it_;
   }

 private:
  std::vector<std::string>::iterator it_;
};

Success?

$ clang++ -std=c++17 enumerate.cc && ./a.out
enumerate.cc:54:35: error: cannot increment value of type 'enumerate::iterator'
  for (const auto& [index, value] : enumerate(string_vec)) {
                                  ^
enumerate.cc:54:37: note: in implicit call to 'operator++' for iterator of type 'enumerate'
  for (const auto& [index, value] : enumerate(string_vec)) {
                                    ^~~~~~~~~
enumerate.cc:45:12: note: selected 'begin' function with iterator type 'enumerate::iterator'
  iterator begin() { return iterator(vec_.begin()); }
           ^
1 error generated.

The crowd murmurs. Ah right - now we need operator++ to handle incrementing the iterator (we’ll just do preincrement for now):

class iterator {
 public:
   explicit iterator(std::vector<std::string>::iterator it) : it_(it) {}

   friend bool operator!=(const iterator& lhs, const iterator& rhs) {
     return lhs.it_ != rhs.it_;
   }

   iterator operator++() {
     it_++;
     return *this;
   }

 private:
  std::vector<std::string>::iterator it_;
};

Surely this will work!

$ clang++ -std=c++17 enumerate.cc && ./a.out
enumerate.cc:54:35: error: indirection requires pointer operand ('enumerate::iterator' invalid)
  for (const auto& [index, value] : enumerate(string_vec)) {
                                  ^
enumerate.cc:54:37: note: in implicit call to 'operator*' for iterator of type 'enumerate'
  for (const auto& [index, value] : enumerate(string_vec)) {
                                    ^~~~~~~~~
enumerate.cc:45:12: note: selected 'begin' function with iterator type 'enumerate::iterator'
  iterator begin() { return iterator(vec_.begin()); }

Ah yes, the whole reason we are doing this - we need to support dereferencing our iterator, which should return an index and the value of it_ (we’ll just use a pair to hold them both):

class iterator {
 public:
   explicit iterator(std::vector<std::string>::iterator it) : it_(it) {}

   friend bool operator!=(const iterator& lhs, const iterator& rhs) {
     return lhs.it_ != rhs.it_;
   }

   iterator operator++() {
     it_++;
     return *this;
   }

   auto operator*() {
     return std::pair(counter_++, *it_);
   }

 private:
  int32_t counter_ = 0;
  std::vector<std::string>::iterator it_;
};

And we’re in business:

$ clang++ -std=c++17 enumerate.cc && ./a.out
# std::vector<std::string>
0: enumerating
1: all
2: values

The crowd lightly applauds.

Supporting `std::vector<T>`

“I got vectors of int32_t’s, not std::string’s!" cries someone from the back row. ‘Time to break out the templates’ you murmur to yourself. The plan is simple:

Make the class itself a template with a parameter T
Replace std::string with T

template <typename T>
class enumerate {
 public:
  explicit enumerate(std::vector<T>& vec) : vec_(vec) {}

  class iterator {
   public:
     explicit iterator(typename std::vector<T>::iterator it) : it_(it) {}

     friend bool operator!=(const iterator& lhs, const iterator& rhs) {
       return lhs.it_ != rhs.it_;
     }

     iterator operator++() {
       it_++;
       return *this;
     }

     std::pair<int32_t, T> operator*() {
       return {counter_++, *it_};
     }

    private:
      typename std::vector<T>::iterator it_;
      int32_t counter_ = 0;
  };

  iterator begin() { return iterator(vec_.begin()); }
  iterator end() { return iterator(vec_.end()); }

 private:
  std::vector<T>& vec_;
};

“I have just the thing for you”, you confidently proclaim:

$ clang++ -std=c++17 enumerate.cc && ./a.out
# std::vector<std::string>
0: enumerating
1: all
2: values

# std::vector<int32_t>
0: 10
1: 9
2: 8

Supporting all container types

Another audience member, this time closer to the bar - “I want this to work with all STL containers”.

We…hadn’t planned on this. As the panic sets in, we recall that cppreference has a section on the named requirements for a ‘Container’ that has the following table:

name	type
`value_type`	T
`reference`	T&
`const_reference`	const T&
`iterator`	iterator pointing to T
`const_iterator`	constant iterator pointing to T
`difference_type`	signed_integer
`size_type`	unsigned_integer

STL containers provide a value_type typedef to pull the T, as well as iterator’s to get the type of the iterator. So to support all containers, we could:

Change the template parameter to Container (since we’re working with all containers now, not just vector)
Use Container::value_type instead of T to get the value of the types in the container
Use Container::iterator instead of std::vector<T>::iterator

template <typename Container>
class enumerate {
 public:
  using value_type = typename Container::value_type;

  explicit enumerate(Container& vec) : vec_(vec) {}

  class iterator {
   public:
    explicit iterator(typename Container::iterator it) : it_(it) {}

    friend bool operator!=(const iterator& lhs, const iterator& rhs) {
      return lhs.it_ != rhs.it_;
    }

    iterator operator++() {
      it_++;
      return *this;
    }

    std::pair<int32_t, value_type> operator*() { return {counter_++, *it_}; }

   private:
    typename Container::iterator it_;
    int32_t counter_ = 0;
  };

  iterator begin() { return iterator(vec_.begin()); }
  iterator end() { return iterator(vec_.end()); }

 private:
  Container& vec_;
};

Will this satisfy the unruly patron?

$ clang++ -std=c++17 enumerate.cc && ./a.out
...
# std::list
0: using
1: a
2: std::list

# std::map
0: a | 1
1: b | 2

# std::array
0: 1
1: 10
2: 100
3: 1000

We exhale a collective sigh of relief. This also works with associative containers like std::map, but unfortunately nobody seems to care.

Supporting C-style arrays

“Wow” the crowd says, “That looks so robust it must even work with arrays!`".

“Naturally”, you smirk.

“And even C-style arrays!"

<Sweat Intensifies>

Even though std::array is just a light wrapper over a C-style array, it still provides the member types needed for our wrapper and satisfies the ‘Container’ requirements. C-style arrays themselves do not.

Now things get interesting - how do we set up our template to handle C-style arrays, which don’t have any of the members we expect? Well let’s clarify our problem a bit - we don’t actually care about the container having value_type and iterator members - we just care that we have a way to get the container’s value type and iterator.

There is an excellent StackOverflow answer that succinctly describes an approach for just this case, and we’ll use a variant of that here. The gist is that even though a C-style array doesn’t have a .begin() member function, it does work with std::begin . This actually solves all of our problems, but not necessarily in an obvious way.

Iterators

First, the simple part - we currently generate enumerate’s iterators by doing:

iterator begin() { return iterator(vec_.begin()); }
iterator end() { return iterator(vec_.end()); }

This won’t work on C-style arrays because they don’t have .begin() and .end() members. However std::begin (and std::end) handle them just fine:

iterator begin() { return iterator(std::begin(vec_)); }
iterator end() { return iterator(std::end(vec_)); }

Value type

Now for the fun part - how do we get the type? We know that std::begin returns an iterator for a container - what does dereferencing that iterator give you? A value. And how can you get the type of that value? decltype. Putting that together, we can extract the value type of a container by:

Calling std::begin with it
Getting the type of the return value with decltype

The last wrinkle is doing this at compile time. We want to do something like:

using ValueType = decltype(*std::begin(Container));

but Container is a type, not a value. Fortunately, this is just what decltype’s compatriot declval is for:

using ValueType = decltype(*std::begin(std::declval<Container&>()));

Note the & - declval’s return type is T&&, but std::begin on a C-style array expects an lvalue, which you can see on cppreference :

template< class T, std::size_t N >
constexpr T* begin( T (&array)[N] ) noexcept;

So if we did:

using ValueType = decltype(*std::begin(std::declval<Container>()));

The compiler would complain thusly:

enumerate.cc:150:32: error: no matching function for call to 'begin'
  using value_type = decltype(*std::begin(std::declval<Container>()));
                               ^~~~~~~~~~
enumerate.cc:270:37: note: in instantiation of template class 'enumerate<int [3]>' requested here
  for (const auto& [index, value] : enumerate(c_array)) {
                                    ^
range_access.h:90:5: note: candidate function [with _Tp = int, _Nm = 3] not viable: expects an l-value for 1st argument
    begin(_Tp (&__arr)[_Nm]) noexcept

By using std::declval<Container&>() instead, referencing collapsing applies and Container& && turns into Container&, which is what we want.

Iterator type

For Container’s iterator type (to pass to our own iterator), we can do the same thing we did for the value type, just without dereferencing:

using IterType = decltype(std::begin(std::declval<Container&>()));

Nervously, we present the following to the crowd:

template <typename Container>
class enumerate {
 public:
  using IterType = decltype(std::begin(std::declval<Container&>()));
  using ValueType = decltype(*std::begin(std::declval<Container&>()));

  explicit enumerate(Container& container) : container_(container) {}

  class iterator {
   public:
    explicit iterator(IterType it) : it_(it) {}

    friend bool operator!=(const iterator& lhs, const iterator& rhs) {
      return lhs.it_ != rhs.it_;
    }

    iterator operator++() {
      it_++;
      return *this;
    }

    std::pair<int32_t, ValueType> operator*() { return {counter_++, *it_}; }

   private:
    IterType it_;
    int32_t counter_ = 0;
  };

  iterator begin() { return iterator(std::begin(container_)); }
  iterator end() { return iterator(std::end(container_)); }

 private:
  Container& container_;
};

And the results?

$ clang++ -std=c++17 enumerate.cc && ./a.out
...
# C-style array
0: 1000
1: 2000
2: 3000

Supporting temporaries

The masses are overjoyed, you’ve done it. In the front row, clapping furiously, someone turns to their neighbor and exclaims “This must even handle temporaries!". The neighbor’s eyes widen with excitement while yours widen in terror - this definitely doesn’t handle temporaries and you know it.

$ clang++ -std=c++17 enumerate.cc && ./a.out
enumerate.cc:284:37: error: no viable constructor or deduction guide for deduction of template arguments of 'enumerate'
  for (const auto& [index, value] : enumerate(std::move(stuff))) {
                                    ^
enumerate.cc:153:12: note: candidate function [with Container = std::vector<std::__cxx11::basic_string<char>, std::allocator<std::__cxx11::basic_string<char>>>] not viable: expects an l-value for 1st argument
  explicit enumerate(Container& container) : container_(container) {}

enumerate expects an lvalue reference to Container, so passing a temporary naturally fails. The plot thickens!

Universal reference

Recall that we do not want to copy the underlying container, which is why we used a reference. However this won’t work with a temporary, so what can we do?

Channeling Scott Meyers / Effective Modern C++ Item 24, a universal reference (or ‘forwarding reference’, as it is officially called) seems like a good fit. With it, we can bind Container&& to an lvalue or rvalue reference. Right?

template <typename Container>
class enumerate {
 public:
  using IterType = decltype(std::begin(std::declval<Container&>()));
  using ValueType = decltype(*std::begin(std::declval<Container&>()));

  explicit enumerate(Container&& container)
      : container_(std::forward<Container>(container)) {}

Not so fast. As gleaned in Universal References in C++11 (see the section on push_back), Container here is not actually deduced. Why? Because in order to instantiate the template, the type of Container must already be known, so Container&& is not deduced and is just a plain old rvalue reference. This means the code above works if we only pass rvalue references but fails with all of our lvalues.

Fortunately, there is a solution. First, let’s make enumerate a function - that will both help ensure we can get a universal reference and also make our API names a bit nicer (enumerate is a verb and should be a function, not a class). Our class will now be called EnumerateWrapper:

template <typename Container>
class EnumerateWrapper {
  // ...
};

template <typename Container>
auto enumerate(Container&& container) {
  return EnumerateWrapper<Container>(std::forward<Container>(container));
}

Now we’re in a deduced context, and Container&& is a universal reference. While we’re here, let’s add template parameters for IterType and ValueType as well. One (very) subtle reason for this - remember how std::begin only works with lvalue C-style arrays, so we had to do:

using IterType = decltype(std::begin(std::declval<Container&>()));
using ValueType = decltype(*std::begin(std::declval<Container&>()));

to get std::declval to work? Well now we are in a deduced context, so we can drop the &:

template <typename Container,
          typename IterType = decltype(std::begin(std::declval<Container>())),
          typename ValueType = decltype(*std::begin(std::declval<Container>()))>
auto enumerate(Container&& container) {
  return EnumerateWrapper<Container, IterType, ValueType>(
      std::forward<Container>(container));
}

And our EnumerateWrapper (the artist formerly known as enumerate) becomes:

template <typename Container, typename IterType, typename ValueType>
class EnumerateWrapper {
 public:
  explicit EnumerateWrapper(Container vec) : vec_(vec) {}

  class iterator {
   public:
    explicit iterator(IterType it) : it_(it) {}

    friend bool operator!=(const iterator& lhs, const iterator& rhs) {
      return lhs.it_ != rhs.it_;
    }

    iterator operator++() {
      it_++;
      return *this;
    }

    std::pair<int32_t, ValueType> operator*() { return {counter_++, *it_}; }

   private:
    size_t counter_ = 0;
    IterType it_;
  };

  iterator begin() { return iterator(std::begin(vec_)); }
  iterator end() { return iterator(std::end(vec_)); }

 private:
  Container vec_;
};

Please work…

$ clang++ -std=c++17 enumerate.cc && ./a.out
...
# Temporary std::vector<std::string>
0: a
1: b
2: c

Unbelievable. Don’t give the time crowd to ask if it works for temporary C-style arrays (it doesn’t). Instead, take a bow and leave the stage!

Supporting initializer lists

You hear the crowd cheering "Encore!", and you walk back out.

"Anyone ever used an initialzer list?", you inquire.

for (const auto& [index, value] : enumerate({"some", "values", "here")) {
  std::cout << index << ": " << value << "\n";
}

Currently, this fails:

$ clang++ -std=c++17 enumerate.cc && ./a.out
enumerate.cc:339:37: error: no matching function for call to 'enumerate'
  for (const auto& [index, value] : enumerate({"some", "values", "here"})) {
                                    ^~~~~~~~~
enumerate.cc:257:6: note: candidate template ignored: couldn't infer template argument 'Container'
auto enumerate(Container&& container) {
     ^
1 error generated.

There are certainly more elegant/devious ways to do this, but how about a simple one - let’s just add an overload for std::initializer_list<T> and then call our ‘real’ enumerate:

template <typename T>
auto enumerate(std::initializer_list<T>&& container) {
  return enumerate(container);
}

Lo and behold, this works.

$ clang++ -std=c++17 enumerate.cc && ./a.out
...
# Initializer list of std::string
0: some
1: values
2: here

And with that, exit stage left, we’re done!

Wrapping up

The full ‘solution’ is below. There are certainly situations where this doesn’t work, and in reality it isn’t that much more convenient than:

int index = 0;
for (const auto& value : values) {
  std::cout << index++ << ": " << value << "\n";
}

but hey, at least it was an adventure.

Full solution

template <typename Container, typename IterType, typename ValueType>
class EnumerateWrapper {
 public:
  explicit EnumerateWrapper(Container vec) : vec_(vec) {}

  class iterator {
   public:
    explicit iterator(IterType it) : it_(it) {}

    friend bool operator!=(const iterator& lhs, const iterator& rhs) {
      return lhs.it_ != rhs.it_;
    }

    iterator operator++() {
      it_++;
      return *this;
    }

    std::pair<int32_t, ValueType> operator*() { return {counter_++, *it_}; }

   private:
    size_t counter_ = 0;
    IterType it_;
  };

  iterator begin() { return iterator(std::begin(vec_)); }
  iterator end() { return iterator(std::end(vec_)); }

 private:
  Container vec_;
};

template <typename Container,
          typename IterType = decltype(std::begin(std::declval<Container>())),
          typename ValueType = decltype(*std::begin(std::declval<Container>()))>
auto enumerate(Container&& container) {
  return EnumerateWrapper<Container, IterType, ValueType>(
      std::forward<Container>(container));
}

template <typename T>
auto enumerate(std::initializer_list<T>&& container) {
  return enumerate(container);
}