0

我们有一个 C# 库类，它继承自 List 但很慢，因为 List.Contains 很慢。我们不能将类更改为从 Dictionary 或 HashSet 之类的其他东西继承，因为很多客户端代码都依赖于该类，而且更改接口过于复杂。有没有一种简单的方法可以在不改变它的情况下加速这种方法？一些列表非常大，所以我们不希望内存中有两个副本。我们也不想覆盖 List 的每个方法。

public class UniqueList<T> : List<T>, IList<T>
{
    public new void Add(T item)
    {
        if (!this.Contains(item) && item != null)
        {
            base.Add(item);
        }
    }
4

3 回答 3

2

从 List 继承是一个非常糟糕的主意，因为您无法控制客户端代码如何使用您的类

List.Contains 是一个O(n)操作。Dictionary.ContainsKey 是O(1)，所以我认为使用 Dictionary 是最好的建议，但如果你真的不想使用它，另一种可能性是保持列表排序以获得O(log n)

public void Add(T item)
{
    int index = BinarySearch(item);
    if (index < 0)
    {
        Insert(~index, item);
    }
}

如果元素已经在列表中，BinarySearch 返回它的索引。如果该元素不在列表中，则 BinarySearch 方法返回一个负数，它是第一个元素的索引的二进制补码，该索引大于我传递给二进制搜索方法的元素。

在您的方案中可能无法使用 BinarySearch，因为它取决于 T 可以是：http: //msdn.microsoft.com/en-us/library/w4e7fxsh.aspx

此方法使用类型 T 的默认比较器 Comparer.Default 来确定列表元素的顺序。Comparer.Default 属性检查类型 T 是否实现 IComparable 泛型接口并使用该实现（如果可用）。如果没有，Comparer.Default 检查类型 T 是否实现了 IComparable 接口。如果类型 T 未实现任一接口，Comparer.Default 将引发 InvalidOperationException。

于 2013-03-05T11:38:40.277 回答
2

简而言之，没有。

因为您继承自List<>您基本上搞砸了，因为即使您隐藏 Contains 方法，您也无法阻止客户端代码将 a 传递UniqueList给接受 a 的方法List<>，这将隐藏您的新 Contains，并使用现有的一。

您需要以艰难的方式解决此问题，删除 上的继承List<>，实现您自己的 Contains，从列表中重新实现您需要的任何方法（在内部您可以使用 aprivate List<>进行存储，并在必要时简单地委托给它），并修复所有此更改中断的代码。

当你破坏东西时，你可以看看 C5 集合类，它促进了针对接口的开发，帮助你避免遇到这个问题（我知道，在马跑了之后更多地关闭谷仓门）

我知道这不是你要找的答案，但你不会得到你想要的答案（真的没有办法解决这个问题，你可以尝试类似Castle Interceptors的东西，但我没有认为他们会在这种情况下工作......但我不能确定他们不会）

再次，为无法真正提供帮助而道歉。

于 2013-03-05T11:39:07.493 回答
0

您可以拥有一个类级别的私有字典，如果在字典中找不到字典，则首先检查字典，然后转到列表并检查，它只是一种优化，它不是纯粹的解决方案，而且还需要额外的内存

于 2013-03-05T10:15:26.613 回答