How to reverse template parameters when tag dispatching is used?

Question

I have been using tag dispatching to model a problem.

Note : This code runs, I am simply interested in a solution that doesn't involve so much coding, only to reverse the arguments of a dispatched algorithm.

Here is the code in question:

#include <iostream>


struct A_tag {}; 
struct B_tag {};

// Tag getter
template<typename Type>
struct get { typedef void tag; }; 

namespace dispatch { 

    template<typename T1, typename T2>
    struct my_algorithm {};

    template<>
    struct my_algorithm<A_tag, B_tag>
    {
        template<typename P1, typename P2> 
        static void apply(P1 const& p1, P2 const& p2) 
        { 
            auto p1val = p1.value(); 
            auto p2val = p2.someFunction();

            std::cout << p1val << " " << p2val << std::endl;
        }  
    };

     //Specialization reversal: can this be made shorter?  
     //A lot of lines used just to reverse the algorithm. 
    template<>
    struct my_algorithm<B_tag, A_tag>
    {
        template<typename P2, typename P1>
        static void apply(P2 const & p2, P1 const & p1)
        {
            my_algorithm<typename get<P1>::tag, typename get<P2>::tag>::apply(p1, p2); 
        }
    };
}

// First and Second are test classes. 
class First
{
    public: 
        double value() const { return 5; };
};

template<>
struct get<First>
{
    typedef A_tag tag; // Expect First to behave as A
};

class Second
{
    public: 
        double someFunction() const { return 6; };
};

template<>
struct get<Second>
{
    typedef B_tag tag; // Expect Second behave as B
};

// Tag dispatcher. 
template<typename P1, typename P2>
void my_algorithm(P1 const & p1, P2 const & p2)
{
    dispatch::my_algorithm<typename get<P1>::tag, typename get<P2>::tag>::apply(p1, p2); 
}

int main(int argc, const char *argv[])
{
    First f; 
    Second s; 

    my_algorithm(f, s);  

    // Commutative algorithm.  
    my_algorithm(s,f); 

    return 0;
}

Some dispatched algorithms work the same irrespective of the order of template parameters. The dispatch::my_algorithm::apply functions do all the work in this example. I have managed to reverse the template parameters using full template specialization for the dispatch::my_algorithm class and calling the static apply function with reversed arguments.

Can the argument reversal be done more quickly? Even if I somehow manage to pack it and "call it" , what happens for other algorithms when apply takes on more arguments?

score 1 · Accepted Answer · answered Jan 20 '14 at 15:55

I would personally think about using overloading, instead of so many classes. And you will also need, somehow, a tag selector.

Let us start with the tag selector.

// Note: to start simply we assume that a tag is only ever present once
//       if not, we just need to add an index.
template <typename Tag,
          typename Type,
          typename std::disable_if<same_type<Tag, typename get<Head>::tag>::type>
struct has_tag: std::false_type {};

template <typename Tag,
          typename Type,
          typename std::enable_if<same_type<Tag, typename get<Head>::tag>::type>
struct has_tag: std::true_type {};

template <typename Tag, typename Head, typename... Tail>
struct tag_selector {
    using type = if_<has_tag<Tag, Head>,
                     Head,
                     typename tag_selector<Tag, Tail...>::type>;
}; // tag_selector

template <typename Tag>
struct tag_selector {}; // compile-time error if tag absent

// A helper function
template <typename Result, typename Head, typename... Tail>
auto tag_select_impl(std::true_type, Head const& head, Tail const&... tail)
    -> Result const&
{
    return Head;
}

template <typename Result, typename Head, typename NH, typename... Tail>
auto tag_select_impl(std::false_type, Head const&, NH const& nh, Tail const&... tail)
    -> Result const&
{
    return tag_select_impl<Result>(has_tag<Tag, NH>{}, nh, tail);
}

// And now the runtime function
template <typename Tag, typename Head, typename... Tail>
auto tag_select(Tag, Head const& head, Tail const&... tail) ->
    typename tag_selector<Tag, Head, Tail...>::type const&
{
    using Result = typename tag_selector<Tag, Head, Tail...>::type;
    return tag_select_impl<Result>(has_tag<Tag, Head>{}, head, tail);
}

