The logic to inverse the indices is not palatable and I could not proceed from this stage.
I take it you are referring to solutions that use std::index_sequence (C++14),
or the like, such as Jonathan Wakeley's',
and that @Columbo's solution in the same vein would be unpalatable too, even if it
it was a C++11 one.
Possibly you dislike "the logic to inverse the indices" because you think it
has an unecessary runtime cost. It has no runtime cost. It's executed at compiletime.
More likely, you know that but just think that this style of solution is inelegant, not
as simple or compact as you'd prefer.
Well, you know this classic recursive algorithm for reversing a sequence S: Take the items of S successively
and push them to the front of another, initially empty sequence S'. At the end, S' is the reverse of S.
There could hardly be anything simpler, and here is a compact C++11 implementation, as applied to tuples.
The header "tuple_plus.h" is assumed to provide your existing definition of the meta-function tuple_reverse
and its prerequisites.
#include "tuple_plus.h"
namespace detail {
template <size_t I, class Wip, typename ...Ts>
Wip
inverse(std::tuple<Ts...> const & model, Wip && wip = std::tuple<>(),
typename std::enable_if<(I >= sizeof...(Ts))>::type * = nullptr)
{
return wip;
}
template <size_t I, class Wip, typename ...Ts>
typename tuple_reverse<std::tuple<Ts...>>::type
inverse(std::tuple<Ts...> const & model, Wip && wip = std::tuple<>(),
typename std::enable_if<(I < sizeof...(Ts))>::type * = nullptr)
{
return
inverse<I + 1>(model,std::tuple_cat(std::make_tuple(std::get<I>(model)),wip));
}
} // namespace detail
template<typename ...Ts>
typename tuple_reverse<std::tuple<Ts...>>::type
inverse(std::tuple<Ts...> const & tup)
{
return detail::inverse<0,std::tuple<>>(tup);
}
Of course we can't just loop over tuple elements, because they can only be accessed via std::get<I>(tup),
for constant index I. So the implementation can't be as compact as it may, say, for std::vector<T>. We
have to follow the usual pattern of template-meta-recursion on index constants. We need a pair of SFINAE overloads,
one getting selected by the compiler when I has the limit value (I >= sizeof...(Ts)) and the other when I has any other
value (I < sizeof...(Ts)). And then we need to implement the function template that you actually want
template<typename ...Ts>
typename tuple_reverse<std::tuple<Ts...>>::type
inverse(std::tuple<Ts...> const & tup);
as a wrapper round this implementation to initialize and conceal the recursion parameters. But with these
unavoidable arrangements, this is the classic sequence-reversing algorithm, applied to tuples in C++11,
without any index_sequence crutches.
N.B. That declaration differs slightly from the one in your post:-
It will accept a 0-length tuple, std::tuple<>, as well as longer tuples. This
is better because your generic definition of the return-type tuple_reverse<Tuple>::type
is specialized for std::tuple<>. So this way the function is defined whenever the
return-type is.
The argument is passed as const &, not just &. You are not going to modify the
input tuple, so the function should accept std::tuple<Ts...> const arguments.
Now I'll explain why this elegant solution is a non-starter, compared with the sort that rests
on index_sequence apparatus.
Here's a program with which you can test a tuple-reversing solution that
fulfils the desired interface.
#include "tuple_plus.h"
#include <type_traits>
///////////////////////////////////////////////////
//
// Paste your implementation here
//
///////////////////////////////////////////////////
///////////////////////////////////////////////////
// Testing it...
#include <iostream>
using namespace std;
struct item
{
static unsigned ctor_count;
static unsigned copy_count;
item()
: id(ctor_count++) {}
item(item const & other)
: id(other.id) {
++copy_count;
}
item & operator=(item const & other) {
id = other.id;
++copy_count;
return *this;
}
static void clear() {
ctor_count = copy_count = 0;
}
unsigned id;
};
unsigned item::ctor_count;
unsigned item::copy_count;
ostream & operator<<(ostream & out, item const & e)
{
return out << "item #" << e.id;
}
template<unsigned I = 0, typename ...Ts>
typename enable_if<(I >= sizeof...(Ts))>::type
tuple_print(tuple<Ts...> const &)
{
cout << "\n";
}
template<unsigned I = 0, typename ...Ts>
typename enable_if<(I < sizeof...(Ts))>::type
tuple_print(tuple<Ts...> const & tup)
{
cout << '[' << get<I>(tup) << "] ";
tuple_print<I + 1>(tup);
}
template<unsigned I>
void test()
{
auto tup_tup =
tuple<
tuple<>,
tuple<item>,
tuple<item,item>,
tuple<item,item,item>,
tuple<item,item,item,item>,
tuple<item,item,item,item,item>,
tuple<item,item,item,item,item,item>>();
item::clear();
auto const & tup = get<I>(tup_tup);
cout << "In..." << endl;
tuple_print(tup);
cout << "Out..." << endl;
tuple_print(inverse(tup));
cout << "To invert a " << I << "-element tuple\n"
<< "I copied " << item::copy_count << " elements\n";
}
int main()
{
test<0>(),test<1>(),test<2>(),test<3>(),test<4>(),test<5>(),test<6>();
return 0;
}
Cut and paste the classic solution at:
// Paste your implementation here
Then compile, with -std=c++11 and run. The output exercises the classic algorithm for
specimen tuples of length 0 to 6, and shows you in each case a) that the algorithm does
indeed reverse the tuple and b) the cost of reversing that tuple, measured in tuple-element copy operatons.
In...
Out...
To invert a 0-element tuple
I copied 0 elements
In...
[item #20]
Out...
[item #20]
To invert a 1-element tuple
I copied 3 elements
In...
[item #19] [item #18]
Out...
[item #18] [item #19]
To invert a 2-element tuple
I copied 7 elements
In...
[item #17] [item #16] [item #15]
Out...
[item #15] [item #16] [item #17]
To invert a 3-element tuple
I copied 12 elements
In...
[item #14] [item #13] [item #12] [item #11]
Out...
[item #11] [item #12] [item #13] [item #14]
To invert a 4-element tuple
I copied 18 elements
In...
[item #10] [item #9] [item #8] [item #7] [item #6]
Out...
[item #6] [item #7] [item #8] [item #9] [item #10]
To invert a 5-element tuple
I copied 25 elements
In...
[item #5] [item #4] [item #3] [item #2] [item #1] [item #0]
Out...
[item #0] [item #1] [item #2] [item #3] [item #4] [item #5]
To invert a 6-element tuple
I copied 33 elements
Investigate the sequence of costs:
0, 3, 7, 12, 18, 25, 33,...
and you can satisfy yourself that it is given by the function:
Cost(n) = (n squared + 5n) / 2
So this algorithm is quadratically costly with tuple-size.
If you want the exercise, you can figure out an implementation, for tuples, of another
stock recursive algorithm for reversing a sequence. Not as simple or
compact as this one, it's the one that goes: Swap the first and last elements of the
sequence, after you have already reversed the sequence in between. The cost may well be lower, but it will still be quadratic.
Which is distressing, because it's well known that reversing a sequence of things
is a linear problem: for instance, an obvious C++ adaptation of the classic algorithm
to reversing an std::vector would have Cost(n) = 4n.
The implicit assumption behind that well known fact is that the sequence is a
Container<T>, for some Container and T; so a reversing algorithm is free to
modify the contained sequence at a position while not modifying it at others, all
the while still having a Container<T>.
But the trouble with reversing an std::tuple is that an
std::tuple<....,A,....,B,....> is an thing of a different type from an
std::tuple<....,B,....,A,....>, and from an std::tuple<....,A,....>. So you can't
actually reverse an std::tuple tup by means of pushing another element on
the front of tup; or swapping the A and B in tup, or the like.
To simulate any such member-wise operation on tup you have to construct a whole
new tuple, of a different type, copying all the elements of tup, and maybe more.
To pick up the banana you have to lift the whole gorilla.
With that in mind, paste @Columbo's implementation into the test program. You'll
need to change invert in his code to inverse. Compile
with std=c++14 and run. (You'll need gcc 4.9 or clang 3.5 for this option,
and gcc 4.9 will emit an unimportant compiler-warning).
Now the output is:
In...
Out...
To invert a 0-element tuple
I copied 0 elements
In...
[item #20]
Out...
[item #20]
To invert a 1-element tuple
I copied 1 elements
In...
[item #19] [item #18]
Out...
[item #18] [item #19]
To invert a 2-element tuple
I copied 2 elements
In...
[item #17] [item #16] [item #15]
Out...
[item #15] [item #16] [item #17]
To invert a 3-element tuple
I copied 3 elements
In...
[item #14] [item #13] [item #12] [item #11]
Out...
[item #11] [item #12] [item #13] [item #14]
To invert a 4-element tuple
I copied 4 elements
In...
[item #10] [item #9] [item #8] [item #7] [item #6]
Out...
[item #6] [item #7] [item #8] [item #9] [item #10]
To invert a 5-element tuple
I copied 5 elements
In...
[item #5] [item #4] [item #3] [item #2] [item #1] [item #0]
Out...
[item #0] [item #1] [item #2] [item #3] [item #4] [item #5]
To invert a 6-element tuple
I copied 6 elements
The sequence of costs is 0,1,2,3,4,5,6,.... For this solution, Cost(n) = n:
it is optimally efficient.
The use of an index_sequence apparatus is in this solution is the essense
of its optimal efficiency. If you are to avoid the quadratic runtime cost of
reversing tup by simulated member-wise operations, the only alternative is
simply to construct the reversed tuple, initialized with elements that
are already mapped, at compiletime, from their counterparts in tup, by the
mapping:
Index I -> tuple_size - I - 1
At runtime, nothing happens but the construction of the reversed tuple,
finished as soon it exists.
But to execute that mapping, at compiletime, you have got to possess a list of the indices to
the elements of tup, at compiletime. That is what the index_sequence
apparatus delivers.
If C++14 is absolutely off-limits, you might accept a flyweight C++11 substitute for
std::index_sequence courtesty of Andy Prowl
With this, you could have the following solution:
namespace detail {
// This is...
template<int... Is>
struct seq { };
template<int N, int... Is>
struct gen_seq : gen_seq<N - 1, N - 1, Is...> { };
template<int... Is>
struct gen_seq<0, Is...> : seq<Is...> {};
// ... the flyweight index_sequence apparatus.
// You can put it in a header.
template<typename Tuple, int ...Is>
typename tuple_reverse<typename std::decay<Tuple>::type>::type
invert(Tuple && tup, seq<Is...>)
{
return
std::make_tuple(
std::get<std::tuple_size<
typename std::decay<Tuple>::type>::value - Is - 1>
(std::forward<Tuple>(tup))...);
}
} //namespace detail
template<typename ...Ts>
typename tuple_reverse<std::tuple<Ts...>>::type
inverse(std::tuple<Ts...> const & tup)
{
return detail::invert(tup,detail::gen_seq<(sizeof...(Ts))>());
}
In the test program, its output is identical to @Columbo's.
Moral: std::index_sequence (or more generally, std::integer_sequence)
is a superbly elegant and fundamental tool for effective TMP in C++.
That's why it's in the Standard Library as of C++14. (BTW, Jonathan
Wakeley is its author`)
