Indexing into arrays of arbitrary rank in C#

Question

I need to iterate over an array of arbitrary rank. This is for both reading and writing, so GetEnumerator will not work.

Array.SetValue(object, int) doesn't work on multidimensional arrays. Array.SetValue(object, params int[]) would require excessive arithmetic for iterating through the multidimensional space. It would also require dynamic invocation to get around the params part of the signature.

I'm tempted to pin the array and iterate over it with a pointer, but I can't find any documentation that says that multidimensional arrays are guaranteed to be contiguous. If they have padding at the end of a dimension then that won't work. I'd also prefer to avoid unsafe code.

Is there an easy way to sequentially address a multidimensional array using only a single index?

Ferdy

I see no error in using "unsafe" code. It's safe to use pointers when you actually know what you are doing and it's a viable and efficient solution. – Taper

Btw it's perfectly valid to pass an int[] where a params int[] is expected. – Germicide

@dtb, you appear to be correct on both syntax points. I never knew you could directly pass an array to a params array parameter. – Ferdy

@Mikael Svenson, I agree that unsafe code is not to be feared, but I also think it should be avoided if there is an equivalent safe solution. – Ferdy

Answer 1

Multidimensional arrays are guaranteed to be contiguous. From ECMA-335:

Array elements shall be laid out within the array object in row-major order (i.e., the elements associated with the rightmost array dimension shall be laid out contiguously from lowest to highest index).

So this works:

int[,,,] array = new int[10, 10, 10, 10];

fixed (int* ptr = array)
{
    ptr[10] = 42;
}

int result = array[0, 0, 1, 0];  // == 42

Germicide

Thanks, that's what I was looking for and gives me a good fall-back implementation. BTW, I think your code chokes on 'int* ptr = array', but the idea is sound. – Ferdy

@Kennet Belenky: I've just double-checked and the code works perfectly well as is. Of course, a solution involving unsafe code doesn't help if you want to avoid unsafe code, but I fear there is no other solution that doesn't come with a lot of (unnecessary) overhead (such as recursively iterating through all dimensions). – Germicide

... however it turns out that pinning only works if the array contains primitive value types. I didn't mention this in the original question, but the array I'm trying to address also has an arbitrary ElementType, and may contain structs, reference types or boxed value types. I guess I have to resort to using an indexing array. – Ferdy

Answer 2

You can use the Rank and GetUpperBound property/method to create an indices array that you can pass to the array's SetValue and GetValue methods:

int[] Indices(Array a, int idx)
{
    var indices = new int[a.Rank];

    for (var i = 0; i < a.Rank; i++)
    {
        var div = 1;

        for (var j = i + 1; j < a.Rank; j++)
        {
            div *= a.GetLength(j);
        }

        indices[i] = a.GetLowerBound(i) + idx / div % a.GetLength(i);
    }

    return indices;
}

..and use it like so:

for (var i = 0; i < array.Length; i++)
{
    var indices = Indices(array, i);
    array.SetValue(i, indices);
    var val = array.GetValue(indices);
}

Lester

Yes, that would be the excessive arithmetic I was talking about. You would also need to use Array.GetLowerBound, not just Array.GetUpperBound. – Ferdy

@kennet Actually, we don't need Array.GetUpperBound, just saw the Array.GetLength method :) – Lester

Answer 3

Perhaps you could join them all into the a single temporary collection, and just iterate over that.

Amphiarthrosis

Easy enough, I'll just use GetEnumerator to address everything in the array. The problem is that I also have to write at various points in the array, and GetEnumerator will fail for that. – Ferdy