可変引数テンプレートのパラメータパックのN番目の型を取得したい。

はじめに

以下のようにして、テンプレートパラメータパックのN番目の型を取得したいです。

template <std::size_t N, typename... Types>
struct nth
{
    using type = /*Types の N番目*/;
};

// エイリアステンプレート
template <std::size_t N, typename... Types>
using nth_t = typename nth<N, Types...>::type;

// テスト
using T1 = char;
using T2 = short;
using T3 = int;
static_assert(std::is_same<nth_t<0, T1, T2, T3>, T1>::value, "");
static_assert(std::is_same<nth_t<1, T1, T2, T3>, T2>::value, "");
static_assert(std::is_same<nth_t<2, T1, T2, T3>, T3>::value, "");

このnthクラスの実装方法について、何パターンか比較してみます。

(1)単純な再帰での実装

再帰を使った nth の単純な実装は次のようになります。

template <std::size_t N, typename Head, typename... Tail>
struct nth<N, Head, Tail...>
	: public nth<N - 1, Tail...>
{};

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

この実装の再帰深度はO(N)となり、あまり要素数が多くなるとコンパイルできません。
ほとんどの場合は問題ありませんが、nthはテンプレートメタプログラミングでそこそこ使うので、できれば再帰深度をおさえたいです。

(2)多重継承を使った実装

多重継承を使った実装は次のようになります。

template <std::size_t N, typename T>
struct element_holder
    : public std::type_identity<T>
{};

template <typename Sequence, typename... Types>
struct type_tuple;

template <std::size_t... Indices, typename... Types>
struct type_tuple<std::index_sequence<Indices...>, Types...>
    : public element_holder<Indices, Types>...
{};

template <std::size_t N, typename T>
element_holder<N, T> select(element_holder<N, T>);

template <std::size_t N, typename... Types>
struct nth
{
private:
    using Seq = std::index_sequence_for<Types...>;
    using TypeTuple = type_tuple<Seq, Types...>;
    using Tmp = decltype(select<N>(std::declval<TypeTuple>()));
public:
    using type = typename Tmp::type;
};

element_holder はインデックスと型をセットにして保持するだけのクラスです。
type_tuple がこの実装のキモとなるクラスで、std::index_sequence を使ってelement_holderを多重継承します。
先頭で挙げた例であれば、次のようにインスタンス化されます。（イメージ)

struct type_tuple
    : public element_holder<0, T1>
    , public element_holder<1, T2>
    , public element_holder<2, T3>
{};

nth クラス内部でtype_tuple型を作り、それをselect関数に渡します。
select関数はelement_holder<N,T>を引数にとるので、type_tupleからelement_holderにキャストされることになり、select関数の返り値の型を見れば、求めたい型がわかります。

この実装それ自体では再帰的にインスタンス化されていませんが、std::index_sequence_for は(おそらく)再帰深度O(logN)で実装されており、全体として再帰深度はO(logN)となります。

(3)void* trick を使った実装

"void* trick"と呼ばれる実装は次のようになります。

template <typename Seq>
struct nth_impl;

template <std::size_t... Indices>
struct nth_impl<std::index_sequence<Indices...>>
{
	template <std::size_t>
	struct void_ptr
	{
		using type = void*;
	};

	template <typename T>
	static T eval(typename void_ptr<Indices>::type..., T*, ...);
};

template <std::size_t N, typename... Types>
struct nth
{
private:
	using Seq = std::make_index_sequence<N>;  // ここは sizeof...(Types) ではなく N

	using tmp_type = decltype(
		nth_detail::nth_impl<Seq>::eval(
			static_cast<std::type_identity<Types>*>(nullptr)...));
public:
	using type = typename tmp_type::type;
};

nth_impl は求めたい番号(N)までの index_sequence を渡してインスタンス化されます。
なので、nth_impl::evalの引数はN個のvoid*が並んだ後にT*, ...と続きます。
例えば3番目の型を取得したい場合は、

template <typename T>
static T eval(void*, void*, void*, T*, ...);

のようにインスタンス化されます。
このeval関数にTypes...をtype_identity<Types>*...として渡すことで、eval関数の戻り値の型はtype_identity<TypesのN番目>となり、求めたい型が取得できます。

この実装も、std::make_index_sequence の再帰深度に依存しており、全体として再帰深度はO(logN)となります。

比較

3つの実装の再帰深度についてまとめると次のようになります。

実装	再帰深度	再帰深度のパラメータ
(1)再帰	O(N)	求めたい番号 `N`
(2)多重継承	O(logN)	パラメータパック全体のサイズ `sizeof...(Types)`
(3)void* trick	O(logN)	求めたい番号 `N`

例えば(1)の実装だと、Types...の要素数は大きくなっても大丈夫ですが、求めたい番号が大きくなると再帰深度の限界にひっかかってコンパイルエラーとなります。(2)の実装では、Types...の要素数が再帰深度の限界に引っ掛からない限り、求めたい番号をいくつにしても大丈夫です。

そこで、N個のパラメータを渡してN-1番目の型を取得するとき、Nをいくつまで大きくしてもエラーにならずにコンパイルできるのか比較してみました。

テスト環境：
MSVC: Visual Studio 2019
GCC: gcc-12
Clang: clang-15
コンパイルオプション: C++20, デバッグビルド

実装	MSVC	GCC	Clang
(1)再帰	498	899	1023
(2)多重継承	50,000～60,000	100,000～1,000,000	3,000,000～4,000,000
(3)void* trick	1,000,000～10,000,000	5,000～6,000	10,000～100,000

Nが大きくなってくると1回の試行にかかる時間が長くなるため(2～3時間とか)、(2)と(3)はおおまかな数字となっています。
(2)と(3)では、再帰深度の限界に当たる前に、コンパイラ内部エラーや「ヒープの領域を使い果たしました」等のエラーとなりました。
(1)はコンパイルオプションで再帰深度の限界を設定することによって、もっと大きな数字でも大丈夫になるはずです。

まとめ

他のテンプレートから呼ばれる可能性も考えると、(1)は少々心もとないです。
(2)か(3)の実装を使えば、どちらでも実用上問題になることはないと思います。