Л5. Послідовності C++: масиви, контейнери й текст

Коротко про лекцію

Переходимо від окремих змінних до послідовностей. Порівняємо вбудований масив, std::array, std::vector і std::string, а потім застосуємо їх до меж та двовимірних даних.

У попередніх лекціях одна змінна зберігала одне значення. Цикл повторював дію та змінював стан. Тепер ці дві ідеї поєднаємо: одна структура зберігатиме багато пов’язаних значень, а цикл обходитиме їх послідовно.

Практичний сенс. Більшість програм обробляє набори даних: оцінки, вимірювання, товари, символи тексту. Послідовність дає цим значенням спільну структуру.

1. Коли одного значення вже недостатньо

Нехай треба зберегти кроки за чотири дні. Чотири окремі змінні працюють, але погано масштабуються:

int monday{4200};
int tuesday{5100};
int wednesday{6800};
int thursday{5100};

Ще один день потребує нового імені та нового рядка. Цикл також не може природно пройти такі змінні як єдину послідовність.

Для набору значень спочатку треба визначити, чи може його розмір змінюватися. Це рішення впливає на тип послідовності.

1.1. Вбудований масив має фіксований розмір

C++ має вбудований масив. Його розмір записується в квадратних дужках і не змінюється після створення:

int raw_steps[4]{4200, 5100, 6800, 5100};

Такий масив часто називають вбудованим масивом. У старому та низькорівневому C++ цей запис трапляється часто, тому його треба вміти читати.

Межа застосування вбудованого масиву

Вбудований масив не має методів size() та at(). std::array зберігає розмір у типі та працює як контейнер стандартної бібліотеки. Тому в новому коді курсу використовуватимемо його для фіксованих послідовностей.

Такий запис треба вміти впізнавати під час читання чужого коду. Далі для фіксованого набору віддаватимемо перевагу std::array.

1.2. std::array описує сучасну фіксовану послідовність

Коли кількість елементів відома під час написання програми, зручно використати std::array. Його тип містить два параметри: тип елемента та кількість позицій. Запис std::array<T, N> читаємо як «масив із N елементів типу T».

Запис між кутовими дужками задає параметри типу. Такий конкретний тип створюється з бібліотечного шаблону. Детальніше власні шаблони функцій розглянемо у Л6.

std::array<int, 4> steps{4200, 5100, 6800, 5100};

Тут int є типом елемента, а 4 — кількістю елементів.

Термін: std::array

std::array<T, N> — контейнер із фіксованою кількістю N елементів типу T. Він має size(), at() і підтримує цикл for за елементами.

Для std::array підключаємо заголовок:

#include <array>

std::array<int, 4> завжди має чотири позиції. Методів для додавання п’ятого елемента в нього немає.

1.3. std::vector описує послідовність зі змінним розміром

Якщо кількість елементів може змінюватися під час роботи програми, використовуємо std::vector. Він теж зберігає елементи одного типу.

std::vector<int> steps{4200, 5100, 6800, 5100};

У записі std::vector<int> параметр int задає тип кожного елемента. Кількість елементів визначається початковими значеннями та може змінюватися пізніше.

Щоб використовувати std::vector, програма підключає:

#include <vector>

Як вибрати між std::array і std::vector

Використовуйте std::array, коли кількість позицій є сталою властивістю задачі. Використовуйте std::vector, коли кількість елементів формується або змінюється під час виконання.

1.4. Елементи вже існують після ініціалізації

У записі

std::vector<int> steps{4200, 5100, 6800, 5100};

std::vector одразу має чотири елементи. Їхні значення та порядок визначені списком у дужках.

Інший запис створює порожню послідовність:

std::vector<int> steps;

Тут розмір дорівнює нулю. Нові елементи з’являться лише після окремої операції додавання. Її введемо тоді, коли почнемо будувати нову послідовність.

Ця різниця важлива. Ініціалізований std::vector уже містить позиції, а порожній std::vector ще не має жодної правильної позиції.

1.5. Один цикл обробляє всі елементи

