テンプレートパラメータパックのN番目の型を取得する

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

## はじめに

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

```cpp
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` の単純な実装は次のようになります。

```cpp
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)多重継承を使った実装

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

```cpp
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`を多重継承します。
先頭で挙げた例であれば、次のようにインスタンス化されます。（イメージ)

```cpp
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"と呼ばれる実装は次のようになります。

```cpp
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番目の型を取得したい場合は、
```cpp
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)の実装を使えば、どちらでも実用上問題になることはないと思います。