型をソートするメタプログラミング

型をソートするとは

例として、サイズでソートするとします。
※名前空間はbloomでくくってます

template <typename T1, typename T2>
struct sort_type
{
    static constexpr bool value = sizeof(T1) < sizeof(T2);
};

//bloom::type_tuple<std::int8_t,std::int16_t,std::int32_t,std::int64_t>
using t = bloom::sort_t<bloom::type_tuple<std::int16_t, std::int64_t, std::int32_t, std::int8_t>, sort_type>;

簡単な例ですが、このように型のサイズで昇順にソートされました。
これの実装を見せながら解説をしようと思います。

※この記事を見るにあたって必要となる知識としては、templateの基礎知識(特殊化、推論)、C++17までの簡単な知識があれば十分なので敷居は低いですが、コードの量が多いのでそれを読み解く根性が何より必要です。

注意

本当はenable_ifなどでメタプログラミングしていますが、コードが長くなるので削除しています。

基盤となるのtype_tuple

まず、何かを実装する前に、複数の型をまとめて扱う型が必要です。
まずコードを見てみましょう。

template <typename... Types>
struct type_tuple
{
    using begin = bloom::iterator<0, Types...>;
    using end = bloom::iterator<sizeof...(Types), Types...>;
};

namespace detail
{
template <index_t Idx, typename... Types>
get_variadic_type<Idx, Types...> get_type_helper(type_tuple<Types...>);
} // namespace detail
template <index_t Idx, typename T>
struct get
    : decltype(detail::get_type_helper<Idx>(std::declval<T>()))
{
};
template <index_t Idx, typename T>
using get_t = typename get<Idx, T>::type;

namespace detail
{
template <typename... Types>
struct get_size_impl
{
    static constexpr size_t value = sizeof...(Types);
};
template <typename... Types>
get_size_impl<Types...> get_size_helper(type_tuple<Types...>);
} // namespace detail
template <typename T>
struct get_size
    : decltype(detail::get_size_helper(std::declval<T>()))
{
};
template <typename T>
inline constexpr size_t get_size_v = get_size<T>::value;

気になるのはイテレータの部分ですね。
これは後程解説しますので、いったん無視してください。
type_tupleは基本的には型を保持するだけです。
get_tやget_sizeといった型や型の数を取得するものも実装しています。

イテレータ

各機能を実装するときにこのイテレータがあるととても楽に実装できます。
まずコードを見ていきましょう。

template <index_t Idx, typename... Types>
struct iterator
    : std::conditional_t<Idx != sizeof...(Types), get_variadic_type<Idx, Types...>, empty_t>
{
    static constexpr bool is_first = (Idx == 0);
    static constexpr bool is_last = (Idx == sizeof...(Types));
    static constexpr index_t index = Idx;
};

//空のイテレータ
using empty_iterator = iterator<0>;

//指定した値だけイテレータを進める
namespace detail
{
template <size_t N, index_t Idx, typename... Types>
struct next_impl
{
    using type = iterator<((Idx + N <= sizeof...(Types)) ? Idx + N : sizeof...(Types)), Types...>;
};

template <size_t N, index_t Idx, typename... Types>
next_impl<N, Idx, Types...> next_helper(iterator<Idx, Types...>);
} // namespace detail
template <typename IteratorT, size_t N = 1>
struct next
    : decltype(detail::next_helper<N>(std::declval<IteratorT>()))
{
};
template <typename IteratorT, size_t N = 1>
using next_t = typename next<IteratorT, N>::type;

//指定した値だけイテレータを戻す
namespace detail
{
template <size_t N, index_t Idx, typename... Types>
struct prev_impl
{
    using type = iterator<(Idx >= N ? Idx - N : 0), Types...>;
};

template <size_t N, index_t Idx, typename... Types>
prev_impl<N, Idx, Types...> prev_helper(iterator<Idx, Types...>);
} // namespace detail
template <typename IteratorT, size_t N = 1>
struct prev
    : decltype(detail::prev_helper<N>(std::declval<IteratorT>()))
{
};
template <typename IteratorT, size_t N = 1>
using prev_t = typename prev<IteratorT, N>::type;

まずイテレータ本体の部分ですが、今どこをイテレータが指しているのかをIdxという非型テンプレートパラメータが保持し、型の集合をTypesで保持しています。is_first,is_last,indexは名前の通りです。
next,prevもIdxが0以下、サイズ以上にならないようにしているだけです。

コードをよく見た人はわかりますが、実はイテレータと言っていますが直接type_tupleを触っているわけではありません。
あたかもtype_tupleの型をイテレーションしているようにコード上は見えますが、型は変化させたものを返すことは出来ても、型そのものを変化させることはできないので、このような実装になっています。

sortの実装

sortの実装にはjoin,push_back,remove_atが必要なので、それの実装からお見せします。

joinの実装

join.hpp

namespace detail
{
template <typename... LTypes, typename... RTypes>
type_tuple<LTypes..., RTypes...> join_helper(type_tuple<LTypes...>, type_tuple<RTypes...>);
template <typename TupleT, typename... AddTupleTypes>
struct join_impl;
template <typename TupleT, typename AddTupleType, typename... Tail>
struct join_impl<TupleT, AddTupleType, Tail...>
    : join_impl<decltype(join_helper(std::declval<TupleT>(), std::declval<AddTupleType>())), Tail...>
{
};
template <typename TupleT, typename AddTupleType>
struct join_impl<TupleT, AddTupleType>
{
    using type = decltype(join_helper(std::declval<TupleT>(), std::declval<AddTupleType>()));
};
} // namespace detail

template <typename TupleT, typename... AddTupleTypes>
struct join
    : detail::join_impl<TupleT, AddTupleTypes...>
{
};

