次の操作をサポートする、一意の要素の順序付けられていないコレクションを保持するデータ構造を探しています
単純に、1 と 2 は連想コンテナーを使用することを提案します。たとえばunordered_set、3 は要素の数が直線的です。ランダム アクセス コンテナーを使用すると、たとえばvector3 が簡単になります。1 は O(1) で実行できますが、2 は再び O(N) になります。
問題は、この線形の複雑さを回避する既知の方法があるかどうかです。
編集: 3 のランダムな要素によって、つまり、N 要素の任意の順序が与えられた場合、0 と N-1 の間の要素番号jを取得します。janstd::vectorの場合は添字付けだけで、 anstd::listまたは anstd::setの場合はリスト/セット イテレータを j 回インクリメントしますbegin()。
あなたのタスクに最適な2つの標準コンテナは、-あなたが言ったようにvector、O(n)の1.と2.、O(1)の3.、setO(log n)の1.と2.です。 3. in O(n)。データ構造のサイズによっては、アルゴリズムの複雑さはそれほど重要ではありません。Avectorには、データの局所性という追加の利点があるため、CPU キャッシュをより有効に活用できます。
要素の実際の順序が重要でないvector場合push_back、swap削除する要素が最後の要素であり、それを削除します。
本当に大きなデータ構造がある場合は、Boost.Multi-Indexを使用して、1. が O(n)、2. が O(log n)、3. が O(1) のデータ構造を構築できます。しかし、私が言ったように、あなたのデータ構造がそれほど大きくないなら、うまくvectorいくはずです。
ランダム アクセス インデックスの順序が問題にならない場合は、償却済み O(log n) ( ) に挿入できますpush_back。swap削除の場合、他のインデックスが無効になるため、このトリックは使用できません。
私は長い間、そのようなデータ構造を探していました。
最近、あなたが探しているすべての機能を備えた非常に有望なライブラリを見つけました。
O(log n) でのランダム アクセスの cntree::set を参照してください。
ここにリンクがあります。 http://dl.dropbox.com/u/8437476/works/countertree/index.html
開発中のようですが、かなり使えるようです。
std::unordered_set. インデックスをキーとして使用する場合、要素へのアクセスは O(N) ではなくj、O(1) です。
検索に使用したい一意のインデックスがあり、それ以外の順序を気にしない場合、連想コンテナーのキーとして他に何を使用する予定でしたか?