Best C # data structure for random populations?

Question

In C #, I have a case where I have a mapping from int to collections.

• int are dense (but not packed) sets from 1 to n, where n is unknown.
• Cells will be loaded randomly.
• the marginal cost of each cell must be ideal (same as List<T> or T[] )
• I want the default cells to fill in upon request

What is the best structure for this?

A List<T> will work well (better in space than a Dictionary<> ), and based on this, I can get most of what I want, but is there something better? As in the code of the best code, you do not write.

Answer 1

A Dictionary<int, Cell> sounds like a good match for me. Or you can easily use List<Cell> , and just make sure 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 become a true follower, one option is to create a facade class that provides a strategy around several different cartographers. Make it use a statically defined array when N is <some value and when the load (packing) exceeds a certain threshold. Apply it to the Tree or Dictionary view when passing certain thresholds.

You did not indicate how you planned to actually interact with this data structure after it was created, so depending on what your access / use patterns are, a mixed strategy may provide better runtime behavior than stick to a single view of the data. Think about This is similar to how the implementation of quicksort algorithms sometimes switches to a simpler sorting algorithm when the collection sorting has less than N data elements.

Hooray!