Русские Блоги
Изучение исходного кода STL, серия 4: Итератор
Итератор
Предисловие
Классификация итераторов
В SGI STL итераторы можно условно разделить на пять категорий в исходном коде в соответствии с методами чтения, записи и доступа:
Эти пять итераторов принадлежат следующим образом: 
Отношения наследования кода:
Один из пяти типов данных типа итератор:
Типы и особенности итераторов
При разработке алгоритма STL требуется тип итератора. В соответствии с различными требованиями и типами существуют разные методы их решения; например: использование механизма вывода параметров шаблона для определения типа локальных переменных; встроенный тип для поиска типа возвращаемого значения; Технология черт решает тип возвращаемого значения, а технология черт частичной специализации решает проблему нативного указателя; тип итератора показан в следующем коде:
В итераторе, чтобы иметь возможность определять вызов функции во время компиляции, применяется перегрузка функции. Поскольку рабочие возможности пяти итераторов различны, например, итератор случайного доступа имеет самые сильные рабочие возможности и может работать в указанной позиции за время O (1), тогда как использование других итераторов может потребовать O (n). Итак, чтобы повысить эффективность, используйте функцию алгоритма с наиболее подходящим типом итератора для вызова:
Чтобы идентифицировать перегруженные функции, SGI STL имеет пять соответствующих классов идентификации итераторов: Наследование предназначено для передачи вызовов. Когда нет соответствия определенного типа итератора, компилятор будет искать и передавать его в соответствии с иерархией наследования.
Например, ниже приведен вызов функции advance (), которая перегружает функцию для разных типов итераторов:
Используйте типы итераторов для более эффективной реализации функции расстояния. Используя предыдущие основы, мы можем реализовать функцию расстояния в соответствии с различными типами итераторов:
Технология _type_traits от SGI STL
Технология Traits, представленная ранее, восполняет недостатки шаблонов C ++ в STL, но в STL технология Traits используется только для стандартизации итераторов и не стандартизирует вещи, кроме итераторов. Поэтому SGI расширяет эту технику на нечто иное, чем итераторы, называемые __type_traits.
Типы добычи следующие:
_Type_traits, определенный в SGI type_traits.h, обеспечивает механизм для завершения решения об отправке функций во время компиляции в соответствии с характеристиками различных типов.
«Объект», который возвращает истину и ложь:
Введение в итераторы в С++
Обновл. 15 Сен 2021 |
На этом уроке мы рассмотрим тему использования итераторов в языке С++, а также связанные с этим нюансы.
Итерация по элементам структур данных
Итерация/перемещение по элементам массива (или какой-нибудь другой структуры) является довольно распространенным действием в программировании. Мы уже рассматривали множество различных способов выполнения данной задачи, а именно: с использованием циклов и индексов (циклы for и while), с помощью указателей и адресной арифметики, а также с помощью циклов for с явным указанием диапазона:
Использование циклов с индексами в ситуациях, когда мы используем их только для доступа к элементам, требует написания большего количества кода, нежели могло бы быть.
При этом данный способ работает только в том случае, если контейнер (например, массив), содержащий данные, дает возможность прямого доступа к своим элементам (что делают массивы, но не делают некоторые другие типы контейнеров, например, списки).
Использование циклов с указателями и адресной арифметикой требует довольно большого объёма теоретических знаний и может сбить с толку читателей, которые не знакомы с адресной арифметикой и не знают её правил. Да и сама адресная арифметика применима лишь в том случае, если элементы структуры данных расположены в памяти последовательно (что опять же верно для массивов, но не всегда выполняется для других типов данных, таких как списки, деревья, карты).
Примечание для продвинутых читателей: Указатели (без адресной арифметики) могут использоваться для перебора/итерации некоторых структур данных с непоследовательным расположением элементов. Например, в связном списке каждый элемент соединен указателем с предыдущим элементом, поэтому мы можем перебирать список, следуя по цепочке указателей.
Циклы for с явным указанием диапазона чуть более интересны, поскольку у них скрыт механизм перебора нашего контейнера, но при всем этом они всё равно могут быть применены к различным структурам данных (массивы, списки, деревья, карты и т.д.). «Как же они работают?» — спросите вы. Они используют итераторы.
Итераторы в С++
Итератор — это объект, разработанный специально для перебора элементов контейнера (например, значений массива или символов в строке), обеспечивающий во время перемещения по элементам доступ к каждому из них.
Контейнер может предоставлять различные типы итераторов. Например, контейнер на основе массива может предлагать прямой итератор, который проходится по массиву в прямом порядке, и реверсивный итератор, который проходится по массиву в обратном порядке.
После того, как итератор соответствующего типа создан, программист может использовать интерфейс, предоставляемый данным итератором, для перемещения по элементам контейнера или доступа к его элементам, не беспокоясь при этом о том, какой тип перебора элементов задействован или каким образом в контейнере хранятся данные. И, поскольку итераторы в языке С++ обычно используют один и тот же интерфейс как для перемещения по элементам контейнера (оператор ++ для перехода к следующему элементу), так и для доступа (оператор * для доступа к текущему элементу) к ним, итерации можно выполнять по разнообразным типам контейнеров, используя последовательный метод.
Указатели в качестве итераторов
Простейший пример итератора — это указатель, который (используя адресную арифметику) работает с последовательно расположенными элементами данных. Давайте снова рассмотрим пример перемещения по элементам массива, используя указатель и адресную арифметику:
Контейнеры, итераторы, функторы, алгоритмы
Кувшинов Д.Р.
Контейнеры и итераторы
Пара итераторов задаёт диапазон range — определение последовательности значений, которую можно перечислить, передвигая итератор вперёд, начиная с первого элемента, на который указывает первый итератор в паре, и до тех пор, пока не будет встречен второй итератор в паре, обозначающий конец последовательности и указывающий на фиктивный элемент, как бы стоящий в последовательности сразу за последним элементом.
Последовательность может представлять собой контейнер, часть контейнера, массив, файл или генерироваться “на ходу”.
Пример диапазона с массивом:
В зависимости от внутреннего устройства контейнера не все характерные для указателей операции могут быть выполнены эффективно на его итераторах. Например, при доступе к связному списку обращение по числовому индексу может потребовать значительного числа операций. Итераторы могут не поддерживать неэффективные операции. Чтобы выделить характерные виды итераторов, в Стандарте C++ определены “категории итераторов”. Принадлежность итератора той или иной категории определяется набором поддерживаемых им операций.
Как правило, итератор нельзя использовать для модификации структуры контейнера (кроме специальных итераторов-адаптеров) без вызова функций самого контейнера.
Категории итераторов
Итератор ввода input iterator предназначен только для однократного чтения (ввода) последовательности значений.
Основная конструкция, поддерживаемая итератором ввода выглядит так:
Итератор вывода output iterator предназначен только для однократной записи (вывода) последовательности. В остальном аналогичен итератору ввода.
Основная конструкция, поддерживаемая итератором вывода, выглядит так:
Однонаправленный итератор forward iterator является расширением концепции “итератор ввода”, т.е. предоставляет возможности итератора ввода (и, возможно, но не гарантированно, итератора вывода). Кроме того, однонаправленный итератор допускает многократное чтение и запись линейной последовательности, по которой можно двигаться только в одну сторону (как по односвязному списку — “вперёд” с помощью операции ++ ).
Итератор произвольного доступа random access iterator является расширением концепции “двунаправленный итератор” и наиболее похож по своему поведению на обычный указатель на элемент массива (который является частным случаем итератора произвольного доступа).
Итератор произвольного доступа допускает адресацию по индексу (оператор [] ), сдвиг в обе стороны на некоторое количество позиций (добавление и вычитание целого числа), вычисление расстояния с помощью вычитания и сравнение на “меньше” и “больше” (согласованное с расстоянием, которое имеет знак).
Для упрощения работы с итераторами Стандартная библиотека предоставляет ряд средств (заголовочный файл ). Перечислим их.
Элементы Стандартной библиотеки для работы с итераторами
Класс характеристик iterator_traits
Классом характеристик traits class называют класс-шаблон, предоставляющий для своего параметра набор некоторых базовых определений, как правило типов и констант, которые некоторым образом характеризуют тип, подставленный в класс характеристик в качестве параметра шаблона.
Теговым классом tag class называют класс, не содержащий никаких членов (пустой), служащий только в качестве номинального значения (имя-константа). То, что это тип, а не значение, позволяет использовать его при выборе конкретного варианта перегруженной функции (см. ниже примеры теговых классов в контексте итераторов). Теговые классы могут состоять в отношениях наследования.
В случае iterator_traits это набор вложенных объявлений типов:
Если шаблон предполагает, что его параметр должен быть итератором, то обычно используются определённые сокращённые названия, указывающие минимальный набор операций, обеспечиваемых итератором, соответственно категориям, например:
Класс iterator
Вспомогательные функции distance, advance, next, prev
Функция distance(from, to) вычисляет расстояние между парой переданных ей итераторов from и to (количество применений оператора инкремента к первому итератору до достижения им второго, либо обычная разность для итераторов произвольного доступа).
Данная функция является хорошим примером использования категории итератора для выбора адекватного алгоритма (данная техника называется “статическая диспетчеризация вызова”). Её можно было бы определить следующим образом:
Функция advance(it, n) сдвигает итератор it (принимает по ссылке) на заданное число шагов n (сдвиг назад при отрицательных значениях n определен для двунаправленных итераторов).
Итераторы-адаптеры
Объекты back_inserter и istream_iterator можно использовать вместе, например, для организации считывания последовательности произвольной длины разделённых пробельными символами чисел. В примере чтение производится из потока cin в контейнер xs, который может иметь тип vector (здесь copy — стандартный алгоритм, о которых см. ниже):
Заметим, что запятая будет поставлена и после последнего выведенного числа, что может быть нежелательным. В этом случае последний элемент следует выводить отдельным вызовом.
Стандартные контейнеры
Ассоциативные контейнеры представлены восемью контейнерами, являющимися комбинациями следующих вариантов (в скобках даны части названий соответствующих стандартных классов): множество (* set ) или словарь (* map ), допускающие повторение элементов (* multi *) или не допускающие, упорядоченные или неупорядоченные ( unordered *).
семантически эквивалентна записи
Тип T здесь не обязан совпадать с типом элементов контейнера, а также может быть ссылочным типом или конструкцией на основе auto (чаще всего используются варианты auto& и auto&& ).
Линейные контейнеры (кроме array ) можно заполнить значениями из заданного диапазона вызовом функции assign (старое содержимое будет уничтожено) и изменить их размер функцией resize (при уменьшении размера лишние элементы удаляются с конца, при увеличении размера новые элементы добавляются в конец).
Линейные контейнеры
Имеется дополнительная фиктивная позиция “перед первым элементом”, возвращаемая функциями before_begin и cbefore_begin (вариант, возвращающий const_iterator ). Элементы можно вставлять в начало: вызов fl.push_front(item) эквивалентен
Функция pop_front удаляет первый элемент списка.
Особенностью контейнеров-списков в составе Стандартной библиотеки C++ также является поддержка более высокоуровневых операций, что проистекает из невозможности эффективного использования одних только итераторов для реализации этих операций:
В целом данные функции аналогичны соответствующим стандартным алгоритмам (см. их список в соответствующем разделе ниже), но выполняются как минимум быстрее, а как максимум — просто выполняются, потому что та же стандартная универсальная сортировка std::sort(from, to) требует итераторов произвольного доступа и поэтому вообще не применима к спискам.
Ассоциативные контейнеры
Все ассоциативные контейнеры поддерживают следующие операции:
Упорядоченные контейнеры построены на сбалансированном двоичном дереве и опираются на строгий порядок (операцию “меньше”, по умолчанию вычисляемую как результат оператора ). Два элемента считаются эквивалентными, если ни один из них не меньше другого.
Последний вариант insert возвращает пару (итератор, булевское значение), первый элемент которой указывает место вставленного или найденного значения, второй же позволяет узнать, было значение вставлено ( true ) или уже находилось во множестве на момент вставки ( false ).
Упорядоченный словарь с неуникальными ключами multimap не определяет operator[] и, по сути, напоминает multiset пар, поиск среди которых ведется только по первому полю (ключу). В качестве примера использования multimap рассмотрим задачу об обращении словаря, хранимого в текстовом файле. Для простоты положим, что словарь состоит из пар слов, упорядоченных по первому слову, слова могут повторяться.
Подумайте, как можно переделать пример с обращением словаря, чтобы не пришлось хранить одни и те же слова дважды (предполагая, что прочитанный словарь нам больше не требуется и его можно уничтожить в процессе обращения)?
Два элемента считаются эквивалентными, если их хэши равны и операция “равно” возвращает истину. Неупорядоченные контейнеры предоставляют доступ к элементам через однонаправленные итераторы.
При вставке, поиске и удалении элементов в среднем неупорядоченные контейнеры в среднем затрачивают постоянное время и могут оказаться заметно быстрее упорядоченных. Однако, в худшем случае время может достигать линейного. Поведение зависит от качества реализации хэш-функции, но полностью избежать таких “скачков” временных затрат может быть невозможно. Поэтому в интерактивных приложениях (например, играх) неупорядоченные контейнеры могут “вести” себя хуже упорядоченных — из-за периодического появления задержек.
Алгоритмы и функторы
Стандартная библиотека C++ содержит несколько десятков функций, называемых алгоритмами, оперирующих на наборах элементов, заданных диапазонами итераторов. Таким образом, итераторы выступают в качестве “клея”, соединяющего алгоритмы и контейнеры. Однако функционал алгоритмов был бы весьма ограничен, если бы не возможность задавать произвольные операции с помощью функторов.
Генератором называют функтор, который не принимает аргументов и возвращает некоторую (генерируемую) последовательность значений. В качестве примера можно привести генератор псевдослучайных чисел.
Предикатом называют функтор, возвращающий булевское значение и используемый, например, при фильтрации последовательностей.
Обычно предикаты являются одноместными (унарными), т. е. принимают один параметр.
Двуместные (бинарные) предикаты, принимающие два параметра и отвечающие некоторому отношению между ними, называют компараторами. Компараторы используются, например, в упорядоченных ассоциативных контейнерах и в стандартном алгоритме sort для определения отношения “меньше”.
Неупорядоченные ассоциативные контейнеры (хэш-таблицы) используют два функтора: компаратор, задающий отношение “равно”, и хэш, задающий способ вычисления хэш-функции для элементов контейнера, возвращающий целое число.
Список стандартных алгоритмов
copy_if(from, from_end, to, pred) — отличается от copy тем, что копирует только те элементы, для которых предикат pred возвращает истину (“фильтр”).
В случае, если диапазон, занимаемый копируемой или перемещаемой последовательностью, пересекается с диапазоном-местом назначения копирования или перемещения, то следует выбирать move или copy для сдвига “назад” и move_backward или copy_backward для сдвига “вперёд”.
Дело в том, что второй итератор в паре, возвращаемой minmax_element указывает не на первый максимальный элемент в диапазоне, а на последний максимальный элемент. Кроме того, minmax_element эффективнее, так как проходит по последовательности только один раз, а не два.
Пример сортировки выбором одновременно минимума и максимума:
remove_copy(begin, end, to, val) и remove_copy_if(begin, end, to, pred) — копируют исходные последовательности, пропуская заданные элементы (аналогично replace – replace_copy и replace_if – replace_copy_if ).
Следующий код считывает последовательность слов с потока ввода, сортирует слова, удаляет дубликаты и выводит полученную последовательность. Обратите внимание, что в нем не встречается ни одного ключевого слова C++.
Рекурсивная быстрая сортировка с выбором первого элемента диапазона в качестве опорного. Общий алгоритм выглядит следующим образом:
stable_sort(begin, end, comp) — отличается от sort тем, что гарантирует устойчивость (сохраняет исходный порядок эквивалентных элементов), однако работает несколько медленнее (обычно в 1.5–3 раза).
Рекурсивная нисходящая сортировка слияниями. Общий алгоритм выглядит следующим образом:
Средства конструирования функторов
Заголовочный файл содержит ряд классов-шаблонов, являющихся функторами-обёртками соответствующих операций: компараторы less (операция ‘ greater (операция ‘>’), less_equal (операция ‘ greater_equal (операция ‘>=’), equal_to (операция ‘==’), not_equal_to (операция ‘!=’), двуместные операции plus (операция ‘+’), minus (операция ‘-’), multiplies (операция ’*’) и т.д. Например, отсортировать vector v по убыванию можно так:
Все эти операции являются шаблонами, принимающими тип аргумента. Если его не указывать, он будет выводиться автоматически в месте применения (C++14).
Впрочем, многие подобные применения на деле проигрывают в краткости и понятности записи циклу for(:). Например, удвоение каждого элемента контейнера v1 “на месте”:
На деле возможности mem_fn и bind довольно ограничены. Наиболее сильным средством, появившимся в ISO C++11, являются замыкания — объекты анонимных функторов, создаваемые в месте использования с помощью лямбда-выражений. Структура лямбда-выражения слагается из следующих элементов:
Например, с помощью лямбда-выражений два из предыдущих примеров можно переписать так:
Замыкания можно сохранять в переменные. При этом ключевое слово auto решает проблему неизвестного типа. Данное свойство позволяет создавать локальные функции внутри другой функции с доступом к локальным переменным внешней функции, если это требуется.
Пример — динамический массив
Данный пример является дальнейшим развитием класса Darr с целью приблизить его интерфейс к интерфейсу стандартных контейнеров (ну и задействовать стандартные алгоритмы по возможности).
Версия 4
Добавим итераторы и другие типичные для стандартных контейнеров объявления вложенных типов. В нашем случае итераторы — просто указатели.
Определим операторы сравнения массивов на равенство и неравенство (поэлементное):
Версия 5
В версии 4 у нас не было конструктора, принимающего диапазон, заданный парой итераторов, и создающего массив из элементов, содержащихся в этом диапазоне. Такие конструкторы есть у большинства стандартных контейнеров, поэтому попробуем создать его и мы.
Чтобы разрешить код вида
следует определить конструктор, принимающий initializer_list :
Делаем свой итератор
Не часто возникает необходимость создать свой итератор и хотелось бы иметь под рукой небольшой HowTo. В этой заметка хочу рассказать как создать простейший итератор, который можно использовать в стандартных алгоритмах типа std::copy, std::find. Какие методы и определения типов нужны в классе контейнере, чтобы его можно было обходить в циклах for из c++11 и BOOST_FOREACH.
Контейнер
В классе контейнере необходимо определить типы iterator и const_iterator (типы нужны во-первых для удобства, а во-вторых без них не будет работать обход при помощи BOOST_FOREACH), а также методы begin и end (тут в зависимости от требований, можно добавить только константные методы возвращающие const_iterator):
Для примера возьмем контейнер хранящий массив целых чисел.
Естественно, ничто не мешает определить iterator и const_iterator как псевдонимы одного и того же типа.
Итератор
Как он определе в g++ 4.9
В конструктор будем передавать указатель на элемент массива хранящийся в OwnContainer.
На этом можно было бы и остановиться, но в библиотеке boost есть базовый класс для создания итераторов, и о нем то же хочу сказать пару слов.
Итератор унаследованный от boost::iterator_facade
Контейнер отличается только типами на которые ссылаются iterator и const_iterator:
Итератор наследуется от шаблонного типа boost::iterator_facade. Это шаблонный класс, первый параметр — тип наследника, второй тип значения, третий тип итератора. В качестве типа итератора может выступать тип используемый в std::iterator, так и специфичные для boost (в описании такой вариант обозначен как old-style), я возьму тот же тип, что и для std::iterator. boost::iterator_facade реализует необходимые методы: operator*, operator++, operator-> и т.д. Но их реализация базируется на вспомогательных методах, которые нужно реализовать в нашем итераторе, а именно dereference, equal, increment, decrement, advance, distance. В простом случе (как наш) потребуются только equal, increment и dereference. Так как эти методы используются для релизации интерфейса итератора, то разместим их в секции privat, а класс их использующий (boost::iterator_core_access) объявим другом.
Заключение
Итератор можно создать и использовать без контейнера, а иногда контейнер не нужен вовсе. Итераторы могут служить обертками над другими итераторами и модифицировать их поведение, например выдавать элементы через один. Или отдельно хранятся данные, а отдельно контейнер с некоторыми ключами или значениями полей. И можно организовать итератор, который будет проходится по всем желементам, но возвращать только те что соответвуют некотрому условию основанному на значениях второго контейнера. Еще идеи можно почерпнуть в статье Недооценённые итераторы написанной k06a.
Для простых итераторов использование boost::iterator_facade не очень актуально, но для более сложных позволяет сократить количество кода, естественно, если библиотека boost уже используется, тянуть её только ради iterator_facade смысла нет.
Недооценённые итераторы
Речь пойдет о стандартной библиотеке шаблонов STL. Будут рассмотрены существующие типы итераторов и их классификация, а также будут предложены несколько новых обёрток над итераторами. Которые позволят в некоторых случаях избежать лямбда-выражений, которых до С++11 как бы и нет.
Вступительное слово
Одной из основных парадигм данной библиотеки было разделение двух сущностей. Контейнеров и алгоритмов. Но для непосредственного воздействия алгоритмом на данные контейнера пришлось ввести промежуточную сущность — итератор.
Итераторы позволили алгоритмам получать доступ к данным, содержащимся в контейнере, независимо от типа контейнера. Но для этого в каждом контейнере потребовалось определить класс итератора. Таким образом алгоритмы воздействуют на данные через итераторы, которые знают о внутреннем представлении контейнера.
Типы итераторов в STL
Помимо итераторов, осуществляющих доступ к данным определённого контейнера в библиотеке STL имеются ещё несколько итераторов:
1. back_insert_iterator и front_insert_iterator
2. insert_iterator
3. istream_iterator и ostream_iterator
Итераторы типов back_insert_iterator и front_insert_iterator при модификации содержимого осуществляют вставку элемента методом push_back() или push_front(). Операции перемещения к предыдущему/следующему элементу контейнера эти итераторы попросту игнорируют.
Итератор insert_iterator при модификации осуществляет вставку данных. Ему в конструктор передаются контейнер и итератор на позицию, куда следует вставлять данные.
Итераторы istream_iterator и ostream_iterator осуществляют считывание данных из потока и запись данных в поток. В конструкторы этих итераторов необходимо передать входной или же выходной поток.
Классификация итераторов
Существующая классификация итераторов насчитывает 5 категорий итераторов:
1. Input iterator
2. Output iterator
3. Forward iterator
4. Bidirectional iterator
5. Random access iterator
Разработка декоратора итератора
Для реализации нескольких следующих идей необходимо было реализовать обертку или декоратор (wrapper). Декоратор итератора должен иметь ту же самую категорию, что и оборачиваемый итератор, а значит предоставлять тот же самый набор методов. В соответствии с приведённой таблицей категорий было разработано:
1. Пять классов-примесей (mixin), реализующих не пересекающиеся наборы методов.
2. Шаблонный класс декоратора, параметризуемый категорией итератора.
3. Пять специализаций шаблона, отличающиеся набором подмешиваемых примесей.
4. Фабрика для удобного (без явных шаблонных параметров) обёртывания итератора.
[На этот код можно взглянуть здесь, он почти работает]
После небольшого обсуждения получившейся структуры с одним хорошим человеком была выработана новая структура. Не такая насыщенная шаблонами и более лаконичная. Решено было реализовать все методы всех категорий итераторов в одном шаблонном классе, параметризуемом категорией итератора. Было использовано следующее свойство языка C++: компилируются только те методы шаблонного класса, вызов которых реально осуществляется.
Таким образом, если потребуется обернуть итератор категории Input будут скомпилированы только те методы которые, относятся к категории Input и вызываются. При попытке вызова метода не принадлежащего этой категории — возникнет ошибка компиляции. А это как раз то к чему мы стремились.
Битовый итератор
Битовый итератор позволяет обходить элементы контейнеров побитно. Итератор может использоваться как для считывания, так и для записи значений битов. У итератора имеются параметры:
1. В каком порядке обходить байты элементов контейнера
2. В каком порядке обходить биты в байтах
Полевой итератор
Полевой итератор представляет из себя итератор, который при разыменовывании возвращает значение одного из полей структуры. Может оказаться весьма полезен для поиска объекта по значению одного из полей. Пример использования:
Макрос fieldof(Class,Field) выглядит следующим образом:
UPD
Как заметил пользователь mayorovp, можно было обойтись указателем на поле класса:
Сортирующий итератор
Сортирующий итератор представляет из себя итератор, выполняющий обход элементов в порядке их сортировки. Элементы контейнера не модифицируются в процессе обхода итератором. Плюсом в данном случае является то, что время на сортировку не тратится (нет определённого участка времени отведённого под сортировку).
При перемещении итератора к следующему элементу осуществляется поиск наименьшего элемента среди оставшихся, которые больше-или-равны предыдущему. Таким образом сложность алгоритма получается O(N 2 ), но специального времени отведённого под сортировку нет. Сортировка осуществляется в процессе обращения к данным. Обращение через итераторы осуществляется пошаговое — сортировка тоже пошаговая.
Итератор параметризуется порядком сортировки. По-умолчанию: сортировка по возрастанию.
