You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
C++11 introduced tuples to the C++ standard library. As the documentation says they offer a fixed-size collection of heterogeneous values. Unfortunately, tuples can be a little bit tricky to deal with in a generic fashion. The C++14 standard introduced a few features that greatly reduce the necessary boilerplate. In this post I will discuss how to deal with tuples with very compact code.
If you would like to follow along you can find the code examples on GitHub. Build instructions can be found in the Readme file.
Introducing Tuples
The difficulty with tuples in C++ is that they can only be indexed at compile time. The standard library function get accepts the index as a template parameter (i.e. at compile time) and returns a reference to the value at that index. The index has to be a constant expression. It cannot be dynamically generated as e.g. in a for-loop. Furthermore, since tuples can have heterogeneous values and C++ is a statically typed language there is no way to dynamically iterate over the values in a generic tuple. We wouldn’t know their types.
The problem can be circumvented by exploiting variadic templates, and parameter pack expansion. A feature that was also introduced in C++11. It allows to, in a way, iterate over tuple elements at compile time. First, we need to define a type that can hold a parameter pack of indices for a given tuple.
template<size_t...Is>structindex_sequence;
Next, we can use parameter pack expansion to index into a generic tuple.
Which would call some_func with the tuple’s elements unpacked into its argument list.
What’s left is to construct an index_sequence that contains the appropriate parameter pack of indices. The C++14 standard introduced make_index_sequence for that purpose. Before that C++ programmers had to implement it themselves or pick one of the many implementations available on the Internet. E.g. this\(O(\log(N))\) implementation on Stack Overflow.
Implementing Functions on Tuples
With all these tools available in the standard-library we can stop worrying, go ahead, and play with tuples to our heart’s content.
Suppose we wanted to implement a function that takes an arbitrary tuple and returns a new tuple that holds the first N elements of the original tuple. Let’s call it take_front. Since tuples have fixed size the parameter N will have to be a template parameter.
The function take_front_impl takes the input tuple and an index_sequence. As before that second parameter is only there so that we can get our hands on a parameter pack of indices. We then use these indices to get the elements of the input tuple and pass them to make_tuple which will construct the result. However, at that point we haven’t actually defined, yet, which elements should be put into that new tuple. This happens within take_front, which constructs an index-sequence consisting of the indices 0 to N-1 and passes it to take_front_impl.
At this point I should mention that all the code in this article is optimized for readability. In production code you would probably want to qualify members of the std namespace, and use perfect forwarding. You should also be aware that the function make_tuple applies non-trivial transformations to its arguments, such as converting references to values and reference_wrapper to references.
With that out of the way, let’s implement another function on tuples. A very useful function that we might want to implement is apply. It takes a tuple and a callable and calls the callable with the elements of the tuple as arguments. It could for example be used in the following way.
The implementation uses the same trick as take_front before. We construct a parameter pack of integers and use a helper function to extract all the tuple elements.
This function is actually part of the library fundamentals technical specification. Note, however, that I swapped the order of the arguments. It’s a matter of taste but I prefer callable arguments in the end of the parameter list because it allows for more readable in-line lambda definitions.
Don’t Split Your Functions
Both of the above functions take_front, and apply are implemented using the same pattern. We first call make_index_sequence to construct an index_sequence which holds a parameter pack of indices. Then we call a helper function that accesses and unpacks that parameter pack. Unfortunately, this splits the function’s body in two pieces which makes the code harder to read. It is often said that patterns hint at a missing language feature. One could argue that the inability to create and immediately unpack parameter packs in the same place is a lacking language feature. However, here I want to discuss how to, at least, localize that pattern such that we don’t need to define helper functions outside of scope.
C++14 introduced another great feature, namely, variadic lambdas. That feature allows to define a lambda that behaves like a variadic template function. For example the following lambda returns the smallest absolute value of all given parameters.
This implementation uses the initializer list overload of min.
Now, how could we use variadic lambdas to avoid the *_impl pattern from above? A first, naive, approach follows. First, we try to separate the idea of constructing an index sequence in one place and unpacking it in another.
The function index_apply expects a callable and passes it to a helper function alongside a parameter pack of indices from 0 to N-1. That helper function then passes these indices as arguments to the callable. We could now try to implement take_front as follows.
This already looks very promising. We have eliminated the need for a specific helper function and can instead rely on one general helper for (hopefully) all cases. However, unfortunately, that code will not compile. The get template takes the index as a template parameter. Template parameters can only be constant expressions. However, the arguments Is... to the lambda are ordinary (run-time) values of type size_t. Therefore, we cannot use them as template parameters.
Fortunately, there is an easy way around that problem. The standard library defines the template class integral_constant which encapsulates a static constant of a specified type. Since it carries its value in a template parameter that value is a constant expression that can also be used as a parameter to other templates. Conveniently, it also defines an implicit constexpr conversion operator such that we can use an integral_constant object in most places where we need a constant expression of the corresponding value type. With this little helper we can implement index_apply as follows.
Both functions call index_apply, specifying how many elements we want to extract. Then they pass a variadic lambda that expects a parameter pack of indices. These indices are passed as instances of integral_constant. Therefore, they can be used right away as a template argument to get.
A Few More Examples
Now that we have index_apply let’s write two more functions on tuples with its help. First, let’s write a function that takes a tuple and returns a new tuple that contains the original tuple’s elements in reversed order.
Now, let’s move on to a more complex example. We will write a function that takes an arbitrary number of tuples and returns a tuple of tuples, where the first contains all the first elements of the input tuples, the second all the second elements, and so on. We’ll call this function zip. We also specify that when called with zero arguments it just returns an empty tuple. If the tuples are of differing length then we will crop all inputs to match the shortest one. All in all we expect zip to fulfill the following assertions.
It would also make sense to implement the function transpose in terms of zip, which takes a tuple of tuples, interprets it like a matrix, and returns a transposed tuple of tuples.
How could we implement zip? There are a few things that we need. First, we need the length of the shortest tuple. For that purpose we can use min again.
Where we used the fact that min is a constexpr function since C++14.
Next, we need to find a way to go through every tuple and every tuple’s elements simultaneously. Unfortunately, the following, naive, implementation will not compile.
We somehow need to nest two parameter pack expansions. However, in the above code it is ambiguous which pack to expand first. Instead of taking a guess for us the compiler will (thankfully) simply refuse to accept this code.
We can circumvent that problem by splitting the task in two. We can think of the result as a tuple of rows where each row contains the I-th elements of all input tuples. For each row the index is fixed. The outer tuple then contains all those rows. In code that reads as follows.
The lambda row constructs a single row of I-th elements of all tuples. To that end it takes one integral_constant as an argument and uses it to extract one element from each tuple. Within index_apply we then construct a tuple of all rows.
Finally, to handle the empty case we simply provide the following overload.
constexprautozip(){returnmake_tuple();}
With that we have implemented zip to the specification above.
Conclusion
In this article we saw how to reduce the boilerplate when extracting elements out of generic tuples. The presented pattern allows to write the full implementation of a function that deals with generic patterns in one place without having to resort to external helper functions.
If you have any comments, thoughts, or criticism please leave a comment. In any case I hope you enjoyed the article. Thanks for reading!
via Andreas Herrmann
September 12, 2024 at 09:01AM
The text was updated successfully, but these errors were encountered:
Unpacking Tuples in C++14
https://ift.tt/4caMdJS
Andreas Herrmann
C++11 introduced tuples to the C++ standard library. As the documentation says they offer a fixed-size collection of heterogeneous values. Unfortunately, tuples can be a little bit tricky to deal with in a generic fashion. The C++14 standard introduced a few features that greatly reduce the necessary boilerplate. In this post I will discuss how to deal with tuples with very compact code.
If you would like to follow along you can find the code examples on GitHub. Build instructions can be found in the Readme file.
Introducing Tuples
The difficulty with tuples in C++ is that they can only be indexed at compile time. The standard library function
getaccepts the index as a template parameter (i.e. at compile time) and returns a reference to the value at that index. The index has to be a constant expression. It cannot be dynamically generated as e.g. in a for-loop. Furthermore, since tuples can have heterogeneous values and C++ is a statically typed language there is no way to dynamically iterate over the values in a generic tuple. We wouldn’t know their types.The problem can be circumvented by exploiting variadic templates, and parameter pack expansion. A feature that was also introduced in C++11. It allows to, in a way, iterate over tuple elements at compile time. First, we need to define a type that can hold a parameter pack of indices for a given tuple.
Next, we can use parameter pack expansion to index into a generic tuple.
Which would call
some_funcwith the tuple’s elements unpacked into its argument list.What’s left is to construct an
index_sequencethat contains the appropriate parameter pack of indices. The C++14 standard introducedmake_index_sequencefor that purpose. Before that C++ programmers had to implement it themselves or pick one of the many implementations available on the Internet. E.g. this \(O(\log(N))\) implementation on Stack Overflow.Implementing Functions on Tuples
With all these tools available in the standard-library we can stop worrying, go ahead, and play with tuples to our heart’s content.
Suppose we wanted to implement a function that takes an arbitrary tuple and returns a new tuple that holds the first
Nelements of the original tuple. Let’s call ittake_front. Since tuples have fixed size the parameterNwill have to be a template parameter.The function
take_front_impltakes the input tuple and anindex_sequence. As before that second parameter is only there so that we can get our hands on a parameter pack of indices. We then use these indices to get the elements of the input tuple and pass them tomake_tuplewhich will construct the result. However, at that point we haven’t actually defined, yet, which elements should be put into that new tuple. This happens withintake_front, which constructs an index-sequence consisting of the indices0toN-1and passes it totake_front_impl.We can use that function like so.
At this point I should mention that all the code in this article is optimized for readability. In production code you would probably want to qualify members of the
stdnamespace, and use perfect forwarding. You should also be aware that the functionmake_tupleapplies non-trivial transformations to its arguments, such as converting references to values andreference_wrapperto references.With that out of the way, let’s implement another function on tuples. A very useful function that we might want to implement is
apply. It takes a tuple and a callable and calls the callable with the elements of the tuple as arguments. It could for example be used in the following way.The implementation uses the same trick as
take_frontbefore. We construct a parameter pack of integers and use a helper function to extract all the tuple elements.This function is actually part of the library fundamentals technical specification. Note, however, that I swapped the order of the arguments. It’s a matter of taste but I prefer callable arguments in the end of the parameter list because it allows for more readable in-line lambda definitions.
Don’t Split Your Functions
Both of the above functions
take_front, andapplyare implemented using the same pattern. We first callmake_index_sequenceto construct anindex_sequencewhich holds a parameter pack of indices. Then we call a helper function that accesses and unpacks that parameter pack. Unfortunately, this splits the function’s body in two pieces which makes the code harder to read. It is often said that patterns hint at a missing language feature. One could argue that the inability to create and immediately unpack parameter packs in the same place is a lacking language feature. However, here I want to discuss how to, at least, localize that pattern such that we don’t need to define helper functions outside of scope.C++14 introduced another great feature, namely, variadic lambdas. That feature allows to define a lambda that behaves like a variadic template function. For example the following lambda returns the smallest absolute value of all given parameters.
This implementation uses the initializer list overload of
min.Now, how could we use variadic lambdas to avoid the
*_implpattern from above? A first, naive, approach follows. First, we try to separate the idea of constructing an index sequence in one place and unpacking it in another.The function
index_applyexpects a callable and passes it to a helper function alongside a parameter pack of indices from0toN-1. That helper function then passes these indices as arguments to the callable. We could now try to implementtake_frontas follows.This already looks very promising. We have eliminated the need for a specific helper function and can instead rely on one general helper for (hopefully) all cases. However, unfortunately, that code will not compile. The
gettemplate takes the index as a template parameter. Template parameters can only be constant expressions. However, the argumentsIs...to the lambda are ordinary (run-time) values of typesize_t. Therefore, we cannot use them as template parameters.Fortunately, there is an easy way around that problem. The standard library defines the template class
integral_constantwhich encapsulates a static constant of a specified type. Since it carries its value in a template parameter that value is a constant expression that can also be used as a parameter to other templates. Conveniently, it also defines an implicitconstexprconversion operator such that we can use anintegral_constantobject in most places where we need a constant expression of the corresponding value type. With this little helper we can implementindex_applyas follows.This, finally, allows us to implement
take_front, andapplywithout the need for any further helper functions.Both functions call
index_apply, specifying how many elements we want to extract. Then they pass a variadic lambda that expects a parameter pack of indices. These indices are passed as instances ofintegral_constant. Therefore, they can be used right away as a template argument toget.A Few More Examples
Now that we have
index_applylet’s write two more functions on tuples with its help. First, let’s write a function that takes a tuple and returns a new tuple that contains the original tuple’s elements in reversed order.That function is nearly identical to
tuple_frontjust that this time we take the full length, and count the indices that we pass togetbackwards.Now, let’s move on to a more complex example. We will write a function that takes an arbitrary number of tuples and returns a tuple of tuples, where the first contains all the first elements of the input tuples, the second all the second elements, and so on. We’ll call this function
zip. We also specify that when called with zero arguments it just returns an empty tuple. If the tuples are of differing length then we will crop all inputs to match the shortest one. All in all we expectzipto fulfill the following assertions.It would also make sense to implement the function
transposein terms ofzip, which takes a tuple of tuples, interprets it like a matrix, and returns a transposed tuple of tuples.How could we implement
zip? There are a few things that we need. First, we need the length of the shortest tuple. For that purpose we can useminagain.Where we used the fact that
minis aconstexprfunction since C++14.Next, we need to find a way to go through every tuple and every tuple’s elements simultaneously. Unfortunately, the following, naive, implementation will not compile.
We somehow need to nest two parameter pack expansions. However, in the above code it is ambiguous which pack to expand first. Instead of taking a guess for us the compiler will (thankfully) simply refuse to accept this code.
We can circumvent that problem by splitting the task in two. We can think of the result as a tuple of rows where each row contains the
I-th elements of all input tuples. For each row the index is fixed. The outer tuple then contains all those rows. In code that reads as follows.The lambda
rowconstructs a single row ofI-th elements of all tuples. To that end it takes oneintegral_constantas an argument and uses it to extract one element from each tuple. Withinindex_applywe then construct a tuple of all rows.Finally, to handle the empty case we simply provide the following overload.
With that we have implemented
zipto the specification above.Conclusion
In this article we saw how to reduce the boilerplate when extracting elements out of generic tuples. The presented pattern allows to write the full implementation of a function that deals with generic patterns in one place without having to resort to external helper functions.
If you have any comments, thoughts, or criticism please leave a comment. In any case I hope you enjoyed the article. Thanks for reading!
via Andreas Herrmann
September 12, 2024 at 09:01AM
The text was updated successfully, but these errors were encountered: