§ 9.3. Структура данных – массив. Контейнеры vector и array. Типы pair и tuple

Школьный курс python
Содержание

Что такое массив и для чего он нужен?

Необходимость использования структур данных типа массива вытекает из практических соображений. Представьте, что вам для решения некоторой задачи (например, для обработки базы данных клиентов, описания координат объектов и проч.) требуется наличие в программе не 3-5 переменных, а десятки, сотни, а то и более объектов для хранения данных! Работать в программе с таким количеством переменных становится невозможным. Проще определить их в виде единого именованного объекта и обращаться, по мере необходимости, к отдельным его элементам, которые организованы простой нумерацией (иными словами, проиндексированы). Поскольку все элементы последовательности имеют общее имя, то к отдельному элементу можно получить доступ по имени и индексу, поэтому элемент последовательности называется также индексированной переменной. С таким массивом данных работать очень удобно, так как он обрабатывается как единое целое с помощью циклов. Наибольшей производительности в работе с массивом можно достичь только в том случае, если все элементы массива относятся к одному и тому же типу. Тогда, для хранения всей совокупности элементов, можно выделить непрерывную область памяти в которой элементы будут располагаться в соседних ячейках, последовательно. Такая структура данных называется линейный или одномерный массив. Линейный массив соответствует математической абстракции вектор.

Си-массивы

Итак, массив (англ. – array) – это структура данных, содержащая совокупность элементов, принадлежащих одному и тому же типу с общим для всех элементов именем. Элементы массива пронумерованы индексами. Индексирование элементов начинается с 0. Обращаться к элементам массива можно с помощью имени и квадратных скобок. Т. е., если массив имеет имя ar, то первый элемент – это ar[0], второй – ar[1] и т. д. Фактически, элементы массива ничем не отличаются от обычных переменных, поэтому иногда их называют индексированными переменными. Они могут участвовать в выражениях как обычные переменные, например:

a[0] = a[1] + a[2];
if (a[0] > a[1]) { ... }
a[0]++;

В C++ для описания базового типа массива используется такое же описание массива, как и в языке С, поэтому такой массив мы будем называть Си-массивом.
Описание массива производится следующим образом:

Тип Имя [Количество элементов]; 

Например:

int mass[20];
float a[5];

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

int ar[10] {5, 4, 11, 9, 0, 10, 3, 8, 2, 13};
float omega[] {1.02, 4.2, 3.7, 2.1};
int alpha[100] {};
Количество элементов инициализируемого массива (omega) можно опустить, компилятор сам подсчитает их количество. Элементы массива alpha будут иметь значение 0 (значение по умолчанию).

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

mas[0] = 15;
omega[2] = 0.3;

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

Ввод и вывод элементов C-массива
// Клавиатурный ввод
// Обычный for
for (size_t i = 0; i < size(ar); i++) {
    cin >> ar[i];
}
// Диапазонный for
for (auto &r : ar) {
   cin >> r;
}
// Вывод в строку
// Обычный for
for (size_t i = 0; i < size(ar); i++) {
    cout << ar[i] << " ";
}
// Диапазонный for
for (auto r : ar) {
   cout << r << " ";
}
Глобальная функция std size() возвращает размер массива. Тип возвращаемого значения size_t. Заполнение случайными числами см. в приложении.

Покажем на примере.
Задача 1. Создать массив из 10 элементов и вывести адреса памяти, соответствующие этим элементам.

Программа 9.3.1
#include <iostream>
using namespace std;

int main() {
	int ar[10];
	for (int i = 0; i < 10; i++) { // Организуем диалог
		cout << "ar[" << i << "] = "; // Строка приглашение
		cin >> ar[i]; // Ввод элемента
	}
	for (int i = 0; i < 10; i++) {
		cout << "Адрес ar[" 
			 << i 
			 << "] => "
			 << &ar[i] // Выводим адрес элемента
			 << endl;
	}
	return 0;
}

Ввод и возможный вывод

ar[0] = 5
ar[1] = 1
ar[2] = 8
ar[3] = 6
ar[4] = 4
ar[5] = 3
ar[6] = 0
ar[7] = 7
ar[8] = 5
ar[9] = 3
Адрес ar[0] => 0x7ffdeb941470
Адрес ar[1] => 0x7ffdeb941474
Адрес ar[2] => 0x7ffdeb941478
Адрес ar[3] => 0x7ffdeb94147c
Адрес ar[4] => 0x7ffdeb941480
Адрес ar[5] => 0x7ffdeb941484
Адрес ar[6] => 0x7ffdeb941488
Адрес ar[7] => 0x7ffdeb94148c
Адрес ar[8] => 0x7ffdeb941490
Адрес ar[9] => 0x7ffdeb941494

