variadic templateで遊ぶ

この記事は、C++ Advent Calendar 2016の5日目の記事です。

まえがき

C++11以降、C++では可変長テンプレートなるものが使えるようになった。要するに0個以上の任意個の型引数を取れるテンプレートである。std::tupleなどでお馴染みだろう。

この記事では、可変長テンプレートを使って様々な(役に立たない)コードを書く予定だ。 事の発端は、以前以下のようなものを作ろうと思い立ってしまったことである。

何をするクラスかというと、template template引数として可変長テンプレートを取るクラスを取り、後続の可変長テンプレート型を逆順にして格納するものだ。

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

可変長テンプレートを取る関数を後ろから処理していくとかではなく、これは型の話である。つまり、こういうことになる。

typename reverse<std::tuple, char, int, double>::type t;
// tはstd::tuple<double, int, char>型

こんなものを作るよりも最初から逆順にして格納すればいいのでは? というのが周囲の普通の反応だったが、例えば任意の長さのtupleを取って反転させる関数を考えると、その返り値の型はまさにこれになる。

template<typename ... Ts>
typename reverse<std::tuple, Ts...>::type
reverse(std::tuple<Ts...> const& t);

私はまだタプルを反転したくなったことはないが、この広い世界のどこかにはタプルを反転したくてたまらない人もいるだろう。多分。

何とかして作り上げて忘れないうちに記事を書いたのだが、少ししてからもっとスッキリと書けることに気づいた。 そして、同様のやり方が他のことに応用できることにも気づいた。というわけで今回はそれについて語ってみたい。

補足しておくと、私は読者層の見当がついていないので、読者はC++テンプレートメタプログラミングにある程度親しんでいると想定している。 テンプレートメタプログラミングとは何か、またそのやり方などはこの記事の主題ではないので、説明不足の点はご容赦いただきたい。

準備

さて、パラメータパックは扱いが難しい。そのままではtypedefができないので、以下のようなことはできないのである。

template<typename ... Ts> struct some_operation; // typedef Ts... types;が定義される
/*...*/
std::tuple<typename some_operation<Ts...>::types> t; // tuple<A, B, C>のようになっている

なのでここを上手く回避する必要がある。 そのついでに、パラメータパックの要素アクセスや変更なども統一してしまえば、大抵の操作は再帰で素直に書けるようになるだろう。

以前はパラメータパックへ先頭要素を追加することだけで満足してしまったが、今回はそこを詰めて、パラメータパックをリストのように使うことを考えてみる。 つまり、「準備」と言ってはいるがここがほぼ本題である。

上記の問題を回避するために、以前も途中で使った空のstructを用いる。

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

種も仕掛けもない空structである。 しかし、これを用いると「パラメータパックを展開して受け取ったpack構造体」という形でパラメータパックを保持・操作できるようになるのだ。 以下ではこれを軸に幾つかの操作を書いていく。

要素アクセス

あると便利なので先頭要素と最後尾を取ってくるstructを作りたい。これは極々素直に実装できる。

template<typename ... T>
struct front;

template<typename T, typename ... Ts>
struct front<pack<T, Ts...>>
{
    typedef T type;
};

template<typename ... T>
struct back;

template<typename T, typename ... Ts>
struct back<pack<T, Ts...>>
{
    typedef typename back<pack<Ts...>>::type type;
};

template<typename T>
struct back<pack<T>>
{
    typedef T type;
};

こんな感じだろうか。typename front<pack<Ts...>>::typeのようにしてpackが持つパラメータパックの先頭要素を取り出せる。 これだけのことならpack<Ts...>にして受ける必要などない(Ts...をそのまま取ればいい)のだが、後々pack<Ts...>を使うことを考えると統一した方が楽になるだろう。

atのようなものを作ることもできる。何番目かを示す数値を受け取ってデクリメントしながらbackと同様に再帰し、0になったらそこで止めればいい。

template<std::size_t N, typename ... T_args>
struct at;

template<std::size_t N, typename T, typename ... T_args>
struct at<N, pack<T, T_args...>>
{
    static_assert(N-1 < sizeof...(T_args), "out_of_range: at");
    typedef typename at<N-1, pack<T_args...>>::type type;
};

template<typename T, typename ... T_args>
struct at<0, pack<T, T_args...>>
{
    typedef T type;
};

要素の変更

次は要素の追加と削除がしたい。 先頭要素なら簡単だ。T, pack<T_args...>を取った場合に特殊化し、pack<T, T_args...>を作れば要素の先頭への追加ができる。 削除はこの逆で、pack<T, T_args...>を受け取ってpack<T_args...>を作れば良い。

template<typename ... T>
struct push_front;

template<typename T, typename ... T_args>
struct push_front<T, pack<T_args...>>
{
    typedef pack<T, T_args...> type;
};

template<typename ... T>
struct pop_front;

