Therocode's blog

First world problems

Have you ever typed out a loop like this…

const std::vector<T> ts = make();

for(const auto& t : ts)
{
    //...
}

…just to realise that you actually need the index of the item as well? Inconveniently forcing you to rewrite the loop to…

const std::vector<T> ts = make();

for(size_t i = 0; i < ts.size(); ++i)
{
    const T& t = ts[i];
    //...
}

I know I have.

Would it not be nice to be able to just do…

const std::vector<T> ts = make();

for(auto [i, t] : enumerate(ts))
{
    //...
}

While at the same time incurring no overhead? Turns out this is possible, so let’s do it.

The enumerate function

To make it possible to pass the result of enumerate(ts) to a range-based for, we need that object to implement a particular interface. It needs to be possible to call begin() and end() on it, either as free functions or member functions. Those need to return objects that in turn support some functionality of the iterator concept, namely pre-increment, inequality comparison as well as dereferencing to access the item in every iteration.

For us to do what we want, we need to implement that functionality on a simple wrapper that basically just wraps the underlying container’s iterators while also keeping track of the current index.

//templating the container type lets us use it on not just std::vector
template <typename container_type>
constexpr auto enumerate(container_type& c)
{
    return enumerate_wrapper(c);
}

Nothing magical going on here, just returning an instance of enumerate_wrapper which wraps our container.

The enumerate_wrapper type

For the enumerate_wrapper type, let’s start by defining it along with some helpful type aliases that will prove usable later.

template <typename container_type>
struct enumerate_wrapper
{
    using iterator_type = std::conditional_t<std::is_const_v<container_type>, typename container_type::const_iterator, typename container_type::iterator>;
    using pointer_type = std::conditional_t<std::is_const_v<container_type>, typename container_type::const_pointer, typename container_type::pointer>;
    using reference_type = std::conditional_t<std::is_const_v<container_type>, typename container_type::const_reference, typename container_type::reference>;
};

By defining these based on std::is_const_v<container_type> we make sure that if enumerate_wrapper is constructed from a const object, we will get the const versions of the iterators/pointers/references that the container provides. This will make our wrapper work for both const and non-const use cases.

Next up we need to define begin() and end() for the wrapper. begin() is going to be used by the loop to create the initial iterator that is then incremented for every iteration in the loop. It will also be dereferenced to access the value that is given to the user on the other side of the : in the range-based for statement. This means that we need to wrap the begin-iterator in a custom iterator type that keeps track of the index and provides it along with the actual value too.

The end() function does nothing special in the loop mechanism - it will only be used to compare against to see if we are at the end of the loop. Conveniently this means that we can just return the underlying container’s end-iterator.

template <typename container_type>
struct enumerate_wrapper
{
    //...type aliases from above omitted...

    constexpr enumerate_wrapper(container_type& c): container(c)
    {

    }

    constexpr enumerate_wrapper_iter begin()
    {
        //return with 0 becuase this is the first index of the looping
        return {0, std::begin(container)};
    }

    constexpr iterator_type end()
    {
        return std::end(container);
    }

    container_type& container;
};

We store the container inside the wrapper so that we can forward the calls to std::begin() and std::end(). As explained above, enumerate_wrapper_iter is a type we use to wrap the underlying iterator as well as keeping track of the current loop index. Let’s look at how to implement it.

The enumerate_wrapper_iter type

To recap, enumerate_wrapper_iter is used by the for loop to advance the loop, check for termination and passing the iteration values to the user code. To support these things, we need to implement the following.

operator++ which should increment both the index and the underlying iterator
operator!= against the end() iterator to know when the loop is terminating
operator* which should return the current index along with the current item

template <typename container_type>
struct enumerate_wrapper
{
    //...type aliases from above omitted...

    struct enumerate_wrapper_iter
    {
        size_t index;
        iterator_type value;

        constexpr enumerate_wrapper_iter& operator++()
        {
            ++index;
            ++value;
            return *this;
        }

        constexpr bool operator!=(const iterator_type& other) const
        {
            return value != other;
        }

        constexpr std::pair<size_t, reference_type> operator*() {
            return std::pair<size_t, reference_type>{index, *value};
        }
    };

    //...members/methods from above omitted...
};

The increment operator is hopefully clear. It simply increments both the index and the underlying iterator.

A thing that might seem unintuitive with the operator!= is that despite enumerate_wrapper_iter containing both index and value, I chose to only compare value for inequality. Why? Because the purpose of this operator is only to terminate the loop, and we are wrapping a container that already supports checking for loop termination using its own iterators. Hence we gain nothing by adding a comparison to index as well. In that sense, the index member can be viewed as a piece of meta-data which doesn’t take part in the mechanism itself - it only keeps track of the loop count, nothing else.

For the last one, operator*, we need to return both the current index along with the value from the dereferenced underlying iterator. std::pair seems like a handy way of doing this since it supports decomposition using structured bindings (meanings we can use it like auto [a, b] = pair;.

Done

That’s it, now we can use it as we wanted to. It supports both const containers as well as non-const ones and as a bonus since we used the type information provided by the container, it will work with other containers too like std::map for instance.

std::vector<T> ts = make_ts();

for(auto [i, t] : enumerate(ts))
{
    //can modify t
}

const std::map<K, V> map = make_map();

for(auto [i, item] : enumerate(map))
{
    auto [key, value] = item;

    //can't modify value
}

Neat!

How is the overhead?

I tested the code on Godbolt’s Compiler Explorer and aside from one or two instructions differing, it seems to compile down to the exact same binary code as if you’d be keeping track of the index manually alongside an iterator based loop, not bad.

A word of warning regarding structured bindings

While the enumerate() function works as intended, there are some pitfalls that are good to know about regarding structured bindings. For example, look at the following code.

std::vector<T> ts = make_ts();

for(const auto [i, t] : enumerate(ts))
{
    //what properties does t have???
}

The const auto before the structured binding might make you think that both i and t are copied by value and stored as const copies but this is in fact not the case. Remember, the value we return when dereferencing the enumerate_wrapper_iter is of the type std::pair<size_t, T&> and the const-copying will apply to this value itself - not what it contains. So i and t will be references to entries that live in a const std::pair<size_t, T&> which is a copy of what was returned from the enumerate_wrapper_iter instance. Confusing? That is unfortunately the cryptic way that structured bindings work.

This means that if you want to use enumerate() to loop over a container where the value in each iteration is a copy, tough luck! You have to explicitly copy it. Also it means that if you run enumerate() on a container that is not const, then the item of each loop is going to be a modifyable reference, no matter if you do const auto& [i, t] or auto [i, t] or whatever. It is a shame that we can’t control the const-ness of each member of the structured binding.

Maybe future standards will give us better tools to decompose values with more control.

Thanks for reading!

Code

The code is uploaded on github as a single header. Feel free to grab it, use it, modify it.

Enumerate - Range-based for loop with indices retained