11

std::vector穴を埋めるためにすべての要素をコピーする必要があるため、a の途中で要素を削除するのはコストがかかると一般に考えられています。

C++ 11では、std::vector代わりにすべての要素を下に移動します。これは非常に高速である必要があります（コピーに関してのみ）。少なくともそう思います。確かに時間的には線形ですが、一般的には古いバージョンよりも高速になるはずです。

これは本当ですか？途中でオブジェクトを削除することを心配する必要はありませんか?

4

5 に答える 5

15

ベクトルの内容によって異なります。それがPODまたはポインターである場合、それが違いを生むとは想像できません。コピーするのが重いが非常に高速に移動できるクラス インスタンスの場合、C++0x で高速化が期待できます。

ただし、std::vectors の途中から要素を削除することがコードのボトルネックである場合、C++0x はおそらく正しい修正ではないと思います。代わりに、そのようなケースをより適切に処理するデータ構造を検討するか、要素の順序が重要でない場合はstd::iter_swapさらに検討してください。std::vector::pop_back

于 2011-07-02T13:11:46.387 に答える
11

標準がコストに使用するものを考慮に入れると、まったく同じようにコストがかかります。標準では、含まれている型に対して実行される操作のコストが示されています。その操作の数は同じですが、それぞれの操作が高速になるだけです。

例として、C++03 で要素を a の途中に挿入するコストを考えてみましょうvector<string>。標準O(N)では、 はベクトルのサイズですがN、実際のコストは です。 は文字列のサイズです。コンテナー内の操作のコストを分析するときにを無視する理由は、コンテナー内の要素に依存するためです。移動可能な型を持つ C++0x でのコストは(文字列を新しい位置に移動できる) になりますが、宣伝されている複雑さは両方の場合になります。O(N * M)MMO(N)O(N)

簡単な反例として、ベクトルの途中での挿入は C++03 ではコストのかかる操作であると考えるとstd::vector<int>、C++0x でのベクトルの途中での挿入は同じくらいコストがかかります。その場合、スピードアップはありません。

また、潜在的な改善は、オブジェクトが移動可能である (移動可能である必要はない) ことに依存し、現在の STL 実装の一部は、(言語サポートなしで) 同様の方法で既に最適化されていることに注意してください。たとえば、Dinkumware などです。実装（私はこれだったと思います）にはいくつかの最適化がありstd::vector<std::vector<T> >、それによって a が成長すると、新しいストレージが作成され、空のベクトルで初期化され（メモリが割り当てられていないため、コストは最小限になります）swap、古いベクトルと新しいベクトルがsされます領域を割り当て、移動セマンティクスを効果的に実装します。

于 2011-07-02T13:14:45.920 に答える
6

事実上、ほとんどの場合、コピーするよりも移動する方がはるかに高速です。コピーする必要がある参照によって格納された情報を持つ型は、コピーを防ぐことができます。たとえば、ほとんどすべてのコンテナー、スマート ポインターなど、およびそれらの型を含むすべてのクラスです。

もちろん、これは依然として線形時間であるため、100 万の int がある場合、これ以上速くなることはありません。ただし、コンテナーやスマート ポインターなどの移動は、コピーよりも数桁速くなる可能性があります。

于 2011-07-02T13:19:39.637 に答える
5

私はまだ C++0x の移動機能の初心者ですが、.NET に固有の便利な高速化がここでどのように得られるかはよくわかりませんvector。

それはすべて要素タイプに帰着する必要があります。要素タイプのオブジェクトが copy よりも move の方が高速でない限り、速度が向上するとは想像できません。

于 2011-07-02T13:06:17.990 に答える
1

まず、ベクターまたはリストが必要だと判断しようとしていますか? データ構造へのインデックス ベースのアクセスが必要ない場合は、コンテナーの途中で削除が行われているため、list が適しています。また、ツリーなどの他のバリアントを考慮して、最適なものを決定する必要があります。これはパフォーマンスに大きな影響を与えないかもしれませんが、情報を共有するためだけに、リストのコンテンツが複数のページ ファイルに分散される可能性があるため、大量のデータを使用するとパフォーマンスが低下します。

右辺値の参照と移動コンストラクターは、コンテナーのパフォーマンスを向上させることができます。いくつかの不要なコピー操作などを回避できます。

于 2011-07-02T16:52:01.410 に答える