template<typename T, typename ... T_args>
struct pop_front<pack<T, T_args...>>
{
    typedef pack<T_args...> type;
};

末尾要素への追加も同様である。

template<typename ... T>
struct push_back;

template<typename T, typename ... T_args>
struct push_back<T, pack<T_args...>>
{
    typedef pack<T_args..., T> type;
};

しかし末尾要素の削除については少々面倒で、以下のようなコードは通らない。パラメータパックは宣言の最後に来なければならないからだ。

template<typename ... T>
struct pop_back;

template<typename ... T_args, typename T>
struct pop_back<pack<T_args..., T>>
{
    typedef pack<T_args...> type;
};

なので再帰で実装する必要がある。最後の要素までは普通に新しいpackにあってよいので、最後の要素にたどり着くまでは要素をpackに格納していく。最後の要素にたどり着いたらそれだけ処理せず返せばよい。

以下の実装では先ほど定義したpush_frontを用いて、最後の要素に辿り着いた時は空のpackが定義され、そのpackに他の要素がpush_frontされていっている。

template<typename ... T>
struct pop_back;

template<typename T, typename ... Ts>
struct pop_back<pack<T, Ts...>>
{
    typedef typename push_front<T, typename pop_back<pack<Ts...>>::type>::type type;
};

template<typename T>
struct pop_back<pack<T>>
{
    typedef pack<> type;
};

連結

packの連結もできるようにしておこう。 パラメータパックは宣言の末尾に来なければ……という話だったが試しに書いてみたら通った。 このあたりの理解度が低いのは問題だ。後で調べよう。

template<typename ... T_args>
struct connect;

template<typename ... T1, typename ... T2>
struct connect<pack<T1...>, pack<T2...>>
{
    typedef pack<T1..., T2...> type;
};

移譲

ところで、ここまで色々用意したが、せっかくごちゃごちゃと弄れるようになったパラメータパックも、packなどという独自のクラスに入ったままだと何の意味もない。 というわけで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;
};

準備はこの位でいいだろうか。では、ここまでの実装をpack.hppにでも保存して、再度reverseの実装に取りかかろう。

reverse

再帰によるreverseの素直な実装は、以下のようなものだろう。haskellを例に取る。知らない人はノリで読んでほしい。

reverse :: [a] -> [a] -- reverseの型:何かのリストを取って何かのリストを返す
reverse [] = []       -- 空リストは反転しても空
reverse (x:xs) = (reverse xs) ++ x -- reverseを再帰的に適用したtailの末尾にheadを足す

準備で作ったものを使えば、pop_frontしたpackreverse再帰的に適用し、その結果のpackに先頭要素をpush_backすればよいことになる。

今回は、packを受け取って反転したpackを返すreverse_implと、 可変長テンプレートと可変長テンプレートを受け取るクラスを受け取って逆順でクラスにテンプレートを与えるreverseクラスを分けて実装することにする。

#include "pack.hpp"
template<typename ... Ts>
struct reverse_impl;

template<typename ... Ts>
struct reverse_impl<pack<Ts...>>
{
    typedef typename push_back<typename front<pack<Ts...>>::type, // 先頭の型
        typename reverse_impl<typename pop_front<pack<Ts...>>::type>::type // 再帰適用
            >::type type; // pack<残りの逆順, 先頭型>
};

template<>
struct reverse_impl<pack<>>
{
    typedef pack<> type; // 空パックは反転しても空。再帰の行き着く先。
};

template<template<typename ... T>class target, typename ... Ts>
struct reverse
{
    typedef typename transfer< // reverse_implの結果出てくるpackの中身をtargetに移す
        target, typename reverse_impl<pack<Ts...>>::type
            >::type type;
};

以前の実装よりもすっきりした(依然としてわかりやすくはないが)

一応確認しておこう。

#include <tuple>

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

max(何が?)

というわけで色々書けそうなので、ついでにもっと色々書いてみる。比較用のクラステンプレートと可変長テンプレートを取って、最大のものを取り出すmaxはどうだろうか。

「大きい方の型」というのはなかなか謎の概念だが、今回は

template<bool B, typename T1, typename T2> struct if_;
template<typename T1, typename T2> struct if_<true,  T1, T2>{typedef T1 type;};
template<typename T1, typename T2> struct if_<false, T1, T2>{typedef T2 type;};

template<typename T1, typename T2>
struct Greater
{
    typedef typename if_<(T1::value > T2::value), T1, T2>::type type;
};

のようなクラスを用いて定義してみる。 ここで実際に比較しているのはGreaterであり、今回は話を簡単にするためにその型の静的メンバ変数valueを比較している。 これはstd::integral_constantを意識してのことだ。 そんなことをするならtemplate<int ... I_args>にすればいいのでは、という気もしたが、型の比較は最悪自分で一つ一つ特殊化して定義することもできるので、これは単に直感的な例に過ぎないことを強調しておきたい。 もう少しまともな例として、sizeof(T)を使って比較することも可能である。

