派生類的基類元素的二進制搜索串列，使用基類比較器

我有一個基類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)
   {}

   // ...
}

請注意，建構式始終是這樣的（顯然，名稱除外）。我還有一個CodeElementComparer實作類IComparer<CodeElement>，它只是通過Name.

我的問題如下：我有每個派生類的一個有點大的串列（<10,000 個元素），我需要在其上運行大量搜索，按名稱（每個數百萬）。在運行任何搜索之前填充串列。因此，我在完成后對每個 List 進行排序（使用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>）。這是我考慮的；不幸的是，我堅持每一種方法：

1. 投射List<T>到List<CodeElement>. 我知道這行不通，因為串列是可寫的，理論上我可以Window用List<Class>這種方式添加 a 。從我從這里的其他問題中收集的資訊來看，將其轉換為IEnumerable<CodeElement>有效，但IEnumerable不支持二進制搜索（因為這需要 O(1) 訪問才能有意義）。
2. Create a dummy of type T, using the constructor. While I know that there will always be a constructor which takes only the name parameter, the compiler does not. If I had a way to specify that all derived classes must have such a constructor, I could make dummy of type T.
3. Change the type of the elements parameter to List<CodeElement>, then cast the return to T. This does compile, but is super unsafe.

Do you have any concise solution to this? EDIT: Although the names are not unique, handling that once when creating a dictionary is still better than dealing with binary search, as @canton7 pointed out. I am still interested in how to handle this with Lists though.

uj5u.com熱心網友回復：

要回答這個問題（不管關于更好的集合型別是否更好的討論），一種方法是使用Span<T>.BinarySearch，它需要一個IComparable<T>而不僅僅是一個T。

為此，您需要Span<T>從List<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'sSpan<T>.BinarySearch and here'sArray.BinarySearch和另一個隨機的。您可以dummy通過復制和調整這些實作之一來避免整個事情。

uj5u.com熱心網友回復：

您可以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;
        }

標籤：c# casting

上一篇：我如何讓最小的聽它的IP？

下一篇：C#Lamda運算式和區域函式理解