はじめに
この記事はC++のテンプレートの限界に挑む記事です。C++が闇の言語と言われる理由が良く分かると思います。テンプレートに夢と希望を抱いて、色々試して絶望するということは非常によくあると思いますが、この記事には絶望しかありません。注意。
この記事を読むために最低限必要な知識がいくつかあります。
- エイリアステンプレート（using宣言)
- テンプレート特殊化
- 可変長テンプレートパラメータ（パラメータパック展開）
- テンプレートテンプレートパラメータ
敬虔なC++信者にとってはこの程度は余裕かもしれませんが。
目標
可変長非型パラメータを取るクラスがあるとしましょう。そのクラスに対し、2種類のパラメータのパックを与えるとします。この時に、この2種類のパラメータのパックに対するクラスを引数として、2種類のパラメータのパックの和集合のパラメータパックを返り値として返す関数を書くことが今回の目標です。
つまり、
template<int...> class A;
みたいなクラスがあったときに、関数func(A<1, 2, 3>, A<2, 3, 5>)がA<1, 2, 3, 5>を返して欲しい、ということです。（{1, 2, 3}と{2, 3, 5}の和集合{1, 2, 3, 5}が返り値のパラメータ）
今回は入力パラメータはソート済みであり、返り値もソートされた状態で返すものとしましょう。すなわち、A<1, 3, 2, 5>とかは2と3がひっくり返っているのでアウトにします。普通にこれを解くなら尺取虫法が単純かつ効率的でしょう。というわけでtemplate版尺取虫法を書きましょう。
（非推奨ですが）勇敢な方は続きを読む前に是非自分で書いてみてください。
考察
プログラムを組み始める前にどう実装するか考える所から始めましょう。普通のプログラムで尺取虫法を実装するにはif文とwhile文（またはfor文）が必要ですね。さらに結果を入れるためのstd::vectorのような可変長コンテナがあるとなおよいでしょう。しかし（C++20ではstd::vectorがconstexpr化するようだが）当然templateにそんなものはないので代わりとなるようなものを用意しなければならないでしょう。
if文
標準ライブラリtype_traitsには、std::conditional_tというまさにtemplate版if文のようなものがあります。実装はおそらく
namespace std {
template<bool, typename T, typename> struct conditional {
using type = T;
};
template<typename T, typename U> struct conditional<false, T, U> {
using type = U;
};
template<bool B, typename T, typename U> using conditional_t =
typename conditional<B, T, U>::type;
}
みたいな感じでしょう。何が起こるかというと、第一テンプレートパラメータのbool値がtrueの時は第二テンプレートパラメータの型、falseなら第三テンプレートパラメータの型になります。
std::conditional_t<true, int, double> == int
std::conditional_t<false, int, double> == double
while文
これはパラメータパック展開を使って一つ一つ展開していきます。具体的には
template<int...> struct pack;
template<int Head, int... Tail> struct pack<Head, Tail...> {
using type = std::array<typename pack<Tail...>::type, Head>;
};
template<> struct pack<> {
using type = int;
};
みたいに書くと再帰的に展開されていき、
pack<1, 2, 3>::type == std::array<std::array<std::array<int, 3>, 2>, 1>
となります。この再帰展開をwhile文のように使います。
可変長コンテナ
std::vectorのような可変長コンテナのtemplate版を考えましょう。template版可変長コンテナ？？？？という感じですが、そんなに難しく考えなくても大丈夫です。必要な機能はstd::vectorでいうpush_backだけなので、それに近い機能を得られれば、もう勝ったも同然。何を使うかというと、所謂テンプレートテンプレートパラメータを使います。どういうものかというと、テンプレートの中にテンプレートが入ってるみたいなやばい奴です。
template<template<int> class T> struct U;
もう見た目がやばいですね。これのどこが可変長コンテナやねん、って感じですが、これと可変長テンプレートを駆使することで、可変長コンテナに近い機能を得られます。
template<template<int...> class, int...> struct remove_zero;
template<template<int...> class Vec, int Head, int... Tail> struct remove_zero<Vec, Head, Tail...> {
template<int... Args> using vec = // イメージ
std::conditional_t<Head == 0, Vec<Args...>, // if (Head == 0) {}
Vec<Head, Args...>>; // else { vec.push_back(Head); }
using type = typename remove_zero<vec, Tail...>::type;
};
template<template<int...> class Vec> struct remove_zero<Vec> {
using type = Vec<>;
};
何をやっているかというとテンプレートパラメータから0を除いています。つまり、
template<int...> struct S;
remove_zero<S, 1, 0, 2, 0, 3>::type == S<1, 2, 3>
となります。いやー疲れましたね。でももう簡単に尺取虫法を実装できますね！！
え？簡単ではない？
実装
というわけで答えです。
#include <iostream>
#include <type_traits>
#include <typeinfo>
template<typename T, T... Value> class A {
};
template<typename T, template<T...> class, T...> struct args_union;
template<typename T, template<T...> class TemplateType, T Head, T... Tail> struct args_union<T, TemplateType, Head, Tail...> {
template<T...> struct args_union_sub;
template<T Head2, T... Tail2> struct args_union_sub<Head2, Tail2...> {
template<T... Args> using template_type = // イメージ
std::conditional_t<(Head2 < Head), TemplateType<Head2, Args...>, // if (Head2 < Head) template_type.push_back(Head2);
TemplateType<Head, Args...>>; // else template_type.push_back(Head);
using type = std::conditional_t<Head == Head2, // if (Head == Head2)
typename args_union<T, template_type, Tail...>::template args_union_sub<Tail2...>::type, // args_union、args_union_subを一個進める;
std::conditional_t<(Head < Head2), // else if (Head < Head2)
typename args_union<T, template_type, Tail...>::template args_union_sub<Head2, Tail2...>::type, // args_unionを一個進める;
// else
typename args_union<T, template_type, Head, Tail...>::template args_union_sub<Tail2...>::type>>;// args_union_subを一個進める;
};
template<> struct args_union_sub<> {
template<T... Args> using template_type = TemplateType<>;
using type = TemplateType<Head, Tail...>;
};
};
template<typename T, template<T...> class TemplateType> struct args_union<T, TemplateType> {
template<T...> struct args_union_sub;
template<T Head2, T... Tail2> struct args_union_sub<Head2, Tail2...> {
template<T... Args> using template_type = TemplateType<Head2, Tail2..., Args...>;
using type = TemplateType<Head2, Tail2...>;
};
template<> struct args_union_sub<> {
template<T... Args> using template_type = TemplateType<>;
using type = TemplateType<>;
};
};
template<typename T> struct Asub {
template<T... Value> using type = A<T, Value...>;
};
template<typename T, T... Value1, T... Value2> constexpr auto tmp_union(const A<T, Value1...>&, const A<T, Value2...>&) {
return typename args_union<T, Asub<T>::template type, Value1...>::template args_union_sub<Value2...>::type();
}
int main() {
A<int, 0, 1, 4, 5, 7> a;
A<int, 1, 2, 4, 5, 8> b;
std::cout << typeid(tmp_union(a, b)).name() << std::endl;
}
class A<int,0,1,2,4,5,7,8>
環境 Visual Studio 2019 Version 16.4.5 / Windows 10
終わりに
さて、ここまでやっておいてなんですが、実はこのプログラムのコンパイル時計算量はO(3^n)と指数時間になっております。尺取虫法なのになんでO(n)じゃないねん、って感じですが、std::conditional_tで3つの型に分岐するところがどうも全て実体化されているようです。まあ当たり前と言えば当たり前ですが。なので実に効率の悪いプログラムとなっております。ちなみに上のプログラムにさらにテンプレートパラメータを足したところヒープを食いつくしてコンパイルエラーとなりました。でも、実行時計算量O(1)だしまあいっか、って気もしますが、何かテンプレート実体化を抑える手を知っている人がいたら是非教えていただきたいです。（std::conditional_tの代わりにstd::enable_if_tを使えばいいのかな？）
最後までこのしんどい記事を読んでくれてありがとうございます。C++の闇の深さがちょっとでも見えればうれしいなと思います。