1

X：私がやりたいこと：

私はタイプを持っています：BaseTypeとDerivedType<int k>（以下のコードを参照）、そしてK派生タイプのベクトルのコレクションを処理する必要がありますstd::vector<DerivedType<k>>、k = 1...K。これらのベクトル内のオブジェクトにアクセスし、に依存する操作を実行したいと思いますk。Kコンパイル時定数です。この問題は、実装で説明されています。

タイプは次のように定義されます。

#include <iostream>
#include <algorithm>

struct BaseType { // Interface of the DerivedTypes
  virtual void print(){std::cout << "BaseType!" << std::endl; }
};

template< int k >
struct DerivedType : public BaseType {
  static const int k_ = k;
  // ... function calls templated on k ...
  void print(){std::cout << "DerivedType: " << k_ << std::endl;}
};

template< int k >
void doSomething ( DerivedType<k>& object ) { object.print(); }

そして私がしたいのは：

int main() {

  // My collection of vectors of the derived types:
  std::vector<DerivedType<0>> derType0(2);
  std::vector<DerivedType<1>> derType1(1);
  std::vector<DerivedType<2>> derType2(3);
  // ... should go to K: std::vector<DerivedType<K>> derTypeK;

  // Iterate over the derived objects applying a k-dependent templated function:
  std::for_each(begin(derType0),end(derType0),[](DerivedType<0>& object){
    doSomething<0>(object);
  });
  std::for_each(begin(derType1),end(derType1),[](DerivedType<1>& object){
    doSomething<1>(object);
  });
  std::for_each(begin(derType2),end(derType2),[](DerivedType<2>& object){
    doSomething<2>(object);
  });

  return 0;
}

Kコンパイル時定数であるを変更するだけでよいように、コードを繰り返さないようにしたいO(10)。理想的には、私はこの「もっと似た」ものを持っているでしょう：

// Pseudocode: do not try to compile this

create_derived_objects(DerivedType,K)
  = std::vector< std::vector<DerivedType<k>>* > my_K_derived_types;                                                  

for each vector<DerivedType<k>>* derivedTypes in my my_K_derived_types
  for each object in (*derivedTypes)
    doSomething<k> on object of type derivedType<k>
    // I could also restrict doSomething<k> to the base interface

派生型の各ベクトルには、オブジェクトが含まO(10^6)れO(10^9)ます。最も内側のループは、私のアプリケーションの中で最も時間のかかる部分であり、dynamic_castを最も外側のループのオプションのみにします。

Y：私が成功せずに試したこと。

私は現在、Abrahams C ++テンプレートメタプログラミングの本を勉強して、を使用できるかどうかを確認していますboost::mpl。私もboost::fusionそれを使用できるかどうかを確認するためにチュートリアルを行っています。ただし、これらのライブラリの学習曲線はかなり大きいため、1週間投資する前に、より優れたシンプルなソリューションが利用できるかどうかを最初に尋ねたいと思いました。

私の最初の試みは、std::vector<DerivedType<k>>を作成できるようにベクトルをラップし、ループvector<WrappedDerivedTypes*>内で単一の各ベクトルに個別にアクセスすることでした。for_eachしかし、ループの中には、if(dynamic_cast<std::vector<DerivedType<0>>>(WrappedVector) != 0 ){ do for_each loop for the derived objects } else if( dynamic_cast...) { do...} ...排除できなかった一連の問題があります。

4

2 に答える 2

3

ベクトルの一般的な連結リスト、戦略パターン、および連結リストを介して再帰的に戦略を適用するものに基づく再帰的ソリューションについてはどうでしょうか? (注: 最後に改良版を参照してください):

#include <iostream>
#include <vector>

template <int j>
class holder {
public:
    const static int k = j;
};

template <int j>
class strategy {
public:
    void operator()(holder<j> t)
    {
        std::cout << "Strategy " << t.k << std::endl;
    }
};

template <int k>
class lin_vector {
private:
    std::vector<holder<k>> vec;
    lin_vector<k-1> pred;
public:
    lin_vector(const lin_vector<k-1> &pred, std::vector<holder<k>> vec)
        : vec(vec), pred(pred) { }
    std::vector<holder<k>> get_vec() { return vec; }
    lin_vector<k-1> &get_pred() { return pred; }
};

template <>
class lin_vector<0> {
public:
    lin_vector() { }
};

template <int k, template <int> class strategy>
class apply_strategy {
public:
    void operator()(lin_vector<k> lin);
};

template <int k, template <int> class strategy>
void apply_strategy<k, strategy>::operator()(lin_vector<k> lin)
{
    apply_strategy<k-1, strategy>()(lin.get_pred());
    for (auto i : lin.get_vec())
    strategy<k>()(i);
}

