Best C# data structure for random order population?

Question

In C# I have a use case where I have a mapping from ints to collections.

• the ints are a dense (but not packed) set from 1 to n where n is not known.
• The cells will be loaded in random order.
• the marginal cost of each cell should be ideal (as good as a List<T> or T[])
• I'd like to have the cells default filled on demand

What is the best structure for this?

A List<T> would work well (better in space than a Dictionary<>) and by deriving from it I can get much of what I want, but is there something better? As in the best code is code you don't write.

Answer 1

A Dictionary<int, Cell> sounds like a good match to me. Or you could use a List<Cell> quite easily, and just make sure that you expand it where necessary:

public static void EnsureCount<T>(List<T> list, int count)
{
    if (list.Count > count)
    {
        return;
    }
    if (list.Capacity < count)
    {
        // Always at least double the capacity, to reduce
        // the number of expansions required
        list.Capacity = Math.Max(list.Capacity*2, count);
    }
    list.AddRange(Enumerable.Repeat(default(T), list.Capacity-list.Count));
}

Answer 2

If you want to be a real stickler, one option is to write a facade class which provides a strategy around a number of different mappers. Make it so that it uses a statically defined array when N is < some value and when the load (packedness) is over some threshold. Have it swap to a Tree or a Dictionary representation when certain thresholds are passed.

You did not state how you planned on actually interacting with this data structure once it had been built, so depending on what your access / usage patterns are, a mixed strategy might provide a better runtime behavior than sticking with a single data representation. Think of it in a similar fashion to how quicksort algorithm implementations will sometimes switch to a simpler sort algorithm when the collection to be sorted has less than N data elements.

Cheers!