コンパイル時に配列を結合する
元ネタ
constexpr で扱えて,実行時の効率もよいデータ構造+アルゴリズム - とくにあぶなくないRiSKのブログ
arrayにpush_back, push_fonrt - bigsleepの日記
index_tuple の技法を使って,constexpr 関数の呼び出しを 2 回に抑える実装を考えました.
#include <cstddef> // array // template <class T, std::size_t N> struct array { T elems[N ? N : 1]; constexpr T const &operator[](std::size_t i) const { return elems[i]; } }; // index_tuple // template <std::size_t ...Indexes> struct index_tuple {}; template < std::size_t Start, std::size_t Finish, std::size_t Step = 1, class Acc = index_tuple<>, bool Break = (Start >= Finish) > struct index_range { typedef Acc type; }; template <std::size_t Start, std::size_t Finish, std::size_t Step, std::size_t ...Indexes> struct index_range<Start, Finish, Step, index_tuple<Indexes...>, false> : index_range<Start + Step, Finish, Step, index_tuple<Indexes..., Start>> {}; // append // template < class T, std::size_t M, std::size_t ...MIndexes, std::size_t N, std::size_t ...NIndexes > constexpr array<T, M + N> append_aux( array<T, M> const &am, index_tuple<MIndexes...>, array<T, N> const &an, index_tuple<NIndexes...> ) { return { { am[MIndexes]..., an[NIndexes]... } }; } template <class T, std::size_t M, std::size_t N> constexpr array<T, M + N> append(array<T, M> const &am, array<T, N> const &an) { return append_aux( am, typename index_range<0, M>::type(), an, typename index_range<0, N>::type()); } // drop // template <std::size_t M, class T, std::size_t N, std::size_t ...Indexes> constexpr array<T, N - M> drop_aux(array<T, N> const &a, index_tuple<Indexes...>) { return { { a[Indexes]... } }; } template <std::size_t M, class T, std::size_t N> constexpr array<T, N - M> drop(array<T, N> const &a) { return drop_aux<M>(a, typename index_range<M, N>::type()); } // てすと // constexpr array<int, 2> a1 = { { 0, 1 } }; constexpr array<int, 2> a2 = { { 2, 3 } }; constexpr auto a3 = append(a1, a2); static_assert(a3[0] == 0 && a3[1] == 1 && a3[2] == 2 && a3[3] == 3, ""); constexpr auto a4 = drop<2>(a3); static_assert(a4[0] == 2 && a4[1] == 3, "");
再帰を constexpr 関数からテンプレート (index_range) に移したとも取れますが,関数に渡すオブジェクトが異なっても index_range のインスタンスは使い回せるので (メモ化ができるので),あるいはより高いコンパイル時パフォーマンスが得られるかもしれません.
また,このアルゴリズムは実行時にも最適に近いものとなっています (constexpr 関数の利点が発揮されている例です).テンプレート引数を少し一般化すれば,ほとんど同じコード量でムーブに対応させることも可能です.