Меню Закрыть

Двумерный массив c через указатель

Содержание

В первой статье были описаны приёмы работы с простейшим видом массивов — одномерным (линейным) массивом. В этой, второй статье будут рассмотрены многомерные массивы. В основном, речь пойдёт о двумерных массивах. Но приведённые примеры легко экстраполируются на массивы любой размерности. Также как и в первой статье, будут рассматриваться только массивы в стиле C/C++, без использования возможностей STL.

Эта статья предполагает у читателя базовые знания об одномерных и многомерных массивах, указателях и адресной арифметике. Почерпнуть эти знания можно в любом учебнике по C/C++.

Классика жанра

Если мы откроем классический труд «Язык программирования C» Брайана Кернигана и Денниса Ритчи, то прочитаем, что «В языке C есть возможность работать с многомерными прямоугольными массивами, хотя на практике они используются гораздо реже, чем массивы указателей». C++ практически полностью унаследовал работу с многомерными массивами своего предтечи.

Определение автоматических многомерных массивов

В этом разделе я буду иногда употреблять термин «матрица» как синоним термина «двумерный массив». В C/C++ прямоугольный двумерный массив чисел действительно реализует математическое понятие «матрица». Однако, в общем случае, двумерный массив — понятие гораздо более широкое, чем матрица, поскольку он может быть и не прямоугольным, и не числовым.

Определение автоматических многомерных массивов почти полностью совпадает с определением одномерных массивов (о чём было рассказано в первой статье), за исключением того, что вместо одного размера может быть указано несколько:

В этом примере определяется двумерный массив из 3 строк по 5 значений типа int в каждой строке. Итого 15 значений типа int .

Во втором примере определяется трёхмерный массив, содержащий 3 матрицы, каждая из которых состоит из 5 строк по 2 значения типа int в каждой строке.

Понятно, что тип данных, содержащихся в многомерном массиве, может быть любым.

При дальнейшем изложении для таких многомерных массивов будет употребляться термин «C-массив», что бы отличать их от массивов других видов.

Инициализация

При статической (определяемой на этапе компиляции) инициализации значения C-массива перечисляются в порядке указания размеров (индексов) в определении массива. Каждый уровень (индекс), кроме самого младшего, многомерного массива заключается в свою пару фигурных скобок. Значения самого младшего индекса указываются через запятую:

В примере показана статическая инициализация прямоугольного массива. Весь список инициализирующих значений заключён в фигурные скобки. Значения для каждой из 3 строк заключены в свою пару из фигурных скобок, значения для каждого из 5 столбцов для каждой строки перечислены через запятую.

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

Заполнение массива значениями

Многомерный массив заполняется значениями с помощью вложенных циклов. Причём, как правило, количество циклов совпадает с размерностью массива:

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

Вывод значений массива на консоль

В продолжение предыдущего примера можно написать:

В результате получим следующий вывод на консоль:

Для трёхмерного массива можно написать код, использующий те же приёмы:

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

Расположение в памяти

Для многомерного C-массива выделяется единый блок памяти необходимого размера: размер_массива1 * размер_массива2 * . * размер_массиваN * sizeof(тип_элемента_массива) .

Значения располагаются последовательно. Самый левый индекс изменяется медленнее всего. Т.е. для трёхмерного массива сначала располагаются значения для первой (индекс 0) матрицы, затем для второй и т.д. Значения для матриц располагаются построчно (ср. со статической инициализацией массива выше).

Читайте также:  Как посмотреть реестр windows 10

Имя (идентификатор) многомерного C-массива является указателем на первый элемент массива (так же как и для одномерных массивов)

Если код из последнего примера немного изменить:

поставить точку останова на return и посмотреть под отладчиком память, отведённую под переменную ary , то будет видно, что значения, расположенные в памяти, последовательно возрастают:

Поскольку все значения многомерного C-массива располагаются последовательно, то, пользуясь адресной арифметикой, можно сделать следующий хак:

В последнем фрагменте осуществляется доступ к значениям двумерного массива как к одномерному массиву. Цивилизованное решение реализуется через union .