So, in brief, all of this is just so that tag_select(tag, args...) returns the first argument that matches the tag. The good news is that it is pretty generic :)

Then, we can actually implement the algorithm:

void internal_impl(First const& first, Second const& second) {
     std::cout << first.value() << " " << second.someFunction() << "\n";
} // internal_impl

template <typename A, typename B>
void interface(A const& a, B const& b) {
    internal_impl(tag_select(A_tag{}, a, b), tag_select(B_tag{}, a, b));
}

Note: the tag select is 1. murky (probably can do cleaner) and 2. only allows const& arguments for now which is annoying; there is probably a way to solve both issues.

+1 :) This is pretty cool. I wondered if variadic templates can be used to reverse N arguments, but I don't know much about them, so I put this on my todo for after I learn more. I've read that structs + static apply could be better than function templates for dispatched algorithms because inheritance and encapsulation can be used (algs that require states, etc). — tmaric, Jan 20 '14 at 16:23
Warning: If you use twice the same tag, you will have the same argument twice (if `get::tag == get::tag`). — Jarod42, Jan 21 '14 at 10:40
@Jarod42: yep, that's what the comment above `has_tag` is about. And furthermore it cannot really be to methods taking the same type twice (but having to shuffle the arguments order). — Matthieu M., Jan 21 '14 at 10:46
@MatthieuM.: I think the ideal solution would be to build an `index_sequence` with index type sorted (I mean from `B, A, A, C` -> `1/*A*/, 2/*A*/, 0/*B*/, 3/*C*/`) and so we can take type by index. — Jarod42, Jan 21 '14 at 11:01
@Jarod42: unfortunately, the problem is *how* to obtain the sequence; should it be `1, 2, 0, 3` or `2, 1, 0, 3` ? — Matthieu M., Jan 21 '14 at 12:08
@MatthieuM.: Those two solutions are equivalent (so good for me). But I agree difficulty is to have at least one of those solutions. — Jarod42, Jan 21 '14 at 12:13
I have done something which creates the sorted `index_sequence` here: http://ideone.com/mA7q7D — Jarod42, Jan 23 '14 at 18:25

score 1 · Answer 2 · answered Jan 20 '14 at 16:26

With tag modification to have an order:

struct A_tag { static const int value = 0; };
struct B_tag { static const int value = 1; };

then with:

template <typename P1, typename P2>
struct ordered_type
{
private:
    typedef typename get<P1>::tag tag_P1;
    typedef typename get<P2>::tag tag_P2;
    static const bool ordered = tag_P1::value <= tag_P2::value;
public:

    typedef typename std::conditional<ordered, tag_P1, tag_P2>::type tag1;
    typedef typename std::conditional<ordered, tag_P2, tag_P1>::type tag2;
    typedef typename std::conditional<ordered, P1, P2>::type type1;
    typedef typename std::conditional<ordered, P2, P1>::type type2;

    static constexpr const type1& getFirst(const P1& p1, const P2& p2)
    {
        return std::get<ordered ? 0 : 1>(std::tie(p1, p2));
    }
    static constexpr const type2& getSecond(const P1& p1, const P2& p2)
    {
        return std::get<ordered ? 1 : 0>(std::tie(p1, p2));
    }
};

You may remove your Specialization reversal and write your tag dispatcher:

// Tag dispatcher.
template<typename P1, typename P2>
void my_algorithm(P1 const & p1, P2 const & p2)
{
    typedef ordered_type<P1, P2> h;

    dispatch::my_algorithm<typename h::tag1,
                           typename h::tag2>::apply(h::getFirst(p1, p2),
                                                    h::getSecond(p1, p2));
}

Thanks, +1 for the tag values, forgot completely about that. What happens when there are say 3 arguments being parsed by the tag dispatcher? — tmaric, Jan 20 '14 at 16:47
@tomislav-maric: this solution works without modification if you have `C_tag::value = 2` and still 2 type to sort. If you want your algorithm to take 3+ arguments, it is feasible but it requires more code to sort the type... — Jarod42, Jan 21 '14 at 10:20

How to reverse template parameters when tag dispatching is used?

2 Answers2