c++ - 整数値のリストを検索して更新する最速のデータ構造は何ですか?

Question

整数の数が不明な unordered integers のリストを維持する必要があります。時間の経過とともに増加または減少する可能性があります。この整数のリストを頻繁に更新する必要があります。vector を使ってみました。しかし、それは本当に遅いです。配列の方が高速に見えますが、リストの長さが固定されていないため、サイズ変更にかなりの時間がかかります。他のオプションを提案してください。

Answer 1

値の順序が重要でない場合は、ハッシュ テーブルを使用します。時間は O(1) です。標準のテンプレート ライブラリで実装を見つけることができると確信しています。

これに失敗すると、特にリストの順序を維持したい場合、スプレイ ツリーは非常に高速です。操作ごとに O(ln n) の償却コストがかかり、定数係数が非常に低くなります。C++ stdlib マップはこのようなものだと思います。

あなたのデータ構造を知ってください。

Answer 2

deque にはサイズ変更のコストはありませんが、順序付けされていない場合、検索時間は線形であり、その途中での削除および挿入操作時間は vector よりも価値があります。
数値の値で検索する必要がない場合は、ハッシュマップまたはマップを選択できます。サイズ変更コストはかかりません。次に、マップのキーを数値のインデックスに設定し、値を数値の値に設定します。検索と挿入操作は線形よりも優れています。

Answer 3

std::list は間違いなくこのような問題のために作成されており、リスト内の要素を追加および削除しても、ベクターのようにメモリを再割り当てする必要はありません。ただし、リストの非伝染性のメモリ割り当てにより、要素の検索はもちろん苦痛を伴う経験になるかもしれませんが、そのエントリを頻繁に検索しない場合は使用できます。