【C++】テンプレートメタプログラミング Part4：型リストとコンパイル時計算

C++ TMP (テンプレートメタプログラミング) シリーズ

Part1 constexpr	Part2 Concepts	Part3 Variadic	Part4 型リスト	Part5 正規表現
✅	✅	✅	👈 Now

はじめに

今回は型リストを使ったコンパイル時計算。

実行時の配列操作のように、型のリストを変換、フィルタ、検索する。

型リストの定義

// 型のリストを保持するだけの構造体
template<typename... Ts>
struct TypeList {};

// 使用例
using IntTypes = TypeList<int, short, long, long long>;
using FloatTypes = TypeList<float, double, long double>;

基本操作

サイズ

template<typename List>
struct size;

template<typename... Ts>
struct size<TypeList<Ts...>> {
    static constexpr size_t value = sizeof...(Ts);
};

template<typename List>
constexpr size_t size_v = size<List>::value;

// 使用例
static_assert(size_v<TypeList<int, double, char>> == 3);
static_assert(size_v<TypeList<>> == 0);

空判定

template<typename List>
struct is_empty : std::false_type {};

template<>
struct is_empty<TypeList<>> : std::true_type {};

template<typename List>
constexpr bool is_empty_v = is_empty<List>::value;

先頭要素

template<typename List>
struct front;

template<typename Head, typename... Tail>
struct front<TypeList<Head, Tail...>> {
    using type = Head;
};

template<typename List>
using front_t = typename front<List>::type;

// 使用例
static_assert(std::is_same_v<front_t<TypeList<int, double>>, int>);

末尾要素

template<typename List>
struct back;

template<typename T>
struct back<TypeList<T>> {
    using type = T;
};

template<typename Head, typename... Tail>
struct back<TypeList<Head, Tail...>> {
    using type = typename back<TypeList<Tail...>>::type;
};

template<typename List>
using back_t = typename back<List>::type;

// 使用例
static_assert(std::is_same_v<back_t<TypeList<int, double, char>>, char>);

リスト操作

先頭に追加 (push_front)

template<typename List, typename T>
struct push_front;

template<typename... Ts, typename T>
struct push_front<TypeList<Ts...>, T> {
    using type = TypeList<T, Ts...>;
};

template<typename List, typename T>
using push_front_t = typename push_front<List, T>::type;

// 使用例
using List = TypeList<int, double>;
using NewList = push_front_t<List, char>;  // TypeList<char, int, double>

末尾に追加 (push_back)

template<typename List, typename T>
struct push_back;

template<typename... Ts, typename T>
struct push_back<TypeList<Ts...>, T> {
    using type = TypeList<Ts..., T>;
};

template<typename List, typename T>
using push_back_t = typename push_back<List, T>::type;

先頭を削除 (pop_front)

template<typename List>
struct pop_front;

template<typename Head, typename... Tail>
struct pop_front<TypeList<Head, Tail...>> {
    using type = TypeList<Tail...>;
};

template<typename List>
using pop_front_t = typename pop_front<List>::type;

// 使用例
using List = TypeList<int, double, char>;
using Popped = pop_front_t<List>;  // TypeList<double, char>

連結 (concat)

template<typename List1, typename List2>
struct concat;

template<typename... Ts1, typename... Ts2>
struct concat<TypeList<Ts1...>, TypeList<Ts2...>> {
    using type = TypeList<Ts1..., Ts2...>;
};

template<typename List1, typename List2>
using concat_t = typename concat<List1, List2>::type;

// 使用例
using A = TypeList<int, double>;
using B = TypeList<char, float>;
using AB = concat_t<A, B>;  // TypeList<int, double, char, float>

変換操作

各要素に変換を適用 (transform)

template<typename List, template<typename> class F>
struct transform;

template<template<typename> class F, typename... Ts>
struct transform<TypeList<Ts...>, F> {
    using type = TypeList<typename F<Ts>::type...>;
};

template<typename List, template<typename> class F>
using transform_t = typename transform<List, F>::type;

// 使用例: ポインタ化
template<typename T>
struct add_pointer {
    using type = T*;
};

using List = TypeList<int, double, char>;
using Pointers = transform_t<List, add_pointer>;
// TypeList<int*, double*, char*>

フィルタ

