variadic template で reverse

今日、ふと思ってこのようなものを実装できないか考えてみた。

template<template<typename ... T> class target, typename ... T_args>
struct reverse
{
    typedef target</* reversed T_args... */> type;
};

例えば、

typename reverse<std::tuple, int, double, std::string>::type t =
    std::make_tuple("foo", 3.14, 42);

みたいなことができてほしい(今書いているコードでできる必要があったわけではないが……)。とっとと実装を見せろ、という人はこの記事の最後にコードの全体がある。

さて、少し考えてみよう。例えば、最後尾の型を持ってくるのは簡単にできる。

template<typename T_head, typename ... T_args>
struct tail_of
{
    typedef tail_of<T_args...>::type type;
};

template<typename T_head>
struct tail_of<T_head>
{
    typedef T_head type;
};
#include <type_traits>
static_assert(std::is_same<tail_of<char, int, double>::type, double>::value, "tail");

しかし、これではchar, intの方をとってくることはできない。順次適用しようにも、「残りの部分」が指定できていないのでできない。

template<typename ... T_args>
struct reverse
{
    typedef target<tail_of<T_args...>::type, /* ??? */> type;
};

もしtemplate parameter packtypedefできたなら、とも思ったがそれはできない。

template<typename ... T_args>
struct pack
{
    typedef T_args... types;
};

もしそれができたとしても、パラメータパックは宣言時は引数リストの最後にないといけないので(展開時はどこにいてもいいのだが……)、

template<typename ... T_args, typename T_tail>
struct rest_type
{
    typedef T_args... types;
};

のようなことはできない。

ではごく普通にインデックスを使うのはどうだろう。幸いsizeof...(T_args)によってtemplate packの長さはわかる。

しかしこれもダメだ。

template<typename ... T_args>
struct reverse
{
    typedef target<type_at<T_args..., sizeof...(T_args)>::type,
                   type_at<T_args..., sizeof...(T_args)-1>::type,
                   type_at<T_args..., sizeof...(T_args)-2>::type,
                   ... /* と書けたらいいのに! */> type;
};

一度std::tupleで受けてtuple_elementで取り出そうとしても本質的な問題は何も変わらない。

さて、思案どころだ。パラメータパックを分割する方法は上の通り難しそうだ。しかしついこの間すごいH本を読んでいたので、Haskellでの素直なreverseの実装は覚えている。

reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]

これを再現しようとすると、

template<template<typename ... T> class target, typename T_head,
         typename ... T_args>
struct reverse_impl
{
    typedef reverse_impl<T_args...>::types, T_head types;
};

やはりtypedef T_args... types;が欲しい状況になった。

では考え方を変えてみよう(と簡単に言うが実際に変えられたのは1時間近く格闘してからだった)。

reverse' (x:xs) = reverse' xs ++ [x]

この部分のコードは、再帰の毎ステップ(と言っていいのか?)で最後尾のリストが順次追加されていく形になっている。

 ((... ++ [x]) ++ [x]) ++ [x]

もし、template parameter packの先頭への追加ができるなら、これは再現可能になる。では挑戦しよう。 実際に要るものは何かと言うと、以下のようにしてくれるクラスだ。

join<T_head, pack<T_args...>>::type // == pack<T_head, T_args...>

これを実現するには、内部で pack<T_head, T_args...> を定義できる必要があるので、packtemplate template parameterとして渡す必要がある。

template<template<typename... T> class pack, typename ... T_args>
struct join;
template<template<typename... T> class pack, typename T_head,
         typename ... T_args>
struct join<pack, T_head, pack<T_args...>>
{
    typedef pack<T_head, T_args...> type;
};

さて、ではこれを使ってreverseを実装してみよう。

template<template<typename ... T> class target, typename packed,
         typename ... T_args>
struct reverse_impl;

template<template<typename ... T> class target, typename packed,
         typename T_head, typename ... T_args>
