Jonathan Boccara's blog

std::index_sequence and its Improvement in C++20

Published March 5, 2021 - 0 Comments

It would be great if we could iterate on the values of a std::tuple like we do for a std::vector or for other STL containers.

But we can’t. To iterate on the values inside of a tuple, we need to proceed in two steps:

  • instantiate a std::index_sequence object with std::make_index_sequence,
  • pass it to another function that performs the iteration.

We’ve seen this in many examples when implementing STL algorithms on tuples.

But in C++20, this becomes a little simpler: we no longer need another function to perform the iteration.

Thanks to Ben Deane for showing this technique to me.

Before C++20: *_impl

For example, to apply a function on each element of tuple before C++20, we have designed the for_each function:

template <class Tuple, class F>
constexpr decltype(auto) for_each(Tuple&& tuple, F&& f)
{
    return for_each_impl(std::forward<Tuple>(tuple), std::forward<F>(f),
                         std::make_index_sequence<std::tuple_size<std::remove_reference_t<Tuple>>::value>{});
}

This function determines the size of the tuple and passes on the responsibility to another function: for_each_impl.

To determine the size of the tuple we use std::tuple_size. But since std::tuple_size only work on tuples and not on references to tuples, we need to remove the potential reference from the type of the incoming parameter.

Indeed, if we pass an lvalue tuple to for_each, the type Tuple is then an lvalue reference.

After determining this size we use it to instantiate a std::index_sequence with std::make_index_sequence. This creates a type that contains a sequence of the integral numbers from 0 up to the size of the tuple minus one.

For example, std::make_index_sequence<10> creates a std::index_sequence<0, 1, 2, 3, 4, 5, 6, 7, 8, 9>.

We can then use the elements of this sequence of integrals to make successive calls to std::get and access the successive elements of the tuple. With C++17’s fold expressions this allow to write this code for for_each_impl:

template <class Tuple, class F, std::size_t... I>
F for_each_impl(Tuple&& tuple, F&& f, std::index_sequence<I...>)
{
    (f(std::get<I>(tuple)), ...);
    return f;
}

This allows to effectively access the successive elements of the tuple (and here, to apply a function on each of them), but at the cost of two technical artefacts:

  • the creation of the std::index_sequence, which takes up a lot of code in for_each,
  • the introduction of the awkwardly named for_each_impl. This name is weird because it doesn’t represent anything in the problem domain. It’s just a technical artefact that takes up some code.

With C++20 lambdas, we can get rid of the indirection of for_each_impl, and have everything in the same function. But we still have to use std::index_sequence.

C++20: everything in one function

One of the many new features of C++20 is an improvement on lambdas: in C++20, lambdas can have a list of template parameters.

This is useful in our case, because we can then have a local lambda in for_each that does what for_each_impl was doing:

template <class Tuple, class F>
constexpr decltype(auto) for_each(Tuple&& tuple, F&& f)
{
    return [] <std::size_t... I>
    (Tuple&& tuple, F&& f, std::index_sequence<I...>)
    {
        (f(std::get<I>(tuple)), ...);
        return f;
    }(std::forward<Tuple>(tuple), std::forward<F>(f),
      std::make_index_sequence<std::tuple_size<std::remove_reference_t<Tuple>>::value>{});
}

The lambda get invoked immediately after it is defined. It is an IILE (immediately invoked lambda expression).

This code is more dense, but we no longer have the meaningless indirection of for_each_impl. Or at least it doesn’t appear as a separate function with a meaningless name.

Lambdas are more powerful than old function objects

Besides the advantages of this technique in itself, there is an interesting observation about the evolution of lambdas.

At the beginning in C++11, lambdas were supposed to replace fully declared function objects (which were often called functors, causing disagreement with the function programming aficionados).

For example, the lambda inside this function:

void f()
{
    int x = 42;
    auto addX = [&x](int i){ return i + x; };

    // ...

Was supposed to replace the more verbose following structure:

void f()
{
    int x = 42;

    class AddX
    {
    public:
        int operator()(int i){ return i + x; };

        explicit AddX(int& x) x_(x);

    private:
        int& x;
    }
    // ...

Lambdas have been catching up with fully defined function objects in terms of features: for example, at the beginning they couldn’t move their captures in. This possibility was added in C++14. They can’t have several overloads. They still can’t, but there is a workaround in C++17 with the “overloaded” technique that consists in inheriting from several lambdas (not our topic here).

With templates though, lambdas go beyond the old function objects. Indeed, it is illegal to define a template in a function object inside a function. Consider the following code to illustrate:

int f()
{
    struct FunctionObject
    {
        template<typename T>
        int operator()(T value){ return value; }
    };

    return FunctionObject{}(41);
}

Since the type using a template is defined inside the function, as a local class, this code is illegal. gcc generates the following error message:

error: invalid declaration of member template in local class

Generalized lambdas made this possible in C++14:

int f()
{
    auto lambda = [] (auto value){ return value + 1; };

    return lambda(41);
}

And now we’re going another step further in this direction by being able to specify the template parameters (which is useless in the below example, but useful with std::index_sequence as shown above):

int f()
{
    auto lambda = [] <typename T>(T value){ return value + 1; };

    return lambda(41);
}

This illustrates the growing power of lambdas that overtook old function objects, and their ability to make our code more and more expressive.

You will also like

Don't want to miss out ? Follow:   twitterlinkedinrss
Share this post!Facebooktwitterlinkedin