constexprでのN引数関数の実装の改良

愚直に線形再帰して1つずつ処理していくとやはり再帰深度が問題になる。
分割統治法を用いることで実装を改良することが出来る。
tuple_elementでN番目の型を対数オーダーで取り出す際に用いた考え方の応用でN/2までのindex_tupleを上手に使うと引数のパックを真ん中で2つに分割出来ることを利用する。

ここではN個の整数の和を計算する例を挙げる(浮動小数点型の場合は単純に加算すると精度が悪いので指摘の通りカハンの加算アルゴリズム等を用いる必要がある)。同様の方法でN個の論理積等も実装出来る。引数が0個だった場合の挙動や、オペレータなどを関数オブジェクトなどで与えるようにして汎用的な分割統治法関数クラスを作れるかもしれない。

実行結果
http://melpon.org/wandbox/permlink/KN4PVVLHU3FP0Bn7

#include <utility>

namespace detail {

template <typename IndexSeq>
struct sum_impl;
template <std::size_t... Indices>
struct sum_impl<std::index_sequence<Indices...>> {
  template <typename T, std::size_t>
  struct indexed_type {
    typedef T type;
  };

  template <typename T, typename... Types>
  static constexpr T eval(
      const typename indexed_type<T, Indices>::type&... args1,
      const Types&... args2) {
    return sum_impl<typename std::make_index_sequence<
               sizeof...(Indices) / 2>>::template eval<T>(args1...) +
           sum_impl<typename std::make_index_sequence<
               sizeof...(Types) / 2>>::template eval<T>(args2...);
  }
};
template <>
struct sum_impl<std::index_sequence<>> {
  template <typename T>
  static constexpr T eval(const T& arg) {
    return arg;
  }
};

}  // detail

template <typename T>
constexpr T sum() {
  return 0;
}
template <typename T, typename... Types>
constexpr T sum(const Types&... args) {
  return detail::sum_impl<std::make_index_sequence<
      sizeof...(Types) / 2>>::template eval<T>(args...);
}

int main() { static_assert(sum<int>(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) == 55, ""); }