139

「C++ コンテナーの選択」と呼ばれるよく知られたイメージ (チート シート) があります。用途に合わせて最適な容器を選ぶ流れ図です。

すでに C++11 バージョンがあるかどうか知っている人はいますか?

これは前のものです： eC++ コンテナの選択

4

4 に答える 4

98

私が知っていることではありませんが、テキストで実行できると思います。listまた、は一般的にそれほど優れたコンテナではなく、 もそうではないため、チャートはわずかにずれていforward_listます。どちらのリストも、ニッチなアプリケーション向けの非常に特殊なコンテナです。

このようなチャートを作成するには、次の 2 つの簡単なガイドラインが必要です。

  • 最初にセマンティクスを選択
  • 複数の選択肢がある場合は、最も単純なものを選びます

パフォーマンスについて心配することは、通常、最初は役に立ちません。ビッグオーの考慮事項は、数千（またはそれ以上）のアイテムを処理し始めたときにのみ有効になります。

コンテナーには、次の 2 つの大きなカテゴリがあります。

  • 連想コンテナ:find操作があります
  • シンプル シーケンスコンテナ

そして、それらの上にいくつかのアダプターを構築できます: stack、queue、priority_queue. アダプタはここでは省略します。アダプタは認識できるほど十分に特殊化されています。

質問 1:連想?

  • 1 つのキーで簡単に検索する必要がある場合は、連想コンテナーが必要です
  • 要素を並べ替える必要がある場合は、順序付けられた連想コンテナーが必要です
  • それ以外の場合は、質問 2 にジャンプします。

質問 1.1:注文しましたか?

  • 特定の順序が必要ない場合はunordered_コンテナーを使用し、それ以外の場合は、従来の順序で対応するものを使用します。

質問 1.2:別のキーですか?

  • キーが値と異なる場合は を使用しmap、それ以外の場合は を使用します。set

質問 1.3:重複？

  • 重複を保持したい場合は を使用しmulti、それ以外の場合は使用しないでください。

例：

一意の ID が関連付けられた複数の人がいて、その ID からできるだけ簡単に人のデータを取得したいとします。

  1. 関数が必要なfindため、連想コンテナが必要です

1.1。私は順序を気にすることができなかったので、unordered_コンテナ

1.2. 私のキー (ID) は、関連付けられている値とは別のものです。map

1.3。ID は一意であるため、重複が入り込むことはありません。

最終的な答えは次のとおりstd::unordered_map<ID, PersonData>です。

質問 2:メモリは安定していますか?

  • 要素がメモリ内で安定している必要がある場合 (つまり、コンテナ自体が変更されたときに要素が動き回ってはならない場合)、いくつかのlist
  • それ以外の場合は、質問 3 にジャンプします。

質問 2.1:どれ?

  • に落ち着くlist; aforward_listは、メモリ フットプリントが少ない場合にのみ役立ちます。

質問 3:動的サイズ?

  • コンテナーのサイズが (コンパイル時に) 既知であり、このサイズがプログラムの過程で変更されず、要素がデフォルトで構築可能であるか{ ... }、(構文を使用して) 完全な初期化リストを提供できる場合は、 array. これは、従来の C 配列を置き換えますが、便利な機能を備えています。
  • それ以外の場合は、質問 4 にジャンプします。

質問 4:ダブルエンド?

  • 前面と背面の両方からアイテムを削除できるようにする場合は を使用しdeque、それ以外の場合は を使用しvectorます。

デフォルトでは、連想コンテナが必要でない限り、選択はvector. それはSutter と Stroustrup の推薦でもあることがわかりました。

于 2012-05-22T11:26:23.053 に答える
52

私はマシューの答えが好きですが、フローチャートを次のように言い換えます。

std::vector を使用しない場合

デフォルトでは、もののコンテナーが必要な場合は、を使用しますstd::vector。したがって、他のすべてのコンテナは、 に代わる機能を提供することによってのみ正当化されstd::vectorます。

コンストラクター

std::vectorアイテムをシャッフルできる必要があるため、そのコンテンツは移動構築可能である必要があります。これはコンテンツに負担をかけるほどの負担ではありません (デフォルトのコンストラクターは必須ではないことに注意してください。などのおかげですemplace)。ただし、他のコンテナーのほとんどは、特定のコンストラクターを必要としません (これも のおかげですemplace)。したがって、移動コンストラクターを絶対に実装できないオブジェクトがある場合は、別のものを選択する必要があります。

