8

ベクトルに要素を追加するには、次の 2 つの方法を検討してください。

std::vector<int> vi1(10,42), vi2;

vi2.insert(vi2.end(),vi1.begin(),vi1.end());
<OR>
std::copy(vi1.begin(),vi1.end(),std::back_inserter(vi2));

std::copyバージョンはよりきれいに見え、2 回入力する必要はありませんvi2。しかし、挿入はメンバー関数であるのに対し、これは一般的なアルゴリズムであるため、同じことinsertを行うよりも優れたパフォーマンスを発揮できるでしょうか?std::copy

私は自分自身をベンチマークできますが、すべてのテンプレート タイプのすべてのベクトルに対して実行する必要があります。誰かがすでにやっていますか?

4

4 に答える 4

9

いくつかの微妙な違いがあります。最初のケース ( std::vector<>::insert) では、コンテナーに範囲を指定しているため、距離を計算し、単一のアロケーターを実行して、最終的に必要なサイズに拡張できます。2 番目のケース ( std::copy) では、情報がインターフェイスに直接存在せず、バッファの複数の再割り当てが発生する可能性があります。

複数の再割り当てが必要な場合でも、挿入の償却コストは一定でなければならないことに注意してください。また、ライブラリの特にスマートな実装には、2 番目のバージョンを効率的にするために必要なすべての情報が含まれていることに注意してくださいstd::copy

于 2013-01-17T15:23:48.307 に答える
1

vector::insertC++ 標準ライブラリのほとんどの主流の実装では、ほとんどの場合、パフォーマンスが向上する可能性があります。その理由は、vectorオブジェクトは現在割り当てられているメモリ バッファの内部情報を持っており、ランダム アクセス イテレータを使用して事前に要素数を計算できるため、挿入全体を実行するのに十分なメモリを事前に割り当てることができるためです。ただし、std::copyとともに をstd::back_inserter呼び出し続けるためvector::push_back、複数の割り当てがトリガーされる可能性があります。

たとえば、libstdc++の の GNU 実装はstd::vector::insert、イテレータ カテゴリが の場合、事前にバッファを割り当てますRandomAccessIterator。入力反復子では、要素の数を事前に決定できないため、vector::insertと同等になる場合があります。std::copy

于 2013-01-17T15:22:38.070 に答える
1

一度に複数のアイテムを挿入するケースを最適化できると思うvector::insertかもしれませんが、見た目よりも難しいです。たとえば、イテレータが出力イテレータの場合はどうでしょうか。何回挿入するかを事前に知る方法はありません。のコードは、 と同じようにinsert複数の を実行する可能性があります。push_backback_inserter

于 2013-01-17T15:24:26.430 に答える
0

と同等ではありませんstd::copypush_back(ある意味で)と同等です。

はい、std::back_inserter同じことを行います。どちらを使用しstd::copyても前面に挿入できますstd:front_inserter(ただし、では使用できませんstd::vector)。代わりに使用すると、指定したイテレータに挿入することもできますstd::inserter。ご覧のstd::copyとおり、3 番目の引数として渡したものに基づいて処理を行います。

ここで、質問の本質に戻ります。挿入する要素の数insertを検出する可能性があるため、パフォーマンスが向上するため、を使用する必要があると思います。あなたの場合、O(1)時間で要素を計算するのが簡単であることを意味するため、パフォーマンスが向上する可能性があります。v1std::vector

于 2013-01-17T15:18:27.803 に答える