17

コンパイラによって計算されたインデックスの関数によって要素が初期化され、結果がアプリケーションイメージのデータセクション（.rodata）に格納される、C ++ 11配列を実装する1つの方法は、テンプレート、部分特殊化、およびconstexprは次のとおりです。

#include <iostream>
#include <array>
using namespace std;

constexpr int N = 1000000;
constexpr int f(int x) { return x*2; }

typedef array<int, N> A;

template<int... i> constexpr A fs() { return A{{ f(i)... }}; }

template<int...> struct S;

template<int... i> struct S<0,i...>
{ static constexpr A gs() { return fs<0,i...>(); } };

template<int i, int... j> struct S<i,j...>
{ static constexpr A gs() { return S<i-1,i,j...>::gs(); } };

constexpr auto X = S<N-1>::gs();

int main()
{
        cout << X[3] << endl;
}

これは、Nの値が大きい場合は機能しません。

error: constexpr evaluation depth exceeds maximum of 512

これは、再帰的なテンプレート評価のヘッドテールスタイルが原因であり、Nに関して線形の深さを持っています。

評価深度が線形ではなく、Nに関して対数になるようにする方法はありますか？（したがって、デフォルトの深度制限を回避します）

4

3 に答える 3

22

コードで使用しているものがインデックス トリックの奇妙な形式である場合は、O(log N)インスタンス化された実装を次に示します。

// using aliases for cleaner syntax
template<class T> using Invoke = typename T::type;

template<unsigned...> struct seq{ using type = seq; };

template<class S1, class S2> struct concat;

template<unsigned... I1, unsigned... I2>
struct concat<seq<I1...>, seq<I2...>>
  : seq<I1..., (sizeof...(I1)+I2)...>{};

template<class S1, class S2>
using Concat = Invoke<concat<S1, S2>>;

template<unsigned N> struct gen_seq;
template<unsigned N> using GenSeq = Invoke<gen_seq<N>>;

template<unsigned N>
struct gen_seq : Concat<GenSeq<N/2>, GenSeq<N - N/2>>{};

template<> struct gen_seq<0> : seq<>{};
template<> struct gen_seq<1> : seq<0>{};

// example

template<unsigned... Is>
void f(seq<Is...>);

int main(){
  f(gen_seq<6>());
}

実例。

于 2012-10-25T16:27:36.080 に答える
4

一般的な constexpression 関数を使用する C++14 では、シーケンス、make_sequence は必要ありません

static constexpr int f(int i) noexcept { return i * 2; }

template< int N, typename F >
static constexpr std::array<int,N> generate_array( F fo ) noexcept
{
     std::array< int, N > result{}; // init with zero
     int i = 0; 
     for( auto& x : result) x = fo(++i);

     return result;
}

// test
constexpr auto arr = generate_array<10>( f );

問題が1つだけあり、それをコンパイルできるコンパイラはありません:)

于 2013-11-18T08:01:45.370 に答える
1

線形テンプレートのインスタンス化の深さを引き起こしている唯一の末尾再帰テンプレートは、 のテンプレート パラメータ リスト内の整数のリストの構築ですS。

あなたが提案するように、これは対数インスタンス化の深さで行うことができます：

template <int ... Ints> struct seq;

template <int Start, int End> 
struct range
{
  typedef concat_seq<range<Start, Start+(End-Start)/2>::type, range<Start+(End-Start)/2, End>::type>::type type;
};

template<int Singleton>
struct range<Singleton, Singleton+1>
{
  typedef seq<Singleton> type;
};

template <int NoSingleton>
struct range<NoSinleton, NoSingleton>
{
  typedef seq<> type;
};

必要に応じて一連の s を追加しtypename、実装(簡単) し、 fromconcat_seqの引数リストを抽出します。fsrange<0, N>::type

于 2012-10-25T16:21:15.867 に答える