Рассмотрим пример использования с массивом диапазонного for (range-based for).
Задача 2. Дан массив. Увеличить в три раза четные элементы массива, а нечетные элементы увеличить на 5.

Программа 9.3.2
#include <iostream>
using namespace std;

int main() {
	int ar[] {12, 14, 10, 22, 32, 41, 85, 10, 12, 23};
	for (auto &r : ar) {
		if (r % 2 == 0)
			r *= 3;
		else
			r += 5;
	}
	for (auto r : ar)
		cout << r << " ";
	cout << endl;
	return 0;
}

Вывод

36 42 30 66 96 46 90 30 36 28 

В переменной r перебираются все элементы массива ar. Эта переменная может быть как ссылочного типа (первый цикл), так и обычной (второй цикл). Если используется переменная не ссылочного типа, то элементы массива будут копироваться (следовательно, изменять элементы массива будет невозможно).

Следует заметить, что средства стандартной библиотеки (STD) доступны и для C-массивов. Например, можно получить итераторы и через них иметь доступ ко множеству функций библиотеки обобщенных алгоритмов. Выше мы показали использование функции size для определения размера массива, также принадлежащей std.

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

Контейнеры vector и array

Контейнеры

Контейнер – это шаблонный класс (англ. – class template) или абстрактный тип, объектом которого является реализация какой-либо абстрактной структуры данных. Назначение контейнера – это организация данных в памяти и предоставление доступа к этим данным. Организация памяти сильно зависит от типа реализуемой структуры данных. Разумеется, такие структуры данных можно реализовать и самостоятельно, на основе стандартных языковых средств. Но контейнер, вкупе с другими средствами STD, предоставляет большой набор уже готовых инструментов для работы с данными. Поскольку контейнер является шаблоном, то работа с различными типами данных будет производиться единообразно. Типами данных, хранящимися в контейнере, могут быть фундаментальные типы, абстрактные типы (создаваемые разработчиком), типы STD, а также объекты других контейнеров. На этом уроке мы познакомимся с двумя последовательными контейнерами array и vector.

array

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

#include <array>

Тип array включает шаблонный параметр, который заключается в угловые скобки ("<", ">"). В нём передаются сведения о типе данных элементов контейнера и их количестве:

array<тип, размер> имя;

Размер массива является константным выражением.
Если при определении объекта типа array начальные значения (элементов) не передаются, то создается массив элементов значения которых не определены (но ячейки памяти будут зарезервированы).
Инициализировать массив списком инициализации можно следующим образом:

array<int, 5> ar1 {};
array<int, 5> ar2 {8};
array<int, 5> ar3 {1, 2, 3, 4, 5};
// Начиная с С++17, шаблонный параметр можно опустить:
array ar4 {1, 2, 3, 4, 5};

В первой строке мы получим массив из 5 нулевых элементов. Во второй - значением 8 будет инициализирован первый элемент, остальные - значением по умолчанию.
Объекты класса array можно создавать копированием другого объекта array. В этом случае, типы объектов должны совпадать:

array<int, 5> ar2 {3, 9, 7, 6, 1};
array<int, 5> ar1(ar2); // или
// array<int, 5> ar1 = ar2;

Ввод и вывод массива array полностью аналогичен вводу и выводу C-массива (см. выше). Покажем это на примере.
Задача 3. Дан массив случайных чисел, состоящий из 20 элементов. Вывести сначала только элементы с четными индексами, а затем с нечетными, но в обратном порядке.

Об использовании генератора случайных чисел см. в приложении. Использование типа int вместо size_t, для счетчика в цикле вывода нечетных позиций, обусловлено тем, что на последнем шаге цикла произойдет выход за границы диапазона типа size_t, что приведет к ошибке в программе. См. ниже вариант этой программы с итераторами.
Программа 9.3.3
#include <iostream>
#include <array>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

int main() {
    // Определяем системный момент времени
    int seed = system_clock::now().time_since_epoch().count();
    default_random_engine rnd(seed); // Инициализируем генератор
    // Включаем функцию равномерного распределение сл. чисел 
    // и определяем промежуток [10;99]
    uniform_int_distribution<int> uid(10, 99);
    // Определение массива из 20 эл-тов
    array<int, 20> ar {};
    // Заполняем массив случайными числами
    // и выводим в строку
    for (auto &r : ar) {
        r = uid(rnd);
        cout << r << " ";
    }
    cout << endl;
    // Решение
    for (size_t i = 0; i < ar.size(); i+=2)
        cout << ar[i] << " "; // Четные позиции
    cout << endl;
    for (int i = ar.size()-1; i > 0; i-=2)
        cout << ar[i] << " "; // Нечетные позиции
    cout << endl;
    return 0;
}

