维护一个有序的列表

本文关键字：列表 一个 维护 | 更新日期: 2023-09-27 18:13:21

我需要存储一个节点集合:

class Node
{
   int Value;
   //other info
}

我有三个要求:

  1. 需要能够有效地检索集合中具有最低值的节点
  2. 需要能够有效地将节点插入集合
  3. 两个节点可以有相同的值

我认为最好的集合应该是某种排序列表。这样，只要从排序列表中取出第一个元素，就能有效地满足需求#1。通过在列表的正确位置插入一个新节点，可以有效地满足需求#2。

但是。net中的SortedList集合就像SortedDictionary一样，要求被排序的键是唯一的，这违反了需求#3。

在。net中似乎没有满足这些要求的集合，主要是因为存在的自排序集合要求排序的键是唯一的。这是什么原因呢?我想这不可能是疏忽吧。我还有什么没理解的?我可以找到类似的问题，但他们通常涉及有人建议SortList，随后意识到这不起作用，然后谈话逐渐消失，没有一个标准的解决方案。至少如果有人会说"c#中没有集合来完成这个任务，你需要一起破解一些东西"，这将是一个答案。

是否可以使用常规的List<Node>并在添加新节点时重新排序列表?这似乎不如在正确的位置插入节点那么有效。也许这就是我该做的?手动迭代列表，直到我自己找到插入新节点的地方?

维护一个有序的列表

如果您所需要的只是有效地插入并快速检索具有最低值的项，那么您不需要排序列表。你需要一堆。查看泛型二进制堆类

通过添加对象id或其他唯一标识符使您的list_key唯一:id 4和5，都具有值"1"将成为"1_4"answers"1_5"，可以轻松地添加到排序列表中，并将按预期排序。

您可以使用SortedList<int, List<NodeInfo>>，其中您将把Value放在键中，并将所有其他属性放在value中:

public class NodeList : SortedList<int, List<NodeInfo>>
{
    public void Add(int key, NodeInfo info)
    {
        if (this.Keys.Contains(key))
        {
            this[key].Add(info);
        }
        else
        {
            this.Add(key, new List<NodeInfo>() { info } );
        }
    }
    public NodeInfo FirstNode()
    {
        if (this.Count == 0)
            return null;
        return this.First().Value.First();
    }
}
public class NodeInfo
{
    public string Info { get; set; }
    // TODO: add other members
}

下面是一些示例用法:

var list = new NodeList();
// adding
list.Add(3, new NodeInfo() { Info = "some info 3" });
// inserting
for (int i = 0; i < 100000; i++)
{
    list.Add(1, new NodeInfo() { Info = "some info 1" });
    list.Add(2, new NodeInfo() { Info = "some info 2" });
    list.Add(1, new NodeInfo() { Info = "some info 1.1" });
}
// retrieving the first item
var firstNodeInfo = list.FirstNode();
// retrieving an item
var someNodeInfo = list[2].First();

在我看来，使用普通列表并在每次插入后重新排序是可以接受的。在。net中排序是非常高效的。查看这个线程:VS2010与VS2008的字符串排序性能下降

你可以在Wintellect的。net Power Collections中使用OrderedMultiDictionary。

相关文章：