Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Implementing std::tuple From The Ground Up: Part 7, tuple_cat Take 2

DZone's Guide to

Implementing std::tuple From The Ground Up: Part 7, tuple_cat Take 2

·
Free Resource

This is the last post in the series. We have a fully functional tuple class, with a decent implementation of tuple_cat — but some reservations about its performance. In this post we’re going to improve it considerably, at the expense of making the implementation more difficult. The main problem with what we did in the previous post is that we are creating many temporary tuple objects. When concatenating n tuples, we create n-2 intermediatetuples that hold partial results. But can it be avoided?

The idea is very elegant and simple. The core of the concatenation is going to be just one line of code. But it’s an ingenious line of code. Let me show it to you first, so we can bask in its glory:

1. returnmake_tuple(get<Jx>(get<Ix>(forward<Tuples>(tuples)))...);

Now, let’s try to understand what’s going on here; the implementation is going to follow automatically once we figure out the basic idea. The tuples variable is a tuple of tuples. Jxand Ix are parameter packs of size_t‘s, so they can be expanded with get<I>. We set them up in a very specific fashion. For example, suppose we are given three tuples: tuple<int, char>tuple<float>, and tuple<char, bool, long>. The tuples variable is then of typetuple<tuple<int, char>, tuple<float>, tuple<char, bool, long>>, and the parameter packs are: Ix = [0, 0, 1, 2, 2, 2]; Jx = [0, 1, 0, 0, 1, 2]. Now think about the expansion:

1. // Remember the type of 'tuples':
2. //   tuple< tuple<int,char> , tuple<float> , tuple<char,bool,long> > tuples;
3.  
4. make_tuple(
5.   get<0>(get<0>(tuples)), get<1>(get<0>(tuples)),
6.   get<0>(get<1>(tuples)),
7.   get<0>(get<2>(tuples)), get<1>(get<2>(tuples)), get<2>(get<2>(tuples))
8. );

Do you see it? get<0>(tuples) returns the first tuple, and then we retrieve the first and second elements from it; get<1>(tuples) returns the second tuple, and then we retrieve its only element; and so on. If we carefully generate the parameter packs Ix and Jx, we can make the nested get invocation retrieve individual elements from the tuple of tuples, indexing into them like a two-dimensional lattice. Specifically, given ntuples of sizes S(0), …, S(n-1), we need to generate the following sequences:

1.        S(0) times           S(1) times              S(n-1) times
2. Ix = [0, 0, ..., 0,      1, 1, ..., 1,      ..., n-1, n-1, ..., n-1     ]
3. Jx = [0, 1, ..., S(0)-1, 0, 1, ..., S(1)-1, ..., 0 ,  1  , ..., S(n-1)-1]

So, assuming that we have a way of generating both sequences, we can implementtuple_cat very easily now. Here it goes:

01. template<typename... Tuples, size_t... Ix, size_t... Jx>
02. auto cat2d(Tuples&& tuples, index_sequence<Ix...>, index_sequence<Jx...>)
03. {
04.   returnmake_tuple(get<Jx>(get<Ix>(std::forward<Tuples>(tuples)))...);
05. }
06.  
07. template<typename... Tuples>
08. auto tuple_cat(Tuples&&... tuples)
09. {
10.   auto ixs = repeating_index_sequence<
11.     std::integral_constant<size_t, 0>,
12.     tuple_size<std::decay_t<Tuples>::type>::value...
13.   >{};
14.   auto jxs = variable_index_sequence<
15.     tuple_size<std::decay_t<Tuples>::type>::value...
16.   >{};
17.   returncat2d(forward_as_tuple(std::forward<Tuples>(tuples)...), ixs, jxs);
18. }

As always, we use the index_sequence trick to force-feed the parameter packs into thecat2d method. Then, all it has to do is invoke the two-dimensional get. All that remains is implementing the repeating_index_sequence and variable_index_sequence helpers.

Exercise 16: Implement the repeating_index_sequence metafunction. It takes an integral constant 0 as a start value, and the sizes of all tuples, and generates the sequence Ix. For example: repeating_index_sequence<std::integral_constant<size_t, 0>, 2, 1, 3>::type isindex_sequence<0, 0, 1, 2, 2, 2>.

Exercise 17: Implement the variable_index_sequence metafunction. It takes the sizes of alltuples and generates the sequence Jx. For example: variable_index_sequence<2, 1, 3>::type is index_sequence<0, 1, 0, 0, 1, 2>.

