Урок №100. Введення в ітератори

  Юрій  | 

  Оновл. 16 Січ 2021  | 

 98

На цьому уроці ми розглянемо тему ітераторів в мові С++.

Ітерація по елементам структур даних

Ітерація/переміщення по елементах масиву (або будь-якої іншої структури) є досить поширеною дією в програмуванні. Ми вже розглядали безліч різних способів виконання даного завдання, а саме: з використанням циклів і індексів (цикли for і while), за допомогою вказівників і адресної арифметики, а також за допомогою циклів for з явним зазначенням діапазону:

Використання циклів з індексами в ситуаціях, коли ми використовуємо їх лише для доступу до елементів, вимагає написання більшої кількості коду, ніж могло б бути.

При цьому даний спосіб працює тільки в тому випадку, якщо контейнер (наприклад, масив), що містить дані, надає прямий доступ до своїх елементів (що роблять масиви, але не роблять деякі інші типи контейнерів, наприклад, списки).

Використання циклів з вказівниками і адресною арифметикою вимагає досить великого обсягу теоретичних знань і може збити з пантелику читачів, які не знайомі з адресною арифметикою і не знають її правил. Та й сама адресна арифметика може бути застосована лише у тому випадку, якщо елементи структури даних розташовані в пам’яті послідовно (що підходить для масивів, але не завжди виконується для інших типів даних, таких як списки, дерева, карти).

Примітка для просунутих читачів: Вказівники (без адресної арифметики) можуть використовуватися для перебору/ітерації деяких структур даних з непослідовним розташуванням елементів. Наприклад, в зв’язаному списку кожен елемент з’єднаний вказівником з попереднім елементом, тому ми можемо перебирати список, використовуючи ланцюжок вказівників.

Цикли for з явним зазначенням діапазону більш цікаві, оскільки у них прихований механізм перебору елементів нашого контейнера, але при цьому вони все одно можуть застосовуватися з різними типами структур даних (масиви, списки, дерева, карти тощо). «Як же вони працюють?» — запитаєте ви. Вони використовують ітератори.

Ітератори в С++

Ітератор — це об’єкт, розроблений спеціально для перебору елементів контейнера (наприклад, значень масиву або символів в рядку), що забезпечує доступ до кожного з елементів.

Контейнер може надавати різні типи ітераторів. Наприклад, контейнер на основі масиву може пропонувати прямий ітератор, який проходиться по масиву в прямому порядку, і реверсивний ітератор, який проходиться по масиву в зворотному порядку.

Після того, як ітератор відповідного типу створений, програміст може використовувати інтерфейс, що надається даним ітератором, для переміщення по елементах контейнеру або доступу до його елементів, не турбуючись при цьому про те, який тип перебору елементів задіяний або яким чином в контейнері зберігаються дані. І, оскільки ітератори в мові С++ зазвичай використовують один і той же інтерфейс як для переміщення по елементах контейнеру (оператор ++ для переходу до наступного елементу), так і для доступу (оператор * для доступу до поточного елементу) до них, ітерації можна виконувати по різним типам контейнерів, використовуючи послідовний метод.

Вказівники в якості ітераторів

Найпростіший приклад ітератора — це вказівник, який (використовуючи адресну арифметику) працює з послідовно розташованими елементами даних. Давайте знову розглянемо приклад переміщення по елементах масиву, використовуючи вказівник і адресну арифметику:

Результат виконання програми:

0 1 2 3 4 5 6

У прикладі, наведеному вище, ми визначили дві змінні: begin (яка вказує на початок нашого контейнера) і end (яка вказує на кінець нашого контейнера). Для масивів кінцевим маркером зазвичай є місце в пам’яті, де міг би перебувати останній елемент, якби контейнер містив на один елемент більше.

Потім вказівник переміщається між begin і end, при цьому доступ до поточного елементу можна отримати за допомогою оператора розіменування.

Попередження: У вас може з’явитися спокуса обчислити кінцеву точку, використовуючи оператор адресу (&) наступним чином:

Але це призведе до невизначеної поведінки, тому що array[std::size(array)] звертається до елементу, який знаходиться за межами масиву.

Замість вищенаведеного слід використовувати:

Ітератори Стандартної бібліотеки С++

Виконання ітерацій є настільки поширеною дією, що всі Стандартні бібліотеки контейнерів забезпечують пряму підтримку ітерацій. Замість обчислення початкової і кінцевої точок вручну, ми можемо просто попросити контейнер зробити це за нас, використавши функції begin() і end():

Результат виконання програми:

1 2 3

У заголовковому файлі iterator також знаходяться дві узагальнені функції (std::begin() і std::end()):

Результат виконання аналогічний попередньому результату:

1 2 3

Не варто зараз турбуватися про типи ітераторів. Зараз важливо зрозуміти лише те, що всю роботу по переміщенню по контейнеру ітератор бере на себе. Нам не обов’язково знати деталі того, як це відбувається. Нам потрібно знати наступні 4 речі:

   початкова точка;

   кінцева точка;

   оператор ++ для переміщення ітератора до наступного елементу (або в кінець);

   оператор * для отримання значення поточного елементу.

Ітератори і цикли for з явним зазначенням діапазону

Всі типи даних, які мають методи begin() і end() або використовуються з std::begin() і std::end(), можуть бути задіяні в циклах for з явним зазначенням діапазону:

Насправді, цикли for з явним зазначенням діапазону для здійснення ітерації непомітно звертаються до викликів функцій begin() і end(). Тип даних std::array також має в своєму арсеналі методи begin() і end(), а значить і його ми можемо використовувати в циклах for з явним зазначенням діапазону. Масиви C-style з фіксованим розміром також можна використовувати з функціями std::begin() і std::end(). Однак з динамічними масивами даний спосіб не працює, так як для них не існує функції std::end() (через те, що відсутня інформація про довжину масиву).

Пізніше ви дізнаєтесь, як додавати функціонал до ваших типів даних так, щоб їх можна було використовувати і з циклами for з явним зазначенням діапазону.

Цикли for з явним зазначенням діапазону використовуються не тільки при роботі з ітераторами. Вони також можуть бути задіяні разом з std::sort() і іншими алгоритмами. Тепер, коли ви знаєте, що це таке, ви можете помітити, що вони досить часто використовуються в Стандартній бібліотеці С++.

“Висячі” ітератори

Подібно вказівникам і посиланням, ітератори також можуть стати “висячими”, якщо елементи, за якими виконується ітерація, змінюють свою адресу або знищуються. Коли таке відбувається, то кажуть, що ітератор був недійсним (або сталася “інвалідація ітератора”). Звернення до недійсного ітератора породжує помилку невизначеної поведінки.

Деякі операції, які змінюють самі контейнери (наприклад, додавання елемента в std::vector), можуть мати побічний ефект, приводячи до зміни адрес елементів контейнера. Коли таке відбувається, поточні ітератори для цих елементів вважаються недійсними. Хороша довідкова документація по C++ обов’язково повинна мати інформацію про те, які операції з контейнерами можуть призвести або призведуть до інвалідаціі ітераторів.

Ось приклад подібної ситуації:

На наступному уроці ми розглянемо алгоритми Стандартної бібліотеки C++.

Оцінити статтю:

1 Зірка2 Зірки3 Зірки4 Зірки5 Зірок (1 оцінок, середня: 5,00 з 5)
Loading...

Залишити відповідь

Ваш E-mail не буде опублікований. Обов'язкові поля відмічені *