У Л4 ми вже використовували цикл для повторення. Тепер повторення пов’язане з елементами послідовності.

C++ має форму for, яка по черзі бере елементи послідовності. Запис

for (int value : steps) {
    // Тут доступне чергове значення value з послідовності.
}

читаємо так: «для кожного значення зі steps виконай блок». value отримує черговий елемент. Двокрапка : у цьому заголовку відділяє змінну поточного елемента від послідовності.

Цю форму називають циклом for за елементами. Вона працює зі std::array, std::vector, рядками та вбудованими масивами.

Спочатку застосуємо її до сучасної фіксованої послідовності:

#include <array>
#include <iostream>

int main() {
    const std::array<int, 4> temperatures{18, 20, 17, 21};

    int total{0};
    for (int value : temperatures) {
        total += value;
    }

    std::cout << "Сума: " << total << "\n";
}

Той самий синтаксис обходу працює з вбудованим масивом. Це корисно для читання старішого C++:

#include <iostream>

int main() {
    const int temperatures[4]{18, 20, 17, 21};

    int total{0};
    for (int value : temperatures) {
        total += value;
    }

    std::cout << "Сума: " << total << "\n";
}

Тепер використаємо той самий цикл зі std::vector:

#include <iostream>
#include <vector>

int main() {
    const std::vector<int> steps{4200, 5100, 6800, 5100};

    int total{0};
    for (int value : steps) {
        total += value;
    }

    std::cout << "Сума: " << total << "\n";
}

У цьому прикладі цикл бере чотири значення по черзі. Кожне значення один раз додається до total. Індекс не потрібний, тому for за елементами прямо відповідає задачі.

flowchart TD
    V["steps = {4200, 5100, 6800, 5100}"] --> L["for бере черговий елемент"]
    L --> S["додати value до total"]
    S --> Q{"Є ще елементи?"}
    Q -- "так" --> L
    Q -- "ні" --> R["готова сума"]

2. Розмір та індекс описують різні речі

Кожний елемент послідовності має позицію. У C++ позиції рахуються від нуля.

Для чотирьох елементів маємо:

Індекс	0	1	2	3
Значення	18	20	17	21

Розмір дорівнює 4, а останній правильний індекс дорівнює 3.

останній індекс = size - 1

Ця різниця пояснює типову помилку index == size.

flowchart TD
    S["розмір = 4"] --> OK["правильні індекси: 0, 1, 2, 3"]
    S --> BAD["індекс 4 = розмір"]
    BAD --> E["позиції 4 вже немає"]

2.1. size() повертає кількість елементів

Функцію, яка належить об’єкту певного типу, називають методом. Метод викликають через крапку після імені об’єкта.

Термін: метод

Метод описує операцію конкретного об’єкта. Запис temperatures.size() викликає метод size() для std::vector temperatures.

temperatures.size()

Для {18, 20, 17, 21} результат дорівнює 4. Метод size() працює і для std::array, тому обидва стандартні контейнери повідомляють свій розмір однаково.

Коли цикл працює з індексом, умова зазвичай має таку форму.

i < temperatures.size()

Оператор < зупиняє цикл перед індексом size().

2.2. at() читає елемент за індексом

temperatures.at(0)

повертає перший елемент.

temperatures.at(temperatures.size() - 1)

повертає останній елемент для непорожньої послідовності.

at() перевіряє межу індексу. Така перевірка особливо корисна, коли індекс обчислюється під час виконання.

Як читати at(i)

i — позиція вже наявного елемента. Для розміру 4 допустимі індекси 0, 1, 2, 3.

2.3. Квадратні дужки дають швидкий доступ без перевірки меж

У C++ поширений ще один запис доступу до елемента:

temperatures[2]

Оператор [] використовує індекс так само, як at(). Різниця стосується перевірки меж. at(i) перевіряє індекс, а values[i] такої перевірки не гарантує.

Межа оператора []

Запис values[i] вимагає правильного індексу. Вихід за межі контейнера створює невизначену поведінку. Для обчислюваного індексу на початковому етапі віддавайте перевагу at(i).

