5

我需要存储节点集合：

class Node
{
   int Value;
   //other info
}

我有三个要求：

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

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

但是SortedList.Net 中的集合就像SortedDictionary并且要求被排序的键是唯一的，这违反了要求 3。

.Net 中似乎没有满足这些要求的集合，主要是因为确实存在的自排序集合要求排序的键是唯一的。这是什么原因？我认为这不可能是疏忽。我在这里没有抓住什么？我可以找到关于此的类似问题，但它们通常涉及某人提出建议SortList，然后意识到这不起作用，然后对话在没有标准解决方案的情况下淡出。至少如果有人会说“C# 中没有用于此任务的集合，您需要一起破解一些东西”，这将是一个答案。

List<Node>每当添加新节点时使用常规并重新排序列表是否可以接受？似乎这不如将节点插入到正确的位置开始那样有效。也许这就是我应该做的？手动遍历列表，直到我自己找到插入新节点的位置？

4

5 回答 5

2

如果您只需要有效地插入并快速检索具有最低值的项目，那么您不需要排序列表。你需要一个堆。查看A Generic Binary Heap Class。

于 2013-05-13T13:21:59.247 回答
1

通过添加对象 id 或其他唯一标识符使您的 list_key 唯一：ID 4 和 5，值均为“1”将变为“1_4”和“1_5”，可以毫无问题地添加到排序列表中，并将排序为预期的。

于 2013-05-13T11:17:56.733 回答
1

您可以使用 a SortedList<int, List<NodeInfo>>，您将在其中放入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();
于 2013-05-13T13:00:22.870 回答
0

在我看来，使用普通列表并在每次插入后重新排序是可以接受的。在 .NET 中排序非常有效。请参阅此线程：VS2010 与 VS2008 中的字符串排序性能下降

于 2013-05-13T11:25:20.310 回答
0

您可以在Wintellect 的 Power Collections for .NET中使用OrderedMultiDictionary。这正是您正在寻找的。

于 2013-05-13T12:21:54.677 回答