How are elements stored in containers in .Net?

Question

Hi
How are elements stored in containers in .Net? For example, a C++ vector stores in sequential order, while List doesn't.
How are they implemented for .Net containers (Array, ArrayList, ...)?
Thanks.

Answer 1

It varies by container. Because the implementation is proprietary, there are no public specs mandating what the underlying data structure must be.

If you're interested in taking the time, I've used the following tools before to understand how MS implemented this class or that:

• Debugging with the Microsoft .NET Framework debugging symbols.
• Inspecting assemblies with Reflector.

Answer 2

It depends on the element. But a C++ Vector is equivalent to a C# List, and a C++ List<T> is equivalent to a C# LinkedList

The C# ArrayList is pretty much, a C# List<object>

Wikipedia lists many data structures, and I suggest you have a look there, to see how the different ones are implemented.

So:

C++        C#                      How
Vector     ArrayList / List        Array (sequential)
List       LinkedList              Linked List (non-sequential, i.e. linked)

Answer 3

In .net, containers (even arrays) handle all access to them. You don't use pointers to work with them (except in extremely rare cases you probably won't ever get into), so it often doesn't matter how they store info. In many cases, it's not even specified how things work behind the scenes, so the implementation can be changed to something "better" without breaking stuff that relies on those details for some stupid reason.

Last i heard, though, arrays store their entries sequentially -- with the caveat that for reference-type objects (everything that's not a struct), "entries" are the references as opposed to the objects themselves. The data could be anywhere in memory. Think of it more like an array of references than an array of objects.

ArrayLists, being based on arrays, should store their stuff the same way.