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

Цель этого вопроса - дать ссылку на то, как правильно распределить многомерные массивы в C. Это тема, которую часто неправильно понимают и плохо объясняют даже в некоторых книгах программирования C. Поэтому даже опытные программисты 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

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

Ответы

Ответ 1

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

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

Формальное определение массива содержится в стандарте 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;
}

Ответ 2

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

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

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

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

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

Это предложение противоречиво (неверно, какие спецификации?)...

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