データ構造は、連続したいくつかのコンテナを操作し、データを含むこの配列内の連続した範囲のインデックスを迅速に取得できることを想像してください。この範囲を「ブロック」と呼ぶことにしましょう。各ブロックは、その頭と尾のインデックスを知っている：高速連続領域検索を伴うデータ構造
struct Block
{
size_t begin;
size_t end;
}
我々は、配列、我々のデータ構造の更新ブロックを操作する場合：
array view blocks [begin, end]
--------------------------------------------------------------
0 1 2 3 4 5 6 7 8 9 [0, 9]
pop 2 block 1 splitted
0 1 _ 3 4 5 6 7 8 9 [0, 1] [3, 9]
pop 7, 8 block 2 splitted
0 1 _ 3 4 5 6 _ _ 9 [0, 1] [3, 6] [9, 9]
push 7 changed end of block 3
0 1 _ 3 4 5 6 7 _ 9 [0, 1] [3, 7] [9, 9]
push 5 error: already in
0 1 _ 3 4 5 6 7 _ 9 [0, 1] [3, 7] [9, 9]
push 2 blocks 1, 2 merged
0 1 2 3 4 5 6 7 _ 9 [0, 7] [9, 9]
をしてもプロファイリングする前に、我々はブロック検索速度は、アプリケーションのパフォーマンスの礎になることを知っています。 基本的用法は次のとおりです。
- 非常に多くの場合、連続したブロックの検索
- 非常にまれ挿入/欠失
- 我々が持っている私たちはブロックの数を最小限にしたいほとんどの時間（断片化を防ぐ）
既に試しました：
std::vector<bool>+std::list<Block*>。すべての変更：true/falseをvectorに書き込んだ後、forループ内をトラバースし、listを再生成します。ブロックのクエリごとにlistを返します。我々が望んでいたよりも遅い。std::list<Block*>リストを直接更新することはありません。リストを返す。多くのコードをデバッグ/テストします。
質問：
- データ構造は、いくつかの一般的な名前を持っていることですか？
- 既に実装されている（デバッグされ、テストされた）データ構造はありますか？
- もしそうでなければ、そのようなデータ構造の迅速かつ堅牢な実装について何をアドバイスできますか？
私の説明が明確でない場合は申し訳ありません。このコンテナの
編集
典型的なアプリケーションでは、バッファを管理している：システムまたはGPUのメモリのいずれかを。 GPUの場合、単一の頂点バッファに大量のデータを格納し、一部の領域を更新/無効化することができます。各ドローコールでは、描画するバッファ内の各有効なブロックの最初と最後のインデックスを知る必要があります（たいていは10〜100回/秒）。時には（1秒に1回）データのブロックを挿入/削除する必要があります。
別のアプリケーションはカスタムの「ブロックメモリアロケータ」です。その目的のために、同様のデータ構造が "Alexandrescu A. - Modern C++ Design"ブックに侵入型リンクリストを介して実装されています。私はより良いオプションを探しています。
私はしばしば、ツリーやベクトルに基づいてこのような「離散的な範囲」のタイプを開発しましたが、そのようなことがすでに増強されていると聞きました。 –
コンテナに範囲が含まれているか、または個別のインデックス範囲にデータが含まれていますか？ –
私たちのアプリケーションでは、単純なバッファ（動的配列）上の何らかのラッパーでなければなりません。私は、GPUバッファのユースケースで編集を追加しました。わかりやすくするために、基底のコンテナは 'std :: vector 'とすることができます。バッファインターフェイス（読み込み/書き込み/更新/マークフリー）は実装するのが難しくありませんが、この "ブロック"に固執しています。 – Drop