101

What's the C# equivalent of C++ vector?

I am searching for this feature:

To have a dynamic array of contiguously stored memory that has no performance penalty for access vs. standard arrays.

I was searching and they say .NET equivalent to the vector in C++ is the ArrayList, so:

Do ArrayList have that contiguous memory feature?

1
  • 4
    Isn't the CLR insufficiently close to the metal for you to specify (or even consistently expect) how a structure is allocated in memory?
    – Aphex
    Commented Aug 4, 2011 at 14:31

4 Answers 4

119

You could use a List<T> and when T is a value type it will be allocated in contiguous memory which would not be the case if T is a reference type.

Example:

List<int> integers = new List<int>();
integers.Add(1);
integers.Add(4);
integers.Add(7);

int someElement = integers[1];
4
  • 8
    I'm not 100% familiar with the CLR, but it makes sense that even if T is a reference type you'll still have contiguous memory. It's basically an array of pointers...
    – josaphatv
    Commented Aug 10, 2013 at 10:01
  • 1
    "which would not be the case if T is a reference type" -- it's just as much the case as for T[] ... the OP asked for "no performance penalty for access vs. standard arrays", and List<T> provides that. And if T is a reference type, that is analogous to T* in C++, so you get just as much contiguousness as in C++. If one wants the objects themselves to be contiguous, then of course one needs value types ... in both languages. The difference, of course, is that in C++ any type can be used as either value or ref, whereas in C# it's a property of the type via the class/struct distinction.
    – Jim Balter
    Commented Jul 28, 2015 at 2:36
  • Learned something today. I thought List<T> is always implemented as a linked list internally. So how does it expand dynamically then when we call Add()? Something like VB6's Redim Preserve which used to copy the entire array to a new location?
    – dotNET
    Commented Oct 7, 2016 at 7:42
  • @dotNet, internally List<T> creates a small array T[]. The items internally are added to the array. Once the size of the array is completed, a new array is created double size of the previous. The data is copied to the new larger array, the smaller is destroyed, and so on. A developer can give a hint to .NET to create a large enough internal array before filling the List via constructor: new List<T>(expected_array_size).
    – Artur A
    Commented Aug 27, 2020 at 20:51
20

use List<T>. Internally it uses arrays and arrays do use contiguous memory.

5
  • 2
    Not entirely true. If T is a reference type, there will not be contiguous memory. Commented Aug 4, 2011 at 14:34
  • 3
    @Matteo if you look at the source, there is private T[] _items; that's used for backend storage, reference type or not.
    – Bala R
    Commented Aug 4, 2011 at 14:37
  • 14
    Well, I know that. But tell me. You have a List<SomeClass>. The references to the SomeClass instances will be stored in contiguous memory, but not the instances themselves. As reference types, they will be in the heap, and you surely know how the heap works. Commented Aug 4, 2011 at 14:39
  • @MatteoMosca storing the references contiguously at least removes one level of indirection. Better than nothing i guess. Commented Nov 18, 2014 at 21:34
  • 9
    @MatteoMosca The OP asked for "no performance penalty for access vs. standard arrays". That's true of List<T> regardless of what T is, so all your comments on this page are off-point.
    – Jim Balter
    Commented Jul 28, 2015 at 2:30
19

C# has a lot of reference types. Even if a container stores the references contiguously, the objects themselves may be scattered through the heap

18

First of all, stay away from Arraylist or Hashtable. Those classes are to be considered deprecated, in favor of generics. They are still in the language for legacy purposes.

Now, what you are looking for is the List<T> class. Note that if T is a value type you will have contiguos memory, but not if T is a reference type, for obvious reasons.

Not the answer you're looking for? Browse other questions tagged or ask your own question.