C# equivalent of C++ vector, with contiguous memory?

Question

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?

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, Aug 04 '11 at 14:31

score 115 · Accepted Answer · answered Aug 04 '11 at 14:31

115

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];

answered Aug 04 '11 at 14:31

Darin Dimitrov

1,023,142
271
3,287
2,928

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 Aug 10 '13 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` 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 Jul 28 '15 at 02:36
Learned something today. I thought `List` 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 Oct 07 '16 at 07:42
@dotNet, internally `List` 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(expected_array_size)`. – Artur A Aug 27 '20 at 20:51

score 18 · Answer 2 · answered Aug 04 '11 at 14:31

18

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

answered Aug 04 '11 at 14:31

Bala R

107,317
23
199
210

2

Not entirely true. If T is a reference type, there will not be contiguous memory. – Matteo Mosca Aug 04 '11 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 Aug 04 '11 at 14:37
14

Well, I know that. But tell me. You have a List. 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. – Matteo Mosca Aug 04 '11 at 14:39
@MatteoMosca storing the references contiguously at least removes one level of indirection. Better than nothing i guess. – Tim Seguine Nov 18 '14 at 21:34
8

@MatteoMosca The OP asked for "no performance penalty for access vs. standard arrays". That's true of List regardless of what T is, so all your comments on this page are off-point. – Jim Balter Jul 28 '15 at 02:30

score 18 · Answer 3 · answered Aug 04 '11 at 14:32

18

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

answered Aug 04 '11 at 14:32

Armen Tsirunyan

130,161
59
324
434

score 17 · Answer 4 · answered Aug 04 '11 at 14:32

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.

score 5 · Answer 5 · answered Apr 08 '14 at 13:18

5

It looks like CLR / C# might be getting better support for Vector<> soon.

http://blogs.msdn.com/b/dotnet/archive/2014/04/07/the-jit-finally-proposed-jit-and-simd-are-getting-married.aspx

answered Apr 08 '14 at 13:18

rjdevereux

1,842
2
21
35

C# equivalent of C++ vector, with contiguous memory?

5 Answers5

Linked