Правильное размещение многомерных массивов
Цель этого вопроса - дать справку о том, как правильно распределить многомерные массивы динамически в Си. Эта тема часто неправильно понимается и плохо объясняется даже в некоторых книгах по программированию на Си. Поэтому даже опытные программисты на C пытаются понять это правильно.
Из моего учителя / книги / учебника по программированию меня учили, что правильным способом динамического размещения многомерного массива является использование указателей на указатели.
Тем не менее, несколько пользователей с высокими репутациями на SO теперь говорят мне, что это неправильно и плохая практика. Они говорят, что указатели на указатели не являются массивами, что я на самом деле не выделяю массивы и что мой код излишне медленен.
Вот как меня учили распределять многомерные массивы:
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
int** arr_alloc (size_t x, size_t y)
{
int** pp = malloc(sizeof(*pp) * x);
assert(pp != NULL);
for(size_t i=0; i<x; i++)
{
pp[i] = malloc(sizeof(**pp) * y);
assert(pp[i] != NULL);
}
return pp;
}
int** arr_fill (int** pp, size_t x, size_t y)
{
for(size_t i=0; i<x; i++)
{
for(size_t j=0; j<y; j++)
{
pp[i][j] = (int)j + 1;
}
}
return pp;
}
void arr_print (int** pp, size_t x, size_t y)
{
for(size_t i=0; i<x; i++)
{
for(size_t j=0; j<y; j++)
{
printf("%d ", pp[i][j]);
}
printf("\n");
}
}
void arr_free (int** pp, size_t x, size_t y)
{
(void) y;
for(size_t i=0; i<x; i++)
{
free(pp[i]);
pp[i] = NULL;
}
free(pp);
pp = NULL;
}
int main (void)
{
size_t x = 2;
size_t y = 3;
int** pp;
pp = arr_alloc(x, y);
pp = arr_fill(pp, x, y);
arr_print(pp, x, y);
arr_free(pp, x, y);
return 0;
}
Выход
1 2 3
1 2 3
Этот код работает просто отлично! Как это может быть неправильно?
2 ответа
Чтобы ответить на этот вопрос, мы должны сначала прояснить некоторые понятия. Что такое массив и как его можно использовать? А что за код в вопросе, если не массив?
Что такое массив?
Формальное определение массива содержится в стандарте C, типах ISO 9899:2011 6.2.5/20.
Тип массива описывает непрерывно распределенный непустой набор объектов с конкретным типом объекта-члена, который называется типом элемента.
Говоря простым языком, массив - это набор элементов одного и того же типа, размещенных непрерывно в соседних ячейках памяти.
Например, массив из 3 целых int arr[3] = {1,2,3}; будет выделяться в памяти, как это:
+-------+-------+-------+
| | | |
| 1 | 2 | 3 |
| | | |
+-------+-------+-------+
Так как насчет формального определения многомерного массива? На самом деле, это то же самое определение, что и приведенное выше. Применяется рекурсивно.
Если бы мы выделяли 2D массив, int arr[2][3] = { {1,2,3}, {1,2,3} }; он будет выделяться в памяти следующим образом:
+-------+-------+-------+-------+-------+-------+
| | | | | | |
| 1 | 2 | 3 | 1 | 2 | 3 |
| | | | | | |
+-------+-------+-------+-------+-------+-------+
В этом примере мы имеем массив массивов. Массив, который имеет 2 элемента, каждый из которых представляет собой массив из 3 целых чисел.
Массив является типом, как и любой другой
Массивы в C часто следуют той же системе типов, что и обычные переменные. Как показано выше, вы можете иметь массив массивов, как вы можете иметь массив любого другого типа.
Вы также можете применить ту же арифметику указателей к n-мерным массивам, что и к простым одномерным массивам. С регулярными одномерными массивами применение арифметики указателей должно быть тривиальным:
int arr[3] = {1,2,3};
int* ptr = arr; // integer pointer to the first element
for(size_t i=0; i<3; i++)
{
printf("%d ", *ptr); // print contents
ptr++; // set pointer to point at the next element
}
Это стало возможным благодаря "распаду массива". когда arr был использован внутри выражения, он "распался" в указатель на первый элемент.
Точно так же мы можем использовать ту же самую арифметику указателя, чтобы перебрать массив массивов, используя указатель массива:
int arr[2][3] = { {1,2,3}, {1,2,3} };
int (*ptr)[3] = arr; // int array pointer to the first element, which is an int[3] array
for(size_t i=0; i<2; i++)
{
printf("%d %d %d\n", (*ptr)[0], (*ptr)[1], (*ptr)[2]); // print contents
ptr++; // set pointer to point at the next element
}
Снова произошел распад массива. Переменная arr который был типа int [2][3] распался в указатель на первый элемент. Первый элемент был int [3] и указатель на такой элемент объявлен как int(*)[3] указатель массива.
Понимание указателей массива и распада массива необходимо для работы с многомерными массивами.
Есть еще случаи, когда массивы ведут себя так же, как обычные переменные. sizeof Оператор работает так же для (не VLA) массивов, как для обычных переменных. Примеры для 32-битной системы:
int x; printf("%zu", sizeof(x)); печать 4,int arr[3] = {1,2,3}; printf("%zu", sizeof(arr)); печать 12 (3*4=12)int arr[2][3] = { {1,2,3}, {1,2,3} }; printf("%zu", sizeof(arr)); печать 24 (2*3*4=24)
Как и любой другой тип, массивы могут использоваться с библиотечными функциями и универсальными API. Так как массивы удовлетворяют требованию размещения последовательно, мы можем, например, безопасно скопировать их с memcpy:
int arr_a[3] = {1,2,3};
int arr_b[3];
memcpy(arr_b, arr_a, sizeof(arr_a));
Непрерывное распределение также является причиной, по которой другие подобные стандартные библиотечные функции, такие как memset, strcpy, bsearch а также qsort Работа. Они предназначены для работы с массивами, расположенными непрерывно. Так что если у вас есть многомерный массив, вы можете эффективно искать его и сортировать с bsearch а также qsortизбавляя вас от хлопот, связанных с реализацией бинарного поиска и быстрой сортировкой, и заново изобретая колесо для каждого проекта.
Все вышеперечисленные соответствия между массивами и другими типами - это очень хорошая вещь, которой мы хотим воспользоваться, особенно при выполнении общего программирования.
Что такое указатель на указатель, если не массив?
Теперь вернемся к коду в вопросе, который использовал другой синтаксис с указателем на указатель. В этом нет ничего загадочного. Это указатель на указатель на тип, не более и не менее. Это не массив. Это не 2D массив. Строго говоря, его нельзя использовать для указания на массив, а также для указания на двумерный массив.
Однако указатель на указатель может быть использован для указания на первый элемент массива указателей, вместо того, чтобы указывать на массив в целом. И вот как это используется в вопросе - как способ "эмулировать" указатель массива. В вопросе он используется для указания на массив из 2 указателей. И затем каждый из 2 указателей используется для указания массива из 3 целых чисел.
Это известно как справочная таблица, которая является своего рода абстрактным типом данных (ADT), который отличается от низкоуровневой концепции простых массивов. Основное отличие состоит в том, как размещается справочная таблица:
+------------+
| |
| 0x12340000 |
| |
+------------+
|
|
v
+------------+ +-------+-------+-------+
| | | | | |
| 0x22223333 |---->| 1 | 2 | 3 |
| | | | | |
+------------+ +-------+-------+-------+
| |
| 0xAAAABBBB |--+
| | |
+------------+ |
|
| +-------+-------+-------+
| | | | |
+->| 1 | 2 | 3 |
| | | |
+-------+-------+-------+
32-битные адреса в этом примере составлены. Поле 0x12340000 представляет указатель на указатель. Он содержит адрес 0x12340000 для первого элемента в массиве указателей. Каждый указатель в этом массиве, в свою очередь, содержит адрес, указывающий на первый элемент в массиве целых чисел.
И вот тут начинаются проблемы.
Проблемы с версией справочной таблицы
Справочная таблица разбросана по всей куче памяти. Это не является непрерывно распределенной памятью в соседних ячейках, потому что каждый вызов malloc дает новую область памяти, необязательно расположенную рядом с другими. Это, в свою очередь, дает нам много проблем:
Мы не можем использовать арифметику указателей, как ожидалось. Хотя мы можем использовать форму арифметики с указателями для индексации и доступа к элементам в справочной таблице, мы не можем сделать это с помощью указателей на массивы.
Мы не можем использовать оператор sizeof. При использовании указателя на указатель он дает нам размер указателя на указатель. Применительно к первому элементу, указанному на, он даст нам размер указателя. Ни один из них не является размером массива.
Мы не можем использовать стандартные библиотечные функции, которые исключают тип массива (
memcpy,memset,strcpy,bsearch,qsortи так далее). Все такие функции предполагают получение массивов в качестве входных данных с непрерывным распределением данных. Вызов их с нашей справочной таблицей в качестве параметра может привести к неопределенным ошибкам поведения, таким как сбой программы.Повторные звонки
mallocвыделение нескольких сегментов приводит к фрагментации кучи, что, в свою очередь, приводит к плохому использованию оперативной памяти.Поскольку память разбросана, ЦП не может использовать кеш-память при переборе справочной таблицы. Эффективное использование кэша данных требует непрерывной части памяти, которая перебирается сверху вниз. Это означает, что справочная таблица по своей конструкции имеет значительно более медленное время доступа, чем реальный многомерный массив.
Для каждого вызова malloc() код библиотеки, управляющий кучей, должен вычислять, где есть свободное место. Аналогично для каждого вызова free() существует служебный код, который должен быть выполнен. Следовательно, как можно меньшее количество обращений к этим функциям часто является предпочтительным для повышения производительности.
Являются ли справочные таблицы плохими?
Как мы видим, существует много проблем с поисковыми таблицами на основе указателей. Но они не все плохие, это инструмент, как и любой другой. Это просто нужно использовать для правильной цели. Если вы ищете многомерный массив, который следует использовать в качестве массива, справочные таблицы явно не тот инструмент. Но они могут быть использованы для других целей.
Справочная таблица - это правильный выбор, когда вам нужно, чтобы все размеры имели индивидуально изменяемые размеры. Такой контейнер может быть полезен, например, при создании списка C-строк. Тогда часто оправданно принимать вышеупомянутую потерю производительности скорости выполнения для экономии памяти.
Кроме того, справочная таблица обладает тем преимуществом, что вы можете перераспределять части таблицы во время выполнения без необходимости перераспределять целый многомерный массив. Если это нужно делать часто, справочная таблица может даже превзойти многомерный массив с точки зрения скорости выполнения. Например, аналогичные справочные таблицы могут использоваться при реализации связанной хеш-таблицы.
Как правильно правильно распределить многомерный массив?
Самая простая форма в современном C - просто использовать массив переменной длины (VLA). int array[x][y]; где x а также y переменные с заданными значениями во время выполнения, перед объявлением массива. Однако VLA имеют локальную область действия и не сохраняются на протяжении всей программы - они имеют автоматическую продолжительность хранения. Таким образом, хотя VLA может быть удобным и быстрым в использовании для временных массивов, это не универсальная замена справочной таблицы в вопросе.
Чтобы действительно распределить многомерный массив динамически, чтобы он получал выделенную продолжительность хранения, мы должны использовать malloc/calloc/realloc. Я приведу один пример ниже.
В современном C вы бы использовали указатели массива на VLA. Вы можете использовать такие указатели, даже если в программе нет фактического VLA. Преимущество использования их над равниной type* или void* повышенная безопасность типов. Использование указателя на VLA также позволяет передавать размеры массива в качестве параметров функции с использованием массива, делая его одновременно безопасным как для переменных, так и для типов.
К сожалению, чтобы использовать преимущества наличия указателя на VLA, мы не можем вернуть этот указатель как результат функции. Поэтому, если нам нужно вернуть указатель на массив вызывающей стороне, он должен быть передан как параметр (по причинам, описанным в разделе " Динамический доступ к памяти", работает только внутри функции). Это хорошая практика в C, но делает код немного сложным для чтения. Это будет выглядеть примерно так:
void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
*aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
assert(*aptr != NULL);
}
Хотя этот синтаксис с указателем на указатель массива может показаться немного странным и пугающим, он не становится более сложным, чем этот, даже если мы добавим больше измерений:
void arr_alloc (size_t x, size_t y, size_t z, int(**aptr)[x][y][z])
{
*aptr = malloc( sizeof(int[x][y][z]) ); // allocate a true 3D array
assert(*aptr != NULL);
}
Теперь сравните этот код с кодом для добавления еще одного измерения в версию справочной таблицы:
/* Bad. Don't write code like this! */
int*** arr_alloc (size_t x, size_t y, size_t z)
{
int*** ppp = malloc(sizeof(*ppp) * x);
assert(ppp != NULL);
for(size_t i=0; i<x; i++)
{
ppp[i] = malloc(sizeof(**ppp) * y);
assert(ppp[i] != NULL);
for(size_t j=0; j<y; j++)
{
ppp[i][j] = malloc(sizeof(***ppp) * z);
assert(ppp[i][j] != NULL);
}
}
return ppp;
}
Теперь это один нечитаемый беспорядок "трехзвездного программирования". И давайте даже не будем рассматривать 4 измерения...
Полный код версии с использованием реальных 2D-массивов
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
*aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
assert(*aptr != NULL);
}
void arr_fill (size_t x, size_t y, int array[x][y])
{
for(size_t i=0; i<x; i++)
{
for(size_t j=0; j<y; j++)
{
array[i][j] = (int)j + 1;
}
}
}
void arr_print (size_t x, size_t y, int array[x][y])
{
for(size_t i=0; i<x; i++)
{
for(size_t j=0; j<y; j++)
{
printf("%d ", array[i][j]);
}
printf("\n");
}
}
int main (void)
{
size_t x = 2;
size_t y = 3;
int (*aptr)[x][y];
arr_alloc(x, y, &aptr);
arr_fill(x, y, *aptr);
arr_print(x, y, *aptr);
free(aptr); // free the whole 2D array
return 0;
}
C не имеет многомерных массивов. Но вы можете иметь массивы массивов (или других агрегатов) и массивы указателей.
Возможный подход заключается в рассуждении с некоторым абстрактным типом данных (возможно, с использованием гибких элементов массива, что является одним из приемов реализации, и вы могли бы использовать другие подходы), как в этом ответе.
Мы не можем предложить какой-либо абстрактный тип данных, потому что это зависит от текста вашего домашнего задания, которого у нас нет. Вам нужно спроектировать свой абстрактный тип данных (на листе бумаги), а затем реализовать его.
После того, как вы перечислили (на бумаге или на доске) все операции, необходимые для вашего ADT, их реализация проста.
Этот код работает просто отлично! Как это может быть неправильно?
Это предложение несовместимо (неправильно с какими спецификациями?) ...
Я рекомендую компилировать все предупреждения и отладочную информацию (например, с gcc -Wall -Wextra -g с GCC), чтобы улучшить ваш код, пока вы не получите никаких предупреждений, использовать отладчик gdb (чтобы понять, что происходит в вашей программе) и другие инструменты, такие как valgrind.