c++ - 具有快速连续范围检索的数据结构

想象一下数据结构，该结构可以操纵一些连续的容器，并允许在该数组内快速检索包含数据的索引的连续范围(可能还有自由范围)。我们将此范围称为“块”。每个块都知道其头尾索引:

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*>。每次更改时:在vector中输入true/false，然后遍历for循环并重新生成list。在每次查询块时，返回list。比我们想要的慢。

std::list<Block*>直接更新列表，因此无需遍历。退货 list 。很多代码需要调试/测试。

问题:

该数据结构是否具有某些通用名称？

是否已经实现(调试和测试)了这样的数据结构？

如果否，那么您对这种数据结构的快速，可靠实现有何建议？

抱歉，如果我的解释不太清楚。

编辑

该容器的典型应用是管理缓冲区:系统或GPU内存。对于GPU，我们可以在单个顶点缓冲区中存储大量数据，然后更新/使某些区域无效。在每个绘制调用中，我们必须知道要绘制的缓冲区中每个有效块的第一个和最后一个索引(每秒，十分之十至数百次)，有时(每秒)，我们必须插入/删除数据块。

另一个应用程序是自定义的“块内存分配器”。为此，在“Alexandrescu A.-Modern C++ Design”一书中通过侵入式链表实现了类似的数据结构。我正在寻找更好的选择。

最佳答案

我在这里看到的是一个简单的二叉树。
您有一个带有begin和end索引的对(块)，即，一对(a,b)，其中a <= b。因此，这组块可以很容易地排序并存储在search-binary-tree 中。
搜索与给定数字相对应的块很容易(只是典型的bynary-tree-search)。因此，当您从数组中删除一个数字时，您需要搜索与该数字相对应的块并将其拆分为两个新块。 请注意，所有块都是叶子，内部节点是形成的两个子节点之间的间隔。
另一方面，插入意味着搜索该块，并测试其兄弟以了解兄弟是否必须折叠。这应该在树上递归地完成。