struct reverse_impl<target, packed, T_head, T_args...>
{
    typedef typename reverse_impl<target,
                typename join<target, T_head, packed>::type,
                T_args...>::type type;
};

template<template<typename ... T> class target, typename packed>
struct reverse_impl<target, packed>
{
    typedef packed type;
};

template<template<typename ... T> class target,
         typename T_head, typename ... T_args>
struct reverse
{
    typedef typename reverse_impl<target, target<T_head>, T_args...>::type type;
};

もうちょっと弄ればreverse_implを無くせるかもしれないが、なんとなく放置している。

中身で、一般の型template<typename ...T> class targetに直接途中に使う型を代入しているが、これはあまりよくないかもしれない。template引数の数でstatic_assertなんかかけていたら、一発で落ちるだろう。ここはtemplate引数を全て転送するようにするべきかもしれない。

template<typename ... T_args>
struct pack{};

template<template<typename ...T>class target, typename ... T_args>
struct transfer;

template<template<typename ...T>class target, typename ... T_args>
struct transfer<target, pack<T_args...>>
{
    typedef target<T_args...> type;
};

これを使うとすると、上のコードで出てくるtargetは最後以外packに置き換える必要がある。そして、最後の特殊化でtypedef packed type; でなく typedef transfer<target, packed> type;にすればよい。

というわけで以下のようになった。

template<typename ... T_args>
struct pack{};

template<template<typename ...T>class target, typename ... T_args>
struct transfer;

template<template<typename ...T>class target, typename ... T_args>
struct transfer<target, pack<T_args...>>
{
    typedef target<T_args...> type;
};

template<template<typename ... T> class target, typename ... T_args>
struct join;

template<template<typename ... T> class target, typename T, typename ... T_args>
struct join<target, T, target<T_args...>>
{
    typedef target<T, T_args...> type;
};

template<template<typename ... T> class target, typename packed,
         typename ... T_args>
struct reverse_impl;

template<template<typename ... T> class target, typename packed,
         typename T_head, typename ... T_args>
struct reverse_impl<target, packed, T_head, T_args...>
{
    typedef typename reverse_impl<target,
                typename join<pack, T_head, packed>::type,
                T_args...>::type type;
};

template<template<typename ... T> class target, typename packed>
struct reverse_impl<target, packed>
{
    typedef typename transfer<target, packed>::type type;
};

template<template<typename ... T> class target, typename ... T_args>
struct reverse
{
    typedef typename reverse_impl<target, pack<>, T_args...>::type type;
};


#include <type_traits>
#include <tuple>

static_assert(
    std::is_same<typename reverse<std::tuple, char, int, short, double>::type,
                 std::tuple<double, short, int, char>>::value,
    "reverse: 4 argument tuple");

static_assert(
    std::is_same<typename reverse<std::tuple, char, int, double>::type,
                 std::tuple<double, int, char>>::value,
    "reverse: 3 argument tuple");

static_assert(
    std::is_same<typename reverse<std::tuple, char, int>::type,
                 std::tuple<int, char>>::value,
    "reverse: 2 argument tuple");

static_assert(
    std::is_same<typename reverse<std::tuple, char>::type,
                 std::tuple<char>>::value,
    "reverse: 1 argument tuple");

static_assert(
    std::is_same<typename reverse<std::tuple>::type,
                 std::tuple<>>::value,
    "reverse: 0 argument tuple");

#include <iostream>
int main()
{
    typename reverse<std::tuple, char, int, double>::type t;
    std::get<0>(t) = 3.14;
    std::get<1>(t) = 42;
    std::get<2>(t) = 'a';

    std::cout << "std::get<0>(t) = " << std::get<0>(t) << std::endl;
    std::cout << "std::get<1>(t) = " << std::get<1>(t) << std::endl;
    std::cout << "std::get<2>(t) = " << std::get<2>(t) << std::endl;
    return 0;
}

結構長くなってしまったが、使い道はあるのだろうか。