我有一个类似的基类CodeElement
public class CodeElement
{
public string Name;
public CodeElement(string name)
{
Name = name;
}
// ...
}
以及几个派生类(Class、Window、Constant等(，如
public class Class : CodeElement
{
public Class(string name) : base(name)
{}
// ...
}
请注意，构造函数总是这样的(显然除了名称(。我还有一个实现IComparer<CodeElement>的类CodeElementComparer，它只是用Name进行比较。
我的问题如下：每个派生类都有一个很大的列表(<10000个元素(，我需要按名称对其进行大量搜索(每个数百万个(。在运行任何搜索之前，都会填充列表。因此，我在每个列表完成后对它们进行排序(使用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;
}
}
运行时很好，问题是定期添加新的派生类，迫使我每次都复制粘贴上面的方法。我要找的是类似的东西
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知道总会有一个构造函数只接受name参数，但编译器不会。如果我有办法指定所有派生类都必须有这样一个构造函数，我可以使类型为T的dummy - 将elements参数的类型更改为
List<CodeElement>，然后将返回值强制转换为T。这确实可以编译，但非常不安全
您对此有什么简明的解决方案吗？编辑：正如@conton7所指出的，尽管名字不是唯一的，但在创建词典时处理一次仍然比处理二进制搜索要好。不过，我仍然对如何使用Lists处理这一问题感兴趣。
要回答这个问题(不管是否讨论了更好的集合类型会更好(，一种方法是使用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>的东西都可以
也就是说，注意二进制搜索并不特别难实现。这是Span<T>.BinarySearch和Array.BinarySearch，还有另一个随机的。您可以通过复制和调整其中一个实现来避免整个dummy。
您可以使用反射创建类型为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;
}