Why is flattening a multidimensional array in C illegal? [duplicate]

Question

My book (Pointers on C by Kenneth Reek) says that the following is illegal although it works fine.

  int arr[5][5];
  int *p=&arr[2][2];
  p=p+3; // As array is stored in row major form I think this 
         //should make p point to arr[3][0]

The book says leaving one row to the next row is illegal. But I cannot understand why.

Answer 1

The reason that the book says it's illegal is because pointer arithmetic is guaranteed to work only on pointers to elements in the same array, or one past the end.

arr is an array of 5 elements, in which each element is an array of 5 integers. Thus, theoretically, if you want to have pointers to array elements in arr[i], you can only do pointer arithmetic that yields pointers in the range &arr[i][0..4] or arr[i]+5 keeping i constant.

For example, imagine arr was a one dimensional of 5 integers. Then a pointer p could only point to each of &arr[0..4] or arr+5 (one past the end). This is what happens with multi-dimensional arrays as well.

With int arr[5][5];, you can only do pointer arithmetic such that you always have a pointer that is in the range &arr[i][0..4] or arr[i]+5 - that's what the rules say. It just may be confusing because these are arrays inside arrays, but the rule is the same no matter what. Conceptually, arr[0] and arr[1] are different arrays, and even though you know they are contiguous in memory, it is illegal to do pointer arithmetic between elements of arr[0] and arr[1]. Remember that conceptually, each element in arr[i] is a different array.

In your example, however, p+3 will point one past the end of arr[2][2], so it looks to me like it is valid nonetheless. It's a poor choice of an example because it will make p point precisely to one past the end, making it still valid. Had the author chosen p+4, the example would be correct.

Either way, I have never had any problems with flattening multidimensional arrays in C using similar methods.

Also see this question, it has got other useful information: One-dimensional access to a multidimensional array: well-defined C?

Answer 2

I gelled on this for awhile, and I'll try my best to explain where I think he's coming from, though without reading the book, it will be at-best-conjecture.

First, technically, the increment you propose (or he proposed) isn't illegal; dereferencing it is. The standard allows you to advance a pointer to one-past the last element of the array sequence from which it is being sourced for valuation, but not for dereference. Change it to p = p + 4 and both are illegal.

That aside, the linear footprint of the array not withstanding, ar[2] has a type, and it is int[5]. If you don't believe that, consider the following, all of which is correctly typed:

int ar[5][5];
int (*sub)[5] = ar+2;   // sub points to 3rd row
int *col = *sub + 2;    // col points to 3rd column of third row.
int *p = col + 3;       // p points to 5th colum of third row.

Whether this lands on ar[3][0] isn't relevant You're exceeding the declared magnitude of the dimension participating in the pointer-math. The result cannot legally be dereferenced, and were it larger than a 3-offset, nor could it be even legally evaluated.

Remember, the array being addressed is ar[2]; not just ar, and said-same is declared to be size=5. That it is buttressed up against two other arrays of the same ilk isn't relevant to the addressing currently being done. I believe Christoph's answer to the question proposed as a duplicate should have been the one selected for outright-solution. In particular, the reference to C99 §6.5.6, p8 which, though wordy, appears below with:

When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integer expression. In other words, if the expression P points to the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the value n) point to, respectively, the i+n-th and i−n-th elements of the array object, provided they exist. Moreover, if the expression P points to the last element of an array object, the expression (P)+1 points one past the last element of the array object, and if the expression Q points one past the last element of an array object, the expression (Q)-1 points to the last element of the array object. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined. If the result points one past the last element of the array object, it shall not be used as the operand of a unary * operator that is evaluated.

Sorry for the spam, but the bolded highlights are what I believe is relevant to your question. By addressing as you are, you're leaving the array being addressed, and as such walking into UB. in short, it works (usually), but is isn't legal.