5

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:

  • very often retrieval of contiguous blocks
  • quite rare insertions/deletions
  • most time we want number of blocks be minimal (prevent fragmentation)

What we have already tried:

  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.

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

Questions:

  1. Is that data structure has some generic name?
  2. Is there already such data structures implemented (debugged and tested)?
  3. If no, what can you advice on fast and robust implementation of such data structure?

Sorry if my explanation is not quite clear.

Edit

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.

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.

4

4 回答 4

5

我在这里看到的是一个简单的二叉树。您有带有 a和 a索引
的对（块），即对where 。因此，可以轻松地对块集进行排序并存储在 search-binary-tree中。 搜索与给定数字对应的块很容易（只是典型的二叉树搜索）。所以当你从数组中删除一个数字时，你需要搜索该数字对应的块并将其拆分成两个新块。请注意，所有块都是叶子，内部节点是两个子节点形成的间隔。beginend(a,b)a <= b

另一方面，插入意味着搜索块，并测试其兄弟以了解是否必须折叠这些兄弟。这应该通过树递归地完成。

于 2013-08-20T23:43:15.357 回答
4

You may want to try a tree like structure, either a simple red-black tree or a B+ tree.

于 2013-08-20T22:49:54.263 回答
1

您的第一个解决方案（布尔向量+块列表）似乎是一个很好的方向，但请注意，您不需要从头开始完全重新生成列表（或遍历整个向量） - 您只需要遍历列表直到您会找到新更改的索引应该固定的位置，然后拆分/合并列表中的相应块。

如果列表遍历被证明太长，您可以实现一个块向量，其中每个块都映射到其起始索引，并且每个孔都有一个块说明孔的结束位置。您可以像列表一样快速遍历这个向量，因为您总是跳转到下一个块（一次 O(1) 查找以确定块的结尾，另一个 O(1) 查找以确定下一个块的开始。好处但是，您也可以直接访问索引（用于推送/弹出），并通过二进制搜索找出它们的封闭块。为了使其工作，您必须对“孔”（合并和拆分）进行一些维护工作它们就像真正的块一样），但在任何插入/删除时也应该是 O(1)。重要的部分是块之间总是有一个洞，反之亦然

于 2013-08-20T23:20:03.307 回答
0

为什么要使用块列表？你需要稳定的迭代器和稳定的引用吗？boost::stable_vector 可能会有所帮助。如果您不需要稳定的引用，也许您想要编写一个包含 std::vector 块和大小为 blocks.capacity() 的辅助内存映射的包装容器，它是来自迭代器索引的映射（保留内部返回的迭代器到块向量中的实际偏移量）和当前未使用的迭代器索引的列表。

每当您从块中删除成员时，您都会重新打包块并相应地打乱地图以增加缓存的一致性，当您想要插入时，只需 push_back 到块。

使用块打包，您可以在以删除速度为代价进行迭代时获得缓存一致性。并保持相对较快的插入时间。

或者，如果您需要稳定的引用和迭代器，或者容器的大小非常大，以牺牲一些访问速度、迭代速度和缓存一致性为代价，您可以将向量中的每个条目包装在一个简单的结构中，该结构包含真正的条目和下一个有效的偏移量，或者只是将指针存储在向量中并在删除时将它们设置为空。

于 2013-12-13T07:21:58.810 回答