Из двух примеров, приведённых выше, следует, что работу с двумерным или многомерным массивом (в понимании на более высоком уровне абстракции) технически можно организовать посредством одномерного массива соответствующего размера:

Этот приём достаточно распространён. Его выгода в том, что массив ary[DIM1 * DIM2] не обязательно должен быть выделен автоматически. Его можно выделять и динамически. Но при этом логически рассматривать как C-массив.

Вышеприведённый код написан в духе чистого C. В C++ обычно такие вещи прячут в класс, оставляя снаружи лаконичный интерфейс без всяких следов адресной арифметики.

Неродные близнецы

Теперь рассмотрим работу с «динамическими» многомерными массивами, т.е. с массивами, память для которых выделяется динамически.

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

Как правило, работа с такими массивами осуществляется следующим образом:

(1) Для доступа к двумерному массиву объявляется переменная ary типа указатель на указатель на тип (в данном случае это указатель на указатель на int ).

(2) Переменная инициализируется оператором new , который выделяет память для массива указателей на int .

(3) В цикле каждый элемент массива указателей инициализируется оператором new , который выделяет память для массива типа int .

Освобождение памяти происходит строго в обратном порядке: сначала уничтожаются массивы значений типа int , а затем уничтожается массив указателей.

Работа с динамическим многомерным массивом синтаксически полностью совпадает с работой с многомерным C-массивом.

Пример кода для трёхмерного массива:

Где собака порылась

Работа с динамическим многомерным массивом синтаксически полностью совпадает с работой с многомерным C-массивом. (Цитирую предыдущий раздел.) Синтаксически — да, но между этими массивами есть глубокое различие, о котором начинающие программисты часто забывают.

Во-первых, для динамического массива выделяется другой объём памяти.

Если посчитать, сколько памяти будет выделяться для двумерного массива из примера выше, то получится: первый оператор new выделил память для 3 указателей, второй оператор new в цикле трижды выделил память для 5 элементов типа int . Т.е. получилось, что выделили памяти для 15 значений типа int и для 3 значений типа указатель на int . Для C-массива компилятором была выделена память только для 15 значений типа int . (Всяческие выравнивания и прочие оптимизации не учитываем!)

Во-вторых, память, выделенная для динамического массива, не непрерывна. Следовательно, хак №1 (обращение с двумерным массивом как с одномерным) работать не будет.

В-третьих, передача многомерных массивов в функции и работа с ними будет отличаться для динамических массивов и C-массивов.

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

Динамический многомерный массив НЕ является C-массивом.

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

Читайте также:  Чем заменить блок питания ноутбука

Стоит отметить, что массив указателей на массивы — структура более гибкая, чем двумерный C-массив. Например, для массива указателей на массивы размеры массивов могут быть разными, или какой-то массив может вообще отсутствовать. Наиболее распространённым примером является «массив строк», т.е. массив указателей на массивы типа char (пример — см. в следующем разделе).

Ещё раз о предосторожности

Из вышеизложенного следует, что нужно чётко отличать многомерные C-массивы вида

от массивов указателей на массивы.

Иногда внешние отличия весьма незначительны. К примеру С-строка — это одномерный массив элементов типа char , заканчивающийся нулевым байтом. Как реализовать массив строк?

Это — пример определения и инициализации двумерного C-массива

Каждая С-строка занимает ровно 10 байт, включая завершающий ноль (считаем, тип char имеет размер 1 байт). Неиспользуемые байты у коротких строк, вроде «May», содержат «мусор» (или нули, если об этом позаботился компилятор). Весь массив занимает один непрерывный блок памяти размером 120 байт (12 строк по 10 символов).

А здесь определён и инициализирован одномерный (!) массив указателей на массивы элементов типа char .

Вся информация, доступная через переменную month , занимает 13 блоков памяти: массив из 12 указателей и 12 блоков памяти, адреса которых хранятся в указателях, содержащих С-строки с названиями месяцев. И нет никакой гарантии, что 12 блоков памяти с С-строками будут расположены в памяти последовательно и в порядке, соответствующем перечислению в инициализаторе.

Но в обоих случаях доступ к символу b в строке «February» будет осуществляться выражением month[1][2] .

И, в заключение, ещё одно предостережение.