Here are the implementations — again, emphasis was put on clarity and not brevity. First, we start with a helper that concatenates index sequences:

01. template<typename...>
02. structcat_index_sequence;
03.  
04. template<size_t... Indices>
05. structcat_index_sequence<index_sequence<Indices...>> : index_sequence<Indices...>
06. {
07. };
08.  
09. template<size_t... Indices1, size_t... Indices2>
10. structcat_index_sequence<index_sequence<Indices1...>, index_sequence<Indices2...>>
11.   : index_sequence<Indices1..., Indices2...>
12. {
13. };
14.  
15. template<size_t... Indices1, size_t... Indices2, typename... Sequences>
16. structcat_index_sequence<
17.   index_sequence<Indices1...>,
18.   index_sequence<Indices2...>,
19.   Sequences...
20. >
21.   : cat_index_sequence<
22.      index_sequence<Indices1..., Indices2...>,
23.      cat_index_sequence<Sequences...>
24.     >
25. {
26. };

Next, a helper that makes a sequence that repeats the element ILength times:

01. template<size_tI, size_tLength>
02. structmake_repeated_sequence : cat_index_sequence<
03.   index_sequence<I>,
04.   typenamemake_repeated_sequence<I, Length - 1>::type
05. >
06. {
07. };
08.  
09. template<size_tI>
10. structmake_repeated_sequence<I, 1> : index_sequence<I>
11. {
12. };

Now we’re ready for repeating_index_sequence. The base case is when there is just oneLength, in which case we generate a sequence with the element I and length Length. Otherwise, we concatenate that sequence with a sequence of I+1 repeated for as many times as specified by the next element in …Lengths:

01. template<typename, size_t...>
02. structrepeating_index_sequence;
03.  
04. template<size_tI, size_tLength>
05. structrepeating_index_sequence<std::integral_constant<size_t, I>, Length>
06.   : make_repeated_sequence<I, Length>
07. {
08. };
09.  
10. template<size_tI, size_tLength, size_t... TailLengths>
11. structrepeating_index_sequence<
12.   std::integral_constant<size_t, I>,
13.   Length,
14.   TailLengths...
15. >
16.   : cat_index_sequence<
17.       typenamemake_repeated_sequence<I, Length>::type,
18.       typenamerepeating_index_sequence<
19.         std::integral_constant<size_t, I + 1>,
20.         TailLengths...
21.       >::type
22.     >
23. {
24. };

And finally variable_index_sequence. The base case is simply make_index_sequence, and the recursive case is a concatenation of that base and the recursively produced sequence:

01. template<size_t...>
02. structvariable_index_sequence;
03.  
04. template<size_tHead>
05. structvariable_index_sequence: make_index_sequence<Head>
06. {
07. };
08.  
09. template<size_tHead, size_t... Tail>
10. structvariable_index_sequence<Head, Tail...>
11.   : cat_index_sequence<
12.       typenamevariable_index_sequence<Head>::type,
13.       typenamevariable_index_sequence<Tail...>::type
14.     >
15. {
16. };

If you fell asleep while we were generating these index sequences, that’s fine. It’s time to wake up though. We now have a complete implementation of tuple_cat. Here are some timing results, measured with clang 3.5. The simple tuples consist only of primitives, whereas the complex tuples have larger objects such as strings embedded in them. (Times are relative to simple tuple/simple cat, which is an arbitrary baseline of 100.)

1.                 simple cat    two-dimensional cat
2. simple tuples   100           71
3. complex tuples  193           88

I think it’s reasonable to say that our efforts paid off — the more complex two-dimensional approach is faster, and doesn’t become much slower if the tuples are more complex.

This concludes our series on implementing tuples. I hope you found it instructive and interesting. tuples offer a variety of opportunities for metaprogramming, optimization, clever and original compile-time thinking, and emphasize the importance of attention to detail. If you liked this series, you might also like the Modern C++ course which I teach at Sela. It’s a 4-day course that covers many topics from modern C++, including advanced template metaprogramming. Oh, and if you followed along and feel confident that you can implement a tuple or extend it? We’re hiring!

I am posting short links and updates on Twitter as well as on this blog. You can follow me: @goldshtn

Topics:

Published at DZone with permission of Sasha Goldshtein, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}