Saturday, December 4, 2010

Passing Arrays as Arguments in C++

In C++ and other programming languages there is the concept of Arrays.
One of the things you might want to do with arrays is pass them to another function so that that function can read the data in the array.

The simplest thing you might think of to accomplish this task might be:

void foo(char* a) {
cout << a[0] << endl; // prints 0
cout << sizeof(a) << endl; // prints 4
}

int main() {
char my_array[128] = {0};
foo(my_array);
return 0;
}


And this does work. What its doing here is passing the pointer to first element in 'my_array' to the function 'foo', and 'foo' uses it as a normal char*.


The problem with this approach is if you want to specify that you want an array of a certain size as the parameter to the function. Since we're treating the array as a pointer, there is no hint to the programmer of the size needed for the array.

There is a feature that originated in C which lets us specify a size parameter, and it looks like this:

void foo(char a[128]) {
cout << a[0] << endl; // prints 0
cout << sizeof(a) << endl; // prints 4
}

int main() {
char my_array[128] = {0};
foo(my_array);
return 0;
}


Now this method is pretty evil in C++ (although in C I guess its more justifiable since it doesn't support the better way which i will explain later).

Now in the function 'foo' you are hinting to the programmer that you want an array with 128 elements, but guess what happens if you give it an array of 10 elements?
Nothing happens, its perfectly fine accepting that.

What happens if you pass it char* instead of an array of char?
Nothing happens, its perfectly fine accepting that.

Also notice what this function prints out. It prints out '4' for sizeof(a)!?

Any experienced coder will know that sizeof(some_array) will be the size of one element times the number of elements. So why is it giving us '4' instead of '128'?

Well it turns out that this feature is equivalent to the first method we used, that is it is as if we're passing a "char*", not an array by reference (as we may have thought).

So once we realize that, it all makes sense, sizeof(char*) on a 32bit system is '4', so that's how we got that number.

For these reasons this approach is what I would call 'evil'. You would expect it to behave a certain way, but it doesn't.

There is a special form of the above C-feature that looks like this:

void foo(char a[]) {
cout << a[0] << endl; // prints 0
cout << sizeof(a) << endl; // prints 4
}

int main() {
char my_array[128] = {0};
foo(my_array);
return 0;
}


This time in the function 'foo' we didn't specify a size of the array.
I don't think there's any reason to use this form as opposed to 'char* a' since they both behave the exact same way. And this time you're not even hinting to the programmer how big you want the array, so its kind-of pointless to have this notation.
'char a[]' might look cool though compared to just using 'char* a', so maybe that's why someone might want to use it. Although i would just recommend using 'char* a' since its more commonly seen (and therefor easier to read imo).


Now that we learned all these bad ways to pass arrays in C++, lets look at a good way.
Passing an array by reference! (Before we were just using different forms of passing a char*, but this time we will pass the array by reference and the compiler will understand that it is array).

It looks like this:

void foo(char (&a)[128]) {
cout << a[0] << endl; // prints 0
cout << sizeof(a) << endl; // prints 128
}

int main() {
char my_array[128] = {0};
foo(my_array);
return 0;
}


Aha! Finally the sizeof(a) is printing out 128 (what we expected it to).
Now 'a' is behaving like an array instead of 'char*' and that is what we wanted.

Now guess what happens if we try to pass an array of 10 elements to function 'foo'?
We get a compiler error! The compiler knows that an array of 10 elements is not an array of 128 elements, so it gives us an error.

Now guess what happens if we try to pass a char* to the function 'foo'?
We get a compiler error! The compiler knows that a char* is not the same as an array of 128 elements, so it gives use an error.

The compiler errors are useful in order to prevent bugs by people who mistakenly are passing arrays of incorrect size to the function.
In another article I will explain ways to circumvent such compiler errors when you 'know' for sure that the pointer/array you're passing is suitable for the function 'foo' but may not have the same type (such as an array of 1000 elements, whereas the function foo will only accept an array of 128 elements).



We have learned how to pass arrays using pointers and references (which means that any data of the array 'a' that was modified in function 'foo' modifies the data in 'my_array'), now we will learn how to pass an array by value (which means that a copy of the array data will be transferred via the stack to function 'foo', so that modifications to 'a' will not effect 'my_array').

Now here's the funny part about this, you can't do it! At least there's no fancy parameter declaration that lets you do this.

There are various workarounds for this problem, and one of them is to create a struct which will act as the array, and then pass the array as that struct on the stack.

For example:

struct temp_struct {
char a[128];
};
C_ASSERT(sizeof(temp_struct)==sizeof(char)*128);

void foo(temp_struct t) {
char (&a)[128] = t.a; // reference to the array t.a
cout << a[0] << endl; // prints 0
cout << sizeof(a) << endl; // prints 128
}

int main() {
char my_array[128] = {0};
foo((temp_struct&)my_array);
return 0;
}


Notice what we did here. We created a struct 'temp_struct' which holds only a single array of the size we're passing. (I will explain what the C_ASSERT does in a bit).
Then we made foo() take as a parameter the 'temp_struct' that we defined earlier.

In the first line of foo's body, we create a reference to the first element inside the foo struct. Then we use this array reference like normally.

Back in the function main(), we need to typecase my_array as a reference of type temp_struct. Basically what we're saying to the compiler is that this array should be treated as if it were a temp_struct, without doing any conversion of the data.
Now the last thing is, since the compiler thinks my_array is a temp_struct, it will copy over the array on the stack (like it would do for any other struct that was passed by value). So with that we have completed our goal.

C_ASSERT is a compile-time assert, and is useful for things like making sure structs you've declared are the size you expected them to be.
The C_ASSERT in the above example is added just to make sure the compiler is generating the struct the same exact size as the array we're dealing with.
If the compiler didn't make the struct the same size, then we would get a compiler error.
I think that a compiler will never end up breaking that C_ASSERT. But I don't know the full c++ standard well enough to guarantee that will never happen, so that's why I add the check in the first place.

Anyways hopefully this article was informative, and by now you should know how to pass an array by treating it as pointer, pass an array by reference, and pass an array by value.

2 comments:

  1. Just my thoughts. This is the limitation of the language. As it's a low-level one it shouldn't implement a complex mechanics under the simple syntax like python or C#. Basically if you define a variable in a function block it's memory should be allocated at the beginning of the function and if an initialization arguments were given they should be copied at the newly created memory location, the memory should be erased when the function returns. This is commonly implemented by using the stack. Example:

    This C++ line:

    unsigned __int32 iData(0);

    Will be translated into this instruction (illustrated into x86 architecture):

    sub esp, 4 ; allocates 4 bytes on the stack for the variable 'iData'
    mov [esp], 0 ; copy 0 to 'iData'

    In this logic arrays should be treated the same way. Example:

    unsigned __int32 iArray[5] = {0, 9, 8, 6, 7}; //Line in C++ - declaring an array of 5 elements with the values 0, 9, 8, 6 and 7

    This should be translated to:

    sub esp, 20 ; allocates 5 * 4 bytes on the stack for the elements in the array 'iArray[5]'

    mov [esp], 0 ; copy 0 to 'iArray[0]'

    mov [esp+ 4], 9 ; copy 9 to 'iArray[1]'

    mov [esp+ 8], 8 ; copy 8 to 'iArray[2]'

    mov [esp+ 12], 6 ; copy 6 to 'iArray[3]'

    mov [esp+ 16], 7 ; copy 7 to 'iArray[4]'

    This should be the RIGHT way of doing it so but instead a static memory will be allocated and just it's pointer will be stored in the stack like this:

    sub esp, 4 ; allocates 4 bytes on the stack for the array POINTER

    mov [esp], [*static array pointer*] ; store the memory location of the array in 'iArray[5]'

    So actually the upper line of code in C++ is equivalent to:

    unsigned __int32 *iArray = {0, 9, 8, 6, 7};

    It's really confusing. You must note that if an structure is created in initialized in 'C' style the memory for it will be allocated on the stack & the upper assignments will be made, instead of permanently allocating it's space for the whole process life-time. This really waste space and also shows the limitations of the language.

    ReplyDelete
    Replies
    1. Also if you write just:

      unsigned __int32 iArray[];

      Without the initialization list an stack memory will be allocated.

      I have also explained some solutions of this problem here (my ideas of an language improvement) - http://stackoverflow.com/questions/19617321/c-native-arrays

      Delete