Возможный вывод

90 97 23 94 99 55 57 61 53 57 69 89 87 80 75 82 76 10 14 81 
90 23 99 57 53 69 87 75 76 14 
81 10 82 80 89 57 61 55 94 97 

Ниже в таблице 1 перечислены общие методы для контейнеров array и vector. Метод - это функция, которая реализована в классе. Функция класса вызывается с помощью дот-нотации (операция ".") в формате:

имя_объекта.имя_функции()
Большинство методов общие для всех последовательных контейнеров, но запоминать их сейчас необязательно! В среде программирования доступные методы класса появляются автоматически, в виде раскрывающегося списка, после ввода операции "точка". Вам нужно только выбрать подходящий метод. Также появится подсказка о том, какие аргументы можно использовать в данном методе. Основные методы запомнить не сложно, так как они имеют понятные имена.
Таблица 1. Общие методы array и vector
Метод Описание
at Ссылка на элемент в указанной позиции с проверкой выхода за границы массива
operator[] Ссылка на элемент в указанной позиции без проверки выхода за границы
front Ссылка на первый элемент
back Ссылка на последний элемент
data Возвращает указатель на базовый массив, служащий хранилищем элементов
begin
cbegin
Возвращает итератор в начале массива
end
cend
Возвращает итератор в конце массива
rbegin
crbegin
Возвращает реверсивный итератор в начале массива
rend
crend
Возвращает реверсивный итератор в конце массива
empty Проверяет, имеются ли в массиве элементы (true, если пустой)
size Размер массива (возвращает беззнаковый тип size_t)
max_size Возвращает максимальное количество элементов, которое может содержать массив
swap Производит обмен элементами между массивами

Помимо вышеперечисленных методов, класс array предоставляет и другие полезные функции и методы:

  • fill – (метод класса) заполняет контейнер указанным значением;
  • operator== – лексикографическое сравнение на равенство
  • to_array – (функция, не являющаяся методом) создает объект array из встроенного массива (требует C++20)
vector

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

#include <vector>;

В классах контейнеров определены специальные методы коструктор и деструктор. Конструктор (англ. - constructor) — специальный метод, вызываемый при создании объекта. Основная задача конструктора - произвести инициализацию. Если для array конструктор и деструктор класса определены неявно, то для vector эти методы класса определены явно, при этом конструктор очень вариативен.
Так выглядит конструктор по умолчанию для вектора:

vector<type> name;

Он создает пустой контейнер. Другие виды конструкторов принимают инициализирующие аргументы. Инициализировать вектор можно следующими способами:

Списком инициализации
vector<int> vec {1, 2, 3, 4, 5};
vector<type> vec2(std::initializer_list init);
Класс array не может обработать существующий объект std::initializer_list, так как в нем нет соответствующего конструктора. Но можно скопировать содержимое списка инициализации с помощью итераторов и функции copy():