template <template <int> class strategy>
class apply_strategy<0, strategy>
{
public:
    void operator()(lin_vector<0> lin) { /* does nothing */ } 
};


template <int k>
lin_vector<k> build_lin()
{
    return lin_vector<k>(build_lin<k-1>(), {holder<k>()});
}

template <>
lin_vector<0> build_lin()
{
    return lin_vector<0>();
}

int main(void)
{
    apply_strategy<5, strategy>()(build_lin<5>());
}

C++11 コンパイラでコンパイルします。ほとんどの場合、 a の構築には大量のコピーが必要であるという事実に不満を感じるでしょうが、lin_vector必要に応じて構造を特殊化することができます (おそらく、predをポインターで置き換えるか、作成戦略をリンク リストに直接埋め込む)。

EDIT :ここには、多くのコピーを回避し、リストの構築と処理をより一貫した均一な方法で処理する改良版があります。

#include <iostream>
#include <vector>

template <int j>
class holder {
public:
    const static int k = j;
};

template <int k>
class lin_vector {
private:
    std::vector<holder<k>> vec;
    lin_vector<k-1> pred;
public:
    std::vector<holder<k>> &get_vec() { return vec; }
    lin_vector<k-1> &get_pred() { return pred; }
};

template <>
class lin_vector<0> {
public:
    lin_vector() { }
};

template <int k, template <int> class strategy>
class apply_strategy {
public:
    void operator()(lin_vector<k> &lin);
};

template <int k, template <int> class strategy>
void apply_strategy<k, strategy>::operator()(lin_vector<k> &lin)
{
    apply_strategy<k-1, strategy>()(lin.get_pred());
    strategy<k>()(lin.get_vec());
}

template <template <int> class strategy>
class apply_strategy<0, strategy>
{
public:
    void operator()(lin_vector<0> &lin) { /* does nothing */ } 
};

template <int j>
class strategy {
public:
    void operator()(std::vector<holder<j>> &t)
    {
        std::cout << "Strategy " << j << ", elements: ";
        for (auto v : t)
            std::cout << v.k << " ";
        std::cout << std::endl;
    }
};

template <int j>
class build_strategy {
public:
    void operator()(std::vector<holder<j>> &t)
    {
        for (unsigned int i = 0; i < j; i++)
            t.push_back(holder<j>());
    }
};

int main(void)
{
    const int K = 5;
    lin_vector<K> list;
    apply_strategy<K, build_strategy>()(list);
    apply_strategy<K, strategy>()(list);
}
于 2012-07-27T13:44:09.113 に答える
1

おそらくやり過ぎですが、仮想ディスパッチのないソリューションも可能です。

最初に必要なのは、doSomething<K>()各派生型に特化した関数テンプレートです。

template <int K>
void doSomething(vector<DerivedType<K> >& x);

template <>
void doSomething<1>(vector<DerivedType<1> >& x) { ... }

template <>
void doSomething<2>(vector<DerivedType<2> >& x) { ... }   // etc.

struct次に、再帰的に定義されたテンプレートを使用して、厳密に型指定されたベクトルのコレクションを構築できます。

template <int K>
struct vov {
    vov<K - 1> prev;
    vector<DerivedType<K> > v;
};

template <>
struct vov<1> {
    vector<DerivedType<1> > v;
};

最後に、再帰関数テンプレートを記述して、この構造を処理できます。

template <int K>
void process(vov<K>& x) {
    doSomething(x.v);     // Type inference will find the right doSomething()
    process(x.prev);      // Here too
}

template <>
void process<1>(vov<1>& x) {
    doSomething(x.v);
}

メインコードは次のようになります。

vov<42> foo;
process(foo);

process()関数呼び出しは再帰を使用して反復を実行するため、 K スタック フレームを不必要に使用する可能性があります。ただし、これは末尾再帰であり、最新の最適化 C++ コンパイラは通常、スタックを無駄にすることなく単純な反復に変換できます。末尾再帰を使用すると、DerivedType<1>ベクターが最後に処理されるように、ベクターを「逆」の順序で処理する必要がありますが、必要に応じて、2 つのテンプレート パラメーターを使用してもう少し精巧なテンプレートでこれを修正できintます (一方は他方に向かって「カウントアップ」します)。 、 int1 に向かって「カウントダウン」する単一のパラメーターの代わりに)。

DerivedType<k>このソリューションでそれぞれの fromを導出してもメリットがないことに注意してください。別の理由で必要でない限り、完全にBaseType忘れてもかまいません。BaseType

これらのプロセスの一部を単純化する MPL プリミティブが存在する可能性があります。知っている人は自由に編集してください。

于 2012-07-27T13:43:45.750 に答える