次の操作をサポートして維持するアイテム（一部のオブジェクト）のリストが必要です。
STLリストは正しい選択のようです。しかし、どうすれば2番目の操作を一定時間で行うことができますか？各ノードへのポインタをどこかに保存して直接削除することもできますが、eraseはイテレータを使用するため、機能しません。
使用例：
items = list<myobj>..
items.push_back(obj1)
items.push_back(obj2)
items.push_back(obj3)
items.remove(obj2) // <- How to do this in constant time.
push_backがどういうわけかノードへのアクセスを与えた場合、私は使用できたでしょう：
map[obj1] = items.push_back(obj1)
items.remove(map[obj1])
1つのオプションは、マップでイテレータを使用することです。もっと簡単な方法はありますか？
妥協点は、ほとんどの std::set 実装のような赤黒ツリーになります。挿入、検索、削除の O(log n) です。ツリーは、基本的に究極の妥協データ構造です。彼らは何も驚くべきことではありませんが、常に十分に仕事を成し遂げます.
それ以外の場合は、リンク リストとベクターの両方を使用してコードをプロファイリングし、ベクターのサイズ変更が本当にひどいものかどうかを調べます (これは、行う頻度によって異なります)。
問題を処理するだけの、より優れた (エレガントではありませんが、非常に効果的な) 解決策があるかもしれません。リストをどのように消費するかについては言及していませんが、値を未使用として取っておくことができる場合は、ベクターを使用して、要素を実際に削除するのではなく、単に削除済みとしてマークすることができます。vector<bool>または、ベクトルを使用して、アイテムが削除されているか有効かを示す別のビットセット (または C++03 ) を持っています。それを削除するには、ビットマップ内のビットを反転するだけです。反復するときは、コンテンツを処理する前に削除ビットマップを確認することを忘れないでください。メモリが問題ではなく、速度のみが重要で、簡単さ/明確さが重要な場合は、 を削除フラグのvector<object>場所vector<pair<bool, object>>に置き換えます。bool
Boost.MultiIndexを見たいと思うかもしれません。これにより、データ構造に対して複数のインデックスを組み合わせることができます。そのため、線形スペースのオーバーヘッドを犠牲にして、一定時間の検索と要素の削除を行うことができます。