Вбудований масив не має at(). Тому в старішому коді його елементи зазвичай читають через values[i]. Цей синтаксис треба впізнавати під час читання програм.

Метод size() повертає значення типу std::size_t. Це цілий невід’ємний тип, який стандартна бібліотека використовує для розмірів і позицій.

Термін: std::size_t

std::size_t — невід’ємний цілий тип для розмірів та індексів контейнерів. На цьому етапі використовуйте його разом із size() і уникайте від’ємних обчислень.

Тому індекс у циклі можна оголосити так:

std::size_t i{0};

Поки достатньо використовувати std::size_t разом із size() і не виконувати з ним від’ємні обчислення.

#include <iostream>
#include <vector>

int main() {
    const std::vector<int> temperatures{18, 20, 17, 21};

    std::cout << "Кількість: " << temperatures.size() << "\n";
    std::cout << "Перший: " << temperatures.at(0) << "\n";
    std::cout << "Останній: "
              << temperatures.at(temperatures.size() - 1)
              << "\n";

    for (std::size_t i{0}; i < temperatures.size(); ++i) {
        std::cout << i << ": " << temperatures.at(i) << "\n";
    }
}

2.4. Коли потрібен індекс

Цикл for за елементами зручний для сумування, підрахунку та перевірки кожного значення.

Індекс потрібен, коли задача залежить від позиції:

1. треба надрукувати номер елемента;
2. треба порівняти сусідні позиції;
3. треба звернутися до конкретної позиції;
4. треба синхронно працювати з двома позиційними структурами.

Вибір форми циклу залежить від задачі. Код має показувати, чи важлива позиція.

2.5. Доступ до елемента не створює новий елемент

Операція at(i) читає або змінює вже наявну позицію. Вона не збільшує std::vector.

Наприклад, для std::vector із трьох елементів правильними є індекси 0, 1, 2. Виклик at(3) не означає «додати четвертий елемент». Це звернення за межу.

Для розширення послідовності використовують операцію, яка явно змінює розмір. У цій лекції такою операцією є push_back().

Корисне правило читання коду:

Запис	Питання
values.at(i)	який елемент уже існує на позиції i?
values.size()	скільки елементів існує зараз?
values.push_back(x)	яке нове значення додаємо в кінець?

2.6. Фіксовану послідовність можна заповнити зі стандартного вводу

Коли кількість позицій відома, std::array можна спочатку створити з нульовими значеннями, а потім заповнити циклом. Для кожної позиції використовуємо вже знайомий std::cin.

Введіть одним рядком 18 20 17 21. Після цього змініть хоча б одне число і передбачте нову суму до повторного запуску.

#include <array>
#include <iostream>

int main() {
    std::array<int, 4> temperatures{};

    // Розмір масиву фіксований, тому цикл читає рівно чотири значення.
    std::cout << "Введіть чотири температури: ";
    for (std::size_t index{0}; index < temperatures.size(); ++index) {
        std::cin >> temperatures.at(index);
    }

    int sum{0};
    for (int value : temperatures) {
        sum += value;
    }

    std::cout << "\nСума: " << sum << "\n";
}

Перший цикл заповнює вже наявні чотири позиції. Другий цикл читає готові елементи й накопичує суму. Розмір контейнера не змінюється під час жодного етапу.

3. Порожня послідовність теж є нормальним випадком

std::vector<int> values{}; створює std::vector без елементів.

Його розмір:

values.size()

дорівнює нулю.

Метод empty() відповідає на питання, чи послідовність порожня:

values.empty()

Він дає true, коли елементів немає.

Метод empty() зручно використовувати перед доступом до першого або останнього елемента. Він перевіряє порожність без обчислення останнього індексу.

Це важливо перед операціями, які потребують хоча б одного елемента. Для порожнього std::vector вираз size() - 1 не описує правильну позицію. Оскільки size() повертає невід’ємний тип, таке віднімання може дати дуже велике число.

#include <iostream>
#include <vector>

