3

我正在尝试确定一种合适的方式来完成以下任务。

我想要范围 - >在特定范围内设置查找（比如[0x0 - 0xffffffff]）。值被插入到范围内（所以如果我们使用 T = 唯一字符串），我可能会 insert("beef3490", [0x1234, 0xFFFF]); 并且单个 id 可能有多个插入，它们可能重叠也可能不重叠。此外，可能会插入其他重叠的值，并且它们重叠的地方我应该收到一组唯一字符串作为结果。最后，值也可以从范围中删除（不一定匹配，但通常包含在它们的初始插入范围内）。

这是一个简化的示例用法：

insert("beef3490", [0x1234, 0xFFFF])
insert("beef3490", [0x11111, 0x22222])
insert("flam1456", [0x8000, 0xA0000])
remove("beef3490", [0x21000, 0x22000])
lookup(0x0) -> set<>
lookup(0x2000) -> set<beef3490>
lookup(0x9456) -> set<beef3490, flam1456>
lookup(0x21212) -> set<flam1456>
lookup(0x99789) -> set<flam1456>

这给我带来了一些问题：

  1. 是否有此类问题的通用名称，或者我可以从中找到见解的类似类型的问题？

  2. 考虑到以下限制，理想的实现是什么：

    • 快速/非常快的查找时间
    • 内存使用不会膨胀（即以下操作具有等效的占用空间）
      • 插入[10,20]，插入[20,30]，删除[14,24]
      • 插入[10,15]，插入[25,30]
    • 与上一个类似，数据结构在长时间运行的系统上应该具有稳定性
    • 插入/删除时间并不是绝对可怕的（尽管它们不需要像查找一样快）

  3. 给定一个理想的实现，您对在 C++ 中使用它有什么建议吗？

感谢所有回复和帮助。

4

1 回答 1

1

是否有此类问题的通用名称，或者我可以从中找到见解的类似类型的问题？

这个问题是区间树或段树问题。具体来说，树/数据结构需要对重叠操作执行聚合。这意味着当两个相交的范围被插入到结构中时，它们在两个范围内查找一个点的值等于 val(range A) + val(range B)。如果值是整数，则“+”操作可以是加法，或者在集合的情况下，它可以是联合操作。

考虑到约束，什么是理想的实现

一种自平衡二叉搜索树（例如红黑树或替罪羊树），用于根据范围优化搜索。插入操作将根据需要额外与范围相交以产生正确的返回值。拆分范围的方式因您的要求而异，但通常是通过“加入”（丢弃有关原始范围的信息但占用空间较小）或“拆分”，仍可以从中推断出原始范围。

给定一个理想的实现，您对在 C++ 中使用它有什么建议吗？

见boost::icl。（升压区间容器库）

于 2013-09-03T02:42:09.270 回答