私はオブジェクトのコレクションのために、次の要件持ちの保守：順序（無制限理論的には、実際には数千のカップルは十分すぎるほどでなければなりません）オブジェクトの順序付きコレクション
私が保管していたオブジェクトが大きくない、プロパティのカップルや小さな配列または2（256個のブール値）
リンクリストを書く前に知っておくべきクラスがありますか？
元の回答：標準ライブラリのstd::list（二重リンクリスト）のようです。
新しい回答： 仕様を変更した後、std::vectorは数千もの要素がなく、ベクトルの途中で膨大な数の挿入や削除がない限り機能します。中間での挿入と削除の線形複雑さは、ベクトル演算の低い定数よりも大きくなる可能性があります。ちょうど開始時と終了時に多くの挿入や削除を行っている場合は、std::dequeも同様に機能する可能性があります。
私は彼があなたにそれを変更したのを見ます。彼は、受け入れ可能なオプションとしてリストを無効にするランダムアクセスを追加しました。 – wheaties
@wheaties：ノートをありがとう - 私はちょうど私の答えを更新しました。たとえ問題が依然として1つを書くと言われても、リンクされたリストは高速ランダムアクセスのためには機能しません。もちろん、それは更新に対するランダムアクセスの比率に依存します。 –
仕様の変更について申し訳ありません。更新された答えをありがとう、非常に感謝します。 –
最適なコンテナを選択するための要件が不足しています。
ダイナミックサイズ（理論的には無制限で、実際には数千のカップルは十分すぎるほどでなければなりません）
STLコンテナは、必要に応じて成長するように設計されています。
秩序がありますが、任意の場所で並べ替えや挿入が可能です。
再注文を許可していますか？ std :: mapは並べ替えることができません。一つのstd :: mapから削除し、別の順序を使用して別のstd :: mapを挿入することはできますが、異なるテンプレートのインスタンス化として、2つの変数は異なる型を持ちます。 std :: listにはsort()メンバ関数[これを指摘してくれてありがとうBlastfurnace]があります。特に大きなオブジェクトでは効率的です。 std :: vectorは、非メンバstd::sort()関数を使用して簡単にソートすることができます。特に小さなオブジェクトに対しては効率的です。
任意の場所で効率的に挿入できるのは、マップやリストで行うことができますが、どのようにそれらの場所を見つけることができますか？リストでは、検索は線形です（あなたはすでに知っているところから始め、要素ごとに順方向または逆方向に走査する必要があります）。 std :: mapはすでにソートされたベクトルと同様に効率的な検索を提供しますが、ベクターに挿入することは、後続の要素をすべてスペースを作るためにシフト（コピー）することを伴います。
すべてのコンテナは、削除を可能にしていますが、挿入のためにそうであるように、あなたが既に場所を知っていればあなたはすなわち、高速リストについては、（厳密に同じ効率の問題を持って、高速なマップの削除
を可能にしますベクトルの削除は遅いですが、要素を削除せずに削除した場合は "マークする"ことができます（たとえば、文字列を空にし、構造体にブール値フラグを付けるなど）。
インデックス付きアクセス - ランダムアクセス
ベクトルが数値的にインデックス付けされる（ただし、バイナリ検索することができる）、任意のキー（ただし、数値指標）マップ。リストは索引付けされず、既知の要素から線形に検索されなければなりません。
カウント
std::listが（それはO（1）スプライスを提供できるように）、しかし、あなたは簡単にサイズを自分で追跡することができます（あなたがスプライスないだろうと仮定するとO（n）のsize()機能を提供し
size()のO（1）時間を持っています。
結論
STDを使用しているかどうかを検討::リストはあなたが必要とする要素のために非効率的な線形検索の多くになります。そうでなければ、リストは効率的な挿入と削除を行います。リゾートは良いです。
マップやハッシュマップが頼っすることができない、迅速な検索と簡単に挿入/削除を許可しますが、簡単に中程度の効率で（別のソート基準に別のマップにからデータを移動することができます。
Aをベクトルは高速検索とインプレイスリソーティングを可能にしますが、挿入/削除が最悪です。要素インデックスを使用したランダムアクセスルックアップでは最も速いです。
-Insertion and Deletion：これはSTLコンテナで可能ですが、リンクリストコンテナ（リスト、マップ、セット）は一定時間内にこれを行いますが、配列のようなコンテナ（ベクトル）は線形時間（一定償却割り当て）で行います。
- 並べ替え：並べ替えられたコレクションを常に保持できることを考慮すると、これは大きな問題ではなく、STLコンテナによって許可されます。マップとセットについては、何もする必要はありません。コレクションは常にソートされた状態に保ちます。ベクタやリストの場合は、その作業を行う必要があります。つまり、新しい要素がある場所をバイナリ検索してそこに挿入する必要があります（ただし、STLアルゴリズムには必要な部分がすべて含まれています）。
-Resorting：ルールAに関してソートされた現在のコレクションを取得し、ルールBに関してコレクションを採用する必要がある場合は、これが問題になる可能性があります。 mapやsetのようなコンテナはソートルールによって（型として）パラメータ化されています。つまり、元のコレクションからすべての要素を抽出し、それらを新しいコレクションルールで新しいコレクションに挿入する必要があります。しかし、ベクターコンテナを使用している場合は、STLソート機能を使用していつでも好みのルールを適用することができます。
ランダムアクセス：あなたはランダムアクセスが必要だと言いました。個人的には、私のランダムアクセスの定義は、一定時間内にコレクション内の任意の要素にインデックスでアクセスできることを意味します。その定義（私はかなり標準だと思います）では、リンクリストの実装は修飾されず、配列のようなコンテナ（std :: vectorなど）を使用する唯一のオプションが残ります。
結論として、std :: vectorを使用して、独自のソートされた挿入とソートされた削除を実装するのが最善でしょう（削除する要素を見つけるためにバイナリ検索を実行するか、新しい要素を挿入します）。保存する必要のあるオブジェクトのサイズが大きく、ソートされたデータ（名前、IDなど）が小さい場合は、ソートされていないオブジェクトのリンクリストを保持することで問題を分割することを検討することができます完全な情報）、キーのソートされたベクトルをリンクされたリスト内の対応するノードへのポインタとともに保持します（この場合、もちろんstd :: listをstd :: listとstd :: vectorを使用します）。
私はSTLコンテナの熟練者ではないので、私は上の方が間違っているかもしれません。 STLを自分で探検し、必要なもの、または少なくとも必要なものすべてを見つけることができます。たぶんBoostライブラリも見てください。
'map'と' set'はリンクリストを使って実装することはできませんが、Red-Blackツリーのような自己平衡型バイナリ検索ツリーとして実装されています（ほとんどの場合）。したがって、これらのコンテナの挿入と削除の複雑さは、定数ではなく対数です。 –
それを指摘してくれてありがとう！私はマップとセットがどのように実装されたかを常にちょっと疑問に思っていましたが、本当にそれを調査したことはありませんでした。 –
典型的な実装は赤黒のツリーですが、標準ではそれを強制しません。 @James McNellis：実際には、SkipListは伝統的なリンクリストの拡張として見ることができ、実際には見たことがないものの、 'map'と' set'実装に適しています。 –
コンテナに保存するオブジェクトのタイプはどれくらいですか？コピーするのは費用がかかりますか？要素がコンテナの中央に挿入または削除される頻度はどれくらいですか？個々の要素にランダムアクセスする必要がありますか？ STLコンテナのいずれかを見ましたか？ –