int main() {
    const std::vector<int> values{};

    if (values.empty()) {
        std::cout << "Послідовність порожня\n";
    } else {
        std::cout << "Перший: " << values.at(0) << "\n";
    }
}

Перед доступом до першого або останнього елемента поставте питання: чи може послідовність бути порожньою?

4. Результатом алгоритму може бути нова послідовність

Раніше результатом часто було одне число: сума, кількість або найкраще значення. Тепер результатом може бути набір елементів.

Нехай треба залишити тільки оцінки від 60.

Алгоритм використовує дві структури.

1. scores містить початкові дані.
2. passed поступово накопичує потрібні елементи.

Новий std::vector можна створити порожнім:

std::vector<int> passed;

Метод push_back() додає один елемент у кінець:

passed.push_back(score);

4.1. Фільтрація як знайомий цикл з новим результатом

#include <iostream>
#include <vector>

int main() {
    const std::vector<int> scores{45, 72, 60, 58, 91};
    std::vector<int> passed;

    // Формуємо окремий результат, залишаючи початкові оцінки без змін.
    for (int score : scores) {
        if (score >= 60) {
            passed.push_back(score);
        }
    }

    // Виводимо пробіл лише між значеннями, тому перед першим його немає.
    std::cout << "Пройшли: ";
    for (std::size_t i{0}; i < passed.size(); ++i) {
        if (i > 0) {
            std::cout << " ";
        }
        std::cout << passed.at(i);
    }

    std::cout << "\nКількість: " << passed.size() << "\n";
}

У цьому алгоритмі вже знайомі три дії.

1. цикл бере чергове значення;
2. if перевіряє умову;
3. стан результату змінюється через push_back().

Новою є форма результату. Замість одного лічильника ми будуємо нову послідовність.

Стан результату можна простежити після кожного вхідного значення:

score	умова score >= 60	passed після кроку
45	false	{}
72	true	{72}
60	true	{72, 60}
58	false	{72, 60}
91	true	{72, 60, 91}

Таблиця показує знайому модель стану. Різниця лише в тому, що станом тепер є цілий std::vector.

flowchart TD
    A["Взяти черговий score"] --> C{"score >= 60?"}
    C -- "так" --> D["Додати score до passed"]
    C -- "ні" --> E["Не змінювати passed"]
    D --> F{"Є ще scores?"}
    E --> F
    F -- "так" --> A
    F -- "ні" --> G["Готовий passed"]

4.2. push_back() змінює розмір

Порожній passed має розмір 0.

Після першого push_back() розмір стає 1. Після трьох додавань розмір дорівнює 3.

Індексом не створюють новий елемент поза поточним розміром. Для додавання в кінець використовуємо push_back().

5. std::string — послідовність символів

Текст теж має структуру. Один символ у C++ можна зберігати у типі char. std::string зберігає послідовність таких символів.

Термін: char

char представляє один символ. Символьний літерал записують в одинарних лапках, наприклад 'a'.

std::string word{"banana"};

Щоб використовувати std::string, підключаємо:

#include <string>

Розмір рядка повертає size():

word.size()

Для "banana" результат дорівнює 6.

Окремий символ можна отримати за індексом:

word.at(0)

Результат має тип char.

5.1. Рядок можна обходити циклом for за елементами

#include <iostream>
#include <string>

int main() {
    const std::string word{"banana"};

    int count_a{0};
    for (char ch : word) {
        if (ch == 'a') {
            ++count_a;
        }
    }

    std::cout << "Довжина: " << word.size() << "\n";
    std::cout << "Літер a: " << count_a << "\n";
}

char ch на кожній ітерації зберігає один символ. Умова ch == 'a' порівнює два символи.

Одинарні лапки використовуються для одного char:

'a'

Подвійні лапки використовуються для текстового рядка:

"banana"

char і std::string виконують різні ролі. char описує один символ, а std::string описує послідовність символів.

Наприклад, вираз ch == 'a' порівнює один символ. Вираз word == "banana" порівнює цілий рядок.

