A very basic auto-expanding list/array

Question

Hi,

I have a method which returns an array of fixed type objects (let's say MyObject).

The method creates a new empty Stack<MyObject>. Then, it does some work and pushes some number of MyObjects to the end of the Stack. Finally, it returns the Stack.ToArray().

It does not change already added items or their properties, nor remove them. The number of elements to add will cost performance. There is no need to sort/order the elements.

Is Stack a best thing to use? Or must I switch to Collection or List to ensure better performance and/or lower memory cost?

Answer 1

Stack<T> will not be any faster than List<T>.

For optimal performance, you should use a List<T> and set the Capacity to a number larger than or equal to the number of items you plan to add.

Answer 2

Use a LinkedList maybe?

Though LinkedLists are only useful with sequential data.

Answer 3

If the ordering doesn't matter and your method doesn't need to add/remove/edit items that have already been processed then why not return IEnumerable<MyObject> and just yield each item as you go?

Then your calling code can either use the IEnumerable<MyObject> sequence directly, or call ToArray, ToList etc as required.

For example...

// use the sequence directly
foreach (MyObject item in GetObjects())
{
    Console.WriteLine(item.ToString());
}

// ...

// convert to an array
MyObject[] myArray = GetObjects().ToArray();

// ...

// convert to a list
List<MyObject> myList = GetObjects().ToList();

// ...

public IEnumerable<MyObject> GetObjects()
{
     foreach (MyObject foo in GetObjectsFromSomewhereElse())
     {
         MyObject bar = DoSomeProcessing(foo);
         yield return bar;
     }
}

Answer 4

Stack<T> is not any faster than List<T> in this case, so I would probably use List, unless something about what you are doing is "stack-like". List<T> is the more standard data structure to use when what you want is basically a growable array, whereas stacks are usually used when you need LIFO behavior for the collection.

Answer 5

If you need the semantics of a stack (last-in first-out), then the answer is, without any doubt, yes, a stack is your best solution. If you know from the start how many elements it will end up with, you can avoid the cost of automatic resizing by calling the constructor that receives a capacity.

If you're worried about the memory cost of copying the stack into an array, and you only need sequential access to the result, then, you can return the Stack<T> as an IEnumerable<T> instead of an array and iterate it with foreach.

All that said, unless this code proves it is problematic in terms of performance (i.e., by looking at data from a profiler), I wouldn't bother much and go with the semantics call.

Answer 6

For this purpose, there is not any other collections in the framework that will perform considerably better than a Stack<T>.

However, both Stack<T> and List<T> auto-grows their internal array of items when the initial capacity is exceeded. This involves creating a new larger array and copying all items. This costs some performance.

If you know the number of items beforehand, initialize your collection to that capacity to avoid auto-growth. If you don't know exactly, choose a capacity that is unlikely to be insufficient.

Most of the built in collections take the initial capacity as a constructor argument:

var stack = new Stack<T>(200);  // Initial capacity of 200 items.

Answer 7

You don't need Stack<> if all you're going to do is append. You can use List<>.Add (http://msdn.microsoft.com/en-us/library/d9hw1as6.aspx) and then ToArray.

(You'll also want to set initial capacity, as others have pointed out.)