C# IDictionary.Keys and IDictionary.Values: what is the most optimal implementation?

Question

I have a C# class that acts as a dictionary so I'm now in the process of supporting IDictionary.

Everything is fine except for the properties Keys and Values:

ICollection<TKey> Keys { get; }
ICollection<TValue> Values { get; }

I don't have a collection of keys or values internally so I'm wondering how to provide these as a ICollection.

My first attempt was to use the magic of "yield return" like this:

ICollection<TValue> Values { 
    get {
        for( int i = 0; i < nbValues; ++i ) {
            yield return GetValue(i);
        }
    }
}

But of course this doesn't work since the returned type is not a IEnumerator but a ICollection...

It's too bad because this would have been the simplest solution !

My second attempt was to copy my values in a newly created array and return the array.

ICollection<TValue> Values { 
    get {
        TValue[] copy = new TValue[nbValues];
        for( int i = 0; i < nbValues; ++i ) {
            copy[i] = GetValue(i);
        }
        return copy;
    }
}

This would work since Array supports ICollection.
But the problem is that ICollection has methods to add and remove entries. If the caller calls these methods only the copy will be modified not the dictionary...

The final solution I chose is to have my dictionary supports IDictionary but also ICollection and ICollection just so that I can return these collections from the properties Keys and Values...

public class MyDictionary : IDictionary<TKey,TValue>, 
                            ICollection<TKey>, 
                            ICollection<TValue>
{
}

So now the get accessor for the properties Keys and Values simply returns "this" ie: the dictionary.

ICollection<TValue> Values { 
    get {
        return this;
    }
}

It's probably the most optimal solution but I found it cumbersome to have to implement two extra interfaces whenever you want to implement IDictionary.

Do you have any other idea ?

I'm thinking that maybe returning the copy as an array was not such a bad idea after all. Anyway there is already a Add and Remove method in IDictionary which make more sense to be used.

Maybe returning a ReadOnlyCollection wrapping the array would be better as any attempt to modify the returned collection would fail?

ICollection<TValue> Values { 
    get {
        TValue[] copy = new TValue[nbValues];
        for( int i = 0; i < nbValues; ++i ) {
            copy[i] = GetValue(i);
        }
        return new System.Collections.ObjectModel.ReadOnlyCollection<TValue>(copy);
    }
}

Answer 1

Thank you all for your answers.

So I ended up doing two utility classes that implement the two ICollection requested by the Keys and Values properties. I have a few dictionaries where I need to add support for IDictionary so I will be reusing them a few times:

Here is the class for the collection of keys:

public class ReadOnlyKeyCollectionFromDictionary< TDictionary, TKey, TValue >
                       : ICollection<TKey>
                       where TDictionary : IDictionary<TKey,TValue>, IEnumerable<TKey>
{
    IDictionary<TKey, TValue> dictionary;

    public ReadOnlyKeyCollectionFromDictionary(TDictionary inDictionary)
    {
        dictionary = inDictionary;
    }

    public bool IsReadOnly {
        get { return true; }
    }

    Here I implement ICollection<TKey> by simply calling the corresponding method on 
    the member "dictionary" but I throw a NotSupportedException for the methods Add,
    Remove and Clear

    public IEnumerator<TKey> GetEnumerator()
    {
        return (dictionary as IEnumerable<TKey>).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return (dictionary as IEnumerable).GetEnumerator();
    }
}

Here is the class for the collection of values:

public class ReadOnlyValueCollectionFromDictionary<TDictionary, TKey, TValue> 
                       : ICollection<TValue>
                       where TDictionary : IDictionary<TKey, TValue>, IEnumerable<TValue>
{
    IDictionary<TKey, TValue> dictionary;

    public ReadOnlyValueCollectionFromDictionary(TDictionary inDictionary)
    {
        dictionary = inDictionary;
    }

    public bool IsReadOnly {
        get { return true; }
    }

    Here I implement ICollection<TValue> by simply calling the corresponding method on 
    the member "dictionary" but I throw a NotSupportedException for the methods Add,
    Remove and Clear

    // I tried to support this one but I cannot compare a TValue with another TValue
    // by using == since the compiler doesn't know if TValue is a struct or a class etc
    // So either I add a generic constraint to only support classes (or ?) or I simply
    // don't support this method since it's ackward in a dictionary anyway to search by
    // value.  Users can still do it themselves if they insist.
    bool IEnumerable<TValue>.Contains(TValue value)
    {
        throw new System.NotSupportedException("A dictionary is not well suited to search by values");
    }

    public IEnumerator<TValue> GetEnumerator()
    {
        return (dictionary as IEnumerable<TValue>).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return (dictionary as IEnumerable).GetEnumerator();
    }
}

Then if my dictionary supports the IEnumerable for TKey and TValue everything becomes so simple:

public class MyDictionary : IDictionary<SomeKey,SomeValue>, 
                            IEnumerable<SomeKey>, 
                            IEnumerable<SomeValue>
{
    IEnumerator<SomeKey> IEnumerable<SomeKey>.GetEnumerator()
    {
        for ( int i = 0; i < nbElements; ++i )
        {
            yield return GetKeyAt(i);
        }
    }

    IEnumerator<SomeValue> IEnumerable<SomeValue>.GetEnumerator()
    {
        for ( int i = 0; i < nbElements; ++i )
        {
            yield return GetValueAt(i);
        }
    }

    // IEnumerator IEnumerable.GetEnumerator() is already implemented in the dictionary

    public ICollection<SomeKey> Keys
    {
        get
        {
            return new ReadOnlyKeyCollectionFromDictionary< MyDictionary, SomeKey, SomeValue>(this);
        }
    }

    public ICollection<Value> Values
    {
        get
        {
            return new ReadOnlyValueCollectionFromDictionary< MyDictionary, SomeKey, SomeValue >(this);
        }
    }
}

It's too bad IDictionary is not returning IEnumerable instead of ICollection for the properties Keys and Values. All this would have been so much easier !

Answer 2

I wouldn't personally expect you to be able to remove keys and values from a dictionary via Keys and Values anyway - I think it's fine to not do so.

Returning a ReadOnlyCollection<T> is fine - that waythe caller will just get an exception if they try to modify the collection, rather than the attempt just being silently ignored.

That exception follows the behaviour of Dictionary<TKey, TValue> by the way:

using System;
using System.Collections.Generic;

class Test
{
    static void Main()
    {
        IDictionary<string, string> dictionary = 
            new Dictionary<string, string> {{ "a", "b" }};
        dictionary.Keys.Clear();
        Console.WriteLine(dictionary.Count);
    }
}

Results:

Unhandled Exception: System.NotSupportedException: Mutating a key collection
derived from a dictionary is not allowed.
   at System.Collections.Generic.Dictionary`2
            .KeyCollection.System.Collections.Generic.ICollection<TKey>.Clear()
   at Test.Main()

As SLaks says, if you can create your own implementation of ICollection<T> which is lazy, that would be better - but if that's tricky for some reason, or indeed if the performance isn't important in your case, just creating the array and wrapping it in ReadOnlyCollection<T> is fine. You should consider documenting the expected performance either way though.

One thing to note if you do create your own lazy implementation: you should probably have some sort of "version number" to make sure that you invalidate the returned collection if the underlying data is changed.

Answer 3

A ReadOnlyCollection is the best approach of the options you listed; these collections are not supposed to be writable.

However that your getter is O(n), which is not good.

The correct approach is to create your own collection classes that implement ICollection<T> and return a live view of the dictionary. (and throw exceptions from mutation methods)

This is the approach taken by Dictionary<TKey, TValue>; it ensures that the property getters are fast, and does not waste extra memory.