Це допомагає читати умову через рівень даних: символ порівнюємо із символом, рядок — із рядком.

5.2. Знайомий шаблон пошуку переноситься на текст

У Л4 ми вже використовували стан found. Той самий шаблон працює для символів рядка.

#include <iostream>
#include <string>

int main() {
    const std::string code{"AB-204"};
    bool has_dash{false};

    for (char ch : code) {
        if (ch == '-') {
            has_dash = true;
            // Після першого роздільника відповідь уже відома, тому решту символів не переглядаємо.
            break;
        }
    }

    if (has_dash) {
        std::cout << "Є роздільник\n";
    } else {
        std::cout << "Роздільника немає\n";
    }
}

Початкове значення false означає, що потрібний символ ще не знайдено. Коли цикл бачить '-', стан змінюється на true.

break завершує цикл, бо подальші символи вже не впливають на відповідь.

6. Двовимірні дані та вкладений обхід

Послідовність може містити інші послідовності. Наприклад, std::vector<std::string> може зберігати текстові рядки.

Коли один цикл виконується всередині іншого, маємо вкладений цикл.

Термін: вкладений цикл

Вкладений цикл — цикл усередині тіла іншого циклу. Зовнішній цикл обирає більшу частину даних, а внутрішній обходить її елементи.

std::vector<std::string> rows{
    ".#..",
    "##..",
    "...#"
};

Зовнішній цикл бере один рядок. Внутрішній цикл проходить символи цього рядка.

flowchart TD
    A["rows"] --> B["взяти один рядок"]
    B --> C["взяти один символ"]
    C --> D{{"символ == # ?"}}
    D -- "так" --> E["marks++"]
    D -- "ні" --> F["без зміни"]
    E --> G{"є ще символи?"}
    F --> G
    G -- "так" --> C
    G -- "ні" --> H{"є ще рядки?"}
    H -- "так" --> B
    H -- "ні" --> I["готовий результат"]

#include <iostream>
#include <string>
#include <vector>

int main() {
    const std::vector<std::string> rows{
        ".#..",
        "##..",
        "...#"
    };

    int marks{0};
    // Для кожного рядка окремо переглядаємо всі його клітинки.
    for (std::string row : rows) {
        for (char cell : row) {
            if (cell == '#') {
                ++marks;
            }
        }
    }

    std::cout << "Позначок: " << marks << "\n";
}

У табличних числових даних корисно явно називати рядок і стовпець. Коли розмір таблиці фіксований, std::array можна вкладати в інший std::array.

std::array<std::array<int, 3>, 2> sales{
    std::array<int, 3>{4, 7, 5},
    std::array<int, 3>{6, 3, 8}
};

Зовнішній контейнер має два рядки. Кожний рядок містить три числа.

#include <array>
#include <iostream>

int main() {
    const std::array<std::array<int, 3>, 2> sales{
        std::array<int, 3>{4, 7, 5},
        std::array<int, 3>{6, 3, 8}
    };

    // Таблиця має фіксований розмір 2 × 3, тому обходимо всі наявні комірки.
    int total{0};
    for (const std::array<int, 3>& row : sales) {
        for (int value : row) {
            total += value;
        }
    }

    std::cout << "Разом: " << total << "\n";
}

Посилання const std::array<int, 3>& row використовує вже знайому модель з Л3. Рядок читається без створення його копії.

Термін: двовимірні дані

Двовимірна структура організує елементи за рядками та стовпцями. Вкладений цикл природно відповідає такій моделі: зовнішній цикл обирає рядок, а внутрішній — елемент цього рядка.

Це перенесення вже знайомої моделі циклу на дані з двома рівнями.

7. Представлення даних обираємо до алгоритму

Форма даних впливає на те, який алгоритм буде природним. До цієї лекції вже введено основні типи, які регулярно трапляються в початкових програмах C++. Таблиця нижче збирає їх в одну карту для читання коду.

