Массив здорового человека

Задача проста: организовать хранение двумерного массива. Во время написания некоторой программы один из моих учеников использовал два разных способа представления двумерного массива в памяти, оба из них не были эффективными, хотя вопрос хранения данных на стеке и в куче уже нами обсуждался. Другой студент, когда я попросил прокомментировать разные способы выделения памяти, испытал затруднения. Получается, что всё бывает не так очевидно, как кажется. А представить визуально и сказать с использованием точных терминов то, что описывается в коде, и вовсе оказывается сложной задачей.

Пусть необходимо хранить следующий массив элементов типа int размерностью 5×10.

35 58 73 32 35 32 59 95 19 39
64 54 45 73 52 20 92 76 94 92
47 93 65 14 25 92 27 93 14 94
90 45 85 31 69 32 95 12 87 53
75 11 47 72 33 42 58 62 57 85

Самый адекватный вариант в большинстве случаев — выделить в куче один массив для всех элементов.

const int w = 10, h = 5;
int* array_of_a_healthy_man = new int[h * w];

Массив здорового человека. Сверху изображён фрагмент стека, внизу — выделенный в куче массив. Двойные индексы приведены для удобства.

Чтобы обратиться к j-му элементу i-й строки, необходимо проделать следующее: array_of_a_healthy_man[i * w + j]. За этой записью скрывается такое выражение: *(array_of_a_healthy_man + i * w + j), то есть несколько арифметических операций и одна операция разыменования указателя. Минимум занятого места на стеке, минимум (дорогих по времени) операций обращения к памяти.

Удаление также происходит в один этап.

delete[] array_of_a_healthy_man;
array_of_a_healthy_man = nullptr;

Если массив оформлен в виде класса, будет удобно перегрузить оператор [], чтобы каждый раз не пересчитывать индексы (но в этом случае необходимо также решить проблему с «фиктивным» классом «строки матрицы»). Тогда будет возможна такая форма записи: array_of_a_healthy_man[i][j].

Однако новичку может показаться привлекательным другой вариант. Почему бы не воспользоваться возможностью языка создать готовый двумерный массив, переложив работу по выделению памяти на компилятор и обеспечив простоту обращения к элементам?

const int w = 10, h = 5;
int array_of_a_smoker[h][w];

Массив курильщика. Элементы хранятся непосредственно на стеке, размер которого весьма и весьма ограничен.

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

Обращение к j-му элементу i-й строки выглядит просто и естественно: array_of_smoker[i][j], что можно назвать единственным преимуществом этого варианта (хоть и с натяжкой, а недостатки значительно перевешивают).

Есть ещё один вариант реализации двумерного массива. Это то, что было названо одним из моих учеников «двумерным указателем». На самом деле это указатель на массив указателей (расположенных в куче), которые в свою очередь указывают на h массивов (также расположенных в куче).

const int w = 10, h = 5;
int** array_of_a_smoker = new int*[h];
for (short i = 0; i < h; ++i)
{
    array_of_a_smoker[i] = new int[w];
}

Другой массив курильщика. На стеке хранится только один указатель. Доступ к значениям осуществляется посредством последовательного вычисления адреса массива, соответствующего строке, а затем — позиции в нём.

Обращение к j-му элементу i-й строки снова выглядит просто и естественно: array_of_a_smoker[i][j]. Но за этой невинной записью скрывается монструозная конструкция: *(*(array_of_a_smoker + i) + j). Это означает: взять адрес начала массива с указателями, выбрать нужную ячейку этого массива, прибавив i (номер ячейки совпадает с номером строки исходного массива), прочитать записанный по вычисленному адресу теперь уже адрес нужного массива с элементами (здесь происходит разыменование указателя); добавить смещение j по искомому массиву (соответствующему найденной строке); указатель с вычисленным адресом разыменовывается, мы получили доступ к искомой ячейке. Несколько арифметических операций и две дорогих по времени операции разыменования указателя.

Память под все массивы выделяется (h + 1) раз. Столько же раз она должна освобождаться. Обе операции занимают значительное время.

for (short i = 0; i < h; ++i)
{
    delete[] array_of_a_smoker[i];
}
delete[] array_of_a_smoker;
array_of_a_smoker = nullptr;

Всё сказанное выше не означает, что второй и третий варианты никогда не могут быть использованы. Второй, например, вполне сгодится для небольшого массива. А третий вариант будет лучше, если участки с занятой и ещё свободной памятью сильно фрагментированы, но это своего рода экстрим (вероятность возникновения такой ситуации мала, издержки будут больше в среднем случае). Получается, что в общем случае преимущество у первого способа, в чём мы только что смогли убедиться. Это вариант с выделением памяти под единственный массив в куче и эффективным вычислением реальных индексов в нём по «виртуальному» номеру строки и столбца.

12 апреля 2015 · массивы · программирование