Итераторы и алгоритмы — различия между версиями
Материал из SEWiki
| Строка 5: | Строка 5: | ||
* задавать последовательность элементов. | * задавать последовательность элементов. | ||
В C++ синтаксис итераторов заимствован у указателей. | В C++ синтаксис итераторов заимствован у указателей. | ||
| + | |||
| + | === Классификация === | ||
Выделяют пять типов итераторов. | Выделяют пять типов итераторов. | ||
| − | # ''Random Access''. Это наиболее мощный тип итераторов. Random access поддерживает произвольный доступ к последовательности элементов. По сути равносилен указателем: поддерживает операции инкремента(<tt>++</tt>), декремента (<tt>--</tt>), прибавления целого числа (<tt>+ val</tt>, <tt>- val</tt>), разыменования (<tt>*</tt>), доступа к члену (<tt>-></tt>). Как пример, итераторы такого типа предоставляет <tt>vector</tt>. | + | # ''Random Access''. Это наиболее мощный тип итераторов. Random access поддерживает произвольный доступ к последовательности элементов. По сути равносилен указателем: поддерживает операции инкремента(<tt>++</tt>), декремента (<tt>--</tt>), прибавления целого числа (<tt>+ val</tt>, <tt>- val</tt>), разыменования (<tt>*</tt>), разыменования со сдвигом (<tt>[]</tt>), доступа к члену (<tt>-></tt>). Как пример, итераторы такого типа предоставляет <tt>vector</tt>. |
# ''Bidirectional''. Двунаправленный итератор является более слабым типом итераторов: позволяет двигаться только вперед и назад, проходя через каждый элемент. Операции: <tt>++</tt>, <tt>--</tt>, <tt>*</tt>, <tt>-></tt>. Как пример, итераторы такого типа предоставляет <tt>list</tt>. | # ''Bidirectional''. Двунаправленный итератор является более слабым типом итераторов: позволяет двигаться только вперед и назад, проходя через каждый элемент. Операции: <tt>++</tt>, <tt>--</tt>, <tt>*</tt>, <tt>-></tt>. Как пример, итераторы такого типа предоставляет <tt>list</tt>. | ||
# ''Forward''. Однонаправленный итератор позволяет двигаться только в одном направлении. Операции: <tt>++</tt>, <tt>*</tt>, <tt>-></tt> | # ''Forward''. Однонаправленный итератор позволяет двигаться только в одном направлении. Операции: <tt>++</tt>, <tt>*</tt>, <tt>-></tt> | ||
| Строка 14: | Строка 16: | ||
# ''Output''. Однонаправленный итератор, позволяющий только записывать данные, но не считывать. | # ''Output''. Однонаправленный итератор, позволяющий только записывать данные, но не считывать. | ||
| + | Вне данной классификации лежит ''Reverse iterator''. Reverse iterator обращает направление для bidirectional и random access итераторов. Для получения начала и конца итератора необходимо вызвать <tt>rbegin()</tt> и <tt>rend()</tt> соответственно. | ||
| + | Reverse iterator реализует функцию base(), возвращающую обычный итератор. Для того, чтобы получить из обычного (bidirectional и random access) итератора reverse, достаточно использовать оператор присваивания. | ||
| + | |||
| + | set< int > s; | ||
| + | set< int > :: reverse_iterator i = s.rbegin(); | ||
| + | set< int > :: iterator j = i.base(); | ||
| + | i = j | ||
| + | '''Внимание, вопрос.''' Почему в одну сторону можно написать <tt>i = j</tt>, а в другую только <tt>j = i.base()</tt>? | ||
| + | '''Внимание, вопрос.''' Почему нельзя менять значения в set? | ||
;Заметка: По сути, итератор является паттерном программирования. Представленная классификация задает терминологию, позволяющую определить, о каком типе итератора идет речь. | ;Заметка: По сути, итератор является паттерном программирования. Представленная классификация задает терминологию, позволяющую определить, о каком типе итератора идет речь. | ||
Версия 09:06, 18 марта 2011
Итераторы
Итератор --- это объект, который указывает на некоторый элемент коллекции (будь то массив или контейнер). Итератор позволяет
- итерировать элементы контейнера;
- задавать последовательность элементов.
В C++ синтаксис итераторов заимствован у указателей.
Классификация
Выделяют пять типов итераторов.
- Random Access. Это наиболее мощный тип итераторов. Random access поддерживает произвольный доступ к последовательности элементов. По сути равносилен указателем: поддерживает операции инкремента(++), декремента (--), прибавления целого числа (+ val, - val), разыменования (*), разыменования со сдвигом ([]), доступа к члену (->). Как пример, итераторы такого типа предоставляет vector.
- Bidirectional. Двунаправленный итератор является более слабым типом итераторов: позволяет двигаться только вперед и назад, проходя через каждый элемент. Операции: ++, --, *, ->. Как пример, итераторы такого типа предоставляет list.
- Forward. Однонаправленный итератор позволяет двигаться только в одном направлении. Операции: ++, *, ->
- Input. Однонаправленный итератор, позволяющий только считывать данные, но не записывать.
- Output. Однонаправленный итератор, позволяющий только записывать данные, но не считывать.
Вне данной классификации лежит Reverse iterator. Reverse iterator обращает направление для bidirectional и random access итераторов. Для получения начала и конца итератора необходимо вызвать rbegin() и rend() соответственно. Reverse iterator реализует функцию base(), возвращающую обычный итератор. Для того, чтобы получить из обычного (bidirectional и random access) итератора reverse, достаточно использовать оператор присваивания.
set< int > s; set< int > :: reverse_iterator i = s.rbegin(); set< int > :: iterator j = i.base(); i = j
Внимание, вопрос. Почему в одну сторону можно написать i = j, а в другую только j = i.base()? Внимание, вопрос. Почему нельзя менять значения в set?
- Заметка
- По сути, итератор является паттерном программирования. Представленная классификация задает терминологию, позволяющую определить, о каком типе итератора идет речь.
