継続的に追加および削除される一連の要素に使用するコンテナ

Question

どのSTLコンテナがパフォーマンスの点で '継続的に'変化する要素のコレクションに最も適しているかを知りたいと思います。これらの要素は、指定された表示空間内のオブジェクトを表し、ビューの変更やオブジェクトの移動や表示の移動に伴い、オブジェクトのコレクションを更新する必要があります。ビューが更新されるたびに、私はUIDでソートされたシーンの中にあるオブジェクトのstd :: vectorを取得します（このリストAを呼び出すことができます）。 Iがthat checkをrunするwant：

• がactually sceneでno longer thingsのcurrent listからvisibleあるobjectsをremoves List Aにbased（このListのBをcall）

• はnew objectsをadds今Bをリストに表示されていること、再びリストAに基づいて4000個のオブジェクトへ

二つは、おそらく今まで見たオブジェクトの数の上限です。オブジェクトのUIDは数十億に達するので、私はビットマップされたベクトルを使用することはできません。私はリストBを更新するためのリストB.私の提案戦略のためのstd ::マップを使用することができます考えていたことである。「i」はリストBの各UIDに対して

• 、UIDの検索がIは（リストAにstd :: lower_boundを使用して）。 UIDがリストAに存在しない場合は、リストBから削除します。

• リストAの各UIDについて、リストBのUID 'i'を検索します（std :: map :: lower_boundを使用） 。リストBにUIDが存在しない場合は、追加します。

私は、具体的には、適切なコンテナタイプを使用している場合、いくつかのアドバイスをしたいと思います。私はstd :: vectorがリストBのために良い選択になるとは思っていませんでした。なぜなら、挿入/削除は高価なので、私はstd :: findよりもバイナリ検索を使いたければ明示的にソートする必要があったからです。しかし、それ以外のコンテナの種類や、それがより適切かどうかはわかりません。

リストBを更新するために選択した一般的な方法が最も効率的な方法であるかどうかを知りたいと思っています。

Answer 1

あなたの問題のようなサウンドは、セット操作を必要とします。 ListAにないオブジェクトをシーンから削除することは、設定された差分操作です。シーンに含まれていないListAからのオブジェクトの追加は、集合体の操作となります。ビットマップに対してデータが適切に整理されていない場合、通常、セット操作はハッシングの候補です。

オペランドの1つをハッシュのようなデータ構造ではないセット操作にすることができます。それはあなたが反復するものであり、行動を（償却された）O（N）を保つために、他のもので検索します。

# left operand is list, right is hash: 

set_diff (list x, hash y): 
    val ret = make_hash() 
    for i in x: 
     if not y[i] 
      ret[i] = i 
    return ret 

# vice versa 

set_diff (hash x, list y) 
    val ret = copy_hash(x) 
    for i in y: 
     if ret[i] 
      delete ret[i] 
    return ret    

ところで、なぜlower_boundを使用して検索しますか。 IDはユニークではないのですか？

Answer 2

あなたが決定する必要があるのはSTL Containersで、操作の複雑さまでスクロールします。 あなたの選択はstd::list、std::dequeおよびstd::vectorの間であり、後者はすべての中で最も遅く、前者は最も速いです。今、それらのうちのどれがあなたのすべての要件を提供していますか？理想的にはstd::listを使用します。挿入はO（n）です。std::dequeはO（n + x）です。ここでxは挿入ポイントまでの要素の数です。しかし、私はあなたが要素を取得するためにstd::deque::at()が必要になると思う。私は両方のリストでこれが必要だと思うので、std::dequeを使うべきです。

Answer 3

両方についてboost unordered setを試しましたか？

ここにはセットが必要ですが、ソートする必要はないようです。その場合、最良の候補は順序付けられていないセットです。あなたが望むもの（単なる物の集合）を与えることに加えて、それはソートに伴う（小さな）パフォーマンスヒットを取り除きます。