2009-09-19 11 views
9

我需要一个相当专业的收集.NET,我不认为BCL可以帮助我,但我认为我会抛出它,因为如果有人知道类似的东西。.NET中是否存在排序的队列?

基本上,我的要求是这样的:

  • 我有对值的,如的列表:(3,10),(5,10),(3,7),(5, 5)
  • 订单是重要的,即。 (3,10)!=(10,3)
  • 单个值的重复项很好,但应该删除重复对(最好是静默)。
  • 踢球者,我需要这个列表一直排序。我只对任何时候排序算法定义的列表中的第一个值感兴趣。

所以,我希望能够做(因为我设想它可能会被执行,其他适合以上的罚款,以实现)一些示例代码:

public class Pair 
{ 
    public Pair(int first, int second) 
    { First = first; Second = second; } 
    public int First { get; set; } 
    public int Second { get; set; } 
} 

SortedQueue<Pair> foo = new SortedQueue<Pair>((left, right) => { 
    return right.First - left.First; 
}); 

foo.Add(new Pair(10, 3)); 
foo.Add(new Pair(4, 6)); 
foo.Add(new Pair(6, 15)); 
foo.Add(new Pair(6, 13)); // This shouldn't cause a problem 

Pair current = foo.Shift(); // current = (4, 6) 

回答

11

我引述:

我需要这个名单排序的所有的时间。 我一直只对 排序算法在任何时候定义的列表中的第一个 值感兴趣。

这听起来像你这样想要一个排序队列但Priority Queue。如果性能是一个问题,那么PQ肯定会更快,O(log n)对O(n)。但是drop-duplicates问题也需要你保留一个并行的HashSet <>。

+5

请参阅“.Net中的优先队列”,http://stackoverflow.com/questions/102398/priority-queue-in-net – 2009-09-19 10:37:24

+0

Thankyou的正确名称和链接。现在我查看了维基百科的文章,我正在考虑实现它的方式是“简单实现”中列出的两种类型的混合体(保留一个标记以表明它是否已排序,只需追加在插入时,然后在检索前按需要排序)。并感谢dangph链接到一些实际的实现。 – 2009-09-19 10:47:20

+0

为了记录,这也是为了实现A *搜索,这个维基百科文章也有一些注释,所以双重荣誉。 – 2009-09-19 10:48:52

5

有你看着SortedDictionarySortedList

+3

我想我一定是失明了。但有一个问题,既不支持重复键,这是一个要求。 – 2009-09-19 05:34:39

+0

我有消息给你Matt:如果你的关键是重复的,它是同一个对象。这里的教训是重写Equals,以便它们在您设置的基础上相等。 – 2009-09-19 05:49:16

+0

我更喜欢使用LINQ来手动覆盖等于... – RCIX 2009-09-19 05:54:57

0

SortedList将是最好的,你所要做的就是在你的Pair类中实现IComparable,并且它会自动排序它们。至于删除重复,我不认为排序列表处理,但你可以继承它,并添加此功能。

0

您应该最有可能使用Lookup类作为The Skeet在his answer中提到。然后你用这样的东西来构建和访问它:

List<Lookup<int, int>> yourList = new List<Lookup<int, int>>(); 
yourList.Add(new Lookup(3,5)); 
//... 
var list = from item in yourList 
      orderby list.Key //or whatever sort criteria you want here 
      select item; 
//use list 

语法可能有点在1或2个点,但它应该工作。

1

目前,.NET并没有内置于.NET中,可以满足您的所有需求。在.NET 4.0中有一个SortedSet类。我意识到它现在可能不会让你感觉好多了。

如果您实现IComparable,SortedList会很近。您只需使用Pair作为键和值。您只会将参考存储到您的Pair中,因此它不会造成巨大的内存开销。但是这不会处理重复。

有很多方法可以自己编写,但没有内置任何内容完全符合您的需求。有一些开源的SortedSet实现(例如Spring.Net中有一个)。这可能是你现在最好的选择。

+0

在Perl中使用哈希多次/ PHP只能访问一个集合类型,每次我只在集合中使用这个键时,它就像是一个黑客,我想抛出。不幸的是,这就是我们所坚持的。但!这是一个个人项目,我已经安装了VS 2010,所以我可能只是使用它... – 2009-09-19 10:53:06