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

Question

想象一下数据结构,它操纵一些连续的容器,并允许快速检索此数组中包含数据(也可能是自由范围)的连续索引范围.我们称这个范围为"块".每个块都知道它的头尾指数:

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]

即使在分析之前,我们也知道块检索速度将成为应用程序性能的基石.基本用法是:

• 经常检索连续的块
• 非常罕见的插入/删除
• 大部分时间我们都希望块数最小(防止碎片)

我们已经尝试过的:

1. std::vector<bool>+ std::list<Block*>.在每次更改时:将true/false写入vector,然后遍历for循环并重新生成list.在每个块的查询返回list.比我们想要的要慢.

2. std::list<Block*>直接更新列表,所以没有遍历.退货清单.很多代码要调试/测试.

问题:

1. 该数据结构是否具有一些通用名称？
2. 是否已经实施(调试和测试)此类数据结构？
3. 如果不是,您可以就快速而强大的数据结构实施提出建议吗？

对不起,如果我的解释不太清楚.

编辑

此容器的典型应用是管理缓冲区:系统或GPU内存.在GPU的情况下,我们可以在单个顶点缓冲区中存储大量数据,然后更新/使某些区域无效.在每次绘制调用时,我们必须知道缓冲区中每个有效块的第一个和最后一个索引(通常是每秒十到几百次),有时(每秒一次)我们必须插入/删除数据块.

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

Answer 1

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

Answer 2

您可能想尝试类似树的结构，可以是简单的红黑树，也可以是 B+ 树。