Is there a way to keep track of the ordering of items in a dictionary?

Question

I have a Dictionary<Guid, ElementViewModel>. (ElementViewModel is our own complex type.) I add items to the dictionary with a stock standard items.Add(Guid.NewGuid, new ElementViewModel() { /*setters go here*/ });,

At a later stage I remove some or all of these items.

A simplistic view of my ElementViewModel is this:

class ElementViewModel
{
    Guid Id { get; set; }
    string Name { get; set; }
    int SequenceNo { get; set; }
}

It may be significant to mention that the SequenceNos are compacted within the collection after adding, in case other operations like moving and copying took place. {1, 5, 6} -> {1, 2, 3}

A simplistic view of my remove operation is:

public void RemoveElementViewModel(IEnumerable<ElementViewModel> elementsToDelete)
    {
        foreach (var elementViewModel in elementsToDelete)
            items.Remove(elementViewModel.Id);

        CompactSequenceNumbers();
    }

---

I will illustrate the problem with an example:

I add 3 items to the dictionary:

var newGuid = Guid.NewGuid();
        items.Add(newGuid, new MineLayoutElementViewModel { Id = newGuid, SequenceNo = 1, Name = "Element 1" });
        newGuid = Guid.NewGuid();
        items.Add(newGuid, new MineLayoutElementViewModel { Id = newGuid, SequenceNo = 2, Name = "Element 2" });
        newGuid = Guid.NewGuid();
        items.Add(newGuid, new MineLayoutElementViewModel { Id = newGuid, SequenceNo = 3, Name = "Element 3" });

I remove 2 items

RemoveElementViewModel(new List<ElementViewModel> { item2, item3 }); //imagine I had them cached somewhere.

Now I want to add 2 other items:

newGuid = Guid.NewGuid();
        items.Add(newGuid, new MineLayoutElementViewModel { Id = newGuid, SequenceNo = 2, Name = "Element 2, Part 2" });
        newGuid = Guid.NewGuid();
        items.Add(newGuid, new MineLayoutElementViewModel { Id = newGuid, SequenceNo = 3, Name = "Element 3, Part 2" });

On evaluation of the dictionary at this point, I expected the order of items to be "Element 1", "Element 2, Part 2", "Element 3, Part 2"

but it is actually in the following order: "Element 1", "Element 3, Part 2", "Element 2, Part 2"

---

I rely on the order of these items to be a certain way. Why is it not as expected and what can I do about it?

Answer 1

.Net Dictionaries are unordered by design.

You should use a KeyedCollection<TKey, TValue> instead; it will preserve the order that items are added to the collection and will also use a hash table for speedy lookups.

For example:

class ElementViewModelCollection : KeyedCollection<Guid, ElementViewModel> {
    protected override Guid GetKeyForItem(ElementViewModel item) { return item.Id; }
}

items.Add(new MineLayoutElementViewModel { Id = Guid.NewGuid(), SequenceNo = 3, Name = "Element 3" });

Note that if you change the Id property after the item is added to the collection, you'll need to call the ChangeItemKey method on the collection. I highly recommend that you make the Id property read-only.

Answer 2

Any reason why you are not using a System.Collections.Generic.SortedDictionary , seems like what you are looking for

Answer 3

Unfortunately, a SortedDictionary isn't fast enough for the huge amount of data we have to store in it and a KeyedCollection defeats the purpose of compacting the SequenceNo property of the elements manually.

Strictly speaking, we should rewrite the way that sequencing happens because my solution is not the prettiest:

Every time an item is deleted, new the dictionary and re-add the non-deleted items to the newed dictionary in order to maintain default sequence. --> hideous practice, I admit. Plan on changing it as soon as I have less pressure.