使用值范围为密钥的字典对象 [英] A dictionary object that uses ranges of values for keys

问题描述

我还需要一种专业词典的。我的使用情况是这样的：用户希望指定值的范围（范围可以是单个点为好）和一个值分配给特定的范围内。然后，我们希望使用单个值作为密钥来执行查找。如果发生内的范围之一这个单一值，则我们将返回相关联的范围内的值。

I have need of a sort of specialized dictionary. My use case is this: The user wants to specify ranges of values (the range could be a single point as well) and assign a value to a particular range. We then want to perform a lookup using a single value as a key. If this single value occurs within one of the ranges then we will return the value associated to the range.

例如：

// 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();

这显然只是一些code，说明我在寻找什么。有谁知道一个算法来实现这样的事情？如果是的话他们能指出我朝它，好吗？

This is obviously just some code to illustrate what I'm looking for. Does anyone know of an algorithm to implement such a thing? If so could they point me towards it, please?

我已经尝试实现自定义的IEqualityComparer对象区间，但无济于事重载equals（）和GetHash code（）为止。这可能是我做错了什么，但。

I have already tried implementing a custom IEqualityComparer object and overloading Equals() and GetHashCode() on Interval but to no avail so far. It may be that I'm doing something wrong though.

推荐答案

词典是不是合适的数据结构，您所描述的操作。

A dictionary is not the appropriate data structure for the operations you are describing.

如果该区间被要求永远不会重叠，那么你可以建立间隔的排序列表和二进制搜索。

If the intervals are required to never overlap then you can just build a sorted list of intervals and binary search it.

如果该区间可以重叠，那么你有一个更难以解决的问题。为了解决这个问题，有效地，你会想建立一个区间树：

If the intervals can overlap then you have a more difficult problem to solve. To solve that problem efficiently you'll want to build an interval tree:

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

这是一个公知的数据结构。请参见算法导论或数据结构的任何其他像样的本科文本。

This is a well-known data structure. See "Introduction To Algorithms" or any other decent undergraduate text on data structures.

这篇关于使用值范围为密钥的字典对象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！