Change cardinality of item in C# dictionary

Question

I've got a dictionary, something like

Dictionary<Foo,String> fooDict

I step through everything in the dictionary, e.g.

foreach (Foo foo in fooDict.Keys)
    MessageBox.show(fooDict[foo]);

It does that in the order the foos were added to the dictionary, so the first item added is the first foo returned.

How can I change the cardinality so that, for example, the third foo added will be the second foo returned? In other words, I want to change its "index."

Answer 1

I am not fully educated in the domain to properly answer the question, but I have a feeling that the dictionary sorts the values according to the key, in order to perform quick key search. This would suggest that the dictionary is sorted by key values according to key comparison. However, looking at object methods, I assume they are using hash codes to compare different objects considering there is no requirement on the type used for keys. This is only a guess. Someone more knowledgey should fill in with more detail.

Why are you interested in manipulating the "index" of a dictionary when its purpose is to index with arbitrary types?

Answer 2

If you read the documentation on MSDN you'll see this:

"The order in which the items are returned is undefined."

You can't gaurantee the order, because a Dictionary is not a list or an array. It's meant to look up a value by the key, and any ability to iterate values is just a convenience but the order is not behavior you should depend on.

Answer 3

4 Guys From Rolla has a rather round-about method of doing this:
http://www.4guysfromrolla.com/webtech/062701-1.shtml.

Answer 4

I don't know if anyone will find this useful, but here's what I ended up figuring out. It seems to work (by which I mean it doesn't throw any exceptions), but I'm still a ways away from being able to test that it works as I hope it does. I have done a similar thing before, though.

        public void sortSections()
    {
        //OMG THIS IS UGLY!!!
        KeyValuePair<ListViewItem, TextSection>[] sortable = textSecs.ToArray();
        IOrderedEnumerable<KeyValuePair<ListViewItem, TextSection>> sorted = sortable.OrderBy(kvp => kvp.Value.cardinality);

        foreach (KeyValuePair<ListViewItem, TextSection> kvp in sorted)
        {
            TextSection sec = kvp.Value;
            ListViewItem key = kvp.Key;

            textSecs.Remove(key);
            textSecs.Add(key, sec);
        }
    }

Answer 5

The short answer is that there shouldn't be a way since a Dictionary "Represents a collection of keys and values." which does not imply any sort of ordering. Any hack you might find is outside the definition of the class and may be liable to change.

You should probably first ask yourself if a Dictionary is really called for in this situation, or if you can get away with using a List of KeyValuePairs.

Otherwise, something like this might be useful:

public class IndexableDictionary<T1, T2> : Dictionary<T1, T2>
{
    private SortedDictionary<int, T1> _sortedKeys;

    public IndexableDictionary()
    {
        _sortedKeys = new SortedDictionary<int, T1>();
    }
    public new void Add(T1 key, T2 value)
    {
        _sortedKeys.Add(_sortedKeys.Count + 1, key);
        base.Add(key, value);
    }

    private IEnumerable<KeyValuePair<T1, T2>> Enumerable()
    {
        foreach (T1 key in _sortedKeys.Values)
        {
            yield return new KeyValuePair<T1, T2>(key, this[key]);
        }
    }

    public new IEnumerator<KeyValuePair<T1, T2>> GetEnumerator()
    {
        return Enumerable().GetEnumerator();
    }

    public KeyValuePair<T1, T2> this[int index]
    {
        get
        {
            return new KeyValuePair<T1, T2> (_sortedKeys[index], base[_sortedKeys[index]]);
        }
        set
        {
            _sortedKeys[index] = value.Key;
            base[value.Key] = value.Value;
        }

    }


}

With client code looking something like this:

    static void Main(string[] args)
    {
        IndexableDictionary<string, string> fooDict = new IndexableDictionary<string, string>();

        fooDict.Add("One", "One");
        fooDict.Add("Two", "Two");
        fooDict.Add("Three", "Three");

        // Print One, Two, Three
        foreach (KeyValuePair<string, string> kvp in fooDict)
            Console.WriteLine(kvp.Value);



        KeyValuePair<string, string> temp = fooDict[1];
        fooDict[1] = fooDict[2];
        fooDict[2] = temp;


        // Print Two, One, Three
        foreach (KeyValuePair<string, string> kvp in fooDict)
            Console.WriteLine(kvp.Value);

        Console.ReadLine();
    }

UPDATE: For some reason it won't let me comment on my own answer.

Anyways, IndexableDictionary is different from OrderedDictionary in that

1. "The elements of an OrderedDictionary are not sorted in any way." So foreach's would not pay attention to the numerical indices
2. It is strongly typed, so you don't have to mess around with casting things out of DictionaryEntry structs

Answer 6

You may be interested in the OrderedDicationary class that comes in System.Collections.Specialized namespace.

If you look at the comments at the very bottom, someone from MSFT has posted this interesting note:

This type is actually misnamed; it is not an 'ordered' dictionary as such, but rather an 'indexed' dictionary. Although, today there is no equivalent generic version of this type, if we add one in the future it is likely that we will name such as type 'IndexedDictionary'.

I think it would be trivial to derive from this class and make a generic version of OrderedDictionary.