Поскольку многомерные C-массивы, как правило, занимают большой объём памяти, их надо с особой осторожностью объявлять внутри функций, в том числе в main() . И с осторожностью в n-ной степени в рекурсивных функциях. Можно легко получить переполнение стека и, как следствие, аварийное завершение программы.

Многомерные массивы при работе с функциями

Поскольку многомерные C-массивы и многомерные динамические массивы — совершенно разные типы данных, то и при работе с функциями подходы будут разные.

Передача в функцию многомерного C-массива

Функция, получающая C-массив в качестве параметра, может выглядеть следующим образом:

Форма (1) — наиболее распространённая.

Форма (2). При передаче многомерного C-массива в функцию можно не указывать длину самого левого измерения. Компилятору для расчёта доступа к элементам массива эта информация не нужна.

Как всегда в C/C++, параметр передаётся в функцию по значению. Т.е. в функции доступна копия фактического параметра. Поскольку имя C-массива является указателем на его первый элемент (т.е. адресом первого элемента), то в функцию передаётся копия адреса начала массива. Следовательно, внутри функции можно изменять значения элементов массива, т.к. доступ к ним осуществляется через переданный адрес, но нельзя изменить адрес начала массива, переданный в качестве параметра, т.к. это — копия фактического параметра.

Возвратить многомерный C-массив из функции в качестве результата стандартными средствами невозможно.

Передача в функцию многомерного динамического массива

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

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

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

Читайте также:  Как почистить телефон андроид от мусора вручную

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

Массив указателей используется в каждой программе, которая может получать входную информацию из командной строки (или при её вызове от операционной системы). Одна из классических форм функции main() имеет вид:

Аргументами функции являются количество строк argc (размер массива указателей) и массив указателей на строки — argv . Т.е. argv — это массив указателей на массивы значений типа char .

Пожалуй это всё, что я хотел рассказать в этой статье. Надеюсь, что кто-то сочтёт её полезной для себя.

Да пребудет с вами святой Бьярн и апостолы его! 😉

В первом случае int **ptr
Во вотором разницы между двумерным массивом и одномерным нет — они в памяти располагаются одинаково — потому можно так — int *ptr;
н-р
#include
#include

for(int i = 0; i Остальные ответы

Мне нужно выводить на экран массив размером около 1000×1000 . Если постоянно обращаться к элементам массива через [][] , это занимает долго времени. Хочу сделать через указатели. Так же должно быть быстрее. Как лучше сделать пробег по такому массиву с наименьшим временем через указатели?

3 ответа 3

Ты думаешь, если был бы выигрыш, то компилятор не догадался бы оптимизировать ptr[ i ][ j ] как

Да и, с большой долей вероятности, боттлнеком у тебя будут именно функции вывода, а не доступа.

А почему вы уверены, что это даст прирост производительности? Ведь объявление вида

практически аналогично (если не принимать во внимание фрагментацию памяти и алгоритмы аллокатора) вот этому:

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

Эта запись аналогична этой:

Раз тут пошла такая пьянка, расскажу немного про указатели, которые указывают на двумерные массивы в памяти.

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

Далее мы выделяем память для этих mat[n] = PTR указателей, ведь диспетчер памяти не обязан выделять память строго друг за другом потому, что это не противоречит самой идеи указателей (здесь фрагментация как таковая роли не играет). Возьмём, к примеру, разряжённую матрицу, в которой каждая строка это односвязной список.

А вот пример, как пройтись одними указателями по динамическому двумерному массиву.

Другое дело статический двумерный массив: вот как раз тут элементы матрицы расположены в памяти друг за другом.

Dexter384, так что в твоём вопросе никакой экономии на спичках не будет. В asm для удобства также есть индексация массивов, только индекс массива умножаем на размер типа, то бишь удобно чтобы лишний раз регистр не смещать туда-сюда. В С/С++ компилятор эту работу делает за нас, то есть умножает на размер типа, если доступ к массиву по индексу, а если через указатель — то смещение на n-байт (то есть на размер типа).

И последнее — для того, чтобы лишний раз куча не фрагментировалась, лучше использовать

Рекомендуем к прочтению

Добавить комментарий

Ваш адрес email не будет опубликован.