How do i create a struct in C# that contains an array but does not use heap?

Question

What i need:

a polygon with arbitrary amount of vertices ( or at least up to max number of vertices )
it should be a struct, so that it can be fast and can be assigned / passed by value

It seems like i can't use arrays or collections for storing vertices, because then my polygon struct would point to objects on a heap, and when one polygon is assigned to another one by value only shallow copy would be performed, and i would have both polygons pointing to the same vertex array. For example:

Polygon a = new Polygon(); 
Polygon b = a; 
// both polygons would be changed 
b.vertices[0] = 5;

Then how do i create a struct that can have arbitrary number (or some fixed number) of vertices, but without using heap at all?

I could just use lots of variables like v1, v2, v3 ... v10 etc, but i want to keep my code clean, more or less.

Is your actual concern about `stack vs. heap` or `reference type vs. value type`? If the former, check out [stackalloc](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/operators/stackalloc). — itsme86, Sep 01 '20 at 17:23
Having a potentially big polygon entirely in stack memory and passing it around (copy it every time you pass it as a function parameter etc.) is not necessarily faster (and possibly even slower) than using a standard collection. Do you have actual problems that you need to fix or are you trying to pre-emptively optimize a problem that might not even exist? — Nico Schertler, Sep 01 '20 at 17:31
I feel like in this case your question is more about deep-copying a list than it is about stack vs. heap. Stack and Heap are implementation details that we don't need to worry about 99% of the time. — Rufus L, Sep 01 '20 at 17:33
Also, see: [.NET Collection that is a struct](https://stackoverflow.com/questions/4471590/net-collection-that-is-a-struct) and [Deep copy of List](https://stackoverflow.com/questions/4226747/deep-copy-of-listt) — Rufus L, Sep 01 '20 at 17:36
With respect, you might get better answers if you explain what you want to do. Your question is about how to do it. Please [edit] your question. And please keep in mind that the C# / Roslyn compiler tech does an excellent job of optimizing code and handling data structures. If you need to outsmart it, you probably know exactly what it's doing wrong for you, and you should tell us.Premature optimization can make code completely unmaintainable. — O. Jones, Sep 01 '20 at 17:42

John Alexiou · Answer 1 · 2020-09-01T20:58:44.603

You have the option to define your array with the fixed keyword, which puts it in the stack.

But you cannot directly access the elements of the array, unless you are in an unsafe context and use pointers.

To get the following behavior:

    static void Main(string[] args)
    {
        FixedArray vertices = new FixedArray(10);
        vertices[0] = 4;

        FixedArray copy = vertices;
        copy[0]  = 8;
        Debug.WriteLine(vertices[0]);
        // 4
        Debug.WriteLine(copy[0]);
        // 8
    }

Then use the following class definition:

public unsafe struct FixedArray 
{
    public const int MaxSize = 100;

    readonly int size;
    fixed double data[MaxSize];

    public FixedArray(int size) : this(new double[size])
    { }

    public FixedArray(double[] values)
    {
        this.size = Math.Min(values.Length, MaxSize);
        for (int i = 0; i < size; i++)
        {
            data[i] = values[i];
        }
    }

    public double this[int index]
    {
        get
        {
            if (index>=0 && index<size)
            {
                return data[index];
            }
            return 0;
        }
        set
        {
            if (index>=0 && index<size)
            {
                data[index] = value;
            }
        }
    }

    public double[] ToArray()
    {
        var array = new double[size];
        for (int i = 0; i < size; i++)
        {
            array[i] = data[i];
        }
        return array;
    }        
}

A couple of things to consider. The above needs to be compiled with the unsafe option. Also the MaxSize but be a constant, and the storage required cannot exceed this value. I am using an indexer this[int] to access the elements (instead of a field) and also have a method to convert to a native array with ToArray(). The constructor can also take a native array, or it will use an empty array to initialize the values. This is to ensure that new FixedArray(10) for example will have initialized at least 10 values in the fixed array (instead of being undefined as it is the default).

Read more about this usage of fixed from Microsoft or search for C# Fixed Size Buffers.

Heap array field

 struct StdArray
 {
     int[] vertices;

     Foo(int size)
     {
         vertices = new int[size];
     }
 }

Stack array field

 unsafe struct FixedArray
 {
     fixed int vertices[100];
     int size;
     Foo(int size)
     {
         this.size = size;
         // no initialization needed for `vertices`
     }
 }

Fixing an object doesn't move it to the stack, nor does it made it behave like a value type. It simply makes sure the GC doesn't move it during its collections. — Servy, Sep 01 '20 at 20:20
@Servy Actually not, `fixed` in structures is a special keyword that moves the values in the stack. I simplified the example and removed the `fixed()` statements and it still works. This has been an improvement since [the initial introduction](https://thedeveloperblog.com/fixed-buffer). Try it and you will see this does exactly as asked. — John Alexiou, Sep 01 '20 at 20:24
As I understand, the ´fixed´ keyword embeds the fixed-size array as part of the struct. Whether the array lives on the stack or the heap will depend on how the struct is used. If it is used as a local variable declaration, then indeed, the data will live on the stack, but if it is used as a member of a reference class, then the buffer will live on the heap (with an instance of the class embedding the whole fixed-size array as part of its fields and not as a reference to an independent array) — BlueStrat, Dec 21 '20 at 18:48
So with a declaration of `class Foo { FixedArray data; }` the data might reside on the heap. That makes sense since the point of `struct` is to keep all data together. — John Alexiou, Dec 21 '20 at 22:17

score 0 · Answer 2 · answered Sep 01 '20 at 17:30

0

If it suits your logic, you could use a Span<T>, which is allocated on the stack. Read more here

answered Sep 01 '20 at 17:30

insane_developer

789
5
6

score 0 · Answer 3 · answered Sep 01 '20 at 17:44

One other way to just copy the array with a copy constructor

public Polygon(Polygon other)
{
    this.vertices = other.vertices.Clone() as int[];
}

then

var a = new Polygon();
a.vertices[0] = 5;

var b = new Polygon(a):
Debug.WriteLine(a.vertices[0]);
// 5
Debug.WriteLine(b.vertices[0]);
// 5

b.vertices[0] = 10;
Debug.WriteLine(a.vertices[0]);
// 5
Debug.WriteLine(b.vertices[0]);
// 10

How do i create a struct in C# that contains an array but does not use heap?

3 Answers3