tupleのデータ構造が知りたくて、GCC (g++) の実装を読んでみた

C++のtupleってどうやって実装してるんだろ、と、ふと気になって、ソースを見てみたら、テンプレートで再帰していて、なんかおもろいなぁってことで、頑張って読んでみました。
細かいメソッドだとか、コンストラクタだとかは読み飛ばして、データ構造に焦点を当てています。

この記事は https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-api-4.5/a01066_source.html のソースをもとに書いています。

#tupleの実装

いきなりですが。ソースの上の方はとりあえず飛ばして、下の方にある、tuple自体の実装を見てみます。

```cpp
00222   /// tuple
00223   template<typename... _Elements> 
00224     class tuple : public _Tuple_impl<0, _Elements...>
00225     {
00226       typedef _Tuple_impl<0, _Elements...> _Inherited;
//          ...
00295     };
00296 
00297 
00298   template<>  
00299     class tuple<>
00300     {
//          ...
00303     };
00304 
00305   /// tuple (2-element), with construction and assignment from a pair.
00306   template<typename _T1, typename _T2>
00307     class tuple<_T1, _T2> : public _Tuple_impl<0, _T1, _T2>
00308     {
//          ...  
00402     };
```

実装は `_Tuple_impl<0, Elements...>` に丸投げしていることが分かります。中身を見てみると、typedefとメソッドがあるのみで、データは全部`_Tuple_impl`が持っていることが分かります。
空タプルの場合は、何もしないメンバ関数 swap が定義されているだけで、つまらないので、これ以上深追いしません。
2-elementの場合、pairとの相性が重視されているようですが、データ構造自体は変わらないので、深追いしません。

そしたら、次に`_Tuple_impl`をみてみましょう。

#\_Tuple\_implの実装
tupleの正体は、実質これだ、といっても過言ではなさそうです。

```cpp
00109   /**
00110    * Contains the actual implementation of the @c tuple template, stored
00111    * as a recursive inheritance hierarchy from the first element (most
00112    * derived class) to the last (least derived class). The @c Idx
00113    * parameter gives the 0-based index of the element stored at this
00114    * point in the hierarchy; we use it to implement a constant-time
00115    * get() operation.
00116    */
00117   template<std::size_t _Idx, typename... _Elements>
00118     struct _Tuple_impl; 
00119 
00120   /**
00121    * Zero-element tuple implementation. This is the basis case for the 
00122    * inheritance recursion.
00123    */
00124   template<std::size_t _Idx>
00125     struct _Tuple_impl<_Idx>
00126     { 
00127     protected:
00128       void _M_swap_impl(_Tuple_impl&) { /* no-op */ }
00129     };
```

冒頭のコメント、楽しそうなことが書いてあります。\_Idxは、getに使うみたいですね。(@cってなんだろ)
*追記: コメント欄で教えていただきましたが、 @cはdoxygenの特殊コマンドのようです。*

0要素の\_Tuple\_implは、実質からっぽのクラスですよ、と。

大事なのは、次からです。

```cpp
00131   /**
00132    * Recursive tuple implementation. Here we store the @c Head element
00133    * and derive from a @c Tuple_impl containing the remaining elements
00134    * (which contains the @c Tail).
00135    */
00136   template<std::size_t _Idx, typename _Head, typename... _Tail>
00137     struct _Tuple_impl<_Idx, _Head, _Tail...>
00138     : public _Tuple_impl<_Idx + 1, _Tail...>,
00139       private _Head_base<_Idx, _Head, std::is_empty<_Head>::value>
00140     {
00141       typedef _Tuple_impl<_Idx + 1, _Tail...> _Inherited;
00142       typedef _Head_base<_Idx, _Head, std::is_empty<_Head>::value> _Base;
00143 
00144       _Head&            _M_head()       { return _Base::_M_head(); }
00145       const _Head&      _M_head() const { return _Base::_M_head(); }
00146 
00147       _Inherited&       _M_tail()       { return *this; }
00148       const _Inherited& _M_tail() const { return *this; }
//          ...
00220     };
```

ひぃ！　なんじゃこりゃ！
`_Tuple_impl<_Idx, _Head, _Tail...>`は、`_Tuple_impl<_Idx+1, _Tail...>` と、 `_Head_base<_Idx, _Head, std::is_empty<_Head>::value>`を継承しています。
Lispか何かを思い出しそうですね。

`_Tuple_impl`自身には、やはり、typedefとメソッドしか含まないので、実際のデータそのものは、`_Head_base`に置かれていると考えられそうです。
先頭のデータを`_Head_base`に持たせて、次のデータは、`_Tuple_impl<_Idx+1, Tail...>`の`_Head_base`に持たせて、その次は...となっていそうです。