さて、max自体は、要素が2つしかなければその大きい方を、2つ以上なら先頭の2つの要素のうち大きい方だけを残し、再帰的に適用すればできる。

template<template<typename T1, typename T2>class T_larger, typename ... Ts>
struct max_impl;

template<template<typename U1, typename U2>class T_larger,
         typename T1, typename T2, typename ... Ts>
struct max_impl<T_larger, pack<T1, T2, Ts...>>
{
    typedef typename max_impl< //先頭の2つの要素の大きい方だけ残す
        T_larger, pack<typename T_larger<T1, T2>::type, Ts...>>::type type;
};

template<template<typename U1, typename U2>class T_larger, typename T>
struct max_impl<T_larger, pack<T>>
{
    typedef T type; // 最後の一つになったらその型を定義
};

template<template<typename, typename>class T_larger, typename ...Ts>
struct max
{
    // 渡された型をpackに格納してmax_implに渡す
    typedef typename max_impl<T_larger, pack<Ts...>>::type type;
};

動くか確認するために以下のようなコードを書く。

static_assert(std::is_same<
    typename max<Greater,
            std::integral_constant<int, 5>,
            std::integral_constant<int, 1>,
            std::integral_constant<int, 9>,
            std::integral_constant<int, 4>,
            std::integral_constant<int, 6>,
            std::integral_constant<int, 7>,
            std::integral_constant<int, 3>
        >::type,
    std::integral_constant<int, 9>
    >::value, "max");

冒頭で言ったsizeof(T)を用いて比較することも考えてみる。

template<typename T1, typename T2>
struct Greater
{
    typedef typename if_<(sizeof(T1) > sizeof(T2)), T1, T2>::type type;
};

static_assert(std::is_same<
    typename max<Greater, std::int8_t, std::int16_t,
                 std::int32_t, std::int64_t>::type,
    std::int64_t>::value, "max");

もっとも大きい型を取ってくることができた。

foldl

ところで、上記のようなことをするならfoldlが欲しくなってくる。 foldlは、2引数関数、初期値、リストの2つの引数を取り、初期値とリストの先頭要素に第一引数である関数を適用した結果を次の初期値として、リストの残りの部分について再帰する関数だ。 あからさまな再帰なしでリストの全長を処理するのに好都合なものである。

普通に実装するとこうなるのではないか。ちゃんと動くか確認してないけど。

template<typename T, typename Iterator>
T foldl(std::function<T(T, typename std::iterator_traits<Iterator>::value_type)> f,
        T acc, Iterator iter, Iterator end)
{
    return (iter == end) ? acc : foldl(f, f(acc, *iter), std::next(iter), end);
}

というわけで可変長テンプレートで使えるfoldlを実装しよう。

foldlは2つの型を受け取るtemplate template引数と、アキュムレータ、パラメータパックの入ったpackを受けとる。 通常は、関数はそのまま、現在のアキュムレータと先頭要素に関数を適用したものを次のアキュムレータとして、そして先頭要素をpopしたpackを使って再帰する。 再帰の終わりで、packが空になっていればアキュムレータを返す。

template<template<typename, typename> class T_f, typename T_acc, typename ... T_args>
struct foldl;

template<template<typename, typename> class T_f, typename T_acc, typename ... T_args>
struct foldl<T_f, T_acc, pack<T_args...>>
{
    typedef typename foldl<T_f,
            // frontとaccに関数適用
            typename T_f<T_acc, typename front<pack<T_args...>>::type>::type,
            typename pop_front<pack<T_args...>>::type // 先頭以外のリスト
        >::type type;
};

template<template<typename, typename> class T_f, typename T_acc>
struct foldl<T_f, T_acc, pack<>> // パックが空なら
{
    typedef T_acc type;
};

以外にすんなりできた。

これでmaxをやってみる。

static_assert(std::is_same<
    typename foldl<Greater,
            std::integral_constant<int, 5>,
            pack<std::integral_constant<int, 1>,
            std::integral_constant<int, 9>,
            std::integral_constant<int, 4>,
            std::integral_constant<int, 6>,
            std::integral_constant<int, 7>,
            std::integral_constant<int, 3>>
        >::type,
    std::integral_constant<int, 9>
    >::value, "foldl-max");

動いているようなので、maxの実装をこっちに変更してみよう。

template<template<typename T1, typename T2>class T_larger, typename T, typename ... Ts>
struct max
{
    typedef typename foldl<T_larger, T, pack<Ts...>>::type type;
};

quick sort

最後に再帰と言えば、という気持ちのあるクイックソートを実装してみよう。ここでもまずは型の大小関係をあまり深く考えず、簡単にT::valueを比較する。

