How to pre-allocate C# List of List of T

Question

I'd like to pre-allocate a List<List<double>>. I know I can pre-allocate 1-D Lists like this:

List<double> MyList = new List<double>(SomeSize);

Is it possible to do this for nested lists? In C++, I would do:

vector<vector<double>> MyList(OuterSize, vector<double>(InnerSize));

I cannot seem to find an efficient way to do this in C#, but I'm sure there's a way...

Answer 1

There is no such way, cause it's not a continuous piece of memory. You would have to program it yourself - iterating through the outer dimension.

A List is not really comparable to a C++ array. You allocate the memory for it, that means you avoid the growing of the List, but the List starts with Count=0, and you have to Add elements, you cannot access it by the indexer. And the initialization with the capacity is optional ! This is just increasing performance a little, if you know your final length in advance.

If you get along with a fixed-length array, you can allocate a multi-dimensional array like

    int[,] x = new int[4,5];

at once.

Answer 2

The only way to preallocate a list is to instantiate it. You can certainly instantiate the outer list, but if you want to preallocate the inner lists you have to instantiate them too, meaning that you have to prepopulate the outer list.

You could use

var list = Enumerable.Range(1, OuterSize)
     .Select( x => new List<T>(InnerSize) )
     .ToList();

This creates a list with Outersize elements, each element containing an empty list that has been preallocated to contain InnerSize elements.

However, with this approach you still have to add items to the inner lists. If you wish to use ElementAt immediately, that doesn't work. You'd have to prepopulate the inner lists. You could use:

var list = Enumerable.Range(1, OuterSize)
    .Select
    (
        x => Enumerable.Range(1, InnerSize)
                 .Select( y => default(T) )
                 .ToList()
    )
    .ToList();

This instantiates a list of OuterSize elements, each of which is a list of InnerSize elements (all of which have the same null/default value).

Answer 3

Your C++ code uses the vector's "fill constructor", which instantiates all elements of the first dimension of the collection with the lists representing the second dimension.

There is no fill constructor for C# List<T> objects that allows specifying the initial capacity. The existing fill constructor guarantees that the list will have "sufficient" capacity for the items provided by the IEnumerable<T> parameter, but it does not guarantee the capacity will closely match the cardinality of the parameter enumerable (in part because enumerables, by design, do not expose their cardinality, so the only way to exactly match the capacity is to resize the list's underlying array one element at a time).

You can do this in two lines with a little Linq, three with a traditional loop, by constructing an empty list of the desired capacity, then adding the objects of the second dimension, each initialized to their desired capacity:

var myList = new List<List<T>>(5);
//Option A: Linq
myList.AddRange(Enumerable.Repeat(0, 5).Select(x => new List<string>(4)));
//Option B: Loop
for(i=0;i<5;i++)
    myList.Add(new List<string>(4));

Your C++, at some level, will do something similar to either of these, there just isn't anything in C# to abstract this behind a constructor.

---

Breaking down the first option, the List<T>.AddRange() method adds each element of an IEnumerable<T> to the list, resizing as necessary (it won't have to here as we're adding up to the specified capacity). So we need to generate an enumerable sequence of lists. Well, there's a Linq method for that. The Enumerable.Repeat() method generates an enumerable sequence that repeats a specified value the specified number of times. However, if we specified "new List()" as the value to repeat, that constructor would execute only once (prior to calling Repeat() to evaluate the parameter value to pass), and we'd get the same reference to a single List repeated four times. We instead want to instantiate four lists, so we need to define that constructor as a line of repeatable code, meaning we need a delegate that we can execute as a method call.

No overload of Enumerable.Repeat() accepts a Func<T> and returns an IEnumerable<T>; if you want to repeat a function with this method, you get an IEnumerable<Func<T>>. But, the Select<T>() function can be called on an enumerable sequence of inputs, and produces the enumerable sequence of all results of the lambda statement (a form of anonymous delegate method definition) given each element of the input enumerable as a parameter (which we ignore because it's garbage; all we care about the input enumerable is that it has 5 elements). So now we have an Enumerable<List<string>> that the parent List will slurp into its internal collection.

Yes, I could have been cleverer and done something like:

myList.AddRange(Enumerable.Repeat(()=>new List<string>(4), 5).Select(x => x()));

This does the same thing, only what the Repeat() method repeats isn't garbage data, it's the reference to a lambda performing the object construction, which then gets called in the Select() method's lambda. But, I now have two lambdas, which are implemented as private formulaically-named functions of the class containing this code, which adds more cruft to the resulting object than we really need. The compiler also can't infer the generic output type of the Repeat() function from the lambda statement, so the above code doesn't compile; I'd have to explicitly specify the generic type, and this line of code (and C# as a language) is verbose enough as it is.