<n個の複雑さを持つベクトルの要素を消去する

Question

n個以上の複雑さを抑えながら、ソートされたベクトルから要素を消去する必要があります。私はvector . eraseの方法を知っていますが、それを消去する方法はありますが、その複雑さはnです。私はちょうど最後の要素でその構造要素を書き換えることができますし、ポップバックを使用して定数でなければならない最後のメソッドを削除することができますが、それはソートされないので、私は再びそれを並べ替える必要があります。この問題を解決して複雑さを下回ることさえ可能ですか？

Answer 1

ソートが必要なので、std::vector（私が知る限り）の解決策はありません。しかし、std::vectorはあなたのケースに適したコンテナではないようです。 std::listはあなたのための1つのオプションです（より良いかもしれません）。この基準から

：http://www.cplusplus.com/reference/list/list/erase/

複雑

消去された要素の数に線形（破壊）。

これは、デストラクタをN回呼び出すことを意味し、Nは削除されるアイテムの数です。したがって、データ構造をソートしたままで、高性能で要素を消去することができれば、削除された項目の数は直線的になります（std::listアイテム数ではなく）

Answer 2

ベクトルを別のコンテナ（例えば、マルチセットなど）で置き換える方がよいでしょうか。