.NET Collection that is a struct

Question

Here's an interesting question ... is there a collection that is a struct somewhere in the .net framework?

Just to clarify, all of the existing collections (List, array, etc.) are all reference types ... even if you set the generic parameter to a value type. But I want to know if there's a way I can make a collection that is actually a struct. I obviously wouldn't plan on passing this around (which would result in a ton of copying) ... I'd keep it as a private member in my class (internal state) so it's only defined once. The idea is that I would be able to avoid invoking the garbage collector just to make a small collection (think XNA).

Assuming one does not exist, a secondary part of the question is, what would be the ideal data structure for this. linked list?

Answer 1

No, such a type does not exist and it would not be a good idea. Structs should be small immutable value types according to the Microsoft guidelines.

From the Value Type Usage Guidelines:

• Act like primitive types.
• Have an instance size under 16 bytes.
• Are immutable.
• Value semantics are desirable.

It would be difficult to implement a linked list as a value type because linked lists are typically defined recursively. This works fine:

class Node<T>
{
    public T Value;
    public Node<T> Next;
}

But this fails because structs have a fixed size and that size must be known when the struct is defined:

struct Node<T>
{
    public T Value;

    // Error: Struct member 'Node<T>.Next' of type 'Node<T>'
    // causes a cycle in the struct layout
    public Node<T> Next; 
}

Answer 2

Actually there is a struct that is a collection. BitVector32 is a struct and acts like a collection of 32 booleans, or 4 bytes or 2 shorts. It's pretty handy when you want to do bittwidling but don't want to think too much about creating masks and such.

Also if you actually plan on rolling your own, be warned that if you make it implement something like IList<Int32> you should never send it to code that reads like

public static void SomeMethod(IList<Int32> list)
{
       ....
}

As that will box it and each member access will most likely lead to boxing instead send it to a method that has this signature::

public static void SomeMethod<T>(T list) where T:IList<Int32>
{
       ....
}

As the second example will emit the constrained opcode before each callvirt which will avoid boxing when invoking struct members. Good luck though.