次の場合、どのSTLコンテナを使用する必要がありますか。
例：dataset（4,10,15）9に最も近い数値を見つけたい場合は、10を返す必要があります。
ベクターを使うことを考えましたが、ベクターの挿入と削除にはコストがかかります。
vector<int>
リストを使用する場合、データに到達する前にO（n）要素にアクセスする必要があります。
list<int>
並べ替えればいいのでセットを使うことを考えていましたが、SETを使う効率がよくわかりません。
だから私は誰かが良い解決策を与えることができることを願っています！
このSO投稿を確認する必要があると思います。どのシナリオで特定のSTLコンテナを使用しますか？小さいサイズの場合、ベクトルは、何をしようとしているかに関係なく、ほとんどのシナリオに適合します。
チャートはガイドですが、コンテナが定期的にアクセスされるという事実はコンテナの選択に影響しません。コンテナのサイズを気にしない限り、intを格納しているという事実は重要ではありません。リストコンテナまたはマップはあなたにとって重要ですか？
並べ替えはマップによって自動的に行われますが、コンテナのサイズがメモリに収まるほど小さい場合、ベクトルとリストの並べ替えは非常に高速になります。
データの挿入は、コンテナ内の任意の場所のリストとマップ用に最適化されています。マップの場合、それ自体が並べ替えられるという利点がありますが、サイズが十分に小さい場合は、新しいエントリを使用して新しいベクトルを作成するのは非常に高速です。
また、ハッシュマップを検討することもできます。それでも、コードのプロファイリングを行うのが最善です。最適なものは使用状況によって異なり、実際に測定してプロファイリングする必要があります。
また、STL<map>が十分に細かいバランスである<set>と判断し、それらのコンテナを使用することもできます。これらのコンテナは、挿入と削除で自動的に並べ替えられ、検索が高速ですが、各エントリのポインタを維持するオーバーヘッドがあり、サイズが大きくなります。ベクトルと比較して使用されるメモリ。これを気にしない場合は、これらのコンテナを検討できます。
それでも重要な場合は、各コンテナーのパフォーマンスをテストおよびプロファイリングして比較すると、コードが想定に対してどのように実行されるかに驚かれることでしょう。
要件が単にパフォーマンスである場合、選択は基本的に常にである必要がありstd::vectorます。
ノードベースのデータ構造（ツリーとリスト）の多くのメモリ割り当てを回避し、空間的な局所性を利用してはるかに効率的なトラバーサルを実現します。
もちろん、ベクトルの中央での挿入/削除では要素を移動する必要がありますが、それでもベクトルを他のデータ構造よりも遅くするのに十分なことはめったにありません。
他のデータ構造を使用する理由は次のとおりです。
std::map/ std::set：それらは便利に最適です。素晴らしく使いやすいので、最適なパフォーマンスが必要ない場合は、ソートされたコンテナー、またはキー/値マップが必要なときにそれらを使用します。（最高のパフォーマンスを得るには、ソートされたベクトルが非常に望ましい場合があります）deque、ポインタは最後に挿入/削除した後も有効であることが保証されますが、イテレータは無効になる可能性があります。、、の場合list、ポインタとイテレータの両方が挿入/削除中に有効であることが保証されますset。map除去）もちろん、これらは単なる経験則です。
パフォーマンスが関係する場合の唯一の普遍的に正しいルールは、「自分でベンチマークする」ことです。vector多くの一般的なシナリオで通常どのように機能するかはわかりますが、コンパイラと標準ライブラリを使用して、コードでどのように機能するかはわかりません。したがって、パフォーマンスが心配な場合は、それを測定してください。さまざまな選択肢を試して、どちらが速いかを確認してください。
セットは、挿入/削除/アクセスするのに十分効率的であり、常にソートされます。考慮すべき唯一のことは、セット内のエントリがconstである（したがって、順序が壊れていない）ことです。したがって、変更するには、削除、更新、および挿入する必要があります。
あなたの質問への答えはデータセットのサイズに完全に依存しています。リストが巨大なサイズに成長するにつれて、削除/挿入する必要のある要素に到達するために線形トラバーサルを実行するのにかかる時間は、かかる時間よりもはるかに長くなります。ベクトルが削除/挿入を行うため。したがって、データセットが小さい場合はリストを使用し、データセットが大きい場合はベクトルを使用します。
並べ替える必要がある場合は、二分探索木を使用します