I have a base class CodeElement like

public class CodeElement
{
   public string Name;

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

   // ...
}

and several derived classes (Class, Window, Constant, etc.) like

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

   // ...
}

Note that the constructor is always like this (except the name, obviously). I also have a class CodeElementComparer implementing IComparer<CodeElement> which simply compares by Name.

My problem is the following: I have one somewhat large list (<10,000 elements) of each derived class on which I need to run a very large number of searches, by name (several million each). The Lists are filled before any searches are run. As such, I sort each List after they are complete (using the CodeElementComparer) and then use List<T>.BinarySearch like this

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;
   }
}

Runtime is just fine, the problem is that new derived classes are regularly added, forcing me to copy paste the above method every time. What I am looking for is something like

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;
   }
}

However, this does not compile, since List<T>.BinarySearch requires dummy to be of type T (even though I am only using an IComparer<CodeElement>). Here's what I considered; unfortunately, I am stuck on each approach:

1. Cast the List<T> to List<CodeElement>. I know this does not work because Lists are writable and I could theoretically add a Window to a List<Class> that way. From what I gathered from other questions on here, casting it to IEnumerable<CodeElement> works, but IEnumerable does not support binary search (since that requires O(1) access to make sense).
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.

CodePudding user response：

To answer the question (regardless of discussions on whether a better collection type would be better), one way is to make use of Span<T>.BinarySearch, which takes an IComparable<T> rather than just a T.

For this, you need to get a Span<T> from your List<T>. This can be done with CollectionsMarshal.AsSpan, but note that this gives you a reference to the underlying array which can change if the list is resized, so use the resulting span with caution!

The final code looks a bit like this:

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);
}

Note that you don't have to use CodeElement as your dummy -- anything which implements IComparable<CodeElement> will do it.

That said, note that a binary search is not particularly hard to implement. Here's Span<T>.BinarySearch and here's Array.BinarySearch, and another random one. You can avoid the whole dummy thing by copying and tweaking one of these implementations.

CodePudding user response：

You can create the dummy instance with type T using reflection. Here is a sample that I just tested :

    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;
        }