可変長引数テンプレートをメタ配列として扱う part2

どうも。
闇のプログラミングの時間です。
記事を投稿するごとに何時使うんだこれって言いたくなるようなネタばかり書いている気がしますが、私はげんきです。

さて、ずいぶん日が開いてしまいましたが、前回の続きです。
前回は、std::integer_sequenceライクな定数配列クラスを扱いました。
今回はそれの型バージョンの話になります。

型の配列に関しては、前回の記事でも一部出現する箇所があったので、前方宣言だけは書いてあったと思います。

c++

namespace geranium {

template<typename ...Args>
class type_sequence;

}

実装する内容は前回と同じような感じです。ただし、型と値では同じようには行かない部分も多いので、同じ名前でもテンプレートエイリアスになっていたり、消えているメンバがあったりします。

make_type_sequence

先に便利なテンプレートエイリアスを作っておきます。
前回のmake_integer_sequenceが1ずつ増加する数列を作成するものであったのに対し、今回のmake_type_sequenceは同じ型をn個並べたtype_sequenceを作るものです。

c++

namespace geranium {

template<typename ...Args>
class type_sequence;

// Tが型type_sequenceかどうか調べる
template<typename T>
struct is_type_sequence: std::false_type {};

template<typename ...Args>
struct is_type_sequence<type_sequence<Args...>>: std::true_type {};

namespace _detail {

template<typename T, std::size_t n>
struct _make_type_sequence
{
    using type =
        typename _make_type_sequence<T, n/2>::type::
        template join<typename _make_type_sequence<T, (n+1)/2>::type>;
};

template<typename T>
struct _make_type_sequence<T, 1>
{
    using type = type_sequence<T>;
};

template<typename T>
struct _make_type_sequence<T, 0>
{
    using type = type_sequence<>;
};

}

template<typename T, std::size_t n>
using make_type_sequence =
    typename _detail::_make_type_sequence<T, n>::type;

}

やり方は前回と似たような感じです。2分割したものを結合するようにして作成しているので、log(n)の再帰で作成できます。理論的にはtype_sequence<int, int, ...(intが10000個)>みたいなのも作れるはず。ただし、コンパイルにはむちゃくちゃ時間がかかることが予想されます。

type_sequence<>

次に、空のtype_sequenceに対する特殊化を作ります。
特殊化なしでやろうとしたんですが無理でした。特殊化すると拡張した時に二回書かないといけないものがあったりして面倒なのですが、仕方ありません。

c++

namespace geranium {

template<>
class type_sequence<> {
public:
    using size_type = std::size_t;

    static constexpr size_type npos = static_cast<size_type>(-1);
    static inline constexpr size_type size() noexcept { return 0; }

    // テンプレートUを特殊化したクラスを返す
    template<template<class ...> class U>
    using unpack = U<>;

    // テンプレートUを利用して、Args...それぞれから生成した型を並べたtype_sequenceを返す
    template<template<class> class U>
    using type_map = type_sequence<>;

    // Args... を末尾に追加して作成したtype_sequenceを返す
    template<typename ...Args2>
    using append = type_sequence<Args2...>;

    // Args... を先頭に追加して作成したtype_sequenceを返す
    template<typename ...Args2>
    using prepend = type_sequence<Args2...>;

    // 他のinteger_sequenceと結合して作成したtype_sequenceを返す
    template<typename U, GERANIUM_ENABLE_WHEN(is_type_sequence<U>())>
    using join = U;

    // n番目からm-1番めを切り取って作成したtype_sequenceを返す
    template<std::size_t n = 0, std::size_t m = 0,
        GERANIUM_ENABLE_WHEN(n==0&&m==0)>
    using slice = type_sequence<>;

    // 先頭からn個を切り取って作成したtype_sequenceを返す
    template<std::size_t n = 1>
    using head = slice<0, n>;

    // 末尾からn個を切り取って作成したtype_sequenceを返す
    template<size_type n = 1>
    using tail = slice<size()-n>;

    // n番目にargs2...を挿入して作成したtype_sequenceを返す
    template<size_type n, typename ...Args2>
    using insert = typename head<n>::template append<Args2...>::
        template join<tail<size()-n>>;

    // n番目からc個を削除した残りで作成したtype_sequenceを返す
    template<size_type n, size_type c = 1>
    using erase = typename head<n>::template join<tail<size()-n-c>>;

    // args...を逆転して作成したtype_sequenceを返す
    using reverse = type_sequence<>;

    // 最初にvalueが見つかる位置を探す
    template<typename T>
    static inline constexpr std::size_t find() { return 0; }  

};

}

wrapper<T>

可変長引数リストからn番目の型を再帰によらずに取り出すために用意します。

c++

namespace geranium {
namespace _detail {

struct wrapper_base {};

template<typename T>
struct wrapper: wrapper_base {};

template<typename ...Args2>
struct types_at {
    template<typename T>
    static T call(Args2..., _detail::wrapper<T>, ...);
};

}
}

