10.23 – Знакомство с std::vector
В предыдущем уроке мы представили std::array , который обеспечивает функциональность встроенных фиксированных массивов C++ в более безопасной и удобной форме.
Аналогичным образом стандартная библиотека C++ предоставляет функциональные возможности, которые делают более безопасной и простой работу с динамическими массивами. Это средство называется std::vector .
В отличие от std::array , который точно соответствует базовой функциональности фиксированных массивов, std::vector содержит некоторые дополнительные возможности. Это помогает сделать std::vector одним из самых полезных и универсальных инструментов в вашем наборе инструментов C++.
Знакомство с std::vector
Представленный в C++03, std::vector предоставляет функциональность динамического массива, которая обеспечивает собственное управление памятью. Это означает, что вы можете создавать массивы, длина которых устанавливается во время выполнения, без необходимости явно выделять и освобождать память с помощью операторов new и delete . std::vector находится в заголовке .
Объявить std::vector просто:
#include // в объявлении не нужно указывать длину std::vector array; // использовать список инициализаторов для инициализации массива (до C++11) std::vector array2 = < 9, 7, 5, 3, 1 >; // использовать унифицированную инициализацию для инициализации массива std::vector array3 < 9, 7, 5, 3, 1 >; // как и в случае с std::array, тип может быть опущен, начиная с C++17 std::vector array4 < 9, 7, 5, 3, 1 >; // вывести к std::vector
Обратите внимание, что как в неинициализированном, так и в инициализированном случае вам не нужно указывать длину массива во время компиляции. Это связано с тем, что std::vector будет динамически выделять память для своего содержимого, сколько потребуется.
Как и в std::array , доступ к элементам массива может осуществляться с помощью оператора [] (который не проверяет границы) или функции at() (которая выполняет проверку границ):
array[6] = 2; // без проверки границ array.at(7) = 3; // проверяет границыВ любом случае, если вы запрашиваете элемент, который находится за пределами массива, вектор не будет автоматически изменять свой размер.
Начиная с C++11, вы также можете присваивать значения std::vector , используя список инициализаторов:
array = < 0, 1, 2, 3, 4 >; // ok, длина массива теперь 5 array = < 9, 8, 7 >; // ok, длина массива теперь 3В этом случае вектор автоматически изменит размер, чтобы соответствовать количеству предоставленных элементов.
Самоочистка предотвращает утечку памяти
Когда переменная вектор выходит за пределы области видимости, она (при необходимости) автоматически освобождает память, которую она контролирует. Это не только удобно (поскольку вам не нужно делать это самостоятельно), но и помогает предотвратить утечки памяти. Рассмотрим следующий фрагмент:
void doSomething(bool earlyExit) < int *array< new int[5] < 9, 7, 5, 3, 1 >>; // выделяем память с помощью new if (earlyExit) return; // выходит из функции без освобождения памяти, выделенной выше // здесь что-то делаем delete[] array; // никогда не вызывается >Если для earlyExit установлено значение true , массив никогда не будет освобожден, и произойдет утечка памяти.
Однако если array является std::vector , этого не произойдет, потому что память будет освобождена, как только массив выйдет за пределы области видимости (независимо от того, завершится функция раньше или нет). Это делает std::vector более безопасным в использовании, чем самостоятельное выделение памяти.
Векторы запоминают свою длину
В отличие от встроенных динамических массивов, которые не знают длину массива, на который они указывают, std::vector отслеживает свою длину. Мы можем запросить длину вектора с помощью функции size() :
#include #include void printLength(const std::vector& array) < std::cout int main() < std::vector array < 9, 7, 5, 3, 1 >; printLength(array); return 0; >Приведенный выше пример печатает:
The length is: 5Как и в случае с std::array , size() возвращает значение вложенного типа size_type (полный тип в приведенном выше примере будет std::vector::size_type ), который является целочисленным значением без знака.
Изменение размера вектора
Изменение размера встроенного динамически размещаемого массива сложно. Изменить размер std::vector так же просто, как вызвать функцию resize() :
#include #include int main() < std::vector array < 0, 1, 2 >; array.resize(5); // устанавливаем размер 5 std::cout
Этот код печатает:
The length is: 5 0 1 2 0 0Здесь следует отметить два момента. Во-первых, когда мы изменили размер вектора, значения существующих элементов были сохранены! Во-вторых, новые элементы инициализируются значением по умолчанию для типа (которое для int равно 0).
Размер векторов может быть уменьшен:
#include #include int main() < std::vector array < 0, 1, 2, 3, 4 >; array.resize(3); // устанавливаем размер 3 std::cout
Этот код печатает:
The length is: 3 0 1 2Изменение размера вектора требует больших вычислительных ресурсов, поэтому вы должны стремиться минимизировать количество таких операций. Если вам нужен вектор с определенным количеством элементов, но вы не знаете значений элементов в момент объявления, вы можете создать вектор со значениями элементов по умолчанию:
#include #include int main() < // Используя прямую инициализацию, мы можем создать вектор из 5 элементов, // каждый элемент равен 0. Если мы используем инициализацию с фигурными // скобками, у вектора будет 1 элемент со значением 5. std::vectorarray(5); std::cout
Эта программа печатает:
The length is: 5 0 0 0 0 0Мы поговорим о том, почему прямая инициализация и инициализация с фигурными скобками обрабатываются по-разному в уроке «16.7 – Список инициализаторов std::initializer_list ». Практическое правило: если тип представляет собой какой-то список, и вы не хотите инициализировать его списком, используйте прямую инициализацию.
Уплотнение логических значений
У std::vector есть еще один крутой трюк. Существует специальная реализация для std::vector типа bool , которая сжимает 8 логических значений в один байт! Это происходит за кулисами и не меняет способ использования std::vector .
#include #include int main() < std::vectorarray < true, false, false, true, true >; std::cout
Этот код печатает:
The length is: 5 1 0 0 1 1Еще не всё
Обратите внимание, что это вводная статья, предназначенная для ознакомления с основами std::vector . В уроке «11.11 – Емкость и стековое поведение std::vector » мы рассмотрим некоторые дополнительные возможности std::vector , включая разницу между длиной и емкостью вектора, и более подробно рассмотрим, как std::vector обрабатывает выделение памяти.
Заключение
Поскольку переменные типа std::vector обеспечивают собственное управление памятью (что помогает предотвратить утечки памяти), запоминают свою длину и могут легко изменять размер, мы рекомендуем использовать std::vector в большинстве случаев, когда необходимы динамические массивы.
Одномерные массивы и циклы
Что такое “цикл” уже рассказывалось во введении.
Цикл с предусловием
Цикл с предусловием характеризуется тем, что перед выполнением каждой итерации проверяется заданное условие. Если это условие ложно, то цикл прекращается. Таким образом, в случае если условие ложно с самого начала, цикл не выполнится ни разу.
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
Цикл 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 == " Пример простого вложенного цикла for (двойной цикл):
// Вывести таблицу умножения for (int i = 1; i 10; ++i) < for (int j = 1; j 10; ++j) < cout "\t"; // Столбец. > cout // Строчка. >Нередко новички в языке C или C++ пытаются записать подобный двойной цикл одной инструкцией for:
// Вывести таблицу умножения? for (int i = 1, j = 1; i 10, j 10; ++i, ++j) cout "\t";Данный цикл будет перебирать пары значений переменных i, j вида 1, 1; 2, 2; … 10, 10 (всего 10 итераций) и выведет таблицу квадратов. Более того, конструкция i
Оператор запятая , вычисляет левую часть (до запятой), отбрасывает результат, затем вычисляет правую часть (после запятой). Этот оператор был введён в 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 '\n'; > // Вывести значения в массиве. #include 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 '\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 (определённая в ), которая при применении к статическому массиву возвращает его размер в элементах. Применить её ненароком к указателю не получится — будет ошибка компиляции.
// Заполняет 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 '\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 '\n'; >Данный подход был обобщён в Стандартной библиотеке C++ в виде принципов работы с абстрактными диапазонами итераторов. Например, вариант fill_with_squares на основе диапазона позволяет переписать пример с заполнением статического массива без использования громоздкого выражения с sizeof. Вместо этого, границы диапазона, соответствующего массиву можно получить с помощью стандартных функций begin и end , определённых в заголовочном файле (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 для диапазона
Данная форма цикла 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 '\n';
При изменении элементов массива в цикле следует указывать ссылочный тип:
// Возвести каждый элемент squares в квадрат. for (auto &s: squares) s *= s;
Инициализация массива
Статические массивы можно инициализировать непосредственно на месте определения, указывая значения элементов. Если этого не сделать, то глобальные массивы инициализируются нулями, а локальные не инициализируются и могут содержать произвольные значения.
При инициализации не обязательно указывать все элементы — конечные можно опустить. Если указанных элементов меньше, чем размер массива, то оставшиеся в его конце элементы будут инициализированы нулями. И наоборот, при наличии в определении массива непустого инициализирующего выражения не обязательно указывать его размер. Если размер не будет указан явно, то в качестве размера будет взято количество элементов в инициализирующем выражении.
Несколько примеров инициализации (попробуйте запустить этот код).
#include using namespace std; // Макрос для "распечатки" статического массива. #define PRINTA(a) \ for (auto item: a) \ cout \ cout 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
Начиная с 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 ", "; cout 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 ", "; cout
Естественный обход многомерного массива осуществляется с помощью вложенных циклов for, каждый из которых перебирает диапазон значений индекса одного из измерений. Статический массив можно обойти целиком с помощью for:
int arr[2][3] = < < 1, 2, 3 >, < 4, 5, 6 > >; for (auto &x: arr) // x -- ссылка на подмассив из трёх элементов for (auto &item: x) cout Значок & после 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, 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;Способ 1
Создать массив указателей на массивы (матрица — вектор векторов). Создать каждый подмассив в виде отдельного динамического массива. Способ позволяет оформлять обращение к элементам динамического многомерного массива так же, как к элементам статического: заключая каждый индекс в квадратные скобки.
// Создать двумерный массив (массив массивов) размеров 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 1][2]; free_2d_array(arr, 2); >Недостатком данного способа является множество выделений-освобождений динамической памяти и возможная “разбросанность” подмассивов в памяти. (Если бы все элементы массива шли в памяти подряд, то из этого можно было бы извлечь пользу в плане производительности и удобства кодирования некоторых операций.)
Преимуществом данного способа является относительная гибкость: можно, например, заменять или переставлять подмассивы, не затрагивая весь массив (достаточно изменить соответствующие указатели головного массива). Можно даже создавать подмассивы разной длины — “рваный” массив jagged array, ragged array .
Способ 2
Данный способ предполагает другую крайность — явно хранить всё содержимое многомерного массива в виде одномерного массива, переводя многомерные индексы в одномерные. Т.е. явно делать то, что делает компилятор при работе со статическими многомерными массивами.
Массив с размерностями (d0, d1, …, dr–1) содержит d0·d1⋯dr–1 элементов. Количество размерностей r называют рангом rank массива. При укладке их подряд в памяти в духе статического многомерного массива получаем следующую формулу приведения r-мерного (векторного) индекса (i0, i1, …, ir–1) к одномерному индексу I в блоке:
В общем случае его удобно вычислять методом Горнера (только вместо домножения на x домножаем на следующий индекс).
В примерах ниже именно этот способ используется для представления матриц с произвольными размерами. В двумерном случае приведённая выше формула приобретает простой вид: I = i1 + i0 d1 (массив строк, в каждой строке по d1 столбцов). Т.е. индекс по первому измерению надо умножить на размер второго измерения и добавить индекс по второму измерению.
Преимуществами способа 2 являются: удобство кодирования и в среднем большее быстродействие операций, выполняемых над массивом целиком, а также минимизация операций выделения и освобождения памяти, минимизация затрат памяти (нет вспомогательного массива).
Недостатки: выделение сразу большого куска памяти может производиться медленно или быть вовсе невозможным из-за фрагментации кучи; простые операции, вроде перестановки строк, невозможно выполнить простой манипуляцией указателями: необходимо либо явно обменивать все элементы строк, либо применять промежуточное преобразование индексов, либо создавать новый изменённый массив.
Способ 3
Данный способ является гибридом двух предыдущих и удобен в случае двумерных массивов. Память выделяется сразу на все элементы массива (первый блок) и отдельно на головной массив с указателями, которые инициализируются вычислением смещений подмассивов (второй блок). В примере ниже указатель на массив-хранилище записывается “перед” первым элементом головного массива, чтобы можно было корректно удалить хранилище, не опираясь на, возможно, изменённые адреса подмассивов.
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 1][2]; free_2d_array(arr, 2); >Шаблон vector
Вектор в библиотеке STL — это удобный массив (вернее, структура, аналогичная массиву), размер которого может изменяться динамически. Вектор целых чисел A задается таким образом:
vector A;
Аналогично можно задавать векторы любого другого типа.
Вектор поддерживает операцию обращения по индексу A[i] , как и обычный массив, но в отличии от обычного массива размер вектора может меняться. У вектора есть метод size , возвращающий количество элементов в векторе в настоящий момент.
Есть несколько способов создать вектор (конструкторы вектора):
vector(B) , где B — вектор такого же типа. Создает копию вектора B
vector(n) , где n — целое число. Создает вектор из n элементов.
vector(n, val) — создает вектор из n элементов, заполненных значением val .
vector A(10, 179); vector B(A);
создаст вектор A из 10 элементов равных 179, а затем вектор B , являющийся копией вектора A .
Конструкторы можно вызывать явно для создания объектов, например, vector(10, 179) создаст объект типа vector и вызовет для вновь создаваемого объекта конструктор.
Для изменения размера вектора можно использовать метод resize . Первый его параметр — новый размер вектора, второй параметр (необязательный, имеет смысл только при увеличении размера вектора) — значение, которым заполняются вновь созданные элементы.
Для добавления нового элемента в конец вектора можно использовать метод push_back(val) . Для удаления последнего элемента из вектора можно использовать метод pop_back() .
Из вектора A можно удалить элемент с индексом i при помощи A.erase(A.begin() + i) . Для удаления элементов с i -го (включая) до j -го (не включая) можно использовать A.erase(A.begin() + i, A.begin() + j) . Также можно использовать итератор end() , возвращающий элемент на конец вектора (фиктивный элемент, следующий за последним). Например, удалить элементы с i -го до конца можно при помощи A.erase(A.begin() + i, A.end()) , а удалить k последних элемента вектора можно при помощи A.erase(A.end() - k, A.end()) . Удаление требует сдвига элементов, поэтому выполняется за линейное время.
Вставить значения в вектор можно при помощи метода insert . Например, вставить элемент val перед i -м элементов вектора A можно при помощи A.insert(A.begin() + i, val) . Если же передать в качестве указателя два итератора, то можно вставить весь фрагмент между итераторами. Например, A.insert(A.begin(), B.begin(), B.end()) вставляет в начало вектора A все содержимое вектора B .
Более подробно обо всех методах работы с векторами можно прочесть на cppreference.com.
Операции со строками в STL
В этом листке мы снова будем работать со строками, активно используя стандартную библиотеку языка C++ STL (Standard template library).
Считывание строк
Напомним, что строки можно считывать двумя способами: до пробельного символа (пробела, конца строки, символа табуляции) при помощи конструкции cin >> S , и до конца строки при помощи функции getline(cin, S) .
Арифметические операторы
Со строками можно выполнять следующие арифметические операции:
= - присваивание значения.
+= - добавление в конец строки другой строки или символа.
+ - конкатенация двух строк, конкатенация строки и символа.
== , != - посимвольное сравнение.
< , >, = - лексикографическое сравнение.
Подробней об операторах для строк читайте здесь.
Конструкторы
Строки можно создавать с использованием следующих конструкторов:
string() - конструктор по умолчанию (без параметров) создает пустую строку.
string(string & S) - копия строки S
string(int n, char c) - повторение символа c заданное число n раз.
string(char c) - строка из одного символа c .
string(string & S, int start, int len) - строка, содержащая не более, чем len символов данной строки S , начиная с символа номер start .
Конструкторы можно вызывать явно, например, так:
S += string(10, 'z');
В этом примере явно вызывается конструктор string для создания строки, состоящей из 10 символов 'z' .
Неявно конструктор вызывается при объявлении строки с указанием дополнительных параметров. Например, так:
string S(10, 'z');
Подробней о конструкторах для строк читайте здесь.
Методы для строк
Методом называется функция, которая применяется к объекту, например, строке. При вызове метода его имя пишется после идентификатора объекта через точку, например, у объекта типа string есть метод size , возвращающий длину строки. Если S — это строка, то метод вызывается так: S.size() . Другой пример: метод substr возвращает подстроку заданной строки:
string S = "Hello, world!"; coutВ данном случае будет выведен текст world .
Векторы в C++: для начинающих
Всем привет! До этого дня мы использовали чистые массивы. Чистые - это значит простые массивы, не имеющие у себя в багаже различных функций. В этом уроке мы пройдем нечистые массивы - векторы.
Что такое вектор (vector)
Вектор - это структура данных, которая уже является моделью динамического массива.
Давайте вспомним о том, что для создания динамического массива (вручную) нам нужно пользоваться конструктором new и вдобавок указателями. Но в случае с векторами всего этого делать не нужно. Вообще, по стандарту пользоваться динамическим массивом через конструктор new - не есть правильно. Так как в компьютере могут происходить различные утечки памяти.
Как создать вектор (vector) в C++
Сначала для создания вектора нам понадобится подключить библиотеку - , в ней хранится шаблон вектора.
#includeКстати, сейчас и в будущем мы будем использовать именно шаблон вектора. Например, очередь или стек, не созданные с помощью массива или вектора, тоже являются шаблонными.
Далее, чтобы объявить вектор, нужно пользоваться конструкцией ниже:
vector тип данных > имя вектора>;
- Вначале пишем слово vector .
- Далее в угольных скобках указываем тип, которым будем заполнять ячейки.
- И в самом конце указываем имя вектора.
vector string> ivector;В примере выше мы создали вектор строк.
Кстати, заполнить вектор можно еще при инициализации (другие способы мы пройдем позже - в методах вектора). Делается это также просто, как и в массивах. Вот так:
vectorint> ivector = элемент[0]>, элемент[1]>, элемент[2]>>;После имени вектора ставим знак равенства и скобки, в которых через пробел указываем значение элементов.
Такой способ инициализации можно использовать только начиная с C++11!
Так, чтобы заполнить вектор строками, нам нужно использовать кавычки - "строка" .
Второй способ обратиться к ячейке
Мы знаем, что в векторе для обращения к ячейке используются индексы. Обычно мы их используем совместно с квадратными скобками [] .
Но в C++ есть еще один способ это сделать благодаря функции - at(). В скобках мы должны указать индекс той ячейки, к которой нужно обратиться.
Вот как она работает на практике:
vector int> ivector = 1, 2, 3>; ivector.at(1) = 5; // изменили значение второго элемента cout . at(1); // вывели его на экранДавайте запустим эту программу:
5 Process returned 0 (0x0) execution time : 0.010 s Press any key to continue.Как указать количество ячеек для вектора
Указывать размер вектора можно по-разному. Можно это сделать еще при его инициализации, а можно хоть в самом конце программы. Вот, например, способ указать длину вектора на старте:
vector int> vector_first(5);Так в круглых скобках () после имени вектора указываем первоначальную длину. А вот второй способ:
vector int> vector_second; // создали вектор vector_second.reserve(5); // указали число ячеекПервая строчка нам уже знакома. А вот во второй присутствует незнакомое слово - reserve , это функция, с помощью которой мы говорим компилятору, какое количество ячеек нам нужно использовать.
Вы можете задать логичный вопрос: “А в чем разница?“. Давайте создадим два вектора и по-разному укажем их количество ячеек.
#include #include // подключили библиотеку using namespace std; int main() setlocale(0, ""); vector int> vector_first(3); // объявили // два vector int> vector_second; // вектора vector_second.reserve(3); cout <"Значения первого вектора (с помощью скобок): "; for (int i = 0; i 3; i++) cout [ i] <" "; > cout <"Значения второго вектора (с помощью reserve): " ; for (int i = 0; i 3; i++) cout [ i] <" "; > system("pause"); return 0; >Значения первого вектора (с помощью скобок): 0 0 0 Значения второго вектора (с помощью reserve): 17 0 0 Process returned 0 (0x0) execution time : 0.010 s Press any key to continue.Как видим, в первом случае мы вывели три нуля, а во втором: 17, 0, 0.
Все потому, что при использовании первого способа все ячейки автоматически заполнились нулями.
При объявлении чего-либо (массива, вектора, переменной и т.д) мы выделяем определенное количество ячеек памяти, в которых уже хранится ненужный для ПК мусор. В нашем случае этим мусором являются числа.
Поэтому, когда мы вывели второй вектор, в нем уже находились какие-то рандомные числа - 17, 0, 0. Обычно они намного больше. Можете кстати попробовать создать переменную и вывести ее значение.
Нужно помнить! При использовании второго способа есть некоторый плюс - по времени. Так как для первого способа компилятор тратит время, чтобы заполнить все ячейки нулями.
Как сравнить два вектора
Если в середине программы нам понадобится сравнить два массива, мы, конечно, используем цикл for и поочередно проверим все элементы.
Вектор опять на шаг впереди! Чтобы нам сравнить два вектора, потребуется применить всего лишь оператор ветвления if.
if (vec_first == vec_second) // сравнили! cout <"Они равны!"; > else cout <"Они не равны"; >Конечно, компилятор все равно прогонит эти два вектора по циклу, проверяя ячейки. Но оцените, насколько благодаря этому программа стала компактнее. Разве это не прекрасно?
Вот так бы выглядела программа выше, если бы мы не использовали знак равенства для векторов.
bool flag = true; if (vec_first.size() == vec_second.size()) for (int i = 0; i vec_first.size(); i++) if (vec_first[i] != vec_second[i]) cout <"Они не равны!"; flag = false; break; // выходим из цикла > > > else flag = false; cout <"Они не равны!"; > if (flag) cout <"Они равны!"; > - Сначала мы создали булеву переменную flag равную true . У нее задача такая:
- Если в условии (строки 5 - 10) она станет равна false - то значит эти векторы не равны и условие (строки 14 - 16) не будет выполняться.
- Если же она после цикла (строки 3 - 12) останется равна true - то в условии (строки 14 - 16) мы сообщим пользователю, что они равны.
- В условии (строка 3) проверяем размеры двух векторов на равенство.
- И если условие (строки 5 - 10) будет равно true - то мы сообщим пользователю, что эти два вектора не равны.
Как создать вектор векторов
Понятно, что вам может понадобиться записать числа в двумерный массив. Но зачем использовать массив, если можно оперировать векторами.
Сейчас вы узнаете, как создать вектор векторов или простым языком массив векторов.
vector vector тип данных > >;Как можно увидеть, нам пришлось только добавить слова vector и еще его .
А чтобы указать количество векторов в векторе, нам потребуется метод resize() .
vector vector int> > vec; vec.resize(10); // десять векторовНо есть еще одни способ добавления векторов в вектор. Для этого способа мы будем использовать функцию push_back() (читайте ниже, что она делает).
vec.push_back(vector int>());- В аргументах функции push_back() находится имя контейнера, который мы хотим добавить. В нашем случае - vector .
- А дальше идет тип контейнера - .
- И все заканчивается отрывающей и закрывающей скобкой () .
Для двумерного вектора тоже можно указать значения еще при инициализации:
vector vector int> > ivector = 1, 4, 7>, 2, 5, 8>, 3, 6, 9>>;- это значения элементов первого массива (первого слоя). Такие блоки значений, как , должны разделяться запятыми.
Методы для векторов:
Сейчас мы разберем некоторые методы, которые часто используются вместе с векторами. Метод - это функция, которая относится к определенному STL контейнеру.
В нашем случае этим STL контейнером является вектор. Если вы дальше собираетесь оперировать векторами - лучше все перечисленные функции запомнить.
Если нам требуется узнать длину вектора, понадобится функция - size() . Эта функция практически всегда используется вместе с циклом for.
for (int i = 0; i ivector.size(); i++) // . >Также, если нам требуется узнать пуст ли стек, мы можем использовать функцию - empty() .
- При отсутствии в ячейках какого-либо значения это функция возвратит - true .
- В противном случае результатом будет - false .
Вот пример с ее использованием:
if (ivector.empty()) // . >2) push_back() и pop_back()
Как мы сказали выше, у векторов имеются методы, которые помогают оптимизировать и улучшить жизнь прог