タイプがランタイムにのみ知られている同種コンテナ

Question

シングルタイプの コレクションがあり、そのタイプは実行時にのみ知られています。タイプが定義されると、決して変更されません。私は現在、このように、ベクトル内のオブジェクトへのポインタを格納している：それは連続したメモリ内のインスタンスを格納することが可能です場合、私は思ったんだけど

std::vector<Animal*> v; 

。私の意図は、よりキャッシュフレンドリーなコードを書いて、コンテナをより速く反復することです。

私はブーストを使用することができ

::各ベクトルの要素のバリアント、例えば、

std::vector<boost::variant< Cat, Dog > > 

しかしsizeof(Dog)がsizeof(Cat)よりもはるかに大きいならば、オブジェクトはタイプCatである場合のメモリの無駄があります。

私はまた、容器のバリアントを使用することができます：

boost::variant< std::vector<Cat>, std::vector<Dog> > 

が、私はイテレータはこのケースでは、彼らはより多くのオーバーヘッドを導入する場合のだろうか分かりません。

「ポインタのベクトルが近づいていますか」ということはできるのですか？

詳細情報：オブジェクトのサイズは50〜250バイトで、コンテナの長さは10K〜1M要素です。コンテナを100万回繰り返します。

ありがとうございます。

EDIT：私は（あまりにも素敵な提案を）ここに同様の質問が見つかりました：私は答えに私のコメントをオンにするつもりです How to write cache friendly polymorphic code in C++?

Answer 1

右完全にここに書き換えて、はるかに簡単です。

私はs3riusにまだstd :: vectorを使用することに同意します。あなたは...

std::vector<Cat> 

をあなたが使用したい猫を保存していると、あなたは犬を保存している場合は、あなたがしたい場合には理想的...

std::vector<Dog> 

はしかし、あなたは、実行時に必要としますあなたが扱うケースを選択するための多型。

1つの方法は、戦略設計パターンである（または、それに触発されている）。これらのベクトルへのインタフェースの基本クラスを定義し、そのインタフェースを実装するテンプレートクラスをそのベクトルが含まれるようにします。

class Animals_IF 
{ 
    public: 
    virtual int size() const = 0; 
}; 

template<typename T> class Animals_Vector 
{ 
    private: 
    std::vector<T> store; 

    public: 
    int size() const; 
}; 

template<typename T> int Animals_Vector<T>::size() const 
{ 
    return store.size(); 
} 

ここでの問題は、それが私が上記の方法例としてsizeを選んだ理由はもちろんである特定のタイプを、知っていないため、インターフェイスがCatまたはDogに言及することはできませんということです。

可能なタイプのboost::variantを使用して値を渡すことが1つの解決策であるため、それぞれのストラテジ/ラッパークラスは、使用する前に、値が正しいタイプであることを確認できます。バリアントの値のラップ/アンラッピングは、（非テンプレートの）基本クラスのテンプレートメソッドによって処理できます。

すべてのラッピングとアンラッピングが非効率的な場合は、どのストラテジを扱うかを判断し、正しいストラテジ/ラッパータイプ（基本クラスではない）を呼び出す必要があります。これを行うには、すべての戦略/ラッパーのケースのboost :: variantを用意してください。これは、あなたもポインタへのポインタを持つことを妨げるものではありません。実際には、（必要に応じてテンプレートメソッドを使用して）クラスにポインタベースのクラスとboost::variantをラップします。

class Animals_IF 
{ 
    public: 
    typedef boost::variant<Cat,Dog> Animal; 

    virtual int size() const = 0; 

    template<typename T> void slow_push (const T &p) 
    { 
     push_ (Animal (p)); 
    } 

    private: 
    virtual void slow_push_ (const Animal &p) = 0; 
}; 

template<typename T> class Animals_Vector 
{ 
    public: 
    int size() const; 

    void fast_push (const T &p); 

    private: 
    std::vector<T> store; 

    void slow_push_ (const Animal &p); 
}; 

template<typename T> int Animals_Vector<T>::size() const 
{ 
    return store.size(); 
} 

template<typename T> void Animals_Vector<T>::fast_push (const T &p) 
{ 
    store.push (p); 
} 

template<typename T> void Animals_Vector<T>::slow_push_ (const Animal &p) 
{ 
    const T* item = boost::get<T> (&p); 

    if (T) store.push (*item); 
    // else throw? 
} 

class Animals 
{ 
    public: 
    int size() const 
    { 
     // null check needed? 
     return ptr->size(); 
    } 

    template<typename T> void slow_push (const T &p) 
    { 
     // null check needed? 
     ptr->slow_push (p); 
    } 

    template<typename T> void fast_push (const T &p) 
    { 
     Animals_Vector<T> *lptr = boost::get<T> (&store); 
     if (lptr) lptr->fast_push (p); 
     // else throw? 
    } 

    private: 
    Animals_IF* ptr; 
    boost::variant<Animals_Vector<Cat>,Animals_Vector<Dog>> store; 
}; 

共有インターフェイスが本当に提供できるものがない場合（すべてのメソッドは値を渡す必要があるため、ラッピングは/バリアントとしてアンラップすることは受け入れられない）全体戦略の事は不要です。異なるstd :: vector型のboost :: variantを持っているだけです。

また、pushはあまりにも単純であるため、上記のfast_pushは高速ではありません。繰り返し実行時の型チェックを避けることができる複雑なメソッドの方が高速ですフロント。

BTW - いい質問です。

Answer 2

。

私はすべての犬をvector<Dog>に入れ、すべての猫をvector<Cat>に入れてから別々に反復することをお勧めします。そうすれば、各ベクトルを最適にパックすることができます。

CRTPを使用すると、問題を起こさずに動物を簡単に追加できるように、自動化することができます。

いくつかの例：

template <typename T> 
class Container{ 
public: 
    static std::vector<T> m_elements; //static vector will contain animals 

    //overloaded operator new adds the Animal to m_elements 
    void* operator new(size_t){ 
     m_elements.push_back(T{}); 
     return &m_elements[m_elements.size() - 1]; 
    } 
}; 

template <typename T> std::vector<T> Container<T>::m_elements; 

//some example animals 
class Dog : public Container<Dog>{ 
public: 
    std::string woof; 

    Dog(char* s = "woof"){ 
     woof = s; 
    } 
}; 

class Cat : public Container<Cat>{ 
public: 
    std::string meow; 

    Cat(char* s = "meow"){ 
     meow = s; 
    } 
}; 

int main(){ 

    new Dog("woof"); 
    new Dog("rrawoof"); 
    new Cat("meow"); 
    new Cat("meweeow"); 

    //easy iteration 
    for(auto dog : Dog::m_elements) 
     std::cout << dog.woof << "\n"; 

    for(auto cat : Cat::m_elements) 
     std::cout << cat.meow << "\n"; 

    std::cout << "end"; 
} 

それはnewか別の質問ですが過負荷にすることをお勧めしますが、それはショーのための素晴らしいですかどうか。