数据结构，快速连续的范围内检索 [英] Data structure with fast contiguous ranges retrieval

问题描述

想象的数据结构，即操纵一些连续的容器中，使指数连续范围的快速检索，该阵列内，包含数据（也可能是免费的范围太）。让我们把这个范围块。每个块都知道它的头部和尾部指数：

Imagine data structure, that manipulates some contiguous container, and allows quick retrieval of contiguous ranges of indices, within this array, that contains data (and probably free ranges too). Let's call this ranges "blocks". Each block knows its head and tail index:

struct Block
{
    size_t begin;
    size_t end;
}

当我们操作数组，我们的数据结构更新模块：

When we manipulating array, our data structure updates blocks:

    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]

即使在分析中，我们知道块检索速度将是应用程序性能的基石。 基本用法是：

Even before profiling, we know that blocks retrieval speed will be cornerstone of application performance. Basically usage is:

• 经常检索连续的块
• 在相当罕见的插入/缺失
• 在大多数时候，我们希望块的数量是最小的（prevent碎片）

我们已经尝试过什么：

1. 的std ::矢量＆lt;布尔＆GT; + 的std ::名单＆LT;阻止*＆GT; 。在每一个变化：写的真/假以向量，然后遍历它的循环，并重新生成列表。在块的每一个查询返回列表。慢于我们想要的。

1. std::vector<bool> + std::list<Block*>. On every change: write true/false to vector, then traverse it in for loop and re-generate list. On every query of blocks return list. Slower than we wanted.

的std ::名单＆LT;阻止*＆GT; 更新列表直接，所以没有穿越。返回列表。许多code调试/测试。

std::list<Block*> update list directly, so no traversing. Return list. Much code to debug/test.

问题：

1. 是数据结构具有一定的通用名称？
2. 是否已有这样的数据结构来实现（调试和测试）？
3. 如果没有，你能在快速和可靠地实现这种数据结构的建议？

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

Sorry if my explanation is not quite clear.

修改

典型应用此容器是管理缓冲区：无论是系统还是GPU内存。在GPU情况下，我们可以存储大量的单顶点缓冲区中的数据，然后更新/无效部分地区。每个绘制调用我们必须知道在缓冲区中的每个有效块的第一和最后一个索引，以绘制（经常，第十到每秒几百倍），有时（每秒一次），我们必须插入/移除数据的块。

Typical application for this container is managing buffers: either system or GPU memory. In case of GPU we can store huge amounts of data in single vertex buffer, and then update/invalidate some regions. On each draw call we must know first and last index of each valid block in buffer to draw (very often, tenth to hundreds times per second) and sometimes (once a second) we must insert/remove blocks of data.

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

Another application is a custom "block memory allocator". For that purpose, similar data structure implemented in "Alexandrescu A. - Modern C++ Design" book via intrusive linked list. I'm looking for better options.

推荐答案

我在这里看到的是一个简单的二叉树。
你必须对（块）与开始和结束指数，也就是对 （A，B），其中 A＆LT; = B 。这样的该组块能够容易地订购并存储在一个搜索二进制树即可。
搜索块至极对应于给定数目是容易的（就在tipical bynary-树搜索）。所以，当你从数组中删除一个号码，你需要搜索对应数块，并将其分为两个新的块。 注意，所有的块是叶，内部节点的间隔至极的两个子节点形式。
插入在另一方面意味着搜索块，并测试它的兄弟们知道，如果兄弟们必须倒塌。这应该递归向上穿过树来完成。

What I see here is a simple binary tree.
You have pairs (blocks) with a begin and an end indices, that is, pairs (a,b) where a <= b. So the set of blocks can be easily ordered and stored in a search-binary-tree.
Searching the block wich corresponds to a given number is easy (Just the tipical bynary-tree-search). So when you delete a number from the array, you need to search the block that corresponds to the number and split it in two new blocks. Note that all blocks are leaves, the internal nodes are the intervals wich the two child nodes forms.
Insertion on the other hand means searching the block, and test its brothers to know if the brothers have to be collapsed. This should be done recursively up through the tree.

这篇关于数据结构，快速连续的范围内检索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！