c++ - インデックス付きセット (ベクトルで効率的に削除するため)

Question

配列から効率的に削除するために独自のクラスを実装しようとしていましたが、そのようなものが既に存在するかどうかを確認したいと思いました。私が欲しいのは、リストのようなアクセス効率ですが、配列を使用しています。キャッシュの一貫性のために配列を使用したいので、(ノードを割り当てるときに std::list を使用する場合と同様に) メモリ アロケータを継続的に呼び出す必要はありません。

私が考えたのは、2 つの配列を持つクラスを作成することでした。1 つ目は要素のセットで、2 つ目の配列は整数のセットで、各整数は最初の配列の空きスロットです。そのため、空きリストからインデックスを取得し、それを新しい要素に使用するだけで、新しいメモリを割り当てることなく、配列から要素を簡単に追加/削除できます。

このようなものはすでに存在しますか？私が独自に行う場合は、独自の反復子も作成する必要があるため、配列内の空のスロットを回避してセットを反復処理できますが、あまり好きではありません。

ありがとう。

注：セットで実行したい操作の種類は次のとおりです。

1. 反復
2. 個々の要素へのランダムアクセス、インデックス (または私が考えているように「ハンドル」) による
3. セット内の任意の要素の削除
4. セットへの要素の追加 (順序は重要ではありません)

Answer 1

要素の順序を維持する必要がない場合は、swap-and-pop を使用します。

削除する要素の上に最後の要素をコピー/移動してから、後ろの要素をポップします。超簡単で効率的。標準の C++ ベクトルと操作を使用する場合は Just Work(tm) であるため、要素を削除するための特別なチェックを気にする必要さえありません。

*iter = std::move(container.back());
container.pop_back();

pop_back() がベクターのイテレーターを無効にしたかどうかは覚えていませんが、そうではないと思います。その場合は、インデックスを直接使用するか、新しい有効な反復子を再計算してください。

auto delta = iter - container.begin();
// mutate container
iter = container.begin() + delta;

Answer 2

空のスロットのスペースに「空の」スロットに関する情報を格納することで、単一の配列を使用できます。

array 内の空のスロットの連続ブロック、たとえばAindexkから始まるスロットの場合、 locationnに保存(k, n')しますA[n](n'は空きインデックスの次のブロックのインデックスです)。配列が単語サイズのオブジェクトを格納している場合、2 つの int を 1 つの単語にパックする必要がある場合があります。

メモリマネージャーが行うように、基本的に空きブロックのリンクリストを保存しています。

コーディングするのは少し面倒ですが、これにより、空きインデックスを O(1) 時間で割り当て、割り当てられたインデックスを O(n) 時間で反復処理できます。ここで、n は割り当てられたスロットの数です。最悪の場合、インデックスの解放には O(n) 時間かかります。これは、断片化されたメモリと同じ問題です。

最初の空きブロックについては、インデックスを個別に保存するか、決して割り当てない規則を使用してA[0]、そこからいつでも空きインデックス検索を開始できます。

Answer 3

std::mapあなたの場合に役立つかもしれません。