Быстрое создание многомерных динамических массивов

Быстрое выделение памяти под многомерные массивы

Рассмотрим выделение памяти под двумерный массив. Типичная реализация, которая используется везде в этом курсе выглядит примерно так

const int M = 100;
const int N = 200;
int **a = NULL;
int i, j;

//Создаём массив указателей
a = (int**) malloc(M * sizeof(int*));
//Каждому элементу из массива указателей присваиваем
//адрес выделенного массива памяти
for (i = 0; i < M; i++) {
	a[i] = (int*) malloc(N * sizeof(int));
}

//Важные действия

//Удаление: сначала удаляем все массивы
for (i = 0; i < M; i++) {
	free(a[i]);
}
//Потом удаляем массив указателей
free(a);

В этом примере сначала выделяется память под массив указателей, потом M раз выделяется память под массивы. Во время удаления массива сначала M раз удаляются массивы, а потом удаляется массив указателей. Операции malloc и free затратные. Кроме того, выделение маленьких кусков памяти приводит к фрагментации памяти, так что последующее выделение памяти становится ещё медленнее.

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

const int M = 100;
const int N = 200;
int **a = NULL;
int i;

a = (int**) malloc(M * sizeof(int*));
a[0] = (int*) malloc(M * N * sizeof(int));
for (i = 1; i < M; i++) {
	a[i] = a[0] + i * N;
}

//Важные действия

free(a[0]);
free(a);

Теперь нам необходимо всего две операции выделения памяти и две операции для освобождения.

У этого подхода есть и ещё одно важное преимущество. Массив a[0] по структуре становится похож на одномерный, так что его можно передавать как одномерный, например, для сортировки. Элементы расположены в нём по рядам, как в двумерном статическом массиве, поэтому без проблем можно его привести к типу указателя на массивы.

Можно пойти ещё дальше и заменить всё одним вызовом malloc: упаковать друг за другом сначала массив указателей, а потом массив массивов.

const int M = 100;
const int N = 200;
int **a = NULL;
int i, j;

a = (int**) malloc(M * sizeof(int*) + N * M * sizeof(int));
a[0] = (int*)(a + M);
for (i = 1; i < M; i++) {
	a[i] = a[0] + i * N;
}

//Важные действия

free(a);

Здесь всего одна операция выделения и одна освобождения.

Для массивов более высокой размерности выделение памяти остаётся очень похожим.

Скорость выполнения соотносится для данных способов выделения памяти как 404:13:12 для массива размером 100 x 200 типа int. Последние два способа выделения памяти, дабы не смущать неокрепшие умы, почти не используются в курсе, но на практике динамически выделять память под многомерные массивы лучше именно таким образом.

Рассмотрим выделение памяти под трёхмерный массив. Трёхмерный массив - массив указателей на указатели, которые ссылаются на массивы указателей, которые ссылаются на массивы объектов заданного типа. Выделение памяти под трёхмерный массив размером M*N*K, соответственно, потребует M + M*N операций выделения памяти и столько же для освобождения.

Первым делом объявим переменные

	const int M = 10;
	const int N = 10;
	const int K = 10;

	int*** a = NULL;
	int* data;
	int** ptrs;
	int i, j, k;

Здесь a - наш будущий трёхмерный массив, data - вспомогательная переменная, которая хранит адрес, по которому начинаются непосредственно данные (белым цветом на рисунке). ptrs - вспомогательная переменная, которая хранит адрес, по которому начинаются массивы указателей (розовый на рисунке).

Для начала выделим память под массив

a = (int***) malloc(M * sizeof(int**) + 
					M*N * sizeof(int*) + 
					M*N*K * sizeof(int));

Затем инициализируем вспомогательные переменные

ptrs = (int**) (a + M);
data = (int*) (a + M + M*N);

Затем надо инициализировать массив указателей на указатели

for (i = 0; i < M; i++) {
	a[i] = ptrs + i*N;
	...
}

Но также нужно инициализировать каждый из массивов указателей

for (i = 0; i < M; i++) {
	a[i] = ptrs + i*N;
	for (j = 0; j < N; j++) {
		a[i][j] = data + j * N*K;			
	}
}

Теперь наш массив принимает вид:

Закрепим

const int M = 10;
const int N = 10;
const int K = 10;

int*** a = NULL;
int* data;
int** ptrs;
int i, j, k, q;

a = (int***) malloc(M * sizeof(int**) +
                    M*N * sizeof(int*) +
                    M*N*K * sizeof(int));

ptrs = (int**) (a + M);
data = (int*) (a + M + M*N);
q = 0;
for (i = 0; i < M; i++) {
    a[i] = ptrs + i*N;
    for (j = 0; j < N; j++) {
        a[i][j] = data + (q++) * N*K;
    }
}

Всё ещё не понятно? – пиши вопросы на ящик