C++で巨大なdequesを格納するためにdequeまたはvectorを使うべきですか？

Question

私は、それぞれがユーザー定義型のデータを格納する40の巨大なデッキを持っているとします。 40はそれほど多くはありませんが、デク自体は巨大です（なぜ私はベクトルに対してデクを使用することにしましたか）。私の質問は、私はこれらの40のdequesのコンテナを必要とする場合は、そのコンテナは、ベクトルまたは両端キューですか？

私の巨大なデュークスを含むベクトルを選択すると、ベクトルがメモリ内で巨大になるか、ベクトルの要素がデクを指すのでしょうか？ 40の巨大なdequesを格納した結果、格納されているベクトルが巨大になった場合、最初にユーザー定義型コンテナにdequesを使用するように選択したときに、連続したメモリ関連の問題を回避するためにdequesを使用する必要があります。

例;

class myClass { 
    // lots of data members resulting in large class object 
} 

int main(){ 

    std::deque<myClass> foo; 

    for(int i=0, i<10000000, i++){ 

    myClass classObject; 
    foo.push_back(classObject); 

    } 

} 

ここで、私たちのクラスオブジェクトを含む1000000要素の両端キューがあります。私はこれらのdequesの40を作成すると想像してください。

今、私はこれを行うべきかどうか、これらの40のデケのためのコンテナが必要です。

std::vector< std::deque<myClass> > bar 

またはこれを行う必要があります。

std::deque< std::deque<myClass> > bar 

Answer 1

一般的に、彼の神聖Stroustrup氏は、それを

を身を置くように私はあなたのデータ構造を知らないが、私はstd::vectorはそれを通常あなたが望むことを意味

を打つことができる賭けます一般的に「リッチ」な計算環境（読み込み：PCなど）は線形アクセスを最適化する上で非常に優れているため、リンクされたリストやその下にあるものではありません。

しかし、これらのデータを運ぶクラスオブジェクトがそれぞれ大きく、「CPUキャッシュエントリと同じくらい大きい」ということは、大きな違いにはなりません。それが正しいデータ構造である場合は、両端キューを使用してください（ほとんどの場合、リニアになっています）。あらかじめ分かっている場合は、その番号をコンストラクタに渡すことによって、1000000要素のメモリを事前に割り当てるように指示することもできます。

とにかく、使用しているメモリ構造は、必要とするメモリ量に効果的な影響を与えません。 40 * 10000000要素が必要になります。それでおしまい。それ以上のメモリがあれば、メモリを増やすか、より良いアルゴリズムを書く必要があります。

Answer 2

ベクトルの要素は、単に質問に

dequeのを指すんあなたは尋ねた：あなたは意味の質問に番号 を：はい。

vector<deque<T>>では、ベクトル要素は実際のオブジェクトであり、ポインタではありません。しかし、std::dequeオブジェクトは、デュークの内容が存在するダブルエンドデータ構造へのポインタを持っているので、かなり薄いです。

あなた40個のデータセットは、vector<deque<T>>（あるいはvector<vector<T>>）を使用してメモリ内に互いに隣接する保存されません - 内側容器は、std::arrayよう割当を含まない場合にのみ、すべてのコンテナーのデータを一緒に格納されます。

ベクトル要素をdequeオブジェクトへのポインタにしたい場合は、vector<unique_ptr<deque<T>>>を使用できます。

Answer 3

私はそれらを見るように彼らは、オプションを検討します：

• std::vector<std::deque>
• std::vector<std::deque *>
• std::deque<std::deque>
• std::deque<std::deque *>

container<std::deque> &違いは、すべてのメンバーが連続して格納されるという点に注意してください（両端キューはほとんどが連続しているわけではありません）。 これは、container<std::deque>でコンテンツにアクセスすると一般的にキャッシュミスはしませんが、実際のデータはポインタでオブジェクトに格納されることを意味します。 container<std::deque *>の場合、コンテナ内の値はキャッシュミスし、データにアクセスすると再びキャッシュされます。

コンテナがデキューまたはベクタであるかどうかは、バックを大きくする可能性があるかどうか、可変レートの繰り返しを気にするかどうかによって異なります。つまり、一度セットされるとベクトルが連続し、その上で線形的に反復する間にミスをキャッシュしません。デキューには保証されません。サブコンテナをホップするとプリフェッチを破る可能性があります。

編集：キャッシュミスが連続していることが好きな理由を忘れてしまいました。答えは断片化です。巨大なデータセットを使用すると、ヒープに大きな負担がかかります。ヒープ全体にメモリが散在しているため、メモリが十分に確保されているにもかかわらず割り当てが失敗する可能性が高くなります。カスタムアロケータは、フラグメンテーションおよびキャッシュミスを引き起こします。

Answer 4

コンテナは、実際のデータをFree Store（ヒープ）から外部ストレージに格納します。したがって、デキューデキューを格納するためには、デキューの内部ハウスキーピングデータはわずか数バイトしか格納されないため、を使用するとメリットはありません。だから私はこのためにstd::vectorを使用します。

数値がの場合、正確に40の場合、私はstd::arrayとみなします。