Astd::dequeは、 の多くのプロパティを持つ一般的な置換std::vectorですが、両端キューの両端にしか挿入できません。真ん中のインサートは移動が必要です。Astd::listは、その内容に要件を課しません。

ブール値が必要

std::vector<bool>ではありません。まあ、それは標準です。ただし、通常は許可されている操作が禁止されvectorているため、通常の意味ではありません。std::vectorそして、それは間違いなく含まれていませんbools。

vectorしたがって、のコンテナーから実際の動作が必要な場合、boolから取得することはできませんstd::vector<bool>。そのため、 で期日を迎える必要がありますstd::deque<bool>。

検索中

コンテナ内の要素を検索する必要があり、検索タグを単なるインデックスにできない場合は、 and を優先して放棄する必要がある場合がありstd::vectorます。キーワード " may " に注意してください。sortedが合理的な代替手段になる場合があります。または、ソート済みを実装するBoost.Container の.setmapstd::vectorflat_set/mapstd::vector

現在、これらには 4 つのバリエーションがあり、それぞれに独自のニーズがあります。

  • map検索タグが探しているアイテムと同じでない場合は、a を使用します。それ以外の場合は、を使用しsetます。
  • コンテナー内に多数のアイテムがあり、検索パフォーマンスが絶対にではなく である必要unorderedがある場合に使用します。O(1)O(logn)
  • multi複数のアイテムに同じ検索タグが必要な場合に使用します。

注文

特定の比較操作に基づいてアイテムのコンテナーを常に並べ替える必要がある場合は、set. または、multi_set複数のアイテムに同じ値が必要な場合。

または、 sorted を使用できますが、ソートstd::vectorしたままにしておく必要があります。

安定

イテレータと参照がいつ無効化されるかが問題になることがあります。他のさまざまな場所にあるアイテムへのイテレータ/ポインタがあるようなアイテムのリストが必要な場合、std::vector無効化へのアプローチは適切ではない可能性があります。現在のサイズと容量によっては、挿入操作を行うと無効になる場合があります。

std::list確実な保証を提供します。イテレータとそれに関連付けられた参照/ポインタは、アイテム自体がコンテナから削除されたときにのみ無効になります。std::forward_listメモリが深刻な懸念事項である場合はそこにあります。

保証が強すぎる場合std::dequeは、弱いが有用な保証を提供します。無効化は途中で挿入すると発生しますが、先頭または末尾で挿入すると、コンテナー内のアイテムへのポインター/参照ではなく、 iteratorの無効化のみが発生します。

挿入性能

std::vector最後に安価な挿入を提供するだけです（それでも、容量を吹き飛ばすと高価になります）.

std::listパフォーマンスの点では高価ですが (新しく挿入されたアイテムごとにメモリ割り当てが必要です)、一貫性があります。また、事実上パフォーマンス コストなしでアイテムをシャッフルしたり、パフォーマンスを低下させずに同じタイプの他のstd::listコンテナーとアイテムを交換したりするための不可欠な機能も提供します。物事をたくさんシャッフルする必要がある場合は、 を使用してstd::listください。

std::deque頭と尾で一定時間の挿入/削除を提供しますが、途中での挿入はかなり高価になる可能性があります. したがって、前面だけでなく背面にも物を追加/削除する必要がある場合は、必要なstd::dequeものかもしれません.

移動セマンティクスのおかげで、std::vector挿入のパフォーマンスは以前ほど悪くない可能性があることに注意してください。一部の実装では、ムーブ セマンティック ベースのアイテム コピー (いわゆる「スワップティミゼーション」) の形式が実装されていましたが、現在ではムーブは言語の一部であるため、標準で義務付けられています。

動的割り当てなし

std::array可能な限り少ない動的割り当てが必要な場合は、適切なコンテナーです。これは C 配列の単なるラッパーです。これは、そのサイズがコンパイル時にわかっている必要があることを意味します。それを受け入れることができる場合は、を使用してstd::arrayください。

そうは言っても、 size を使用std::vectorしてreserveing することは、bounded に対しても同様に機能しますstd::vector。このように、実際のサイズは変動する可能性があり、メモリ割り当ては 1 つしか取得できません (容量を使い果たした場合を除きます)。

于 2012-05-23T07:35:25.400 に答える
27

上記のフローチャートの C++11 バージョンを次に示します。[元々は、元の作者であるMikael Perssonに帰属せずに投稿された]

于 2014-06-22T01:47:27.467 に答える