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

Пусть необходимо хранить следующий массив элементов типа int размерностью \(5\times 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;

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