我可以使用什么数据结构来存储和检索离散值的范围？

Question

我有一个JavaScript程序,我将在其中管理很多整数范围.在这种情况下,范围只是一个开始和结束值(或任何等价的,如开始和长度值),并引用另一个对象.范围可以重叠,并且可以相同(尽管引用的对象将是不同的).

可能的起始值和结束值介于0和4294967295之间(2 ³² - 1或0xFFFFFFFF),尽管域中有几个大的"漏洞",即使是部分也不会覆盖范围.与可能性领域相比,大多数范围将非常小:我预计绝大多数范围的长度将小于2000.

我对此结构最重要的用例是查找包含给定整数值的所有范围.大多数情况下,我希望查找失败(没有包含给定值的范围).

否则,我显然还需要向它添加元素(通常)并从中删除元素(很少).偶尔也会,我需要找到与给定范围重叠的所有范围,而不是包含单个值的所有范围.

我可以使用什么样的数据结构？范围列表中的线性搜索是不切实际的,因为查找在大多数情况下都会失败; 而且我需要经常进行查找.

Answer 1

我喜欢 System.Tuple 之类的东西[或 F# 列表，但很少有人知道 F#]。

如果范围是连续的，则可以简单地将开始和结束整数作为元组 Tuple nums = (start, end)，否则将具有开始结束的元组作为元组的第一个条目，将列表作为第二个条目可能适合你，Tuple nums = ((start, end), List)。