C++のtupleってどうやって実装してるんだろ、と、ふと気になって、ソースを見てみたら、テンプレートで再帰していて、なんかおもろいなぁってことで、頑張って読んでみました。
細かいメソッドだとか、コンストラクタだとかは読み飛ばして、データ構造に焦点を当てています。
この記事は https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-api-4.5/a01066_source.html のソースをもとに書いています。
tupleの実装
いきなりですが。ソースの上の方はとりあえず飛ばして、下の方にある、tuple自体の実装を見てみます。
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の正体は、実質これだ、といっても過言ではなさそうです。
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は、実質からっぽのクラスですよ、と。
大事なのは、次からです。
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& 型に変換できます。
参照のダウンキャストと分かったので、編集しました。江添さんのところに、参照の初期化時について、リファレンス互換(reference-compatible)という言葉を使って、この変換が可能なことを示しています。ここで出てくるのは初期化ではないので、この場合どうなるのかについては、記述が見当たらなかったのですが、おそらく、初期化と同様とみなすのが妥当でしょう。
これで、_Tuple_implが要素を、先頭要素のheadと、それ以降のtailに分けて、先頭要素は_Head_baseに、それ以降は別の_Tuple_implに持たせる、という構造が見えてきました。念のため、_Head_baseの定義もみておきましょう。
_Head_baseの定義
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初心者ゆえ、読みが足りない・浅い部分も多々あるかと思います。