type_sequence<Args...>

そして本体です。

c++

namespace geranium {

template<typename T, typename ...Args>
struct type_find;

template<typename ...Args>
class type_sequence {
public:
    using size_type = std::size_t;

    static constexpr size_type npos = static_cast<size_type>(-1);
    static inline constexpr size_type size() noexcept { return sizeof...(Args); }

    // テンプレートUを特殊化したクラスを返す
    template<template<class ...> class U>
    using unpack = U<Args...>;

    // テンプレートUを利用して、Args...それぞれから生成した型を並べたtype_sequenceを返す
    template<template<class> class U>
    using type_map = type_sequence<typename U<Args>::type ...>;

    // Args... を末尾に追加して作成したtype_sequenceを返す
    template<typename ...Args2>
    using append = type_sequence<Args..., Args2...>;

    // Args... を先頭に追加して作成したtype_sequenceを返す
    template<typename ...Args2>
    using prepend = type_sequence<Args2..., Args...>;

    // 他のinteger_sequenceと結合して作成したinteger_sequenceを返す
    template<typename U, GERANIUM_ENABLE_WHEN(is_type_sequence<U>())>
    using join = typename U::template prepend<Args...>;

    // Args...のn番目の型を返す。
    template<size_type n>
    using at = decltype(make_type_sequence<_detail::wrapper_base, n>::
        template unpack<_detail::types_at>::call(_detail::wrapper<Args>{}...));

    // 先頭を返す
    using front = at<0>;

    // 末尾を返す
    using back = at<size()-1>;

    template<size_type  ...indices>
    struct _slice
    {
        using type = type_sequence<at<indices>...>;
    };

    // n番目からm-1番めを切り取って作成したtype_sequenceを返す
    template<std::size_t n = 0, std::size_t m = size(),
        GERANIUM_ENABLE_WHEN(n<=m&&m<=size())>
    using slice = typename make_integer_sequence<std::size_t, n, m-n>::
        template unpack<_slice>::type;

    // 先頭からn個を切り取って作成したtype_sequenceを返す
    template<std::size_t n = 1>
    using head = slice<0, n>;

    // 末尾からn個を切り取って作成したtype_sequenceを返す
    template<size_type n = 1>
    using tail = slice<size()-n>;

    // n番目にargs2...を挿入して作成したtype_sequenceを返す
    template<size_type n, typename ...Args2>
    using insert = typename head<n>::template append<Args2...>::
        template join<tail<size()-n>>;

    // n番目からc個を削除した残りで作成したtype_sequenceを返す
    template<size_type n, size_type c = 1>
    using erase = typename head<n>::template join<tail<size()-n-c>>;

    // Args...を逆転して作成したtype_sequenceを返す
    template<size_type n>
    struct _reverse {
        using type = at<size()-n-1>;
    };
    using reverse = 
        typename make_index_sequence<size()>::
            template type_map<_reverse>;

    // 最初にTが見つかる位置を探す
    template<typename T>
    static constexpr inline size_type find() noexcept {
        return type_find<T, Args...>::value;
    }

};

namespace _detail {

template<typename T, typename ...Args>
struct type_find;

template<typename T>
struct type_find<T> {
    static constexpr std::size_t length = 0;
    static constexpr std::size_t npos = static_cast<std::size_t>(-1);
    static constexpr std::size_t value = npos;
};

template<typename T1, typename T2>
struct type_find<T1, T2> {
    static constexpr std::size_t length = 1;
    static constexpr std::size_t npos = static_cast<std::size_t>(-1);
    static constexpr std::size_t value = npos;
};

template<typename T>
struct type_find<T, T> {
    static constexpr std::size_t length = 1;
    static constexpr std::size_t npos = static_cast<std::size_t>(-1);
    static constexpr std::size_t value = 0;
};


template<typename T, typename ...Args>
struct type_find {
    template<typename ...Args2>
    using self_template = type_find<Args2...>;
    static constexpr std::size_t length = sizeof...(Args);
    static constexpr std::size_t npos = static_cast<std::size_t>(-1);
    using pre_half = typename type_sequence<Args...>::
        template slice<0, length/2>::template prepend<T>::
        template unpack<self_template>;
    using post_half = typename type_sequence<Args...>::
        template slice<length/2>::template prepend<T>::
        template unpack<self_template>;
    static constexpr std::size_t value =
        pre_half::value != npos ?
            pre_half::value:
            (post_half::value != npos ?
                (pre_half::length + post_half::value):
                npos);
};

}

template<typename T, typename ...Args>
struct type_find :
    std::integral_constant<std::size_t, _detail::type_find<T, Args...>::value>
{};
}

前回の記事と見比べていただけば、結構似通っているところもあると思います。
あとfindは再帰の深さのオーダーがlog(n)になるようにしてみました。

終わりに

なんだかすごい疲れました。途中から解説がおざなりになっているので、分からないことがあればコメントしていってください。
それでは今日はこの辺で。