Covariance and Generics

Have you ever thought about why the following code works? Or are you astounded why I ask this question?

class Base{}
class Derived : Base{}

void Foo(Base[] b)
{
    foreach(Base b in b)
        Console.WriteLine(b);
}

Foo(new Derived[]{new Derived(), new Derived()});

Arrays are covariant in C#. This means that you can assign an array of derived types to an array of base types as shown above. Having a strong C++ background, I always wondered why this is possible, because typeof(object[])!= typeof(A[]) is definitely true. And what even makes me wonder more is how often I use the covariance of arrays today!

I noticed that I unintentionally adopted it, when I first tried out .NET Generics about a year

ago and asked myself whether I can pass an IEnumerable<Derived> as an IEnumerable<Base>. Well, I couldn't and was a little bit disappointed. Of course I understand that generics are not covariant and shouldn't be, but still it was annoying to copy the content of one collection to another:

IEnumerable<Base> derived = ...

ICollection<Base> copy = new List<Base>();

foreach(Derived d in derived) 
   copy.Add(d);

So I decided to provide an adapter implementation to avoid the copying. The new C# 2.0 iterator feature made this task very easy. Basically it generates the IEnumerable<T> implementation for you and eliminates the need for the for copying the collection:

public static class Adapt
{
    public static IEnumerable<Base>
       Covariant(IEnumerable<Derived> derived) where Derived : Base
    {
        foreach (Derived b in derived)
            yield return b;
    }
}

This covariant adapter and some more for adapting non generic collections of the System.Collections namespace to their generic counterpart and vice versa are available through the NSTL project, a port and adaption of the C++ STL for .NET.

Whats next in the NSTL

After working a lot to extend the NSTL, a port and adaption of the C++ STL to .NET, on the algorithm and functional side, I had the choice between providing missing containers or experiment into the direction of LINQ. I first decided to head the LINQ direction, so I experimented writing overloads of algorithms using he .NET IEnumerable<T> interface directly. It showed quickly that it should be possible to write almost every algorithm of the NSTL in that fashion. The new "yield" iterator feature in C# 2.0 simplifies things a lot here, too. It also showed, that these overloads will provide a huge benefit in for .NET 2.0 users today. And last but not least, it showed that these overloads will be a lot of work, especially because of the case to case decision which overload is used to implement another to avoid code duplication and the pure amount of algorithms.

So I decided to plan this step more thoroughly, especially the unit test front. To bridge time and be able to ship a release in the regular schedule of 2-3 months I will provide provide a set of containers that are missing in the .NET world:

• PriorityQueue<T>, which is a queue the always returns the element with the highest priority
  
• Hashset<T>, a hash container that keeps a unique collection of items and offers constant time add, remove and contains access.
  
• Hashmap<Key, Value> is like Dictionary<Key, Value> a hashtable. It differs from it by providing the possibility to change the values of the table while iterating over the keys
• MultiHashmap<Key, Value> which extends Hashmap<Key, Value> with the possibility to store multiple values to a key
• Deque<T> which is very similar to List<T>, except that it allows constant time insertion at both ends