initializer_list iList {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
array ar1 {};
copy(begin(iList), end(iList), ar1.begin())
Копированием или перемещением другого вектора
// Копирующий конструктор
vector<type> vec2(vec1); // или
// vector<type> vec2 = vec1;
// Перемещение
vector<type> vec3(std::move(vec1)); 
Копиями элемента
vector<type> vec(n, el);
Инициализация n копиями элемента el. Для array используется функция fill()
Итераторами в интервале [first, last)
vector<type> vec(first, last);
Сведения об итераторах см. ниже.

Определение вектора, с инициализацией или без таковой, иначе называется созданием объекта или экземпляра класса vector.
Деструктор - это специальный метод, который разрушает объект, созданный конструктором. После вызова деструктора используемая память освобождается (объект удаляется из программы).

Если элементы являются указателями, то объекты, на которые они указывают, не уничтожаются.

Имя деструктора совпадает с именем класса, но ему предшествует символом "~":

vec.~vector();

Вектор наиболее популярный контейнер, однако его использование не всегда оправдано. Для вектора, как динамического массива, существуют два важных понятия - это размер и объем. Размер вектора — это количество элементов в контейнере, а объём — это объем памяти используемой контейнером. Если при вставке в вектор новых элементов его размер становится больше его объёма, то происходит перераспределение памяти. Это означает, что будет выделена новая облась памяти, способная принять новый размер массива, а также произведено копирование элементов в эту новую область.

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

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

vector<type> vec(count);

Второй заключается в использовании метода reserve(), который предназначен для резервирования памяти заранее:

vector<type> vec;
vec.reserve(count);

Для работы с размером и объемом вектора (помимо size, max_size и epmty) определены следующие методы:

  • reserve – устанавливает минимально возможное количество элементов в векторе
  • capacity – возвращает количество элементов, которое может содержать вектор до того, как ему потребуется выделить больше места.
  • shrink_to_fit – уменьшает количество используемой памяти за счет освобождения неиспользованной, т. е. уменьшает capacity до size (необязательно, что будет выполнен)
Для вектора определены методы-модификаторы, которые изменяют содержимое контейнера. Эти методы перечислены в таблице 2.

Обратите внимание! Если в классе контейнера определен метод выполняющий задачу аналогичную функции библиотеки обобщенных алгоритмов algorithm, то необходимо применять метод класса, а не функцию библиотеки, так как метод класса работает более эффективно.
Таблица 2. Методы-модификаторы контейнера vector
Метод Описание
clear Очищает контейнер (объем не будет изменен)
insert Вставляет элементы
emplace Создает элементы на месте (в позиции итератора). Не использует копирование или перемещение.
emplace_back Создает элементы на месте в конце массива
erase Удаляет элементы
push_back Добавляет элемент в конец
pop_back Удаляет последний элемент
resize Изменяет размер массива
assign Заменяет содержимое на новое

Задача 4. Дан массив случайных чисел, состоящий из 20 элементов и число k. Обнулить те его элементы, которые больше k.

Программа 9.3.4
#include <iostream>
#include <vector>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

int main() {
    int seed = system_clock::now().time_since_epoch().count();
    default_random_engine rnd(seed);
    uniform_int_distribution<int> uid(1, 9);
    vector<int> vec;
    vec.reserve(20);
    // Использовать диапазонный for нельзя!
    // так как массив увеличивает свой размер
    for (size_t i=0; i < 20; i++)
		vec.push_back(uid(rnd));
	// Во всех остальных случаях 
	// использовать диапазонный for можно
	// Выводим исходный массив
	for (auto r : vec)
		cout << r << " ";
    cout << endl;
    // Решение задачи
    int k;
    cout << "k = "; cin >> k;
    for (auto &r : vec)
		if (r > k)
			r = 0;
	for (auto r : vec)
		cout << r << " ";
    cout << endl;
    
    return 0;
}

Обратите внимание! Диапазонный цикл for нельзя применять в тех задачах, в которых массив vector может изменить свой размер (в любую сторону)! В других же задачах его применять можно (и даже нужно, поскольку код становится намного компактнее).

Итераторы

Итератор (англ. - iterator) - это такой объект, который позволяет перебирать элементы массива, переходя от одного элемента - к другому.

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

iter1
Для получения итератора существуют специальные функции begin() и end(). Функция begin() возвращает итератор, указывающий на начало массива (первый элемент), а end() возвращает итератор, указывающий на позицию, следующую за последним элементом. Таким образом, функции begin() и end() определяют полуоткрытый интервал [first, last).
Перед использованием итераторов их необходимо определить. Тип итератора достаточно сложный, поэтому обычно используют спецификатор auto. Как мы уже упоминали, итераторы можно определять и для C-массивов.

// Для C-массива:
auto first1 = begin(ar1);
auto last1  = end(ar1);
// Для контейнеров array и vector:
auto first2 = ar2.begin();
auto last2  = ar2.end();

где first1, last1, first2 и last2 - это имена итераторов, а ar1 и ar2 - имена массивов.
Для перемещения итератора по элементам массива используется операция ++, применяемая к итератору first (обычно, итератор end не перемещается, но это возможно):

first++

Перемещение итератора по элементам массива можно сравнить с перемещением фишки в настольной игре

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

*first

Эти операции можно объединить (поскольку ассоциативность обеих операций слева-направо):

*first++

Это выражение означает, что сначала будет выведен элемент (операция разыменования), а затем произойдет переход к следующему элементу.
Итераторы удобно использовать для контроля выхода за границы массива (что равносильно ошибке, приводящей к краху приложения). В этом случае, для обхода массива, лучше всего подходит цикл while. Рассмотрим пример использования итераторов в программе.
Задача 5. Заполнить массив членами арифметической прогрессии, первый член которой равен a, а разность q.

Программа 9.3.5
#include <iostream>
#include <array>
using namespace std;

int main() {
    int a, q;
    cout << "a = "; cin >> a;
    cout << "q = "; cin >> q;
    array<int, 20> ar;
    // Получаем итераторы
    auto first = ar.begin();
    auto last  = ar.end();
    while (first != last) {
        // Присваиваем элементу массива значение n-го члена прогрессии
        *first = a;
        // увеличиваем значение n-го члена на разность
        a += q;
        // переходим к следующему
        first++;
    }
    // Выводим элементы массива
    for (auto r : ar)
        cout << r << " ";
    cout << endl;
    return 0;
}

Для итераторов существует реверсивная форма. Эта форма не имеет каких-либо принципиальных различий по сравнению с обычной формой. Для создания реверсивных итераторов используют функции rbegin() и rend(). В этой форме итератор rbegin указывает на последний элемент массива, а rend - на элемент предшествующий первому. Иными словами, мы как бы разворачиваем массив. Ясно, что такая форма предназначена для обхода массива не с начала, а с конца. Решим задачу 3 с помощью итераторов.

Программа 9.3.6
#include <iostream>
#include <array>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

int main() {
    int seed = system_clock::now().time_since_epoch().count();
    default_random_engine rnd(seed);
    uniform_int_distribution<int> uid(10, 99);
    array<int, 20> ar {};
    for (auto &r : ar) {
        r = uid(rnd);
        cout << r << " ";
    }
    cout << endl;
    // Определяем обычные итераторы
    auto first = ar.begin();
    auto last = ar.end();
    while (first < last) {
		cout << *first << " ";
		first += 2;
	}
    cout << endl;
    // Определяем реверсивные итераторы
    auto rfirst = ar.rbegin();
    auto rlast = ar.rend();
    while (rfirst < rlast) {
		cout << *rfirst << " ";
		rfirst += 2;
	}
    cout << endl;
    return 0;
}
Обратите внимание, что программный код вывода элементов массива фактически повторяется. Но использовать обычную функцию здесь нельзя, так как типы итераторов обычных и реверсивных отличаются. Чтобы абстрагироваться от типов данных используют шаблонные функции, но эта тема выходит за рамки нашего курса. См. здесь.

Типы pair (пара) и tuple (кортеж)

pair

std::pair - это класс, который предоставляет возможность хранить два разнородных объекта, как единое целое. pair используется в разных местах STD, в частности, в алгоритме minmax(), методе класса set equal_range(), для работы с элементами ассоциативных контейнеров, которые также представляют из себя пары: Ключ: Значение. Например, с помощью пары удобно описывать положение объекта на плоскости (принимать или возвращать координаты x и y в функциях).
Для создания объекта пары используется следующий синтаксис:

pair<T1, T2> p1;
pair<T1, T2> p2(val1, val2);
pair<T1, T2> p3(p1);

где T1 и T2 - это типы элементов пары.
Начиная с C++17 можно не использовать в определении шаблонные параметры (передающие тип), если производится инициализация пары (или кортежа, см. ниже):

pair p4('A', 17);
Таблица 3. Операции и функции pair
Функция Описание
operator= присваивание (с возможностью неявного преобразования типов)
p.first доступ к первому значению пары (по ссылке)
p.second доступ ко второму значению пары (по ссылке)
p.swap(other_p), swap(p, other_p) обмен значениями между p и other_p
operator== операция сравнения на равенство
make_pair(val1, val2) возвращает пару

Задача 6. В массив вводятся n элементов - значения пар координат x и y точек в декартовой системе координат. Определить, какая из точек ближе всего находится к центру координат. Выведите координаты этой точки.

Программа 9.3.7
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

double dist(pair<double, double>);

int main(){
    int n;
    cout << "n = "; cin >> n;
    vector<pair<double, double>> ar;
    ar.reserve(n);
    // Заполняем массив
    for (int i = 0; i < n; i++) {
        double x, y;
        cin >> x >> y;
        ar.emplace_back(x, y);
    }
    // Вычисляем
    double min = 1000.;
    int j;
    for (size_t i = 0; i < ar.size(); i++) {
        if (dist(ar[i]) < min) {
            min = dist(ar[i]);
            j = i;
        }
    }
    cout << "На минимальном расстоянии от центра\n"
            "находится точка: "
         << j + 1
         << "\nКоординаты:\n"
         << "x = " << ar[j].first << "\n"
         << "y = " << ar[j].second << endl;
    return 0;
}

double dist(pair<double, double> xy) {
    auto [x, y] = xy; // распакова пары
    return hypot(pow(x, 2), pow(y, 2));
}

Ввод/вывод

n = 5
9 7
5 5
6 1
2 3
1 4
На минимальном расстоянии от центра
находится точка: 4
Координаты:
x = 2
y = 3

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

Присваивать значение паре можно с помощью простого синтаксиса, например:

pair<int, int> p3;
p3 = {2, 4};
tuple

Шаблонный класс std::tuple (кортеж) представляет собой набор разнородных значений фиксированного размера (два и более). Таким образом, кортеж является обобщением std::pair. Также как и pair, кортеж удобно применять, если из функции нужно принять более одного значения или передавать несколько аргументов в виде единого объекта. Также как и пара, кортеж может быть элементом массива. Доступ к элементам кортежа осуществляется с помощью функции get(), в шаблонном параметре которой указывается индекс. Однако, следует отличать кортеж от массива. Например, в кортеже не используется операция [] (обращение по индексу). Элементы кортежа нельзя вывести с помощью цикла for (включая диапазонного), наподобие вывода элементов массива.
Для начала работы с tuple необходимо включить одноименный заголовок:

#include <tuple>

Использовать декомпозицию можно и для кортежа. Минус такого подхода в том, что если один или несколько элементов кортежа не будут нужны при распаковке, весь набор переменных все равно придется создавать. Для того, чтобы при распаковке получать только нужные элементы кортежа, используется функция tie() и "заглушка" ignore. В этом случае переменные должны быть объявлены до распаковки.

tuple<string, int, double> t;
t = {"Sidorova", 987456, 4.5};
string S;
double d;
tie(S, ignore, d) = t;
cout << S << '\n'
     << d << endl;

В этом фрагменте аргументы функции tie (S и d) являются ссылками на переменные, которые будут инициализированы соответствующими значениями кортежа с индексами 0 и 2. Первый индекс будет проигнорирован.
Пример работы с tuple показан в программе ниже.

Программа 9.3.8
#include <iostream>
#include <iomanip>
#include <tuple>
#include <array>
using namespace std;

int main() {
    // Определение первого кортежа с инициализацией;
    // шаблонный параметр можно опустить:
    tuple t1 {"Ivanov", 123456, 4.2};
    // Определение второго и третьего кортежа;
    // шаблонный параметр опускать нельзя:
    tuple<string, int, double> t2, t3;
    // Получаем элементы второго кортежа
    // с помощью get()
    get<0>(t2) = "Petrov";
    get<1>(t2) = 654321;
    get<2>(t2) = 4.8;
    // Получаем элементы третьего кортежа;
    // так более компактно:
    t3 = {"Bashirov", 987456, 4.5};
    // Заносим в массив
    array<tuple<string, int, double>, 3> ar;
    ar[0] = t1;
    ar[1] = t2;
    ar[2] = t3;
    // Большое количество кортежей нужно получать в цикле
    // Выводим циклом:
    for (auto r : ar) {
        // Определяем переменные для распаковки:
        string name;
        int id;
        double prod;
        // Распаковка кортежа:
        tie(name, id, prod) = r;
        // Вывод:
        cout << setw(8) << name
             << setw(9) << id
             << setw(5) << prod
             << endl;
    }

    return 0;
}

Вывод

  Ivanov   123456  4.2
  Petrov   654321  4.8
Bashirov   987456  4.5

Задачи с массивами

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

I. Поиск или подсчет элементов по критерию

Задача 7. Дан массив из 50 элементов ar и число n. Найти элемент массива, который наиболее близок к числу k (т. е., такой элемент n, для которого величина |k – n| является минимальной).

Программа 9.3.9
#include <iostream>
#include <array>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

// Функция получения случайного числа
int RND(int a, int b) {
    int seed = system_clock::now().time_since_epoch().count();
    static default_random_engine rnd(seed);
    static uniform_int_distribution<int> uid(a, b);
    return uid(rnd);
}

// Решение задачи
// Функция pos возвращает позицию 
// искомого элемента
size_t pos(array<int, 50> &mas, int d) {
    int minD = 100;
    size_t posEl;
    for (size_t i = 0; i < mas.size(); i++) {
        if (abs(mas[i]-d) < minD)
        {
            minD = abs(mas[i]-d);
            posEl = i;
        }
    }
    return posEl;
}

int main() {
    array<int, 50> ar {};
    // Заполняем и выводим исходный массив
    for (auto &r : ar) {
        r = RND(10, 1000);
        cout << r << " ";
    }
    int k;
    cout << "\nk = "; cin >> k;
    // Вызываем нашу функцию
    // На выводе:
    cout << "Элемент ar["
         << pos(ar, k)
         << "] => "
         << ar[pos(ar, k)]
         << endl;
    return 0;
}

Вывод

902 341 56 620 334 391 174 645 519 421 902 96 667 955 239 747 744 752 322 577 997 129 991 469 550 44 46 408 16 344 387 68 853 275 178 93 927 762 251 269 555 464 822 187 16 486 758 589 143 539 
k = 300
Элемент ar[18] => 322
II. Анализ элементов массива

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

Программа 9.3.10
/* Если в массиве встретятся две равные по размеру цепочки,
 * при этом они будут иметь максимальную длину, то будет
 * выведено начало первой такой найденной цепочки
 */
#include <iostream>
#include <array>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

// Функция получения случайного числа
int RND(int a, int b) {
    int seed = system_clock::now().time_since_epoch().count();
    static default_random_engine rnd(seed);
    static uniform_int_distribution<int> uid(a, b);
    return uid(rnd);
}

// Решение задачи
// Функция range возвращает std::pair:
// длина цепочки и её начало
pair<size_t, size_t> range(array<int, 50> &mas) {
    size_t maxD = 0, k = 0, j;
    for (size_t i = 0; i < mas.size(); i++) {
        if (mas[i] == mas[i+1]) // Если соседние элементы равны,
            ++k; // то считаем длину цепочки
        else {
            ++k; // добавляем оставшийся
            if (k > maxD) { // Проверяем длину цепочки:
                maxD = k; // если нашли длиннее, то сохраняем длину
                j = i; // и позицию (пред)последнего элемента
            }
            k = 0; // обнуляем счетчик
        }
    }
    return make_pair(maxD, j + 1 - maxD);
}

int main() {
    array<int, 50> ar {};
    // Заполняем и выводим исходный массив
    for (auto &r : ar) {
        r = RND(0, 1);
        cout << r << " ";
    } // Распаковка пары:
    auto [d, n] = range(ar);
    cout << "\nДлина цепочки => "  << d
         << "\nначало цепочки => " << n
         << endl;
    return 0;
}

Вывод

0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 
Длина цепочки => 6
начало цепочки => 21
III. Преобразование массива

Задача 8. Дан массив из 50 элементов ar. Развернуть в обратном порядке элементы находящиеся между ar[k] и ar[m] элементами, включительно (k < m).

Программа 9.3.11
#include <iostream>
#include <array>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

// Функция получения случайного числа
int RND(int a, int b) {
    int seed = system_clock::now().time_since_epoch().count();
    static default_random_engine rnd(seed);
    static uniform_int_distribution<int> uid(a, b);
    return uid(rnd);
}

// Функция обмена значениями эл-тов
void Swap (int &a, int &b) {
    int buf = a;
    a = b;
    b = buf;
}

// Решение задачи
// Функция rot - это процедура
void rot(array<int, 50> &mas, int x, int y) {
    for (int i = 0; i < (y-x+2)/2; i++) {
        Swap(mas[x+i], mas[y-i]);
    }
}

int main() {
    array<int, 50> ar {};
    // Заполняем и выводим исходный массив
    for (auto &r : ar) {
        r = RND(10, 99);
        cout << r << " ";
    }
    int k, m;
    cout << "\nk = "; cin >> k;
    cout << "m = "; cin >> m;
    rot(ar, k, m);
    // Вывод измененного массива
    for (auto &r : ar) {
        cout << r << " ";
    }
    cout << endl;
    return 0;
}

Вывод

70 71 39 17 12 66 19 35 44 15 21 70 65 65 89 10 64 90 54 95 47 31 11 13 85 17 14 15 20 80 60 88 46 67 16 41 14 99 50 20 63 95 99 76 12 11 38 35 85 18 
k = 2
m = 10
70 71 21 15 44 35 19 66 12 17 39 70 65 65 89 10 64 90 54 95 47 31 11 13 85 17 14 15 20 80 60 88 46 67 16 41 14 99 50 20 63 95 99 76 12 11 38 35 85 18 
Для передачи C-массива в функцию по ссылке используется следующий синтаксис:

// Прототип
type & fun(int[]);
// Вызов
fun(ar)
// Определение
type & fun(int mas[]) {
    ...
}

Т. е. используются квадратные скобки без указания количества элементов.

Приложение

Заполнение массива случайными числами

Заполнение массива случайными числами

Для решения задач с массивами, содержащими большое количество элементов (такой массив за реальный промежуток времени заполнить с клавиатуры невозможно), возникает необходимость их быстрого заполнения данными каким-либо способом. Для этих целей используется генератор случайных чисел. Такой генератор реализован в Си-библиотеке cstdlib и библиотеке C++ random. Рассмотрим оба этих подхода.

Си-подход. Функция rand()

Для получения случайного числа необходимо выполнить следующее. Включить заголовочные файлы:

#include <cstdlib>
#include <ctime>

Библиотека ctime нужна для получения момента времени, который используется как отправная точка для последовательности случайных чисел. Непосредственно случайное число возвращает функция rand(). Значение числа лежит в промежутке от 0 до RAND_MAX (константа со значением максимального целого числа, возвращаемого функцией rand()), включительно.
Чтобы получать значения случайных чисел на определенном промежутке (включающим, возможно, и отрицательные числа) используется выражение:
A + rand() % (B - A + 1),
где А и B – это границы отрезка [A, B], множество значений которого используется для создания последовательности случайных чисел.
Функция rand() выдает машиннозависимую последовательность. На одном и том же компьютере будет генерироваться одна и та же последовательность случайных чисел. Чтобы избежать повторяющегося результата, используют две функции: srand() – инициализирующую генератор начальным значением и time(), которая, с аргументом 0, возвращает количество секунд прошедших с 01.01.70 г. (время UNIX). Это обеспечивает генерацию разных числовых последовательностей, что важно для решения задач. В итоге, код программы, в которой производится заполнение массива случайными числами, будет выглядеть следующим образом:

Программа 9.3.12
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

int main() {
	srand(time(0));
	int ar[100];
	// Ввод элементов
	for (int i = 0; i < 100; i++)
		ar[i] = 10 + rand() % 90; // [10; 99]
	// Вывод элементов
	for (int i = 0; i < 100; i++)
		cout << ar[i] << setw(3);
	return 0;
}
Использование библиотеки random

В библиотеке random определены два типа взаимосвязанных классов:

  • random-number engine – процессоры (генераторы) случайных чисел и
  • random-number distribution – распределения случайных чисел

Мы будем использовать генератор случайных чисел по умолчанию, который называется default_random_engine. Объект генератора может быть проинициализирован начальным значением (в программе ниже – это по прежнему будет момент времени).
Для определения диапазона генерации случайных чисел необходимо использовать распределение случайных чисел.
Таких распределений тоже несколько и все они описываются математическим формулами. Мы будем использовать равномерное распределение случайных величин с помощью uniform_int_distribution (равномерное распределение случайных целых чисел). В качестве аргумента, объекту класса распределения передается промежуток на котором должна построиться последовательность случайных чисел. Эта последовательность, также, как и в предыдущем случае, машиннозависимая. Для создания уникального начального значения можно использовать библиотеку ctime (аналогично предыдущему примеру), но мы будем использовать другую библиотеку STD – chrono. В результате, наша программа будет выглядеть следующим образом:
Задача 9. Заполнить массив случайными числами из отрезка [10, 99].

Программа 9.3.13
#include <iostream>
#include <iomanip>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

int main() {
	int ar[100];
	int seed = system_clock::now().time_since_epoch().count();
	default_random_engine rnd(seed);
	uniform_int_distribution<int> d(10, 99);
	for (int i = 0; i < size(ar); i++)
		ar[i] = d(rnd);
	cout << "Элементы массива:" << endl;
	for (int i = 0; i < size(ar); i++)
		cout << ar[i] << setw(3);
	return 0;
}
Более подробные сведения о библиотеке chrono см. здесь.
Примеры решения задач
Задача 10. Дан массив. Определить:

  1. среднее арифметическое элементов массива;
  2. количество элементов меньших k.
  3. Поменять местами максимальный и минимальный элементы массива

Программа 9.3.14

#include <iostream>
#include <array>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

int main() {
//============================= 1 =============================//
	int seed = system_clock::now().time_since_epoch().count();
    default_random_engine rnd(seed);
    uniform_int_distribution<int> d(10, 99);
    int s = 0, k;
    array<int, 20> ar {};
    cout << "Исходный массив:" << endl;
    for (auto &i : ar) {
        i = d(rnd);
        cout << i << " ";
        s += i;
    }
    cout << "\nСреднее арифметическое => "
         << float(s) / 20 << endl;
//=========================== 2, 3 ===========================//
    cout << "k = "; cin >> k;
    s = 0;
    int max = ar[0], m = 0;
    int min = ar[0], n = 0;
    for (size_t i = 1; i < ar.size(); i++) {
        if (ar[i] < k) s++;
        if (ar[i] > max) {max = ar[i]; m = i;}
        if (ar[i] < min) {min = ar[i]; n = i;}
    }
    cout << "Элементов < " << k
         << " => " << s << endl;
    s = ar[m];
    ar[m] = ar[n];
    ar[n] = s;
    cout << "Измененный массив:" << endl;
    for (auto &i : ar) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}
Исходный массив:
62 21 79 88 51 79 13 86 56 61 72 97 18 79 83 51 71 38 88 32 
Среднее арифметическое => 61.25
k = 20
Элементов < 20 => 2
Измененный массив:
62 21 79 88 51 79 97 86 56 61 72 13 18 79 83 51 71 38 88 32 
Вопросы
Темы сообщений
Задания А
Задания Б
Задания С
Ссылки
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (3 оценок, среднее: 5,00 из 5)
Загрузка...

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.


Обсуждение закрыто.