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

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*>。每次更改时:向vector写入true/false，然后遍历for循环并重新生成list。在每个块的查询上返回list。比我们想要的慢。
2. std::list<Block*>更新列表直接，所以没有遍历。退货单。需要调试/测试的代码很多。

问题：

1. 该数据结构是否有一些通用名称？
2. 是否已经实现了这样的数据结构(调试和测试)？
3. 如果没有，您可以就这种数据结构的快速和健壮的实现提出什么建议？

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

编辑

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

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

Answer 1

我在这里看到的是一个简单的二叉树。

您有带begin和end索引的对(块)，也就是在a <= b中的对( (a,b) )。因此，--这组块可以很容易地排序并存储在搜索二叉树中。

搜索对应于给定数字的块是很容易的(仅仅是一站式的二叉树搜索)。因此，当您从数组中删除一个数字时，您需要搜索与该数字相对应的块，并将其拆分为两个新块。注意，所有的块都是叶子，内部节点是两个子节点形成的间隔。

另一方面，插入意味着搜索块，并测试它的兄弟，以确定兄弟是否必须崩溃。这应该通过树递归地完成。

Answer 2

您可能想尝试一种类似于树的结构，无论是简单的红黑树还是B+树。

Answer 3

您的第一个解决方案( bools向量+块列表)似乎是一个不错的方向，但请注意，您不需要从头开始完全重新生成列表(或遍历整个向量)--只需遍历列表，直到找到新更改的索引应该修复的位置，然后拆分/合并列表上的适当块。

如果遍历列表的时间太长，您可以实现一个块向量，其中每个块映射到它的开始索引，每个洞有一个块，表示洞的结束位置。您可以以列表的速度遍历这个向量，因为您总是跳到下一个块(一个O(1)查找来确定块的结束，另一个O(1)查找来确定下一个块的开始。然而，它的好处是您还可以直接访问索引(用于push/pop)，并通过二进制搜索找出它们的封闭块。要使其工作，您将不得不对“漏洞”进行一些维护工作(合并并像真正的块一样拆分它们)，但对于任何插入/删除，也应该是O(1)。重要的是，街区之间总是有一个洞，反之亦然。