使用键值范围的字典对象

Question

我需要一种专门的字典.我的用例是这样的:用户想要指定值的范围(范围也可以是单个点)并为特定范围分配值.然后,我们想要使用单个值作为键来执行查找.如果此单个值出现在其中一个范围内,那么我们将返回与该范围关联的值.

例如:

// represents the keyed value
struct Interval
{
    public int Min;
    public int Max;
}

// some code elsewhere in the program
var dictionary = new Dictionary<Interval, double>();
dictionary.Add(new Interval { Min = 0, Max = 10 }, 9.0);
var result = dictionary[1];
if (result == 9.0) JumpForJoy();

这显然只是一些代码来说明我正在寻找的东西.有谁知道实现这样的事情的算法？如果是这样,他们会指向我吗,拜托？

我已经尝试在Interval上实现一个自定义IEqualityComparer对象并重载Equals()和GetHashCode()但到目前为止无济于事.可能是我做错了.

Answer 1

字典不是您所描述的操作的适当数据结构.

如果要求间隔永远不会重叠,那么您可以构建一个排序的间隔列表并对其进行二进制搜索.

如果间隔可能重叠,那么您需要解决更难的问题.要有效地解决这个问题,你需要构建一个区间树:

http://en.wikipedia.org/wiki/Interval_tree

这是一个众所周知的数据结构.请参阅"算法简介"或任何其他体面的数据结构文本.

Answer 2

这仅在间隔不重叠时才起作用.而你的主要问题似乎是从单个(键)值转换为间隔.

我会在SortedList周围写一个包装器.SortedList.Keys.IndexOf()会找到一个索引,可用于验证间隔是否有效,然后使用它.