Тип	Що представляє	Короткий приклад
bool	логічне значення	bool ready{true};
char	один символ	char grade{'A'};
short	ціле з невеликим діапазоном	short delta{-2};
int	звичайне ціле	int students{28};
long	ціле з платформозалежним розміром	long code{380L};
long long	велике ціле зі знаком	long long views{3'000'000'000LL};
unsigned int	невід’ємне ціле	unsigned int attempts{3U};
float	дробове число з меншою точністю	float temperature{21.5F};
double	основний дробовий тип курсу	double price{58.25};
long double	дробове число з точністю не меншою за double	long double ratio{2.5L};
std::size_t	розмір або індекс контейнера	std::size_t index{0};
std::string	послідовність символів	std::string name{"Ada"};

Це карта вибору й розпізнавання, а не список для механічного запам’ятовування. Для звичайних цілих обчислень достатньо int, а для дробових курс переважно використовує double. Спеціальні варіанти потрібні тоді, коли задача дає окрему причину для їх вибору.

Ситуація	Зручне представлення
одна температура	double
чотири квартальні значення, кількість завжди стала	std::array<double, 4>
багато температур, кількість може змінюватися	std::vector<double>
старий або низькорівневий код із фіксованим масивом	вбудований масив T[N]
одне слово або речення	std::string
кілька текстових рядків	std::vector<std::string>

Якщо задача каже «для кожного значення», це сильна ознака послідовності.

Якщо задача каже «символ», «слово», «рядок», треба перевірити, чи природно представити дані через std::string.

7.1. Представлення визначає доступні операції

Для одного окремого значення природна операція працює без обходу послідовності.

Для std::vector природними стають:

1. обхід усіх елементів;
2. доступ за індексом;
3. перевірка розміру;
4. побудова нової послідовності.

Для std::string природними стають:

1. обхід символів;
2. доступ до позиції;
3. перевірка довжини;
4. пошук або підрахунок символів.

Спочатку визначте форму даних. Потім вибирайте цикл та стан алгоритму.

7.2. Знайомі алгоритмічні патерни не зникають

Новий контейнер не скасовує моделі з Л4. Він дає їм природне джерело елементів.

Потреба	Стан алгоритму	Приклад для std::vector або std::string
порахувати елементи	count	кількість оцінок від 60
знайти суму	total	сума кроків
знайти ознаку	found	чи є дефіс у коді
побудувати результат	result	std::vector оцінок, що пройшли

Тому під час читання нового коду спочатку шукайте знайомий алгоритмічний стан. Потім дивіться, як контейнер постачає черговий елемент.

8. Межі послідовності треба перевіряти окремими випадками

Для std::vector або std::string корисні щонайменше п’ять типів тестів:

1. порожня послідовність;
2. один елемент;
3. кілька звичайних елементів;
4. потрібний елемент на першій позиції;
5. потрібний елемент на останній позиції.

Для фільтрації додайте ще два випадки:

1. жоден елемент не проходить умову;
2. усі елементи проходять умову.

Такі випадки перевіряють межі індексів та стан результату.

8.1. Типова помилка межі

Умова

i <= values.size()

дозволяє i == values.size(). Такої позиції вже немає, тому правильний шаблон обходу індексів має вигляд:

for (std::size_t i{0}; i < values.size(); ++i)

Для порожнього std::vector умова одразу хибна, тому тіло не виконається.

9. Робочий порядок для задачі з послідовністю

Перед написанням коду виконайте шість кроків:

1. Визначте, чи задача працює з одним значенням або послідовністю.
2. Для послідовності вирішіть, чи її розмір фіксований або змінний.
3. Назвіть тип одного елемента та потрібну структуру: std::array, std::vector або std::string.
4. Вирішіть, чи потрібна позиція елемента.
5. Виберіть цикл за елементами або цикл з індексом.
6. Визначте форму результату та перевірте порожній випадок і межі.

Такий порядок відділяє модель даних від деталей синтаксису.

10. Інтерактивна самоперевірка лекції

Самоперевірка вимагає рахувати індекси, читати цикли, прогнозувати побудову std::vector та знаходити помилки меж.