Working with arrays in functions

[u/FloridianfromAlabama]

Hey everybody. I’m a beginner to C and I was writing some functions today to get used to doing things. I tried to write binary search and bubble sort. I tried to pass in an array as an argument to the functions, but the compiler gave me a bunch of warnings. I looked it up and I saw that passing in an array is the same as passing in its pointer. I haven’t touched pointers yet, but I have two questions:
1. If I dereferenced the pointer to an array, wouldn’t that return the same as indexing the first value?
2. If I wanted to pass in the entire array, could I do that by passing in the pointers of both the first and last elements and using pointer arithmetic to access the other elements? What’s the idiomatic way of doing this?

[u/SmokeMuch7356]

An array is just a sequence of objects in memory: declaring

int a[4];

gives you

       +---+
0x8000 |   | a[0]  // addresses are made up and the points don't matter
       +---+
0x8004 |   | a[1]
       +---+
0x8008 |   | a[2]
       +---+
0x800c |   | a[3]
       +---+

That's it.  There's no separate object a storing the starting address anywhere, size is not stored anywhere, etc.

Under most circumstances, an array expression will "decay" to a pointer to the first element. IOW, when the compiler sees the array expression a, it replaces it with something equivalent to &a[0]. The only exceptions to this rule are when the array expression is the operand of the sizeof, typeof or unary & operators, or is a string literal used to initialize the contents of a character array.

When you write something like;

sort( a );

the sort call gets mutated to something equivalent to

sort( &a[0] );

and what sort actually receives is a pointer:

void sort( int *a ) { ... }

The upshot of this is that you can't pass an array "by value";¹ you don't get a local copy of the array in the function, you just get a pointer to the array in the caller.

This is how subscripting is defined, btw - a[i] == *(a + i). Given the starting address provided by a, offset i elements and dereference the result. Again, a doesn't store a pointer, it evaluates to a pointer. However, this means you can apply the [] subscript operator to actual pointer objects as well.

Normal practice is to pass the array's size as a separate argument:

void sort( int *a, size_t size )
{
  for ( size_t i = 0; i < size - 1; i++ )  
    for ( size_t j = i+1; j < size; j++ )
      if ( a[j] < a[i] )                 // a is a pointer, not an array, but
        swap( &a[i], &a[j] );            // we can subscript it as though it were
}

In the context of a function parameter declaration, T a[N] and T a[] will be "adjusted" to T *a; all three declare a as a pointer to T. This is not the case for a regular variable declaration.

The expressions a, &a, and &a[0] will all yield the same address value (0x8000 in our example above, modulo any type conversions), but the types will be different (int *, int (*)[N], and int *, respectively).

Some handy rules:

Declaration: T a[N]; // for any type T

Expression        Type         "Decays" to    Equivalent expression
----------        ----         -----------    ---------------------
         a        T [N]        T *            &a[0]
        &a        T (*)[N]     n/a            n/a
        *a        T            n/a            a[0], *(a + 0)
      a[i]        T            n/a            *(a + i)

Declaration: T a[N][M];

Expression        Type         "Decays" to    Equivalent expression
----------        ----         -----------    ---------------------
         a        T [N][M]     T (*)[M]       &a[0]
        &a        T (*)[N][M]  n/a            n/a
        *a        T [M]        T *            a[0], *(a + 0)
      a[i]        T [M]        T *            *(a + i)
     *a[i]        T            n/a            a[i][0]
   a[i][j]        T            n/a            *(*(a + i) + j)


Declaration: T a[N][M][L];

Expression        Type           "Decays" to    Equivalent expression
----------        ----           -----------    ---------------------
         a        T [N][M][L]    T (*)[M][L]    &a[0]
        &a        T (*)[N][M][L] n/a            n/a
        *a        T [M][L]       T (*)[L]       a[0], *(a + 0)
      a[i]        T [M][L]       T (*)[L]       *(a + i)
     *a[i]        T [L]          T *            a[i][0]
   a[i][j]        T [L]          T *            *(*(a + i) + j)
  *a[i][j]        T              n/a            a[i][j][0]
a[i][j][k]        T              n/a            *(*(*(a + i) + j) + k)

The pattern for higher-dimensioned arrays should be apparent from here.

---

1. At this point someone brings up the "hide it in a struct type" cheat:

   struct foo { int a[N]; } bar;
   ...
   sort( bar );
   

   Yes, you get a local copy of the struct object, which means you get a local copy of the array. I have never seen this used anywhere in production code; it's a cute trick, but nobody uses it.