quicksortは、リストの要素からピボットを一つ選択し、それよりも大きいものと小さいもののリストを作り、それぞれのリストに同じことをする、というソートである。つまり、

[5,1,9,4,6,7,3]

なるリストがあれば、ピボットとして例えば5を選択し、

[1,4,3] ++ 5 ++ [9,6,7]

のようにして、左右のリストで同じことをするのである。

となってくると、リスト内包記法のようなものが欲しい。packの要素から条件に一致するもののみを取り出したpackを簡単に作れるようにしておくと便利だろう。

というわけで先にそちらを作る。まずはboolを受け取って、trueだったときだけ型をpackに追加するクラスを書く。

template<bool cond, typename T, typename ... Ts>
struct conditional_append;

template<typename T, typename ... Ts>
struct conditional_append<true, T, pack<Ts...>> // trueなら
{
    typedef pack<T, Ts...> type; // 先頭に追加
};

template<typename T, typename ... Ts>
struct conditional_append<false, T, pack<Ts...>> // falseなら
{
    typedef pack<Ts...> type; // 何もしない
};

これを使って、template型引数が条件を満たしていればvaluetrueになるようなクラスを受け取り、フィルタするようなクラスを作る。

template<template<typename T>class T_cond, typename ... Ts>
struct filter_impl;

template<template<typename T>class T_cond, typename T1, typename ... Ts>
struct filter_impl<T_cond, pack<T1, Ts...>>
{
    typedef typename conditional_append<T_cond<T1>::value, // 条件式
        T1, typename filter_impl<T_cond, pack<Ts...>>::type // 残りのパックに再帰的に適用したものに追加
            >::type type;
};

template<template<typename T>class T_cond>
struct filter_impl<T_cond, pack<>>
{
    typedef pack<> type; // 空なら何をしようと空
};

template<template<typename T>class T_cond, typename ... Ts>
struct filter
{
    typedef typename filter_impl<T_cond, pack<Ts...>>::type type;
};

ここでは、先頭以外に再帰的にfilter_implを適用したpackに、先頭をconditional_appendしている。

これを使えばquicksortの実装が簡単になるだろう。

template<template<typename T1, typename T2>class T_comp, typename ... Ts>
struct quick_sort_impl;

template<template<typename T1, typename T2>class T_comp,
         typename T_pivot, typename ... Ts>
struct quick_sort_impl<T_comp, pack<T_pivot, Ts...>>
{
    template<template<typename>class T_cond, typename T>
    struct not_
    {
        constexpr static bool value = not T_cond<T>::value;
    };

    template<typename T_lhs> using lcompare = T_comp<T_lhs, T_pivot>;
    template<typename T_rhs> using rcompare = not_<lcompare, T_rhs>;

    typedef typename connect< //左右のpackを繋げる
        typename quick_sort_impl<T_comp, 
            typename filter<lcompare, Ts...>::type>::type, // 左側のpack
        typename push_front<T_pivot, // ピボットを右側のpackの先頭に追加
            typename quick_sort_impl<T_comp,
                typename filter<rcompare, Ts...>::type>::type>::type
            >::type type;
};

template<template<typename T1, typename T2>class T_comp>
struct quick_sort_impl<T_comp, pack<>>
{
    typedef pack<> type;
};

template<template<typename T1, typename T2>class T_comp, typename ... Ts>
struct quick_sort
{
    typedef typename quick_sort_impl<T_comp, pack<Ts...>>::type type;
};

確認のコード。template using aliasでも使えばよかった。

template<typename T1, typename T2>
struct Lesser : std::integral_constant<bool, (T1::value < T2::value)>{};

static_assert(std::is_same<
    quick_sort<Lesser,
            std::integral_constant<int, 5>,
            std::integral_constant<int, 1>,
            std::integral_constant<int, 9>,
            std::integral_constant<int, 4>,
            std::integral_constant<int, 6>,
            std::integral_constant<int, 6>,
            std::integral_constant<int, 7>,
            std::integral_constant<int, 3>
        >::type,
    pack<std::integral_constant<int, 1>,
        std::integral_constant<int, 3>,
        std::integral_constant<int, 4>,
        std::integral_constant<int, 5>,
        std::integral_constant<int, 6>,
        std::integral_constant<int, 6>,
        std::integral_constant<int, 7>,
        std::integral_constant<int, 9>
        >
    >::value, "sort");

あとがき

というわけで、可変長テンプレートを使って色々と役に立たない面白いものを書いてみたつもりである。楽しんでいただけたら幸いである。

今回の実装はあまり深く考えずに何にでもとりあえずpackを使っていたが、例えば最初のmaxの実装にはpackは必要ない。 上手くすれば他のもpackなしでできるかもしれないので、少し考えてみるのもいいかもしれない。

ここで使ったコードは、

github.com

に置かれている。