`_Head&            _M_head()       { return _Base::_M_head(); }`
これは、`_Head_base`の定義を見ればわかりそうですが、大体想像がつきますね。

`_Inherited&       _M_tail()       { return *this; }`
型が違うじゃないか！　って思いましたが。参照はダウンキャストができるんですね。
すなわち、`_Tuple_impl` は `_Inherited` を継承しているため、 `_Tuple_impl&` 型は `_Inherited&` 型に変換できます。

*参照のダウンキャストと分かったので、編集しました。[江添さんのところ](https://ezoeryou.github.io/cpp-book/C++11-Syntax-and-Feature.xhtml#dcl.init.ref)に、参照の初期化時について、リファレンス互換(reference-compatible)という言葉を使って、この変換が可能なことを示しています。ここで出てくるのは初期化ではないので、この場合どうなるのかについては、記述が見当たらなかったのですが、おそらく、初期化と同様とみなすのが妥当でしょう。*

これで、`_Tuple_impl`が要素を、先頭要素のheadと、それ以降のtailに分けて、先頭要素は`_Head_base`に、それ以降は別の`_Tuple_impl`に持たせる、という構造が見えてきました。念のため、`_Head_base`の定義もみておきましょう。

#\_Head\_baseの定義
```cpp
00060   template<std::size_t _Idx, typename _Head, bool _IsEmpty>
00061     struct _Head_base;
00062 
00063   template<std::size_t _Idx, typename _Head>
00064     struct _Head_base<_Idx, _Head, true>
00065     : public _Head
00066     {
00067       _Head_base()
00068       : _Head() { }
00069 
00070       _Head_base(const _Head& __h)
00071       : _Head(__h) { }
00072 
00073       template<typename _UHead>
00074         _Head_base(_UHead&& __h)
00075     : _Head(std::forward<_UHead>(__h)) { }
00076 
00077       _Head&       _M_head()       { return *this; }
00078       const _Head& _M_head() const { return *this; }
00079     
00080       void _M_swap_impl(_Head&) { /* no-op */ }
00081     };
00082 
00083   template<std::size_t _Idx, typename _Head>
00084     struct _Head_base<_Idx, _Head, false>
00085     {
00086       _Head_base()
00087       : _M_head_impl() { }
00088 
00089       _Head_base(const _Head& __h)
00090       : _M_head_impl(__h) { }
00091 
00092       template<typename _UHead>
00093         _Head_base(_UHead&& __h)
00094     : _M_head_impl(std::forward<_UHead>(__h)) { }
00095 
00096       _Head&       _M_head()       { return _M_head_impl; }
00097       const _Head& _M_head() const { return _M_head_impl; }        
00098 
00099       void
00100       _M_swap_impl(_Head& __h)
00101       { 
00102     using std::swap;
00103     swap(__h, _M_head_impl);
00104       }
00105 
00106       _Head _M_head_impl; 
00107     };
```

予想通り、このクラスは`_Head _M_head_impl`とあるとおり、データを持っています。
ただし、`_Head`の型が空っぽか空っぽじゃないかで分けており、空っぽじゃないときだけ、データを持っています。
この判断は、`_Tuple_impl`側でしていて、`std::is_empty`を使ってやっています。

これで、tupleのデータ構造が分かりました。
ただ、ここで終わるのも尻切れトンボですので、ひとつ例を挙げてみましょう。

#例：tuple\<int, char, double>

矢印で継承関係を表しています。

|tuple\<int, char, double\>| ||
|:--:|:--:|:--:|
|↓|||
|\_Tuple_impl\<0, int, char, double\>|→|\_Head_base\<0, int, true>|
|↓|||
|\_Tuple_impl\<1, char, double\>|→|\_Head_base\<1, char, true>|
|↓|||
|\_Tuple_impl\<2, double\>|→|\_Head_base\<2, double, true>|
|↓|||
|\_Tuple_impl\<3\>|||

コンパイル時にこんなのがつくれるなんてすごいですね(棒読み)

#おしまい
C++初心者の投稿にお付き合いいただき、ありがとうございます。

tupleの構造をふと疑問に思って読み進めていたら、テンプレートの深淵のごくごく一部をのぞき込むことができた気がします。

識者の方、間違いや補足などありましたら、コメント欄までお願いします。
私はC++やTMP初心者ゆえ、読みが足りない・浅い部分も多々あるかと思います。