Ітератор
У комп'ютерному програмуванні ітератор — це об'єкт, який дозволяє програмісту обходити елементи колекції, зокрема списку.[1][2][3] Різні типи ітераторів часто вже є доступними через інтерфейс колекції. Хоча інтерфейс і семантика конкретного ітератора є фіксованими, ітератори часто реалізуються в термінах структур, які лежать в основі реалізації колекції, і часто тісно пов'язані з колекцією, щоб забезпечити робочу семантику ітератора. Ітератор виконує обхід, а також надає доступ до елементів даних у колекції, але сам не виконує ітерації.
Поведінка ітератора схожа на курсор бази даних. Ітератори вперше з'явилися в мові програмування CLU в 1974 році[4].
Внутрішні ітератори — це функції вищого порядку (часто приймають анонімні функції, але не обов'язково), такі як map(), reduce() тощо, які реалізують обхід колекції, застосовуючи дану функцію до кожного елемента по черзі. Прикладом може бути функція map Python:
digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
squared_digits = map(lambda x: x**2, digits)
# Ітерація по цьому ітератору дає послідовність 0, 1, 4, 9, 16, ..., 81.
Зовнішній ітератор можна розглядати як тип вказівника, який виконує дві основні операції: посилання на один окремий елемент у колекції об'єктів (так званий доступ до елемента) і модифікація себе таким способом, щоб він вказував на наступний елемент (так званий обхід елементів).[5] Також має бути спосіб створити ітератор, щоб він вказував на деякий перший елемент, а також якийсь спосіб визначити, коли ітератор вичерпає всі елементи в колекції. Залежно від мови та намірів використання ітератори також можуть забезпечувати додаткові операції або демонструвати різну поведінку.
Основна мета ітератора — дозволити користувачеві обробляти кожен елемент колекції, при цьому ізолюючи користувача від внутрішньої структури колекції.[2] Це дозволяє колекції зберігати елементи довільним способом та дозволяє користувачеві розглядати їх так, ніби це проста послідовність або список. Клас ітератора зазвичай розробляється в тісній координації з відповідним класом-колекцією. Зазвичай колекція надає методи для створення ітераторів.
Лічильник циклу іноді також називають ітератором циклу. Однак лічильник циклів забезпечує лише функціональні можливості обходу, а не функції доступу до елементу.
Одним із способів реалізації ітераторів є використання обмеженої форми співпрограми, відомої як генератор. На відміну від підпрограми, співпрограма генератора може надавати (yield) значення при виклику декілька разів замість того, щоб повертати його лише один раз. Більшість ітераторів природно виражаються як генератори, але оскільки генератори зберігають свій локальний стан між викликами, вони особливо добре підходять для складних ітераторів із збереженням стану, таких як обходи дерев. Існують тонкі відмінності у використанні термінів «генератор» та «ітератор», які відрізняються залежно від автора та мови.[6] У Python генератор — це конструктор ітератора: функція, яка повертає ітератор. Нижче наведено приклад генератора Python, який повертає ітератор для чисел Фібоначчі за допомогою оператора yield Python:
def fibonacci(limit):
a, b = 0, 1
for _ in range(limit):
yield a
a, b = b, a + b
for number in fibonacci(100): # Генератор створює ітератор
print(number)
Деякі об'єктно-орієнтовані мови, такі як C#, C++ (пізніші версії), Delphi (пізніші версії), Go, Java (пізніші версії), Lua, Perl, Python, Ruby, забезпечують вбудований[en] спосіб ітерації елементів об'єкта-колекції без введення явного об'єкта-ітератора. Фактичний об'єкт-ітератор може існувати в реальності, але якщо він існує, він не відображається у вихідному коді мови.[5][7]
Неявні ітератори часто проявляються оператором «foreach» (або еквівалентом), наприклад, у наступному прикладі Python: У Python ітератор — це об'єкт, який можна перетворити на ітератор, який потім ітерується під час циклу for; це робиться неявно:
for value in iterable:
print(value)
Або в інших випадках вони можуть бути створені самим об'єктом колекції, як у цьому прикладі Ruby: Цей стиль ітерації іноді називають «вбудованою ітерацією», оскільки його код повністю виконується в контексті ітерованого об'єкта (який контролює всі аспекти ітерації), а програміст надає лише операцію для виконання на кожному кроці (використовуючи анонімну функцію).
iterable.each do |value|
puts value
end
Мови, які підтримують спискові вирази або подібні конструкції, також можуть використовувати неявні ітератори під час створення списку результатів, як у Python:
names = [person.name for person in roster if person.male]
Іноді неявна прихована природа є лише частковою. У мові C++ є кілька шаблонів функцій для неявної ітерації, наприклад for_each(). Ці функції все ще вимагають явних об'єктів ітератора як початкового входу, але наступна ітерація не відкриває об'єкт ітератора для користувача.
Ітератори є корисною абстракцією вхідних потоків — вони надають потенційно нескінченний ітерований (але не обов'язково індексований) об'єкт. Деякі мови, такі як Perl і Python, реалізують потоки як ітератори. У Python ітератори — це об'єкти, що представляють потоки даних.[8] Альтернативні реалізації потоку включають мови, керовані даними[en], такі як AWK і sed.
У процедурних мовах зазвичай використовують оператор індексу та лічильник циклу для проходження всіх елементів послідовності, такої як масив. Хоча індексування також може використовуватися з деякими об'єктно-орієнтованими колекціями, використання ітераторів може мати деякі переваги:[9]
- Цикли підрахунку не підходять для всіх структур даних, зокрема для структур даних без довільного доступу або з повільним довільним доступом, таких як списки або дерева.
- Ітератори можуть забезпечити послідовний спосіб ітерації структур даних усіх типів і, отже, зробити код більш читабельним, придатним для повторного використання та менш чутливим до змін у структурі даних.
- Ітератор може накладати додаткові обмеження на доступ, наприклад гарантувати, що елементи не можуть бути пропущені або що раніше відвіданий елемент не може бути доступний другий раз.
- Ітератор може дозволити змінювати об'єкт-колекція, не пошкоджуючи ітератор. Наприклад, як тільки ітератор вийшов за межі першого елемента, можна було б вставити додаткові елементи на початок колекції з передбачуваними результатами. При використанні індексації це проблематично зробити, оскільки номери індексів повинні змінюватися.
Здатність колекції модифікуватися під час ітерації його елементів стала необхідною в сучасному об'єктно-орієнтованому програмуванні, де взаємозв'язки між об'єктами та наслідками операцій можуть бути неочевидними. Використовуючи ітератор, ви убезпечені від таких наслідків. Однак, до цього твердження варто ставитися з недовірою, тому що, частіше за все, з міркувань ефективності, реалізація ітератора настільки тісно прив'язана до колекції, що може перешкоджати модифікації основної колекції, щоб не пошкодити себе.
Для колекцій, які можуть переміщувати свої дані в пам'яті, єдиний спосіб не пошкодити ітератор — колекція має якимось чином відстежувати всі активні ітератори та оновлювати їх на льоту. Оскільки кількість ітераторів у певний момент часу може бути як завгодно великою порівняно з розміром зв'язаної колекції, їх одночасне оновлення різко погіршить гарантію складності операцій колекції.
Альтернативним способом збереження кількості оновлень, прив'язаних до розміру колекції, було б використання свого роду механізму ручки, тобто набору непрямих покажчиків на елементи колекції, які потрібно оновлювати разом із колекцією, і дозволити ітераторам вказувати на ці непрямі покажчикі замість того, щоб вказати безпосередньо на елементи даних. Але такий підхід негативно вплине на продуктивність ітератора, оскільки для доступу до фактичного елемента даних він повинен використовувати подвійний вказівник. Зазвичай це небажано, тому що багато алгоритмів, що використовують ітератори, викликають операцію доступу до даних ітераторів частіше, ніж попередній метод. Тому особливо важливо мати ітератори з дуже ефективним доступом до даних.
Загалом, це завжди компроміс між безпекою (ітератори залишаються завжди робочими) та ефективністю. У більшості випадків додаткова безпека не вартує тієї ціни ефективності, яку потрібно за неї заплатити. Використання альтернативної колекції (наприклад, однозв'язаного списку замість вектора) було б кращим вибором (глобально ефективнішим), якщо потрібна стабільність ітераторів.
Ітератори можна класифікувати відповідно до їхньої функціональності. Ось (неповний) список категорій ітераторів:[10][11]
| Категорія | Мова |
|---|---|
| Bidirectional iterator | C++ |
| Forward iterator | C++ |
| Input iterator | C++ |
| Output iterator | C++ |
| Random access iterator | C++ |
| Trivial iterator | C++ (старий STL)[12] |
Різні мови або бібліотеки, що використовуються з цими мовами, визначають типи ітераторів. Деякі з них[13]
| Тип | Мова |
|---|---|
| Array iterator | PHP, R[14] |
| Caching iterator | PHP |
| Constant iterator | C++,[15] PHP |
| Directory iterator | PHP, Python |
| Filter iterator | PHP, R |
| Limit iterator | PHP |
| List iterator | Java,[7] R |
| Recursive array iterator | PHP |
| XML iterator | PHP |
Ітератори в Python є фундаментальною частиною мови і в багатьох випадках залишаються непоміченими, оскільки вони неявно використовуються в операторі for (foreach), у списках і у виразах генератора. Усі стандартні вбудовані типи колекцій Python підтримують ітерацію, а також багато класів, які є частиною стандартної бібліотеки. У наступному прикладі показано типову неявну ітерацію по послідовності:
for value in sequence:
print(value)
Словники Python (форма асоціативного масиву) також можна безпосередньо перебирати, коли повертаються ключі словника; або метод items() словника можна повторити, де він дає відповідні пари ключ-значення як кортеж:
for key in dictionary:
value = dictionary[key]
print(key, value)
for key, value in dictionary.items():
print(key, value)
Однак ітератори можна використовувати та визначати явно. Для будь-якого ітерованого типу послідовності або класу вбудована функція iter() використовується для створення об'єкта ітератора. Потім об'єкт ітератора можна повторити за допомогою функції next(), яка використовує внутрішній метод __next__(), який повертає наступний елемент у колекції. (Попереднє твердження стосується Python 3.x. У Python 2.x використовується еквівалентний метод next().) Виняток StopIteration буде викликано, коли більше не залишиться елементів. У наступному прикладі показано еквівалентну ітерацію в послідовності з використанням явних ітераторів:
it = iter(sequence)
while True:
try:
value = it.next() # in Python 2.x
value = next(it) # in Python 3.x
except StopIteration:
break
print(value)
Будь-який визначений користувачем клас може підтримувати стандартну ітерацію (неявну або явну) шляхом визначення методу __iter__(), який повертає об'єкт ітератора. Потім об'єкт-ітератор повинен визначити метод __next__(), який повертає наступний елемент.
Генератори Python реалізують цей протокол ітерації.
- Iteratee[en], у якому замість того, щоб розробник повторно викликав ітератор для отримання нових значень,
iterateeвикликається неодноразово для обробки нових фрагментів даних — приклад інверсії керування. - Шаблони проєктування програмного забезпечення
- Ітерація
- Шаблон ітератора
- Діапазон
- Шаблон відвідувача
- Вказівник
- ↑ Gatcomb, Joshua. Understanding and Using Iterators. Perl.com. Архів оригіналу за 6 серпня 2012. Процитовано 8 серпня 2012.
A user-defined iterator usually takes the form of a code reference that, when executed, calculates the next item in a list and returns it. When the iterator reaches the end of the list, it returns an agreed-upon value.
- ↑ а б Watt, Stephen M. A Technique for Generic Iteration and Its Optimization. The University of Western Ontario, Department of Computer Science. Архів оригіналу (PDF) за 6 серпня 2012. Процитовано 8 серпня 2012.
Iterators were introduced as constructs to allow looping over abstract data structures without revealing their internal representation.
{{cite web}}: Недійсний|url-status=unknown(довідка) - ↑ Alex Allain. STL Iterators. Cprogramming.com - Your resource for C and C++. Процитовано 8 серпня 2012.
You can think of an iterator as pointing to an item that is part of a larger container of items.
- ↑ Liskov, Barbara (1992). «A history of CLU». The second ACM SIGPLAN conference on History of programming languages.
- ↑ а б Difference between an external iterator and an internal iterator. CareerRide.COM. 3 квітня 2009. Архів оригіналу за 19 вересня 2012. Процитовано 8 серпня 2012.
An internal iterator is implemented by the member functions of the class which has the iteration logic. An external iterator is implemented by a separate class which can be attached to the object which has iteration logic. The advantage of external iterator is that, many iterators can be made active simultaneously on the existing or same object.
{{cite web}}: Недійсний|url-status=unknown(довідка) - ↑ Watt, Stephen M. A Technique for Generic Iteration and Its Optimization. The University of Western Ontario, Department of Computer Science. Архів оригіналу (PDF) за 6 серпня 2012. Процитовано 8 серпня 2012.
Some authors use the term iterator, and others the term generator. Some make subtle distinctions between the two.
{{cite web}}: Недійсний|url-status=unknown(довідка) - ↑ а б Freeman, Eric; Freeman, Elisabeth; Kathy, Sierra; Bert, Bates (2004). Hendrickson, Mike; Loukides, Mike (ред.). Head First Design Patterns (paperback). Т. 1. O'REILLY. с. 338. ISBN 978-0-596-00712-6. Процитовано 9 серпня 2012.
- ↑ Glossary — Python 3.8.4 documentation. Процитовано 15 липня 2020.
- ↑ Vecerina, Ivan (1 лютого 2006). index vs iterator. BYTES. Архів оригіналу за 9 серпня 2012. Процитовано 8 серпня 2012.
An index only can be used for containers that (efficiently) support random access (i.e. direct access to an element at a given position). An iterator is a more general concept. Iterators offer efficient traversal of linked lists, files, and a number of other data structures. It often leads to the generation of more efficient code.
{{cite web}}: Недійсний|url-status=unknown(довідка) - ↑ Kevin Waterson. C++ Iteratoren: Iterator-Kategorien (нім.). cppreference.com. Процитовано 9 серпня 2012.
- ↑ Kevin Waterson. Iterators: Concepts. sgi. Процитовано 9 серпня 2012.
- ↑ larsmans (6 березня 2011). Types of iterator: Output vs. input vs. forward vs. random access iterator. stackoverflow. Архів оригіналу за 8 серпня 2012. Процитовано 9 серпня 2012.
{{cite web}}: Недійсний|url-status=unknown(довідка) - ↑ Kevin Waterson. Introduction to SPL: Introduction to Standard PHP Library (SPL). PHPRO.ORG. Процитовано 9 серпня 2012.
- ↑ Collier, Andrew. Iterators in R. Архів оригіналу за 18 жовтня 2018. Процитовано 16 листопада 2013.
- ↑ concurrent_unordered_set Template Class. Intel Threading Building Blocks for Open Source. Архів оригіналу за 1 травня 2015. Процитовано 9 серпня 2012.
The iterator types iterator and const_iterator are of the forward iterator category
- Java's Iterator, Iterable and ListIterator Explained (англ.)
- .NET interface (англ.)
- Стаття «Understanding and Using Iterators» Джошуа Гаткомба (англ.)
- Стаття «A Technique for Generic Iteration and Its Optimization» Стівенна Уотта[en] (англ.)
- Iterators (англ.)
- Boost C++ Iterator Library (англ.)
- Java interface (англ.)
- PHP: Object Iteration (англ.)
- STL Iterators (англ.)
- What are iterators? — Reference description (англ.)