[Boost-users] contiguous Boost.Multimap revisited

Subject: [Boost-users] contiguous Boost.Multimap revisited
From: anony (janezz55_at_[hidden])
Date: 2010-06-20 09:24:55

>From a post by Mathias Gaunard:

> Who claimed such a thing?
> An array is always stored contiguously; an array of arrays is no
> different in that regard.

I need to direct you to the controversy that my old post has caused:

[Boost-users] Boost.Range fancify please

In any case, Patrick Hogan claimed an array of arrays may not be stored
contiguously (i.e. that it is not required by the standard):

anony wrote:
> What I see in
>
> vertices[][3] = { ... };
>
> is an a array object of array objects. Nowhere in the standard did I
> ever see multidimensional arrays specifically mentioned.
It's in:
5.3.4 New section 5 (which notes: the type of new int[i][10] is int
(*)[10]), and 6
8.3.4 Arrays sections 2, 3, 4, 7, and 8
8.5.1 aggregates sections 10 and 11 on array initialization,
13.1 Overloadable Declarations section 3 which notes that Parameter
declarations that differ only in a pointer * versus an array [] are
equivalent. That is, the array declaration is adjusted to become a
pointer declaration (8.3.5)
20.5.6.4 Array modifications, Table 39.

and on and on in many more places, all consistently saying the for a
multidimensional array, all but the final dimensions are pointers.

> Since the
> elements of this array are arrays, these arrays must be contiguous in
> memory.
What you're missing, is that it's required in the standard (8.3.4
section 6), to consider an array as a pointer to it's first element, so
an array of arrays is an array of pointers (well explained in 8.3.4
section 7 and 8). For example in gcc, this code:

#include <iostream>

int main()
{
    int array[2][2];

    std::cout << std::hex << array[0] << std::endl;
    std::cout << array[1] << std::endl;
    std::cout << &array[0][0] << std::endl;
    std::cout << &array[1][0] << std::endl;
    std::cout << std::dec << sizeof(array[1]) << std::endl;
    std::cout << sizeof(array[1][1]) << std::endl;

}

prints out
0xbff3519c
0xbff351a4
0xbff3519c
0xbff351a4
8
4

on one particular run, showing that array[0], and array[1] are just the
addresses of their first elements, their elements are 8 byte pointers to
4 byte ints. The pointers are the elements of the array, and as you
pointed out, have to be contiguous. There's nothing in the standard
that requires that the rows pointed to have to be contiguous, because
they aren't the elements of the array, the pointers to them are. So,
the contents of the rows have to be contiguous, and the pointers to the
rows have to be contiguous, but the rows themselves don't have to be.
There's nothing in the standard that requires it. You get away with it
with one set of data on one compiler, because it's easy for the compiler
with this data to allocate memory for all the rows at once, but nothing
guarantees that it will work. Liking it, or wishing that it was the way
the spec has it, doesn't help. You're relying on undefined behavior.

Patrick