Правильное распределение многомерных массивов

objective этого вопроса – дать ссылку на то, как правильно распределить многомерные массивы в C. Это тема, которую часто неправильно понимают и плохо объясняют даже в некоторых книгах программирования C. Поэтому даже опытные программисты C стараются понять это правильно.


Я учился у своего преподавателя / книги / учебника по программированию, что правильный способ динамического выделения многомерного массива – использование указателей на указатели.

Однако несколько высокопоставленных пользователей на SO теперь говорят мне, что это неправильная и плохая практика. Говорят, что указатели на указатели не являются массивами, что я фактически не выделяю массивы и что мой код бесполезно медленный.

Вот как меня научили выделять многомерные массивы:

#include  #include  #include  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 

Этот код работает просто отлично! Как это может быть неправильно?

Чтобы ответить на вопрос, мы должны сначала прояснить некоторые концепции. Что такое массив и как его можно использовать? И каков код в вопросе, если не массив?


Что такое массив?

Формальное определение массива найдено в стандарте C, ISO 9899: 2011 6.2.5 / 20 Types .

Тип массива описывает смежно выделенный непустой набор объектов с конкретным типом объекта-члена, называемый типом элемента.

На простом английском языке массив представляет собой набор элементов одного и того же типа, выделенных смежно, в соседних ячейках памяти.

Например, массив из 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 работают. Они предназначены для работы с массивами, выделенными смежно. Поэтому, если у вас multidimensional array, вы можете эффективно его искать и сортировать с помощью bsearch и qsort , сохраняя при этом bsearch реализации двоичного поиска и быстрого сортировки себя и тем самым повторно изобретая колесо для каждого проекта.

Все вышеупомянутые консистенции между массивами и другими типами - это очень хорошая вещь, которую мы хотим использовать, особенно при создании общего программирования.


Что такое указатель на указатель, если не массив?

Теперь вернемся к коду в вопросе, который использовал другой синтаксис с указателем на указатель. В этом нет ничего загадочного. Это указатель на указатель на тип, не более того. Это не массив. Это не 2D-массив. Строго говоря, он не может использоваться для указания массива и не может использоваться для указания на 2D-массив.

Однако указатель на указатель можно использовать для указания на первый элемент массива указателей вместо того, чтобы указывать на массив как целое. И именно так он используется в вопросе - как способ «эмулировать» указатель на массив. В этом вопросе он используется для указания массива из 2 указателей. И затем каждый из двух указателей используется для указания массива из 3 целых чисел.

Это называется поисковой таблицей, которая является своего рода абстрактным типом данных (ADT), который отличается от концепции простых уровней простых массивов. Основное различие заключается в том, как распределяется справочная таблица:

 +------------+ | | | 0x12340000 | | | +------------+ | | v +------------+ +-------+-------+-------+ | | | | | | | 0x22223333 |---->| 1 | 2 | 3 | | | | | | | +------------+ +-------+-------+-------+ | | | 0xAAAABBBB |--+ | | | +------------+ | | | +-------+-------+-------+ | | | | | +->| 1 | 2 | 3 | | | | | +-------+-------+-------+ 

32-разрядные адреса в этом примере составлены. Поле 0x12340000 представляет указатель на указатель. Он содержит адрес 0x12340000 для первого элемента в массиве указателей. Каждый указатель в этом массиве, в свою очередь, содержит адрес, указывающий на первый элемент в массиве целых чисел.

И вот здесь проблемы начинаются.


Проблемы с версией справочной таблицы

