C / C++ Внутренние Интерфейсы Многомерных Массивов

Question

У меня есть вопрос о том, как C / C++ внутренне хранит многомерные массивы, объявленные с использованием нотации foo[m][n], Я не ставлю под сомнение чистые указатели на указатели и т. Д.... Я спрашиваю по причинам скорости...

Поправьте меня, если я ошибаюсь, но синтаксически foo это массив указателей, которые сами указывают на массив

int foo[5][4]
*(foo + i)           // returns a memory address
*( *(foo + i) + j)    // returns an int

Я слышал из многих мест, что компилятор C / C++ конвертирует foo[m][n] за одномерный массив за кулисами (вычисление требуемого одномерного индекса с i * width + j). Однако если бы это было правдой, то следующее

*(foo + 1)          // should return element foo[0][1]

Таким образом, мой вопрос: правда ли, что foo[m][n] (всегда?) хранится в памяти как плоский одномерный массив?? Если так, то почему вышеуказанный код работает так, как показано.

Answer 1

Да, C/C++ хранит многомерный (прямоугольный) массив как непрерывную область памяти. Но ваш синтаксис неверен. Чтобы изменить элемент foo[0][1], следующий код будет работать:

*((int *)foo+1)=5;

Явное приведение необходимо, потому что foo+1, такой же как &foo[1] что совсем не то же самое, что foo[0][1], *(foo+1) указатель на пятый элемент в плоской области памяти Другими словами, *(foo+1) в основном foo[1] а также **(foo+1) является foo[1][0], Вот как распределяется память для вашего двухмерного массива:

Answer 2

Двумерный массив:

int foo[5][4];

это не что иное, как массив массивов:

typedef int row[4];   /* type "row" is an array of 4 ints */
row foo[5];           /* the object "foo" is an array of 5 rows */

Здесь нет указателей, явных или неявных.

Массивы не указатели. Указатели не являются массивами.

Что часто вызывает путаницу, так это то, что выражение массива в большинстве случаев неявно преобразуется в указатель на его первый элемент. (И отдельное правило гласит, что то, что выглядит как объявление параметра массива, на самом деле является объявлением указателя, но в этом примере это не применимо.) Объект массива - это объект массива; объявление такого объекта не создает никаких объектов указателя. Ссылка на объект массива может создать значение указателя (адрес первого элемента массива), но в памяти нет объекта указателя.

Объект массива foo хранится в памяти как 5 смежных элементов, где каждый элемент представляет собой массив из 4 смежных элементов int элементы; следовательно, все это хранится как 20 смежных int объекты.

Оператор индексирования определяется в терминах арифметики указателей; x[y] эквивалентно *(x + y), Обычно левый операнд будет либо выражением указателя, либо выражением массива; если это выражение массива, массив неявно преобразуется в указатель.

Так foo[x][y] эквивалентно *(foo[x] + y) что в свою очередь эквивалентно *(*(foo + x) + y), (Обратите внимание, что никакие приведения не нужны.) К счастью, вам не нужно так писать, и foo[x][y] это намного легче понять.

Обратите внимание, что вы можете создать структуру данных, к которой можно получить доступ с foo[x][y] синтаксис, но где foo на самом деле это указатель на указатель на int. (В этом случае префикс каждого [] оператор уже является выражением указателя и не нуждается в преобразовании.) Но для этого вам нужно объявить foo как указатель на указатель на int:

int **foo;

а затем выделить и инициализировать всю необходимую память. Это более гибкий, чем int foo[5][4], поскольку вы можете определить количество строк и размер (или даже существование) каждой строки динамически.

Раздел 6 FAQ по comp.lang.c объясняет это очень хорошо.

РЕДАКТИРОВАТЬ:

В ответ на комментарий Арракиса важно помнить о различии между типом и представлением.

Например, эти два типа:

struct pair { int x; int y;};
typedef int arr2[2];

очень вероятно, имеют одинаковое представление в памяти (два последовательных int объекты), но синтаксис для доступа к элементам совсем другой.

Аналогично, типы int[5][4] а также int[20] имеют одинаковую разметку памяти (20 последовательных int объекты), но синтаксис для доступа к элементам отличается.

Вы можете получить доступ foo[2][2] как ((int*)foo)[10] (обработка 2-мерного массива, как если бы он был 1-мерным массивом). И иногда это полезно, но, строго говоря, поведение не определено. Вероятно, вам это сойдет с рук, потому что большинство реализаций C не выполняют проверку границ массива. С другой стороны, оптимизирующие компиляторы могут предполагать, что поведение вашего кода определено, и генерировать произвольный код, если это не так.

Answer 3

C-массивы - даже многомерные - являются смежными, то есть массив типа int [4][5] структурно эквивалентен массиву типа int [20],

Однако эти типы по-прежнему несовместимы в соответствии с семантикой языка C. В частности, следующий код нарушает стандарт C:

int foo[4][5] = { { 0 } };
int *p = &foo[0][0];
int x = p[12]; // undefined behaviour - can't treat foo as int [20]

Причина этого заключается в том, что стандарт C (вероятно, намеренно) сформулирован таким образом, что делает возможными реализации проверки границ: p происходит от foo[0], который имеет тип int [5]действительные индексы должны быть в диапазоне 0..5 (Соотв. 0..4 если вы действительно получаете доступ к элементу).

Многие другие языки программирования (Java, Perl, Python, JavaScript, ...) используют зубчатые массивы для реализации многомерных массивов. Это также возможно в C с помощью массива указателей:

int *bar[4] = { NULL };
bar[0] = (int [3]){ 0 };
bar[1] = (int [5]){ 1, 2, 3, 4 };
int y = bar[1][2]; // y == 3

Однако зубчатые массивы не являются смежными, и указываемые массивы не обязательно должны быть одинакового размера.

Из-за неявного преобразования выражений массива в выражения указателя индексация неровных и не зубчатых массивов выглядит идентично, но фактические вычисления адреса будут совсем другими:

&foo[1]    == (int (*)[5])((char *)&foo + 1 * sizeof (int [5]))

&bar[1]    == (int **)((char *)&bar + 1 * sizeof (int *))

&foo[1][2] == (int *)((char *)&foo[1] + 2 * sizeof (int))
           == (int *)((char *)&foo + 1 * sizeof (int [5]) + 2 * sizeof (int))

&bar[1][2] == (int *)((char *)bar[1] + 2 * sizeof (int)) // no & before bar!
           == (int *)((char *)*(int **)((char *)&bar + 1 * sizeof (int *))
                      + 2 * sizeof (int))

Answer 4

int foo[5][4];

foo не является массивом указателей; это массив массивов. Ниже изображение поможет.