template<typename List, template<typename> class Pred>
struct filter;

template<template<typename> class Pred>
struct filter<TypeList<>, Pred> {
    using type = TypeList<>;
};

template<template<typename> class Pred, typename Head, typename... Tail>
struct filter<TypeList<Head, Tail...>, Pred> {
private:
    using tail_result = typename filter<TypeList<Tail...>, Pred>::type;
public:
    using type = std::conditional_t<
        Pred<Head>::value,
        typename push_front<tail_result, Head>::type,
        tail_result
    >;
};

template<typename List, template<typename> class Pred>
using filter_t = typename filter<List, Pred>::type;

// 使用例: 整数型のみ抽出
using AllTypes = TypeList<int, double, char, float, long>;
using IntegerTypes = filter_t<AllTypes, std::is_integral>;
// TypeList<int, char, long>

検索操作

要素の存在確認 (contains)

template<typename List, typename T>
struct contains;

template<typename T>
struct contains<TypeList<>, T> : std::false_type {};

template<typename T, typename... Tail>
struct contains<TypeList<T, Tail...>, T> : std::true_type {};

template<typename Head, typename... Tail, typename T>
struct contains<TypeList<Head, Tail...>, T> 
    : contains<TypeList<Tail...>, T> {};

template<typename List, typename T>
constexpr bool contains_v = contains<List, T>::value;

// 使用例
using List = TypeList<int, double, char>;
static_assert(contains_v<List, int>);
static_assert(!contains_v<List, float>);

インデックスで取得 (at)

template<typename List, size_t N>
struct at;

template<typename Head, typename... Tail>
struct at<TypeList<Head, Tail...>, 0> {
    using type = Head;
};

template<typename Head, typename... Tail, size_t N>
struct at<TypeList<Head, Tail...>, N> {
    using type = typename at<TypeList<Tail...>, N - 1>::type;
};

template<typename List, size_t N>
using at_t = typename at<List, N>::type;

// 使用例
using List = TypeList<int, double, char, float>;
static_assert(std::is_same_v<at_t<List, 0>, int>);
static_assert(std::is_same_v<at_t<List, 2>, char>);

型のインデックスを取得 (index_of)

template<typename List, typename T, size_t N = 0>
struct index_of;

template<typename T, size_t N>
struct index_of<TypeList<>, T, N> {
    static constexpr size_t value = static_cast<size_t>(-1);  // not found
};

template<typename T, typename... Tail, size_t N>
struct index_of<TypeList<T, Tail...>, T, N> {
    static constexpr size_t value = N;
};

template<typename Head, typename... Tail, typename T, size_t N>
struct index_of<TypeList<Head, Tail...>, T, N> 
    : index_of<TypeList<Tail...>, T, N + 1> {};

template<typename List, typename T>
constexpr size_t index_of_v = index_of<List, T>::value;

// 使用例
using List = TypeList<int, double, char>;
static_assert(index_of_v<List, int> == 0);
static_assert(index_of_v<List, char> == 2);

高度な操作

重複削除 (unique)

template<typename List>
struct unique;

template<>
struct unique<TypeList<>> {
    using type = TypeList<>;
};

template<typename Head, typename... Tail>
struct unique<TypeList<Head, Tail...>> {
private:
    using tail_unique = typename unique<TypeList<Tail...>>::type;
public:
    using type = std::conditional_t<
        contains_v<tail_unique, Head>,
        tail_unique,
        typename push_front<tail_unique, Head>::type
    >;
};

template<typename List>
using unique_t = typename unique<List>::type;

// 使用例
using List = TypeList<int, double, int, char, double>;
using Unique = unique_t<List>;  // TypeList<int, double, char>

反転 (reverse)

template<typename List>
struct reverse;

template<>
struct reverse<TypeList<>> {
    using type = TypeList<>;
};

template<typename Head, typename... Tail>
struct reverse<TypeList<Head, Tail...>> {
    using type = typename push_back<
        typename reverse<TypeList<Tail...>>::type,
        Head
    >::type;
};

template<typename List>
using reverse_t = typename reverse<List>::type;

// 使用例
using List = TypeList<int, double, char>;
using Reversed = reverse_t<List>;  // TypeList<char, double, int>

ソート（型サイズで）