Смотровая таблица разбросана по всей памяти кучи. Это не смежно распределенная память в смежных ячейках, потому что каждый вызов в malloc дает новую область памяти, не обязательно расположенную рядом с остальными. Это, в свою очередь, дает нам массу проблем:

  • Мы не можем использовать арифметику указателя, как и ожидалось. Хотя мы можем использовать форму арифметики указателя для индексации и доступа к элементам в таблице поиска, мы не сможем использовать указатели на массивы.

  • Мы не можем использовать оператор sizeof. Используемый в указателе на указатель, это даст нам размер указателя на указатель. Используемый для первого пункта, на который указывает, это даст нам размер указателя. Ни один из них не является размером массива.

  • Мы не можем использовать стандартные библиотечные функции, за исключением типа массива ( memcpy , memset , strcpy , bsearch , qsort и т. Д.). Все такие функции предполагают получение массивов в качестве входных данных, причем данные распределяются смежно. Вызов их с помощью нашей таблицы поиска в качестве параметра приведет к неопределенным ошибкам поведения, таким как сбои в работе программы.

  • Повторные вызовы malloc для выделения нескольких сегментов приводят к fragmentации кучи, что, в свою очередь, приводит к плохому использованию ОЗУ.

  • Поскольку память разбросана, процессор не может использовать кэш-память при повторении через справочную таблицу. Для эффективного использования кэша данных требуется непрерывный fragment памяти, который повторяется сверху вниз. Это означает, что поисковая таблица по дизайну имеет значительно более медленное время доступа, чем реальный multidimensional array.

  • Для каждого вызова функции malloc () код библиотеки, управляющий кучей, должен вычислять, где есть свободное пространство. Точно так же для каждого вызова free () есть служебный код, который должен быть выполнен. Поэтому, как можно меньше звонков на эти функции, предпочтительнее, ради производительности.


Неужели справочные таблицы плохие?

Как мы видим, существует множество проблем с поисковыми таблицами на основе указателей. Но они не все плохо, это инструмент, как любой другой. Он просто должен использоваться для правильной цели. Если вы ищете multidimensional array, который следует использовать в качестве массива, то выглядящие таблицы, безусловно, являются неправильным инструментом. Но они могут использоваться для других целей.

Таблица поиска - это правильный выбор, когда вам нужно, чтобы все размеры имели полностью переменные размеры, индивидуально. Такой контейнер может быть полезен, например, для создания списка строк C. Поэтому часто бывает оправданным использовать вышеупомянутую скорость выполнения, чтобы сохранить память.

Кроме того, таблица поиска имеет то преимущество, что вы можете повторно распределить части таблицы во время выполнения без необходимости перераспределения целого многомерного массива. Если это то, что нужно делать часто, справочная таблица может даже превосходить multidimensional array с точки зрения скорости выполнения. Например, аналогичные справочные таблицы могут использоваться при реализации скошенной хеш-таблицы.


Как правильно распределить multidimensional array динамически?

Простейшей формой в современном C является простое использование массива переменной длины (VLA). int array[x][y]; где x и y - переменные заданные значения во время выполнения, объявление предшествующего массива. Тем не менее, VLA имеют локальную область действия и не сохраняются на протяжении всей программы - у них есть автоматическая продолжительность хранения. Таким образом, хотя VLA могут быть удобными и быстрыми в использовании для временных массивов, это не является универсальной заменой справочной таблице в вопросе.

Чтобы действительно распределить multidimensional array динамически, так что он получает выделенную длительность хранения , мы должны использовать 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 

Теперь это один непонятный беспорядок «трехзвездочного программирования». И позволяет даже не рассматривать 4 измерения ...


Полный код версии с использованием реальных 2D-массивов

 #include  #include  #include  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 

C не имеют многомерных массивов. Но у вас могут быть массивы массивов (или других агрегатов) и массивы указателей.

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

Мы не можем предложить какой-либо абстрактный тип данных, потому что это зависит от текста вашей домашней работы, чего у нас нет. Вам нужно создать свой абстрактный тип данных (на листе бумаги), а затем реализовать его.

После того, как вы указали (на бумаге или на плате) все операции, необходимые для вашего ADT, их реализация проста.

Этот код работает просто отлично! Как это может быть неправильно?

Это предложение непоследовательно (неправильно по каким спецификациям?) …

Я рекомендую скомпилировать все предупреждения и информацию об отладке (например, с помощью gcc -Wall -Wextra -g с GCC ), чтобы улучшить код до тех пор, пока вы не получите никаких предупреждений, чтобы использовать отладчик gdb (чтобы понять, что происходит в вашей программе) и другие инструменты, такие как valgrind .

Давайте будем гением компьютера.