高效地将范围映射到值组

Question

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

我想在特定范围内（例如[0x0-0xffffffff]）进行范围集合查找。值会以范围方式插入到该范围内（因此，如果我们使用T =唯一字符串，则可能插入（“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. 在以下限制条件下，什么是理想的实现:

   • 快速/非常快的查找时间
   • 内存使用不会膨胀（即以下操作具有等效的占用空间）
   • • Insert [10,20], Insert[20,30], Remove[14,24]
   • • Insert [10,15], Insert[25,30]
   • 与上一个类似，数据结构应对长期运行系统保持稳定
   • 插入/删除时间不是极其糟糕的（虽然它们不需要像查找一样快）

3. 给定一个理想的实现，你有关于如何在C++中使用它的建议吗？

感谢所有的回答和帮助。

- Kestred

---

请使用std::hash_map<std::string, std::hash_set<long>>。 - andre

@andre：遗憾的是，这个查找方向是错误的！ - Dietmar Kühl

一个映射到字符串集合的区间树？ - nickie

@DietmarKühl：我看到了相似之处，但范围树似乎主要用于进行高效的范围查找（即lookup(0x100, 0xFFF)），而这种结构永远只会查找单个键，并期望匹配值。 - Kestred

重复的问题？https://dev59.com/YnI95IYBdhLWcg3wzRTv - Adam Burry

Answer 1

有没有一个通用的名称来描述这种问题，或者类似的问题可以从中获得启示？

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

在约束条件下，什么是理想的实现方式？

一个自平衡二叉搜索树（如红黑树或牺牲节点树），建立以基于范围的搜索为优化目标。插入操作将根据需要插入相交的范围以产生正确的返回值。范围分割的方式因您的要求而异，但通常是通过“连接”进行的，这会丢弃关于原始范围的信息，但占用更小的空间，或者是通过“拆分”，从中仍然可以推导出原始范围。

在理想的实现下，你有没有使用C++的建议？

请查看 boost::icl（Boost 区间容器库）。

- Kestred