使用基数 class 比较器对基数 class 的元素进行派生 class 的二进制搜索列表

Question

我有一个基础classCodeElement喜欢

public class CodeElement
{
   public string Name;

   public CodeElement(string name)
   {
      Name = name;
   }

   // ...
}

和几个派生的 classes（Class、Window、Constant 等）如

public class Class : CodeElement
{
   public Class(string name) : base(name)
   {}

   // ...
}

请注意，构造函数总是这样（显然除了名称）。我还有一个 class CodeElementComparer 实现 IComparer<CodeElement> ，它只是通过 Name.

进行比较

我的问题如下：我有一个有点大的列表（<10,000 个元素）每个派生 class 我需要运行大量搜索，按名称（每个数百万）。列表在任何搜索运行之前被填充。因此，我在每个列表完成后对它们进行排序（使用 CodeElementComparer），然后像这样使用 List<T>.BinarySearch

private Class FindClass(List<Class> classes, string name)
{
   Class dummy = new Class(name);
   int index = classes.BinarySearch(dummy, codeElementComparer);
   if (index >= 0)
   {
      return classes[index];
   }
   else
   {
      return null;
   }
}

运行时还好，问题是定期添加新的派生classes，迫使我每次都复制粘贴上面的方法。我正在寻找的是

private T FindElement<T>(List<T> elements, string name) where T : CodeElement
{
   CodeElement dummy = new CodeElement(name);
   int index = elements.BinarySearch(dummy, codeElementComparer);
   if (index >= 0)
   {
      return elements[index];
   }
   else
   {
      return null;
   }
}

但是，这不会编译，因为 List<T>.BinarySearch 要求 dummy 是 T 类型（即使我只使用 IComparer<CodeElement>）。这是我考虑的；不幸的是，我坚持每一种方法：

将 List<T> 转换为 List<CodeElement>。我知道这不起作用，因为列表是可写的，理论上我可以通过这种方式将 Window 添加到 List<Class>。从我从这里的其他问题中收集到的信息来看，将其转换为 IEnumerable<CodeElement> 是可行的，但 IEnumerable 不支持二进制搜索（因为这需要 O(1) 访问权限才能有意义）。
使用构造函数创建 T 类型的虚拟对象。虽然 I 知道总会有一个只接受名称参数的构造函数，但编译器不会。如果我有办法指定所有派生的 classes 必须有这样的构造函数，我可以制作 T.
将元素参数的类型更改为 List<CodeElement>，然后将 return 转换为 T。这确实可以编译，但是超级不安全。

你有什么简洁的解决方法吗？编辑：虽然名称不是唯一的，但正如@canton7 指出的那样，在创建字典时处理一次仍然比处理二进制搜索要好。不过，我仍然对如何使用列表处理这个问题很感兴趣。

Answer 1

您可以使用反射创建类型为 T 的虚拟实例。这是我刚刚测试的示例：

    private T FindElement<T>(List<T> elements, string name) where T : CodeElement {

        //CodeElement dummy = new CodeElement(name);
        //using System;
        T dummy = (T)Activator.CreateInstance(typeof(T), name);
        int index = elements.BinarySearch(dummy, codeElementComparer);
        if (index >= 0) {
            return elements[index];
        } else {
            return null;
        }

Answer 2

要回答这个问题（不管讨论是否更好的集合类型会更好），一种方法是使用 Span<T>.BinarySearch，它需要 IComparable<T> 而不仅仅是 T.

为此，您需要从 List<T> 中获取 Span<T>。这可以通过 CollectionsMarshal.AsSpan 来完成，但请注意，这为您提供了对基础数组的引用，如果列表的大小发生变化，该数组可能会发生变化，因此请谨慎使用生成的跨度！

最终代码看起来有点像这样：

private T FindElement<T>(List<T> elements, string name) where T : CodeElement
{
   CodeElement dummy = new CodeElement(name);
   var span = CollectionsMarshal.AsSpan(elements);
   int index = span.BinarySearch(dummy);
   if (index >= 0)
   {
      return span[index];
   }
   else
   {
      return null;
   }
}

class CodeElement : IComparable<CodeElement>
{
    public string Name { get; }
    public CodeElement(string name) => Name = name;
    
    public int CompareTo(CodeElement other) => Comparer<string>.Default.Compare(Name, other?.Name);
}

请注意，您不必使用 CodeElement 作为 dummy -- 任何实现 IComparable<CodeElement> 的东西都可以。

也就是说，请注意二分查找并不是特别难以实现。 Here's Span<T>.BinarySearch and here's Array.BinarySearch, and another random one。您可以通过复制和调整这些实现之一来避免整个 dummy 事情。

使用基数 class 比较器对基数 class 的元素进行派生 class 的二进制搜索列表

Binary search list of derived class for element of base class, using a base class comparer

c#

casting