40

I have a template function with varargs template arguments, like this

template<typename Args...>
void ascendingPrint(Args... args) { /* ... */ }

And I want to write

template<typename Args...>
void descendingPrint(Args... args) {
  /* implementation using ascendingPrint()? */
}

How do I reverse the order of the parameter-pack args before passing it along, i.e. in pseudo-code:

template<typename Args...>
void descendingPrint(Args... args) {
  ascendingPrint( reverse(args) );
}
towi
  • 21,587
  • 28
  • 106
  • 187
  • [This one](http://stackoverflow.com/questions/8773426/iterating-variadic-template-arguments-in-reverse-order) could be useful! – Carsten Apr 09 '13 at 14:23
  • @Aschratt I saw that, I think the question title there is misleading. – towi Apr 09 '13 at 14:24
  • 1
    Expanding into a tuple and generating indices in reverse order would be a relatively easy way, although that induces an overhead for constructing the tuple. – Xeo Apr 09 '13 at 14:24
  • @towi: Sorry you did not find an solution there, but I thought the example could fit your requirement: `typename Mapped_scope_deep::type` needs to be written as `typename Mapped_scope_deep::type` – Carsten Apr 09 '13 at 14:25
  • @Xeo Good idea, like [reverse tuple in c++](https://sydius.me/2011/07/reverse-tuple-in-c/). – towi Apr 09 '13 at 14:26

6 Answers6

29

Overall approach and usage

The overal approach consists in packing the arguments into an std::tuple of references, exploiting the perfect forwarding machinery of std::forward_as_tuple().

This means that, at run-time, you should incur in very small overhead and no unnecessary copy/move operations. Also, the framework does not use recursion (apart from compile-time recursion, which is unavoidable for generating indices), so no risk of run-time overhead even in case the compiler would not manage to inline the recursive function calls (which is unlikely anyway, so this is more of an academic argument).

Moreover, this solution is general, in that you can use it as a header-only library to invoke your functions with reversed arguments and with minimum effort: descending_print() should be just a minimal thin wrapper around ascending_print().

Here is how it should look like:

MAKE_REVERT_CALLABLE(ascending_print)

template<typename... Args>
void descending_print(Args&&... args)
{
    revert_call(REVERT_ADAPTER(ascending_print), std::forward<Args>(args)...);
}

What follows is a presentation of the implementation.

First step: reverting a type sequence

Here is a simple way to revert a type sequence:

#include <tuple>
#include <type_traits>

template<typename, typename>
struct append_to_type_seq { };

template<typename T, typename... Ts>
struct append_to_type_seq<T, std::tuple<Ts...>>
{
    using type = std::tuple<Ts..., T>;
};

template<typename... Ts>
struct revert_type_seq
{
    using type = std::tuple<>;
};

template<typename T, typename... Ts>
struct revert_type_seq<T, Ts...>
{
    using type = typename append_to_type_seq<
        T,
        typename revert_type_seq<Ts...>::type
        >::type;
};

A small test program:

int main()
{
    static_assert(
        std::is_same<
            revert_type_seq<char, int, bool>::type,
            std::tuple<bool, int, char>
            >::value,
        "Error"
        );
}

And a live example.

Second step: reverting a tuple

The next step consists in reverting a tuple. Given the usual indices trick machinery:

template <int... Is>
struct index_list { };

namespace detail
{
    template <int MIN, int N, int... Is>
    struct range_builder;

    template <int MIN, int... Is>
    struct range_builder<MIN, MIN, Is...>
    {
        typedef index_list<Is...> type;
    };

    template <int MIN, int N, int... Is>
    struct range_builder : public range_builder<MIN, N - 1, N - 1, Is...>
    { };
}

template<int MIN, int MAX>
using index_range = typename detail::range_builder<MIN, MAX>::type;

Together with the functions defined above, a tuple can easily be reverted this way:

template<typename... Args, int... Is>
typename revert_type_seq<Args...>::type
revert_tuple(std::tuple<Args...> t, index_list<Is...>)
{
    using reverted_tuple = typename revert_type_seq<Args...>::type;

    // Forwarding machinery that handles both lvalues and rvalues...
    auto rt = std::forward_as_tuple(
            std::forward<
                typename std::conditional<
                    std::is_lvalue_reference<
                        typename std::tuple_element<Is, reverted_tuple>::type
                        >::value,
                    typename std::tuple_element<Is, reverted_tuple>::type,
                    typename std::remove_reference<
                        typename std::tuple_element<Is, reverted_tuple>::type
                        >::type
                    >::type
                >(std::get<sizeof...(Args) - Is - 1>(t))...
        );

    return rt;
}

template<typename... Args>
typename revert_type_seq<Args...>::type
revert_tuple(std::tuple<Args...> t)
{
    return revert_tuple(t, index_range<0, sizeof...(Args)>());
}

Here is a simple test program:

#include <iostream>

int main()
{
    std::tuple<int, int, char> t(42, 1729, 'c');
    auto rt = revert_tuple(t);

    std::cout << std::get<0>(rt) << " "; // Prints c
    std::cout << std::get<1>(rt) << " "; // Prints 1729
    std::cout << std::get<2>(rt) << " "; // Prints 42
}

Here is a live example.

Third step: reverting a function's arguments

The final step consists in unpacking the tuple when calling our target function. Here is another generic utility to save us a couple of lines:

template<typename... Args>
typename revert_type_seq<Args...>::type
make_revert(Args&&... args)
{
    auto t = std::forward_as_tuple(std::forward<Args>(args)...);
    return revert_tuple(t);
}

The above function creates a tuple whose elements are the arguments provided, but in reverse order. We are not ready to define our target:

template<typename T>
void ascending_print(T&& t)
{
    std::cout << std::forward<T>(t) << " ";
}

template<typename T, typename... Args>
void ascending_print(T&& t, Args&&... args)
{
    ascending_print(std::forward<T>(t));
    ascending_print(std::forward<Args>(args)...);
}

The above function(s) prints all the arguments provided. And here is how we could write descending_print():

template<typename T, int... Is>
void call_ascending_print(T&& t, index_list<Is...>)
{
    ascending_print(std::get<Is>(std::forward<T>(t))...);
}

template<typename... Args>
void descending_print(Args&&... args) {
    call_ascending_print(make_revert(std::forward<Args>(args)...),
         index_range<0, sizeof...(Args)>());
}

A simple test case again:

int main()
{
    ascending_print(42, 3.14, "Hello, World!");
    std::cout << std::endl;
    descending_print(42, 3.14, "Hello, World!");
}

And of course a live example.

Final step: simplification

The above solution may be non-trivial to understand, but it can be made trivial to use, and quite flexible. Given a couple of generic functions:

template<typename F, typename... Args, int... Is>
void revert_call(F&& f, index_list<Is...>, Args&&... args)
{
    auto rt = make_revert(std::forward<Args>(args)...);
    f(std::get<Is>(rt)...);
}

template<typename F, typename... Args>
void revert_call(F&& f, Args&&... args)
{
    revert_call(f, index_range<0, sizeof...(Args)>(), 
                std::forward<Args>(args)...);
}

And a couple of macro definitions (I couldn't find a way to create an overload set for a function template, sorry):

#define MAKE_REVERT_CALLABLE(func) \
    struct revert_caller_ ## func \
    { \
        template<typename... Args> void operator () (Args&&... args) \
        { func(std::forward<Args>(args)...); } \
    };

#define REVERT_ADAPTER(func) \
    revert_caller_ ## func()

It becomes really easy to adapt any function for being called with arguments in reverse order:

MAKE_REVERT_CALLABLE(ascending_print)

template<typename... Args>
void descending_print(Args&&... args)
{
    revert_call(REVERT_ADAPTER(ascending_print), std::forward<Args>(args)...);
}

int main()
{
    ascending_print(42, 3.14, "Hello, World!");
    std::cout << std::endl;
    descending_print(42, 3.14, "Hello, World!");
}

To conclude, as usual, a live example.

Community
  • 1
  • 1
Andy Prowl
  • 124,023
  • 23
  • 387
  • 451
  • 1
    "I couldn't find a way to create an overload set for a function template" -- Well, my dear friend, have [this](https://dl.dropbox.com/u/14327987/lifting_lambdas.htm)! Hopefully in C++14, anyways. :) – Xeo Apr 09 '13 at 17:03
  • @Xeo: I really hope we will have it! – Andy Prowl Apr 09 '13 at 17:06
  • While I do like your goal to keep the implementation of `descending_print` simple without much boilerplate code in it, have to look into the other solutions if this complexity is really necessary. Although, I like the `MAKE_REVERT_CALLABLE`-idea, which I would have never thought of, (except it being a macro, *smile*) I need to understand why it is required. – towi Apr 10 '13 at 07:28
  • @towi: The macro is necessary because there is no way (yet!) to pass the name of a function template (in this case, `ascending_print()`) as an argument to `revert_call()`, because the name of a function template denotes a whole overload set. Note, that if `ascending_print()` were *not* a template **or** an overloaded function, the macro would not be needed. – Andy Prowl Apr 10 '13 at 07:34
  • @AndyProwl Yes, I understood the macro-necessity, and I looked up N3617. The way through "make revert callable" is what eludes me. I figure, that compared to the other solutions, your solution uses *perfect forwarding* and should therefore be a bit more efficient in the general case? What do you think of @Alex `revert`/`apply`? – towi Apr 10 '13 at 07:42
  • @towi: Alex's solution is neat but uses recursion and leads to many template instantiations. However, this is more of an academic remark, because concretely none of the proposed solutions here should bring any significant run-time penalty; the compiler is expected to inline each function call. However, it does not do perfect forwarding, which is IMO a limitation. Also, a solution that does not use recursion is slightly preferable IMO. – Andy Prowl Apr 10 '13 at 07:49
  • @towi: Xeo's solution is probably as good as mine - he's using an approach I thought of while I was deep into the implementation of mine, so I just did not want to give up ;) My approach shows how to revert a tuple, which might be interesting anyway. It is more compact on the implementation side and (I must admit) smarter than my solution, but (as it is now) requires a bit more on the client's side to invoke a function with reversed arguments. However, a macro could do the trick in his case as well. – Andy Prowl Apr 10 '13 at 07:51
  • @towi: And yes, my solution does perfect-forward the arguments. – Andy Prowl Apr 10 '13 at 07:55
  • @AndyProwl I agree *perfect forwarding* would be preferable, I don't worry about lots of *template instantiations*, tough -- I am a run-time-performance-guy. But very good that you point out that your solution is *recursion-less*, I hadn't realized that, yet. Good point, very good point. That is what the indexing is all about. Ok. – towi Apr 10 '13 at 07:57
  • @towi: Yes, indeed recursion is not needed here - except for computing indices, that just has to be done recursively. I realize in my previous comment, where I was writing ("It is more compact on the implementation side [...]") it may not be clear that I was referring to Xeo's solution - just to clarify. So once more: his solution has a more compact implementation and is a bit smarter than mine, but as it is, requires a bit more of work on the client side - could be fixed, though. – Andy Prowl Apr 10 '13 at 08:05
  • +1 for the sum of your long explanatory text in conjunction with the explanation in the comments. Maybe you can work something of those into the answer -- pointing out the non-recursiveness,the perfect-forwarding, etc. – towi Apr 10 '13 at 08:16
  • @towi: I do mention perfect forwarding already, but I will mention recursion as well. Thank you – Andy Prowl Apr 10 '13 at 08:17
  • @AndyProwl I haven't looked at it, but I would imagine that the implementation of `std::get` requires recursion?!?! – Alex Apr 10 '13 at 08:19
  • @Alex: No, it doesn't. You can have a look at how stdlibc++ implements `std::tuple`, it's done through recursive inheritance at compile-time, not recursive function call at run-time. Thus, accessing a member of the tuple through `get<>` is just the same as accessing a class member – Andy Prowl Apr 10 '13 at 08:24
  • @Alex Firstly, even if `std::get<>` would required to be recursive, since it is part of the StdLib I could envision compiler handling this special -- like some to for `printf`-format-strings. Secondly, if only `get<>` must be template-instantiated it is very likely it imposes no *addition* overhead -- as opposed to instantiating a different template-function by recursion, I guess. But I am still torn -- as I said in an earlier comment, I actually like recursion per-se, and I am a runtime-performabnce-guy, anyway. – towi Apr 10 '13 at 08:25
  • @AndyProwl Ah! So `std::get` is nothing but a `static_cast` (depending on the implementation...) – Alex Apr 10 '13 at 08:34
  • @Alex: [Here](https://ideone.com/hYCz8X)'s something that party implements a reversed `tuple` (called `packer`), and lets overload-resolution do the job of converting to the correct `element`. – Xeo Apr 10 '13 at 08:51
  • @Xeo This is great! A nice reverse-tuple implementation in just a few lines! – Alex Apr 10 '13 at 10:03
24

I think instead of reversing the arguments, you can reverse your logic! For example reverse the operations on arguments.

template <typename T>
void ascendingPrint(const T& x)
{
    cout << x << " ";
}

template<typename T, typename ... Args>
void ascendingPrint(const T& t, Args... args)
{
    ascendingPrint(t);                   // First print `t`
    ascendingPrint(args...);             // Then print others `args...`
}

template <typename T>
void descendingPrint(const T& x)
{
    cout << x << " ";
}

template<typename T, typename ... Args>
void descendingPrint(const T& t, Args... args)
{
    descendingPrint(args...);            // First print others `args...`
    descendingPrint(t);                  // Then print `t`
}

and then

int main()
{
    ascendingPrint(1, 2, 3, 4);
    cout << endl;
    descendingPrint(1, 2, 3, 4);
}

Output

1 2 3 4 
4 3 2 1
masoud
  • 55,379
  • 16
  • 141
  • 208
  • 1
    I like this...it's far easier to read. :) I worry a little bit about the recursion, though. Is there something promising the template will expand to something iterative, or at least tail-recursive? – cHao Apr 09 '13 at 14:59
  • 1
    @cHao - Why, how many arguments do you really have? Hundreds? – Bo Persson Apr 09 '13 at 15:26
  • @BoPersson: I'm more wondering about the potential explosion of templates. Each instance of the template causes instantiation of a version for a subset of its args. If the compiler doesn't promise to inline, passing a dozen args may create a dozen different functions. Or is that not really an issue? – cHao Apr 09 '13 at 16:09
  • 1
    I like it, too. I am a wee bit concerned about *code duplication*. Although, it should be straight forward in almost all situations to reverse the implementation, it introduces non-trivial duplication. – towi Apr 10 '13 at 07:30
  • 3
    +1 for reminding everyone, that generalization is not always the best choice :-) – towi Apr 11 '13 at 07:55
16

Here's the simple approach I mentioned in the comments: Generating indices in reverse and unpacking a tuple with that.

// reversed indices...
template<unsigned... Is> struct seq{ using type = seq; };

template<unsigned I, unsigned... Is>
struct rgen_seq : rgen_seq<I-1, Is..., I-1>{};

template<unsigned... Is>
struct rgen_seq<0, Is...> : seq<Is...>{};

#include <tuple>

namespace aux{
template<class Tup, unsigned... Is>
void descending_print(Tup&& t, seq<Is...>)
{
    ascending_print(std::get<Is>(std::forward<Tup>(t))...);
}
} // aux::

template<class... Args>
void descending_print(Args&&... args)
{
    auto t = std::forward_as_tuple(std::forward<Args>(args)...);
    aux::descending_print(t, rgen_seq<sizeof...(Args)>{});
}

Live example.

Xeo
  • 129,499
  • 52
  • 291
  • 397
  • 1
    Beautiful, and you are promoted by AndyProwl. I give you a +1, too -- but I have to admit I needed his explanations to fully appreciate your code. – towi Apr 10 '13 at 08:19
  • @towi: Maybe [this](http://loungecpp.wikidot.com/tips-and-tricks%3aindices) helps? – Xeo Apr 10 '13 at 08:35
14

Here is a recursive implementation of a specialized revert<>:

// forward decl
template<class ...Tn>
struct revert;

// recursion anchor
template<>
struct revert<>
{
    template<class ...Un>
    static void apply(Un const&... un)
    {
        ascendingPrint(un...);
    }
};

// recursion
template<class T, class ...Tn>
struct revert<T, Tn...> 
{
    template<class ...Un>
    static void apply(T const& t, Tn const&... tn, Un const&... un)
    {
        // bubble 1st parameter backwards
        revert<Tn...>::apply(tn..., t, un...);
    }
};

// using recursive function
template<class A, class ...An>
void descendingPrint(A const& a, An const&... an)
{
    revert<An...>::apply(an..., a);
}

It works with gcc-4.6/7/8 and clang and is probably standard compliant -- the only difficult part being the call of revert<Tn...>::apply(tn..., t, un...).

It has drawbacks though (as recursion often has), that it generates a lot of template-instantiations of the target function (code bloat) and does not use perfect forwarding, which may be an issue (but maybe could be improved to use it).

towi
  • 21,587
  • 28
  • 106
  • 187
Alex
  • 709
  • 3
  • 10
  • Beautiful, and looking like a literal translation of Haskell to TMP /smile/. out This looks simple enough. Why do you say "works with gcc 4.8"? Don't you think its Std? I can't see why it weren't. Are you worried about the multiple *parameter-packs* of `apply`? As far as I remember _function-templates_ **can** have more then one *parameter-pack* -- only _class-templates_ can not. Leaves `apply(tn..., t, un...)` and the question if the compiler can unroll all the arguments correctly. "Proven by example" (gcc) it seems it should, but does the Standard say so, too? – towi Apr 10 '13 at 07:37
  • 2
    @towi Thanks! I think this is std C++, but gcc 4.8 was the only compiler I have tested. [Here](http://liveworkspace.org/code/2Sxk4k$0) is a slightly modified version. Works with gcc 4.6/7/8 and clang, but not with the Intel compiler. – Alex Apr 10 '13 at 08:17
  • 2
    I accepted your answer in favor of the non-recursive ones because I do like recursion myself and this version is the easiest for me to understand.But it was a difficult choice: I urge the readers of this to **read the other answers too**, of [AndyPowl](http://stackoverflow.com/a/15904742/472245) and [Xeo](http://stackoverflow.com/a/15908420/472245), (and maybe the comments) -- they may have benefits you need. And [M-M](http://stackoverflow.com/a/15904836/472245) has a point too, if you do not need a general solution. – towi Apr 11 '13 at 07:54
  • I think it is worth to mention it here that we always force inlining in such recursion situations, which yield in significant performance gain, even with light optimization. – Géza Török Jan 20 '19 at 04:59
  • I know this is nitpicking but "revert" has a different meaning than "reverse". I mention because I think it's probably a hypercorrection; you probably thought that technically "revert" is the verb form of "reverse". But "reverse" is correct as a verb (actually that's how it's most often used). – Arthur Tacca May 10 '20 at 11:50
5

This can be done using C++17 fold expression and a little trick for right-to-left order execution.

#include <iostream>

template< typename T> void print(T&& val) { std::cout << val; }

template< typename ... Types > void descendingPrint(Types&&... vals) {
    int tmps = 0;
    ((print(vals), tmps) = ...);
}

int main() {
    descendingPrint(1, ' ', 2, ' ', 3);
    return 0;
}
user3324131
  • 923
  • 8
  • 10
  • Very clever and concise way of forcing the expanded pack to respect different order of evaluation. Shame that we have to use such tricks, but well, said tricks are not *that* bad. – Fureeish Dec 03 '22 at 12:47
3

My solution supports perfect forwarding and does not involve a recursion:

#include <iostream>
#include <utility>
#include <tuple>

#include <cstdlib>

template< typename ...types >
void
ascendingPrint(types &&... _values)
{
    (std::cout << ... << std::forward< types >(_values)) << std::endl;
}

template< typename ...types, std::size_t ...indices >
void
descendingPrintHelper(std::tuple< types... > const & refs, std::index_sequence< indices... >)
{
    constexpr std::size_t back_index = sizeof...(indices) - 1;
    return ascendingPrint(std::forward< std::tuple_element_t< back_index - indices, std::tuple< types... > > >(std::get< back_index - indices >(refs))...);
}

template< typename ...types >
void
descendingPrint(types &&... _values)
{
    auto const refs = std::forward_as_tuple(std::forward< types >(_values)...);
    return descendingPrintHelper(refs, std::make_index_sequence< sizeof...(types) >{});
}

int
main()
{
    ascendingPrint(1, ' ', 2, ' ', 3);
    descendingPrint(1, ' ', 2, ' ', 3);
    return EXIT_SUCCESS;
}

Live example (or even simplier).

Also modern compilers can perfectly optimize out all the unnecessary stuff: https://godbolt.org/g/01Qf6w

Tomilov Anatoliy
  • 15,657
  • 10
  • 64
  • 169
  • 1
    It should be noted that *fold expressions* are a C++1z feature, and the indices facilities are C++14. The former can be emulated in C++11, the latter can be implemented in C++11. – dyp Jun 25 '15 at 09:48
  • @dyp Also there is `constant evaluation for non-type template arguments` feature involved, but I don't know whether it C++11/4/z or not. – Tomilov Anatoliy Jun 25 '15 at 10:15
  • What do you mean with *constant evaluation for non-type template arguments*? Even C++03 allows using constant expressions as non-type template arguments. – dyp Jun 25 '15 at 10:32
  • @dyp http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4268.html Maybe I am wrong. – Tomilov Anatoliy Jun 25 '15 at 10:44
  • 1
    Ah, note it says *for **all** non-type template arguments*. My earlier statement was too general; constant expressions are allowed since C++03 *for non-type template arguments of integral/enumeration type*. Up to and including C++14, there are restrictions on non-type template arguments of e.g. pointer type. See http://stackoverflow.com/q/15885399/ – dyp Jun 25 '15 at 11:37