Чтобы ответить на этот вопрос, мы должны сначала прояснить некоторые концепции. Что такое массив и как его использовать? А какой в вопрос код, если не массив?
Что такое массив?
Формальное определение массива можно найти в стандарте 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 может быть удобным и быстрым в использовании для временных массивов, он не является универсальной заменой рассматриваемой таблицы поиска.
Чтобы действительно динамически распределить многомерный массив, чтобы он получил выделенную продолжительность хранения, мы должны использовать _42 _ / _ 43 _ / _ 44_. Ниже я приведу один пример.
В современном 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;
}
Теперь это - одна непонятная неразбериха "трехзвездочного программирования". И даже не говоря о четырех измерениях ...
Полный код версии, использующей настоящие 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;
}
person
Lundin
schedule
07.02.2017
