Что такое “цикл” уже рассказывалось во введении.
Цикл с предусловием характеризуется тем, что перед выполнением каждой итерации проверяется заданное условие. Если это условие ложно, то цикл прекращается. Таким образом, в случае если условие ложно с самого начала, цикл не выполнится ни разу.
while ( /* условие повторения, круглые скобки обязательны */ )
{
// действия, выполняемые в цикле
}Вечный цикл на основе while:
while (true)
{
// действия, выполняемые в цикле
}Для выхода из цикла “посередине” предназначена инструкция break. Также часто удобно использовать return, что позволяет прекратить выполнение сразу всех вложенных циклов в данной функции.
while (true)
{
/* действия */
if ( /* условие выхода */ )
break;
/* действия */
}
// Сюда приходим при выполнении break.Например, можно модифицировать пример так, чтобы в случае ввода признака конца файла происходил выход из программы, а ошибки ввода игнорировались как и прежде. Для этого добавим “посередине” комбинацию if-break:
while (true)
{
cout << "Enter a sequence of integers:\n";
for (int i; cin >> i;)
cout << i << ' ';
if (cin.eof())
break;
cout << "\nPress Enter to repeat\n";
console_delay();
}Цикл с постусловием отличается от цикла с предусловием тем, что условие повторения проверяется после каждой итерации (т.е. является условием продолжения цикла). Соответственно, хотя бы один раз цикл выполнится.
На практике цикл do-while применяется намного реже цикла while.
do
{
// действия, выполняемые в цикле
} while( /* условие продолжения, круглые скобки обязательны */ );Цикл for в C является “общим типом” цикла и используется значительно чаще while и do-while.
Например, вечный цикл на основе for записывается следующим образом:
for (;;)
{
// действия, выполняемые в цикле
}Следующие два цикла эквивалентны:
while (condition())
perform_action();
for (; condition();)
perform_action();Общий вид конструкции for следующий:
for ( /* определение переменных */ ; /* условие повторения */ ; /* инкремент */ )
{
// действия, выполняемые в цикле
}Определение переменных может содержать определение группы переменных (одного типа), либо просто произвольное выражение, которое вычисляется однажды перед входом в цикл. Определённые в этой локации переменные существуют только во время выполнения цикла и видны только из тела цикла.
Условие повторения проверяется перед каждой итерацией. Таким образом, цикл for может не выполнить ни одной итерации.
Инкремент — произвольное выражение, которое вычисляется после каждой итерации.
// Вывести таблицу квадратов натуральных чисел от 1 до 10.
for (int i = 1; i <= 10; ++i)
cout << "i == " << i << "\ti squared == " << i * i << endl;Пример простого вложенного цикла for (двойной цикл):
// Вывести таблицу умножения
for (int i = 1; i <= 10; ++i)
{
for (int j = 1; j <= 10; ++j)
{
cout << i * j << "\t"; // Столбец.
}
cout << endl; // Строчка.
}Нередко новички в языке C или C++ пытаются записать подобный двойной цикл одной инструкцией for:
// Вывести таблицу умножения?
for (int i = 1, j = 1; i <= 10, j <= 10; ++i, ++j)
cout << i * j << "\t";Данный цикл будет перебирать пары значений переменных i, j вида 1, 1; 2, 2; … 10, 10 (всего 10 итераций) и выведет таблицу квадратов. Более того, конструкция i <= 10, j <= 10 равна j <= 10. На данном цикле это не сказывается из-за того, что i всегда равно j.
Оператор запятая , вычисляет левую часть (до запятой), отбрасывает результат, затем вычисляет правую часть (после запятой). Этот оператор был введён в C как раз для того, чтобы было удобно записывать несколько действий внутри инкремента цикла for, и пригождается в некоторых других случаях, поэтому иногда будет встречаться в примерах. Оператор , отличается от запятой, разделяющей элементы в списках (например, параметры функции). Чтобы “включить” оператор , в контексте списка, надо взять выражение в скобки: sin( (++x, y) ) выполнит ++x и вернёт sin(y).
В случае, когда требуется группа однотипных значений определённого размера, удобно воспользоваться средством языка программирования, называемым массив array. Простейшей формой организации массивов в языке C++ являются одномерные статические массивы.
Слово одномерный означает, что для выбора конкретного значения из группы используется одно целое число — порядковый номер этого значения — его индекс (от лат. index — “указательный палец”). У такого массива единственное измерение, имеющее размер, равный количеству элементов в массиве. Индексы в C и C++ всегда отсчитываются от нуля (первый элемент) до размера измерения – 1 (последний элемент). Размер массива не может быть меньше единицы.
Слово статический означает, что память под массив распределяется компилятором (“статически”). При этом, однако, “статический” массив может размещаться в автоматической памяти и быть локальной переменной функции. Размер статического массива должен быть известен на момент компиляции (константа времени компиляции) и не может быть изменён во время работы программы.
Далее представлен простой пример, демонстрирующий определение статического массива и обращение к его элементам (с помощью оператора []).
// Определение -- глобальный статический массив из 10 элементов типа float.
float global_array[10];
// Заполняет global_array конкретными значениями.
void fill_global_array()
{
for (int i = 0; i < 10; ++i)
global_array[i] = i * i; /* Элементу с индексом i
присваивается значение, равное квадрату i */
}
// Печатает содержимое global_array.
void print_global_array()
{
for (int i = 0; i < 10; ++i)
std::cout << global_array[i] << '\n';
}
// Вывести значения в массиве.
#include <iostream>
int main()
{
fill_global_array();
print_global_array();
return 0;
}В примере выше размер задан конкретным числом, но использование в таких целях непосредственно чисел чревато ошибками: если изменить размер массива в его определении, то можно забыть изменить его в других местах. Если выполнять автоматическую замену числа в тексте, то каждый случай замены надо проверять, а для больших программ это неудобно. Поэтому лучше определять размер в виде именованной константы и затем везде использовать не конкретное число, а его название.
// Размер массива -- глобальная константа времени компиляции.
// Размеры массивов имеют тип size_t.
const size_t GLOBAL_ARRAY_SIZE = 10;
// Определение -- глобальный статический массив.
float global_array[GLOBAL_ARRAY_SIZE];
// Заполняет global_array конкретными значениями.
void fill_global_array()
{
for (size_t i = 0; i < GLOBAL_ARRAY_SIZE; ++i)
global_array[i] = i * i; /* Элементу с индексом i
присваивается значение, равное квадрату i */
}
// Печатает содержимое global_array.
void print_global_array()
{
for (int i = 0; i < GLOBAL_ARRAY_SIZE; ++i)
std::cout << global_array[i] << '\n';
}
Указатели являются адресами в явной форме и широко применяются при работе с массивами. Массив автоматически приводится к указателю на свой первый элемент. Для указателей допускается “арифметика указателей”. Эта арифметика напоминает аффинную структуру поверх векторного пространства: вектора можно и складывать, и вычитать, и умножать на число, а точки можно только вычитать, получая вектор. Также можно добавлять к точке или вычитать из точки вектор, получая другую точку. Аналогично с указателями: роль “векторов” играют целые числа, роль “точек” — указатели.
Указатели можно вычитать, получая целое число со знаком — смещение offset от одного указателя к другому в элементах массива, на которые указывают эти указатели. Если указатели не указывают на элементы одного массива, то попытка вычислить их разность приводит к неопределённому поведению. И наоборот, к указателю на некоторый элемент массива можно добавить (или вычесть из него) целое число (смещение), чтобы получить указатель на другой элемент массива, отстоящий от первого на заданное смещением число элементов. Полученный указатель может “выходить” на верхнюю границу массива, указывая на несуществующий элемент, который шёл бы сразу за последним элементом массива. Разность между таким указателем и указателем на первый элемент массива (на начало массива) равна размеру массива. Наконец, указатели позволяют обращаться к ним как к массивам, что эквивалентно обращению к смещённому на индекс указателю.
int arr[100] = {};
int *a = arr; // то же, что &arr[0]
arr[50] = 50;
assert(a[50] == arr[50]);
a += 25; // сдвинуть указатель на 25 элементов вперёд
assert(a[25] == 50);
assert(a - &arr[0] == 25);
// Обращение по индексу эквивалентно обращению по смещённому указателю:
assert(*(a + 25) == 50);
// а можно даже так, ведь сумма здесь коммутативна:
assert("character array"[10] == 10["character array"]);Указатели можно сравнивать не только на “равно” и “не равно”, но и “меньше”, “больше” и т.д. При этом p < q эквивалентно p - q < 0.
Часто с указателями используются операции инкремента ++ и декремента --. Они передвигают указатель на, соответственно, следующий и предыдущий элементы. Рассмотрим пример — копирование массива символов до первого нулевого символа (включая его):
size_t str_copy(char *dest, const char *src, size_t dest_size)
{
size_t copied = 0;
while (copied != dest_size && *dest++ = *src++)
++copied; // нулевой символ не считаем в общем числе скопированных
return copied;
}Здесь *dest++ и *src++ передвигают соответствующие указатели на одну позицию вперёд, но так как постинкремент возвращает старое значение переменной, то именно это старое значение указателя подвергается разыменованию, поэтому мы получаем ссылки на символы, стоящие на тех позициях, на которые указывали dest и src до инкремента.
Размер статического массива в контексте видимости его объявления или определения можно запросить у компилятора (ведь размер известен на момент компиляции). Оператор sizeof, применённый к имени массива, возвращает его размер в байтах. Чтобы получить количество элементов, можно разделить размер массива в байтах на размер одного элемента.
// Заполняет global_array конкретными значениями.
void fill_global_array()
{
for (size_t i = 0; i < sizeof(global_array) / sizeof(global_array[0]); ++i)
global_array[i] = i * i; /* Элементу с индексом i
присваивается значение, равное квадрату i */
}Данный способ применяется в примерах ниже, но следует помнить, что он тоже несёт в себе опасность ошибки. Дело в том, что массивы часто передают по указателю и затем используют этот указатель как массив (для указателя также определён оператор [], и действует он аналогично). Нередко программисты забывают о том, что некое имя — это уже не имя массива, а имя указателя на него. Оператор sizeof в таком случае возвращает размер указателя в байтах, а не размер массива, на который он указывает. Это очень неприятная ошибка, встречающаяся в реальном ПО, написанном на языке C.
// Попытается заполнить array квадратами. Но не сможет.
void fill_with_squares(float array[])
{
// Увы, но sizeof(array) / sizeof(array[0]) здесь равно 1 или 2 на большинстве современных систем
// и никак не зависит от реального размера массива array.
for (size_t i = 0; i < sizeof(array) / sizeof(array[0]); ++i)
array[i] = i * i;
}Функция fill_with_squares на самом деле не видит определения массива, который может быть передан ей в качестве параметра. Это легко понять хотя бы исходя из того соображения, что исходный код, который будет использовать данную функцию, может быть написан уже после того, как тело этой функции было откомпилировано (раздельная компиляция).
Синтаксис объявления параметра функции в виде массива на самом деле объявляет передачу адреса массива (указателя на него) и только адреса. Поэтому не важно, какой размер указать там между квадратными скобками — можно не указывать никакого (как в примере). Если этот размер указать, то он может послужить для удобства чтения или в качестве намёка компилятору (с точки зрения оптимизации или предупреждений), но на семантику программы влияния не окажет.
Впрочем, C++ позволяет форсировать определённый размер массива, если принимать массив по ссылке. Например, в следующей функции мы требуем массивы из трёх элементов, представляющие трёхмерные вектора, над которыми выполняется операция “векторное произведение”. Однако такая функция будет работать только со статическими массивами. На практике это может оказаться слишком ограничивающим.
void cross_product(float (&res)[3], float (&left)[3], float (&right)[3])
{
res[0] = left[1] * right[2] - left[2] * right[1];
res[1] = left[2] * right[0] - left[0] * right[2];
res[2] = left[0] * right[1] - left[1] * right[0];
}В C++17 введена стандартная функция size (определённая в <iterator>), которая при применении к статическому массиву возвращает его размер в элементах. Применить её ненароком к указателю не получится — будет ошибка компиляции.
// Заполняет global_array конкретными значениями.
void fill_global_array()
{
for (size_t i = 0; i < size(global_array); ++i)
global_array[i] = i * i; /* Элементу с индексом i
присваивается значение, равное квадрату i */
}Впрочем, при отсутствии такой стандартной функции, её можно написать самостоятельно. Для этого даже не требуется поддержка компилятором новых стандартов C++. Но требуется использовать такой элемент языка как “шаблон функции” — это материал 2-го семестра.
template <class Item, size_t Size>
size_t size(Item (&)[Size])
{
return Size;
}
Итак, правильный способ передачи в функцию массива, размер которого не задан некоторой глобальной константой, состоит в передачи как его адреса, так и его размера. Побочным эффектом такого подхода является возможность передавать части массива (например, все элементы со второго до предпоследнего) — такие части массивов ещё называют срезы slices. Сам массив является наибольшим своим срезом.
// Заполняет array квадратами индексов.
void fill_with_squares(float array[], size_t array_sz)
{
for (size_t i = 0; i < array_sz; ++i)
array[i] = i * i;
}
// Выводим array в консоль.
void print_array(float array[], size_t array_sz)
{
for (size_t i = 0; i < array_sz; ++i)
cout << array[i] << '\n';
}
int main()
{
// Локальный статический массив. Его размер виден только внутри main.
float squares[100];
// Здесь можно использовать приём на основе sizeof.
fill_with_squares(squares, sizeof(squares) / sizeof(squares[0]));
print_array(squares, sizeof(squares) / sizeof(squares[0]));
return 0;
}Другой способ передачи среза — передать два указателя: один (“begin”) — на первый элемент среза, второй (“end”) — на (возможно, фиктивный) элемент, следующий за последним элементом среза. Таким образом, последовательность элементов задаётся своего рода полуинтервалом [begin, to), называемым также диапазоном range. Проходящий по ней указатель вначале устанавливается на begin, а при достижении им значения end работа прекращается. Например, функцию fill_with_squares для работы с диапазоном можно переписать следующим образом:
// Заполняет [begin, end) квадратами индексов.
void fill_with_squares(float* begin, float* end)
{
// Количество элементов равно разности указателей.
for (size_t i = 0; begin + i != end; ++i)
begin[i] = i * i;
}Иногда в такой ситуации можно обойтись и без индекса. Например, если мы заполняем массив копиями заранее заданного значения:
// Заполняет [begin, end) копиями value.
void fill(float* begin, float* end, float value)
{
while (begin != end)
*begin++ = value;
}Или просто выводим массив в консоль:
// Выводим array в консоль.
void print_array(float* begin, float* end)
{
while (begin != end)
cout << *begin++ << '\n';
}Данный подход был обобщён в Стандартной библиотеке C++ в виде принципов работы с абстрактными диапазонами итераторов. Например, вариант fill_with_squares на основе диапазона позволяет переписать пример с заполнением статического массива без использования громоздкого выражения с sizeof. Вместо этого, границы диапазона, соответствующего массиву можно получить с помощью стандартных функций begin и end, определённых в заголовочном файле <iterator> (C++11). Дополнительный плюс этого подхода в том, что попытка вызвать begin или end от указателя приведёт к ошибке компиляции, т.е. ошибка, аналогичная ошибке с sizeof, здесь невозможна.
int main()
{
// Локальный статический массив. Его размер виден только внутри main.
float squares[100];
// begin(squares) возвращает указатель на первый элемент массива, а
// end(squares) возвращает указатель на фиктивный элемент, следующий за последним элементом массива.
fill_with_squares(begin(squares), end(squares));
// Вывести в консоль.
print_array(begin(squares), end(squares));
return 0;
}Если функция принимает размер массива, а не диапазон, то вместо sizeof всё равно можно использовать комбинацию begin/end: end(squares) - begin(squares).
Данная форма цикла for была введена в язык C++ в стандарте 2011 года и представляет собой вариант цикла “выполнить для каждого элемента”. Итерация выполняется для каждого элемента обобщённого диапазона. Для этого запись вида
for (Type var : range)
{
// var пробегает по всем элементам range
// действия, выполняемые в цикле
}трактуется компилятором приблизительно как следующий код (переменные с префиксом __ не видны из пользовательского кода):
for (auto __begin = std::begin(range), __end = std::end(range);
__begin != __end; ++__begin)
{
Type var = *__begin;
// действия, выполняемые в цикле
}Поэтому, например, вместо
// Вывести в консоль.
print_array(begin(squares), end(squares));можно было написать
// Вывести в консоль.
for (auto i: squares)
cout << i << '\n';При изменении элементов массива в цикле следует указывать ссылочный тип:
// Возвести каждый элемент squares в квадрат.
for (auto &s: squares)
s *= s;Статические массивы можно инициализировать непосредственно на месте определения, указывая значения элементов. Если этого не сделать, то глобальные массивы инициализируются нулями, а локальные не инициализируются и могут содержать произвольные значения.
При инициализации не обязательно указывать все элементы — конечные можно опустить. Если указанных элементов меньше, чем размер массива, то оставшиеся в его конце элементы будут инициализированы нулями. И наоборот, при наличии в определении массива непустого инициализирующего выражения не обязательно указывать его размер. Если размер не будет указан явно, то в качестве размера будет взято количество элементов в инициализирующем выражении.
Несколько примеров инициализации (попробуйте запустить этот код).
#include <iostream>
using namespace std;
// Макрос для "распечатки" статического массива.
#define PRINTA(a) \
for (auto item: a) \
cout << item << ' '; \
cout << endl
int main()
{
// Указан и размер и значения всех элементов.
int xyz[3] = { 1, 2, 3 };
PRINTA(xyz);
// Последние три элемента будут нули.
int zero_tail[6] = { 7, 7, 7 };
PRINTA(zero_tail);
// Типичная инициализация локального массива нулями.
float zeroes[10] = {};
PRINTA(zeroes);
// Размер не указан, определяется количеством значений в инициализаторе.
char word[] = { 'w', 'o', 'r', 'd' };
PRINTA(word);
// В качестве инициализатора можно использовать строковый литерал.
// В конце добавляется нулевой символ, поэтому размер greets 11, а не 10.
char greets[] = "greetings!";
PRINTA(greets) << sizeof(greets) << '\n';
greets[3] = 'a';
cout << greets << endl;
}Начиная с C++11, писать = в инициализаторе массива не обязательно:
int a[] { 1, 2, 3 };есть то же самое, что
int a[] = { 1, 2, 3 };
Поддержка многомерных массивов языками C и C++ весьма ограничена. Можно создать статический многомерный массив, который интерпретируется как массив массивов. Например, массив из двух массивов по три элемента типа int:
int arr[2][3] = { { 1, 2, 3 }, { 4, 5, 6 } };В памяти такие массивы укладываются последовательно одним блоком, эквивалентным одномерному массиву размера, равного произведению размеров по каждому из измерений. Т.е. в случае приведённого выше примера имеем блок из шести int (24 байта, если int занимает 4 байта), заполненный значениями 1, 2, …, 6 подряд — порядок заполнения в памяти соответствует порядку записи в инициализаторе: первая строка-подмассив из трёх элементов, затем вторая строка-подмассив из трёх элементов.
При обходе такого массива самый правый индекс соответствует элементам, стоящим друг за другом непосредственно, шаг же по прочим индексам равен произведению размеров измерений, стоящих правее. Т.е. arr[i][j] и arr[i][j+1] — соседствуют в памяти, а вот расстояние между адресами arr[i][j] и arr[i+1][j] равно размеру всей строки arr[i], т.е. 3*sizeof(int) в этом примере.
Статический массив можно передать в функцию по указателю, но при этом необходимо явно указывать размеры всех измерений кроме самого левого, потому что иначе у компилятора не будет информации о том, на каком расстоянии в памяти элементы отстоят друг от друга (неизвестен шаг между ними). Например, можно передать в функцию указатель на массив произвольного размера, состоящий из массивов по три int:
void print(int a[][3], size_t n)
{
for (size_t i = 0; i < n; ++i)
for (size_t j = 0; j < 3; ++j)
cout << a[i][j] << ", "; cout << endl;
}
int main()
{
int arr[2][3] = { { 1, 2, 3 }, { 4, 5, 6 } };
print(arr, 2);
}Более того, так как размеры подмассивов известны компилятору (зашиты в тип параметра a), то можно оперировать ими как обычными статическими массивами. Например, пробегать по ним, используя форму цикла for для диапазонов:
void print(int a[][3], size_t n)
{
for (size_t i = 0; i < n; ++i)
for (int item: a[i])
cout << item << ", "; cout << endl;
}Естественный обход многомерного массива осуществляется с помощью вложенных циклов for, каждый из которых перебирает диапазон значений индекса одного из измерений. Статический массив можно обойти целиком с помощью for:
int arr[2][3] = { { 1, 2, 3 }, { 4, 5, 6 } };
for (auto &x: arr) // x -- ссылка на подмассив из трёх элементов
for (auto &item: x)
cout << item << endl;Значок & после auto обозначает ссылку на объект, которая представляет собой неявный указатель и ведёт себя как объект, на который она ссылается (не требует явного разыменования). Во втором цикле for использование ссылки не обязательно (там можно опять поставить просто int как в предыдущем примере), а вот в первом — обязательно. Это связано с тем, что хотя в C++ и возможен тип int[3] (тип элементов массива arr, понимаемого как массив массивов), но невозможны временные значения такого типа. Поэтому оперировать статическими массивами можно только по указателю или завуалированному указателю — ссылке.
При инициализации статических многомерных массивов можно опускать внутренние фигурные скобки. При этом следует помнить, что логика заполнения массива элементами заключается в последовательном копировании заданных значений в массив (от младших адресов в памяти к старшим) и заполнении остатка нулями. Так же как и в случае одномерных массивов, начиная с C++11, можно опускать = в инициализаторе.
// То же самое, что
//int arr[2][3] = { { 1, 2, 3 }, { 4, 5, 6 } };
int arr[2][3]
{
1, 2, 3,
4, 5, 6
};Может быть опасно изменять код, удаляя “лишние” скобки в инициализаторе:
int m[3][3]
{
{ 1 }, // то же, что { 1, 0, 0 } -- остаток забивается нулями
{ 0, 1 }, // то же, что { 0, 1, 0 }
{ 0, 0, 1 }
};Удалив внутренние скобки, получим запись последовательности { 1, 0, 1, 0, 0, 1, 0, 0, 0 } в m[3][3] (интерпретируемом как m[9])
int m[3][3]
{
1,
0, 1,
0, 0, 1
};
/* Получили фактически
int m[3][3]
{
{ 1, 0, 1 }, // первые три указанных числа
{ 0, 0, 1 }, // следующие три указанных числа
{ 0, 0, 0 } // остаток забивается нулями.
};
-- это совсем не то же самое, что в предыдущем примере! */
Впрочем, статические массивы не очень популярны, а многомерные статические массивы используются только в особых случаях: обычно для матриц заранее фиксированных размеров (например, представляющих линейные отображения в трёхмерном пространстве). Чаще используются динамические массивы.
Многомерные динамические массивы в C и C++ можно реализовать различными способами. Далее представлено три способа.
Динамические массивы — массивы, располагающиеся в динамической памяти. В отличие от статических массивов, размер динамических массивов может определяться по ходу выполнения программы.
В C++ предусмотрены операторы new[] для создания динамических массивов (оператор возвращает ненулевой указатель на массив, в случае ошибки бросается исключение) и delete[] для их удаления.
// Создать массив из 5 int, не инициализировать.
auto a = new int[5];
// Создать массив из 6 int, инициализировать нулями.
auto b = new int[6]{};
assert(b[0] == 0);
// Создать массив из 3 int, инициализировать заданными значениями.
auto c = new int[3]{1, 2, 3};
assert(c[0] == 1 && c[1] == 2 && c[2] == 3);
// Создать массив строк, инициализировать по умолчанию (пустые строки).
// -- std::string не может быть неинициализированным.
auto s = new std::string[10];
assert(s[0] == "");
// Удаление s, c, b, a.
delete[] s;
delete[] c;
delete[] b;
delete[] a;Создать массив указателей на массивы (матрица — вектор векторов). Создать каждый подмассив в виде отдельного динамического массива. Способ позволяет оформлять обращение к элементам динамического многомерного массива так же, как к элементам статического: заключая каждый индекс в квадратные скобки.
// Создать двумерный массив (массив массивов) размеров n, m.
int** alloc_2d_array(size_t n, size_t m)
{
int **a = new int*[n]; // создать массив указателей на массивы int
for (size_t i = 0; i < n; ++i)
a[i] = new int[m]; // создать каждый подмассив отдельно
return a;
}
// Удалить двумерный массив (массив массивов) со старшим размером n.
void free_2d_array(int **a, size_t n)
{
for (size_t i = 0; i < n; ++i)
delete[] a[i]; // удалить каждый подмассив
delete[] a;
}
int main()
{
auto arr = alloc_2d_array(2, 3);
arr[1][2] = 2; // элемент с индексами 1, 2
cout << arr[1][2];
free_2d_array(arr, 2);
}
Недостатком данного способа является множество выделений-освобождений динамической памяти и возможная “разбросанность” подмассивов в памяти. (Если бы все элементы массива шли в памяти подряд, то из этого можно было бы извлечь пользу в плане производительности и удобства кодирования некоторых операций.)
Преимуществом данного способа является относительная гибкость: можно, например, заменять или переставлять подмассивы, не затрагивая весь массив (достаточно изменить соответствующие указатели головного массива). Можно даже создавать подмассивы разной длины — “рваный” массив jagged array, ragged array.
Данный способ предполагает другую крайность — явно хранить всё содержимое многомерного массива в виде одномерного массива, переводя многомерные индексы в одномерные. Т.е. явно делать то, что делает компилятор при работе со статическими многомерными массивами.
Массив с размерностями (d0, d1, …, dr–1) содержит d0·d1⋯dr–1 элементов. Количество размерностей r называют рангом rank массива. При укладке их подряд в памяти в духе статического многомерного массива получаем следующую формулу приведения r-мерного (векторного) индекса (i0, i1, …, ir–1) к одномерному индексу I в блоке:
В общем случае его удобно вычислять методом Горнера (только вместо домножения на x домножаем на следующий индекс).
В примерах ниже именно этот способ используется для представления матриц с произвольными размерами. В двумерном случае приведённая выше формула приобретает простой вид: I = i1 + i0 d1 (массив строк, в каждой строке по d1 столбцов). Т.е. индекс по первому измерению надо умножить на размер второго измерения и добавить индекс по второму измерению.
Преимуществами способа 2 являются: удобство кодирования и в среднем большее быстродействие операций, выполняемых над массивом целиком, а также минимизация операций выделения и освобождения памяти, минимизация затрат памяти (нет вспомогательного массива).
Недостатки: выделение сразу большого куска памяти может производиться медленно или быть вовсе невозможным из-за фрагментации кучи; простые операции, вроде перестановки строк, невозможно выполнить простой манипуляцией указателями: необходимо либо явно обменивать все элементы строк, либо применять промежуточное преобразование индексов, либо создавать новый изменённый массив.
Данный способ является гибридом двух предыдущих и удобен в случае двумерных массивов. Память выделяется сразу на все элементы массива (первый блок) и отдельно на головной массив с указателями, которые инициализируются вычислением смещений подмассивов (второй блок). В примере ниже указатель на массив-хранилище записывается “перед” первым элементом головного массива, чтобы можно было корректно удалить хранилище, не опираясь на, возможно, изменённые адреса подмассивов.
int** alloc_2d_array(size_t n, size_t m)
{
int **a = new int*[n + 1]; // создать головной массив
*a++ = new int[n * m]; // создать хранилище
a[0] = a[-1];
for (size_t i = 1; i < n; ++i)
a[i] = a[i - 1] + m;
return a;
}
void free_2d_array(int **a)
{
delete[] *--a; // удалить хранилище
delete[] a; // удалить головной массив
}
int main()
{
auto arr = alloc_2d_array(2, 3);
arr[1][2] = 2; // элемент с индексами 1, 2
cout << arr[1][2];
free_2d_array(arr, 2);
}
Кувшинов Д.Р. © 2015