template <typename TupleT, typename... AddTupleTypes>
using join_t = typename join<TupleT, AddTupleTypes...>::type;

二つのtype_tupleを連結させる機能です。
ここでは特に特別なことをしていませんが、あえて言うならjoin_helperの推論でしょうか。

template <typename... LTypes, typename... RTypes>
type_tuple<LTypes..., RTypes...> join_helper(type_tuple<LTypes...>, type_tuple<RTypes...>);

テンプレートパラメータを書かずとも、引数から可変長引数を推論してくれるテクニックです。
ここに詳しいことは書いてありますので、ぜひ参考にしてください。
C++のパラメータパック基礎&パック展開テクニック

push_backの実装

push_back.hpp

template <typename TupleT, typename... PushBackTypes>
struct push_back
    : join<TupleT, type_tuple<PushBackTypes...>>
{
};

template <typename TupleT, typename... PushBackTypes>
using push_back_t = typename push_back<TupleT, PushBackTypes...>::type;

指定した型を指定したtype_tupleの後ろにつける機能です。
先ほどのjoinを利用しただけですので、特に難しいことはありませんが、別で作成したほうが名前から意味が汲み取りやすいので実装しました。

remove_atの実装

remove_at.hpp

namespace detail
{
template <typename CurrentItr, index_t... RemoveValues>
struct remove_at_impl_idx
{
    using type = std::conditional_t<std::disjunction_v<std::bool_constant<CurrentItr::index == RemoveValues>...>, empty_type_tuple, type_tuple<typename CurrentItr::type>>;
};
template <typename DestTupleT, typename CurrentItr, typename EndItr, index_t... RemoveValues>
struct remove_at_impl
    : remove_at_impl<
          join_t<DestTupleT, typename remove_at_impl_idx<CurrentItr, RemoveValues...>::type>,
          next_t<CurrentItr, 1>, EndItr, RemoveValues...>
{
};
template <typename DestTupleT, typename EndItr, index_t... RemoveValues>
struct remove_at_impl<DestTupleT, EndItr, EndItr, RemoveValues...>
{
    using type = DestTupleT;
};
} // namespace detail
template <typename TupleT, index_t... RemoveValues>
struct remove_at
    : detail::remove_at_impl<empty_type_tuple, typename TupleT::begin, typename TupleT::end, RemoveValues...>
{
};
template <typename TupleT, index_t... RemoveValues>
using remove_at_t = typename remove_at<TupleT, RemoveValues...>::type;

これは指定した位置の型を削除する機能です。
vectorのような可変長配列なら、受け取った変数から値を削除しますが、型は変更できないので、一つ一つ複製しています(DestTupleTがそれです)。
メインで処理している部分はremove_at_impl_idxです。
ここでその位置が指定されているかを判断し、指定されていなかったら型が入ったtype_tupleを返し、指定されていたら型が入っていないtype_tupleを返しDestTupleTにjoinしています。
この処理をすべての型に対して行って一つ一つjoinしています。
push_backで処理したいところですが、push_backはtype_tuple以外の型を指定する必要があるため(int,float)、型を返さないという処理ができないため、joinで空のtype_tuple(実質、型を返さない)で結合しています。

sortの実装

sort.hpp

namespace detail
{
template <typename DestTupleT, typename PushBackItr, typename CurrentItr, typename EndItr,
          typename SourceTupleT, template <typename, typename> typename SortType>
struct sort_impl;
template <typename DestTupleT, typename PushBackItr, typename CurrentItr, typename EndItr,
          typename SourceTupleT, template <typename, typename> typename SortType>
struct sort_impl
    : sort_impl<DestTupleT,
                std::conditional_t<SortType<typename PushBackItr::type, typename CurrentItr::type>::value, PushBackItr, CurrentItr>,
                next_t<CurrentItr, 1>, EndItr, SourceTupleT, SortType>
{
};
template <typename DestTupleT, typename PushBackItr, typename EndItr,
          typename SourceTupleT, template <typename, typename> typename SortType>
struct sort_impl<DestTupleT, PushBackItr, EndItr, EndItr, SourceTupleT, SortType>
    : sort_impl<push_back_t<DestTupleT, typename PushBackItr::type>,
                typename remove_at_t<SourceTupleT, PushBackItr::index>::begin,
                next_t<typename remove_at_t<SourceTupleT, PushBackItr::index>::begin>,
                typename remove_at_t<SourceTupleT, PushBackItr::index>::end,
                remove_at_t<SourceTupleT, PushBackItr::index>, SortType>
{
};
template <typename DestTupleT, template <typename, typename> typename SortType>
struct sort_impl<DestTupleT, empty_iterator, empty_iterator, empty_iterator, empty_type_tuple, SortType>
{
    using type = DestTupleT;
};
} // namespace detail
template <typename TupleT, template <typename, typename> typename SortType>
struct sort
    : detail::sort_impl<empty_type_tuple,
                        typename TupleT::begin,
                        next_t<typename TupleT::begin>,
                        typename TupleT::end,
                        TupleT,
                        SortType>
{
};
template <typename TupleT, template <typename, typename> typename SortType>
using sort_t = typename sort<TupleT, SortType>::type;

とても長くて複雑ですが、やっていることは選択ソートです。
最初から最後まで見て、最大(最小)を先頭に持っていき、次のループは次からスタートして・・・を繰り返して、ソートするアルゴリズムです。
条件分岐は基本的に部分特殊化でしています。
通常では比較し、最大(最小)を保持させ、イテレータが終了したら、型をpush_backし、また前回の最初+1の位置からスタートし、イテレータがなくなり、スタート地点もイテレータがない状態ならすべてを走査したことになるので、終了。
という流れです。

最後に

ちょっと雑でしたが、興味のある方はぜひコメントしてください。
ありがとうございました。