c++ - コンテナの複雑さ

Question

したがって、 と がstd::set<int>ありstd::list<int>ます。
コンテナを整理したい。セットの場合、挿入された要素の
ように複雑になります。リストの場合、要素の挿入+呼び出しの ような複雑さがあります。 どちらの場合も複雑さは ですが、 の場合は余分な操作があります。そして、リバランスのための一定の時間があります。O(nlogn)n
O(n)nO(nlogn)list::sort
O(nlogn)O(n)std::listset

ここで質問があります。どのコンテナがより速く動作しますか?

Answer 1

「const」ソートされたコンテナーが必要なため、std::vectorキャッシュに適したコンテナーをお勧めします。

初期化中:

• push_backすべての要素O(n)。
• std::sortベクトルO(n log n).
• std::unique重複を削除したい場合（そうですstd::set）。O(n).

したがって、初期化はO(n log n).

要素が存在するかどうかを確認するには、の代わりにstd::binary_searchto haveを使用します。O(log n)O(n)