再帰深度を抑えたtuple的コンテナの構築

本当に一部の機能のみ実装。要素型とindexをテンプレートパラメータにペアにして保持するvalue_holderを多重継承する方針。make_overloadの際に初めて知った、テンプレート引数を展開しながら一気に多重継承するという技法を早速パクりました。getでindexをキーとして継承元の関数を呼び分ける。線形再帰しつつ構築する従来の方法では構築の再帰深度がネックとなり、要素数の上限を強く制約していましたが、この方法なら問題無い筈。
sprout::type_tupleの要素アクセスがO(logN)の筈なので、要素数Nのtupleを構築する際の計算量はO(NlogN)・再帰深度は定数、要素アクセスはO(logN)。
しかしこのテンプレートパラメータの形式だと、make_tupleを介さずに構築するのは厳しそう。 http://melpon.org/wandbox/permlink/0wtvQEAV4kelxRYJ

#include <sprout/utility.hpp>
#include <sprout/type_traits.hpp>
#include <sprout/type.hpp>
#include <sprout/index_tuple.hpp>

template <typename T, sprout::index_t N>
struct value_holder {
 public:
  constexpr value_holder(T arg) : value(arg) {}

  constexpr T operator()() const {
    return value;
  };

 private:
  T value;
};

template <typename T, sprout::index_t... Indices>
class tuple : value_holder<typename sprout::tuple_element<Indices, T>::type,
                           Indices>... {
 public:
  constexpr tuple(typename sprout::tuple_element<Indices, T>::type... args)
      : value_holder<typename sprout::tuple_element<Indices, T>::type, Indices>(
            args)... {}

  template <sprout::index_t N>
  constexpr typename sprout::tuple_element<N, T>::type get() const {
    return value_holder<typename sprout::tuple_element<N, T>::type, N>::
        operator()();
  }
};

template <typename... Types, sprout::index_t... Indices>
constexpr auto make_tuple_impl(sprout::index_tuple<Indices...>&&,
                               Types&&... args) {
  return tuple<sprout::type_tuple<Types...>, Indices...>(
      SPROUT_FORWARD(Types, args)...);
}

template <typename... Types>
constexpr auto make_tuple(Types&&... args) {
  return make_tuple_impl(sprout::index_range<0, sizeof...(Types)>::make(),
                         SPROUT_FORWARD(Types, args)...);
}

int main() { 
  constexpr auto t = make_tuple(1, 'a', 3.14, 2);
  static_assert(t.get<0>() == 1, "");
  static_assert(t.get<1>() == 'a', "");
  static_assert(t.get<2>() == 3.14, "");
  static_assert(t.get<3>() == 2, "");
}

[追記] すぐに@iorateさんが上記コードを元に更に優れた実装をしてくれました。

http://melpon.org/wandbox/permlink/NcsYuaNaWZkmLNew
この実装なら、従来のようにconstexpr tuple<int, char, double, int> t(1, 'a', 3.14, 2);と書いても構築出来ますし、sprout::type_listへの要素アクセスが発生しないので、構築時の計算量もO(N), 再帰深度はO(logN)、要素アクセスも定数になっていてオーダーも改善されて素晴らしいです。

部分特殊化として以下のように書けば確かに複数のテンプレートパラメータパックを保持出来ますね。そして、get_implの実装でNと*thisから呼ぶべきvalue_holder<T, N>を得るのがとても賢い…。

template <typename Indices, typename... Types>
class tuple_base;

template <sprout::index_t... Indices, typename... Types>
class tuple_base<sprout::index_tuple<Indices...>, Types...> : value_holder<Types, Indices>...

自分頭悪いなーって感じました。このコードは即保存しました…見事です。
この方針は、pairのネスト等を用いたtupleの実装より大幅に優れているのではないでしょうか。

[追記2]
というか、これって、定数オーダーで要素アクセス出来る型tupleとして使えるような…？
http://melpon.org/wandbox/permlink/UUgjw947JW91H770
と思い、改造して型tupleを実装してみました。

#include <sprout/utility.hpp>
#include <sprout/type_traits.hpp>
#include <sprout/type.hpp>
#include <sprout/index_tuple.hpp>
 
template <typename T, sprout::index_t N>
struct indexed_identity : public sprout::identity<T> {};
 
template <typename Indices, typename... Types>
class type_tuple_base;
 
template <sprout::index_t... Indices, typename... Types>
class type_tuple_base<sprout::index_tuple<Indices...>, Types...> : indexed_identity<Types, Indices>... {
 public:
  constexpr type_tuple_base()
      : indexed_identity<Types, Indices>()... {}
    
  template <sprout::index_t N>
  static constexpr auto get() {
    return get_impl<N>(type_tuple_base<sprout::index_tuple<Indices...>, Types...>());
  }  
 
 private:
  template <sprout::index_t N, typename T>
  static constexpr auto get_impl(indexed_identity<T, N> const & t) {
      return t;
  }
 
 public:
  template <sprout::index_t N>
  using at = typename decltype(get<N>())::type;
};
 
template <typename... Types>
class type_tuple : public type_tuple_base<typename sprout::index_range<0, sizeof...(Types)>::type, Types...> {
 public:
  using type_tuple_base<typename sprout::index_range<0, sizeof...(Types)>::type, Types...>::type_tuple_base;
};
 
int main() { 
  using t = type_tuple<int, char, double, int>;
  constexpr t::at<0> a = 1;
  constexpr t::at<1> b = 'a';
  constexpr t::at<2> c = 3.14;
  constexpr t::at<3> d = 2;
    
  static_assert(a == 1, "");
  static_assert(b == 'a', "");
  static_assert(c == 3.14, "");
  static_assert(d == 2, "");
}

ろくにテストしてないのでバグがあるかもしれませんが、方針としてはいけそうですね。
これで構築の計算量がO(N)、構築時の再帰深度が(index_rangeを呼び出すので)O(logN)、要素アクセスが定数オーダーに落ちたので、コンパイラマジックに頼らずとも十分優れたオーダーになり、一応tuple、型tuple辺りの実装オーダーの改良には決着が付いたと言えるんじゃないでしょうか。

[他の方々tuple対数オーダー構築に関する試み]
対数オーダーtupleを作ろうとしたが力尽きた
https://gist.github.com/wx257osn2/8051199
対数オーダー再起で構築されるtupleのギミックを大雑把に実装した
http://txt-txt.hateblo.jp/entry/2014/05/25/124633