// 挿入ソート
template<typename List, typename T, template<typename, typename> class Compare>
struct insert_sorted;

template<typename T, template<typename, typename> class Compare>
struct insert_sorted<TypeList<>, T, Compare> {
    using type = TypeList<T>;
};

template<typename Head, typename... Tail, typename T, 
         template<typename, typename> class Compare>
struct insert_sorted<TypeList<Head, Tail...>, T, Compare> {
    using type = std::conditional_t<
        Compare<T, Head>::value,
        TypeList<T, Head, Tail...>,
        typename push_front<
            typename insert_sorted<TypeList<Tail...>, T, Compare>::type,
            Head
        >::type
    >;
};

template<typename List, template<typename, typename> class Compare>
struct sort;

template<template<typename, typename> class Compare>
struct sort<TypeList<>, Compare> {
    using type = TypeList<>;
};

template<typename Head, typename... Tail, template<typename, typename> class Compare>
struct sort<TypeList<Head, Tail...>, Compare> {
    using type = typename insert_sorted<
        typename sort<TypeList<Tail...>, Compare>::type,
        Head,
        Compare
    >::type;
};

// サイズ比較
template<typename A, typename B>
struct smaller_size : std::bool_constant<(sizeof(A) < sizeof(B))> {};

template<typename List>
using sort_by_size_t = typename sort<List, smaller_size>::type;

// 使用例
using List = TypeList<long long, char, int, short>;
using Sorted = sort_by_size_t<List>;  
// TypeList<char, short, int, long long>

実践例: 型安全なビジター

template<typename... Types>
class Variant {
    TypeList<Types...> types_;
    std::aligned_union_t<0, Types...> storage_;
    size_t type_index_ = 0;

public:
    template<typename T>
    void set(T value) {
        static_assert(contains_v<TypeList<Types...>, T>, 
                      "Type not in variant");
        new (&storage_) T(std::move(value));
        type_index_ = index_of_v<TypeList<Types...>, T>;
    }
    
    template<typename Visitor>
    auto visit(Visitor&& vis) {
        return visit_impl<0>(std::forward<Visitor>(vis));
    }

private:
    template<size_t N, typename Visitor>
    auto visit_impl(Visitor&& vis) {
        if constexpr (N >= sizeof...(Types)) {
            throw std::runtime_error("Invalid type index");
        } else {
            if (type_index_ == N) {
                using T = at_t<TypeList<Types...>, N>;
                return vis(*reinterpret_cast<T*>(&storage_));
            }
            return visit_impl<N + 1>(std::forward<Visitor>(vis));
        }
    }
};

実践例: コンパイル時型マップ

template<typename Key, typename Value>
struct Pair {
    using key_type = Key;
    using value_type = Value;
};

template<typename... Pairs>
struct TypeMap {
    using pairs = TypeList<Pairs...>;
};

template<typename Map, typename Key>
struct lookup;

template<typename Key>
struct lookup<TypeMap<>, Key> {
    // Not found - コンパイルエラー
};

template<typename Key, typename Value, typename... Rest>
struct lookup<TypeMap<Pair<Key, Value>, Rest...>, Key> {
    using type = Value;
};

template<typename First, typename... Rest, typename Key>
struct lookup<TypeMap<First, Rest...>, Key> 
    : lookup<TypeMap<Rest...>, Key> {};

template<typename Map, typename Key>
using lookup_t = typename lookup<Map, Key>::type;

// 使用例
using MyMap = TypeMap<
    Pair<int, std::string>,
    Pair<double, std::vector<int>>,
    Pair<char, bool>
>;

static_assert(std::is_same_v<lookup_t<MyMap, int>, std::string>);
static_assert(std::is_same_v<lookup_t<MyMap, char>, bool>);

まとめ

操作	関数
サイズ	size_v
先頭要素	front_t
インデックス取得	at_t
追加	push_front_t, push_back_t
削除	pop_front_t
変換	transform_t
フィルタ	filter_t
検索	contains_v, index_of_v
重複削除	unique_t
反転	reverse_t
ソート	sort_by_size_t

型リスト操作はコンパイル時のデータ構造。実行時の配列操作と同じ発想で考えられる。

次回はコンパイル時正規表現を実装する。

続きが気になったら、いいね・ストックしてもらえると嬉しいです！