Делаем свой итератор
Не часто возникает необходимость создать свой итератор и хотелось бы иметь под рукой небольшой 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 смысла нет.
Реализация итераторов в C# (часть 1)
От переводчика:
Не так давно мой менее опытный коллега спросил меня о том, для чего используется yield return в C#. Я не очень часто пишу свои итераторы, поэтому, отвечая ему, я сомневался в своих словах. Справившись в MSDN, я укрепился в сказанном, но у меня возник вопрос: “А во что же всё таки компилируется эта инструкция?” К тому моменту, я уже был знаком с переводимой статьёй, однако всё, что в ней сказано, давно “выветрилось”. Статья старая, но мне думается, что она может быть полезна для определённой группы разработчиков, привыкшей читать русскоязычные статьи и документы.
Как и анонимные методы, итераторы в C# являются сложным синтаксическим сахаром. Вы можете реализовать их полностью самостоятельно (в конце концов, в ранних версиях C# вам приходилось делать это), но использовать компилятор намного удобнее. Идея, стоящая за итераторами заключается в том, что они принимают функцию с yield return выражениями (и, возможно, yield break выражениями) и конвертируют её в конечный автомат. Когда вызывается yield return, состояние функции сохраняется, и при повторном обращении к итератору для получения очередного объекта это состояние восстанавливается. Главное в итераторах то, что все локальные переменные итератора (в том числе параметры итератора как предварительно инициализировнные локальные переменные, включая скрытый параметр this) становятся переменными-членами (далее полями) вспомогательного класса. Помимо этого вспомогательный класс содержит поле state, которое следит, где произошло прерывание исполнения, и поле current, хранящее самый последний из уже перечисленных объектов.
Метод CountFrom создаёт перечислитель целых чисел, который производит целые числа от start до limit включительно с шагом 1. Компилятор неявно конвертирует этот перечислитель во что-то вроде этого:
Перечисляющий класс автоматически генерируется компилятором и, как было обещано, он содержит поля для состояния и текущего объекта, плюс по одному полю на каждую локальную переменную. Свойство Current просто возвращает текущий объект. Вся же настоящая работа происходит в методе MoveNext.
Кроме этого есть выражения yield break.
Каждое выражение yield break преобразуется в
где n2 — число, на единицу большее, чем наибольший номер из всех состояний, использующихся в выражениях yield return. Не забывайте, что в конце каждой функции подразумевается вызов yield break.
Наконец, компилятор вставляет большой диспетчер состояний в самом начале функции.
по одному case-выражению создаётся для каждого состояния, плюс на начальное и конечное состояние n2.
Введение в итераторы в С++
Обновл. 15 Сен 2021 |
На этом уроке мы рассмотрим тему использования итераторов в языке С++, а также связанные с этим нюансы.
Итерация по элементам структур данных
Итерация/перемещение по элементам массива (или какой-нибудь другой структуры) является довольно распространенным действием в программировании. Мы уже рассматривали множество различных способов выполнения данной задачи, а именно: с использованием циклов и индексов (циклы for и while), с помощью указателей и адресной арифметики, а также с помощью циклов for с явным указанием диапазона:
Использование циклов с индексами в ситуациях, когда мы используем их только для доступа к элементам, требует написания большего количества кода, нежели могло бы быть.
При этом данный способ работает только в том случае, если контейнер (например, массив), содержащий данные, дает возможность прямого доступа к своим элементам (что делают массивы, но не делают некоторые другие типы контейнеров, например, списки).
Использование циклов с указателями и адресной арифметикой требует довольно большого объёма теоретических знаний и может сбить с толку читателей, которые не знакомы с адресной арифметикой и не знают её правил. Да и сама адресная арифметика применима лишь в том случае, если элементы структуры данных расположены в памяти последовательно (что опять же верно для массивов, но не всегда выполняется для других типов данных, таких как списки, деревья, карты).
Примечание для продвинутых читателей: Указатели (без адресной арифметики) могут использоваться для перебора/итерации некоторых структур данных с непоследовательным расположением элементов. Например, в связном списке каждый элемент соединен указателем с предыдущим элементом, поэтому мы можем перебирать список, следуя по цепочке указателей.
Циклы for с явным указанием диапазона чуть более интересны, поскольку у них скрыт механизм перебора нашего контейнера, но при всем этом они всё равно могут быть применены к различным структурам данных (массивы, списки, деревья, карты и т.д.). «Как же они работают?» — спросите вы. Они используют итераторы.
Итераторы в С++
Итератор — это объект, разработанный специально для перебора элементов контейнера (например, значений массива или символов в строке), обеспечивающий во время перемещения по элементам доступ к каждому из них.
Контейнер может предоставлять различные типы итераторов. Например, контейнер на основе массива может предлагать прямой итератор, который проходится по массиву в прямом порядке, и реверсивный итератор, который проходится по массиву в обратном порядке.
После того, как итератор соответствующего типа создан, программист может использовать интерфейс, предоставляемый данным итератором, для перемещения по элементам контейнера или доступа к его элементам, не беспокоясь при этом о том, какой тип перебора элементов задействован или каким образом в контейнере хранятся данные. И, поскольку итераторы в языке С++ обычно используют один и тот же интерфейс как для перемещения по элементам контейнера (оператор ++ для перехода к следующему элементу), так и для доступа (оператор * для доступа к текущему элементу) к ним, итерации можно выполнять по разнообразным типам контейнеров, используя последовательный метод.
Указатели в качестве итераторов
Простейший пример итератора — это указатель, который (используя адресную арифметику) работает с последовательно расположенными элементами данных. Давайте снова рассмотрим пример перемещения по элементам массива, используя указатель и адресную арифметику:
Iterators
Почти каждой написанной вами программе придется выполнять итерацию определенной коллекции. Для этого вы напишете код, проверяющий каждый элемент в коллекции.
Кроме того, вы создадите методы итератора, то есть методы, которые создают итератор для элементов соответствующего класса. Итератор — это объект, который выполняет обход контейнера, в частности списков. Итераторы можно использовать для следующих целей:
Язык C# предоставляет возможности для создания и использования последовательностей. Эти последовательности можно создавать и использовать синхронно или асинхронно. В этой статье представлены общие сведения об этих функциях.
Итерация для каждого
Вы полнить перечисление коллекции несложно. Ключевое слово foreach перечисляет коллекцию, выполняя внедренный оператор по одному разу для каждого элемента в коллекции:
Если последовательность создается асинхронно, можно использовать инструкцию await foreach для асинхронного использования этой последовательности.
Источники перечисления с применением методов итератора
Напишем метод итератора, выдающий последовательность целых чисел от 0 до 9:
Это синтаксис применим как для синхронных, так и для асинхронных итераторов. Давайте рассмотрим практический пример. Допустим, вы занимаетесь проектом IoT и имеете дело с датчиками устройств, которые создают большой поток данных. Чтобы получить представление об этих данных, можно написать метод, формирующий выборку из каждого N-го элемента данных. С этой задачей справится вот такой небольшой метод итератора:
Если при чтении из устройства Интернета вещей создается асинхронная последовательность, метод необходимо изменить, как показано в следующем методе:
Немного изменим последний метод, вставив в каждом случае оператор yield return :
Подробнее об операторе foreach
Компилятор преобразует первую асинхронную выборку в конструкцию следующего вида:
Общий случай асинхронного использования разворачивается следующим образом:
К счастью, запоминать все это не нужно. Оператор foreach обрабатывает все эти нюансы в фоновом режиме, а компилятор создает правильный код для любой из этих конструкций.
Как более менее правильно написать итератор(не STL).
Написать свой итератор, чтобы алгоритмы STL работали с моим классом
Как написать свой итератор, чтобы действовал как стандартный и мог использовать STL алгоритмы. (У.
Как можно получить итератор на элемент обрабатываемый в лямбде в функции for_each?STL
Как можно получить итератор на элемент обрабатываемый в лямбде? for_each(arr.begin(), arr.end().
Найти вероятность того, что герб выпадет: 2 раза; не менее 2 раз; не более 2 раз; не менее одного и не более трех раз
Монету бросают 6 раз. Найти вероятность того, что герб выпадет: а) 2 раза; б) не менее 2 раз; в)не.
STL итератор на конец контейнера
Подскажите пожалуйста у меня задача сделать дерево и слизать интерфейс с STL std::map. Вопрос в.
Решение
Вот еще из моих материалов.
Надеюсь, что даже в таком виде это поможет разобраться.
Итератор для последовательного контейнера
Для дека нам потребуются конструкторы и деструктор. Минимально необходимое множество операций включает операции добавления элемента в начало и конец дека, операции удаления первого и последнего элемента. Еще необходимы функция проверки, есть ли в контейнере элементы, и функция, выдающая количество элементов в контейнере. Обычно в состав методов включают и методы получения значений первого и последнего элемента контейнера. Рассмотрим более подробно операцию доступа к элементам контейнера.
Так как внутренняя структура элемента скрыта, поскольку прописана в приватной части класса-дека, программа-клиент не сможет работать с элементами контейнера посредством указателей. Для перебора элементов контейнер должен обеспечить последовательный доступ к элементам другим способом. Это можно сделать двояким образом:
1. либо реализовать методы доступа непосредственно как методы контейнера;
2. либо инкапсулировать все операции доступа в отдельный класс-итератор.
Второе решение предпочтительней хотя бы потому, что позволяет отделить интерфейс доступа от интерфейса контейнера. Это позволит в дальнейшем иметь один и тот же универсальный интерфейс доступа для разных типов контейнеров. Таким образом, итераторы играют очень важную роль при инкапсуляции информации контейнеров.
ВНИМАНИЕ
Именно таким образом реализованы итераторы в стандартной библиотеке шаблонов STL. Это одно из решений, оказавших существенное влияние на состав и структуру стандартной библиотеки.
Класс-итератор можно реализовать как отдельный независимый класс. Но так как итератор должен иметь доступ к внутренней структуре элемента контейнера, он должен с этим классом «дружить». Очевидно, что итератор очень тесно связан с внутренней организацией контейнера, поэтому лучше его реализовать как вложенный класс [1-9.7] класса-контейнера, как и класс-узел. Поскольку программе-клиенту потребуется создавать объекты-итераторы, этот класс должен быть определен в открытой части класса контейнера.
Назовем класс-итератор именем iterator. Мы нарушили собственное правило начинать имя класса с буквы Т только потому, что при создании итератора программа-клиент обязана будет указать префикс — имя объемлющего класса, например
Для того, чтобы начать перебирать элементы контейнера, итератору надо присвоить первоначальное значение на первый элемент контейнера. Обычно для этого в контейнер включают метод begin(), который в качестве результата возвращает итератор, установленный в начало последовательности элементов контейнера.
Метод end() возвращает итератор, установленный в конец последовательности элементов контейнера. Что считать концом последовательности, составляет важный вопрос реализации. По примеру STL (STL — прекрасный пример для подражания!) будем считать, что концом последовательности является позиция за последним элементом последовательности. Таким образом, пара методов begin(), end() определяет полуоткрытый интервал, который содержит первый элемент, но выходит за пределы последнего элемента. Это в точности соответствует ситуации, описанной нами при реализации конструктора класса TArray (см. листинг 3.3).
Полуоткрытый интервал обладает двумя достоинствами:
— не нужно специально обрабатывать пустой интервал, так как в пустом интервале begin() равно end();
— упрощается проверка завершения перебора элементов контейнера — цикл продолжается до тех пор, пока итератор не достигнет позиции end().
Для реализации полуоткрытого интервала в контейнер обычно добавляют «пустой» фиктивный элемент, не содержащий данных.
Реализация контейнера-дека
Обратимся теперь непосредственно к реализации. Сначала покажем составляющие класса TDeque, а затем всю его структуру. В листинге 3.19 представлена приватная часть класса.
В этом случае друзей объявлять не требуется – они и так имеют доступ ко всем элементам класса.
Чтобы не отвлекаться от главной задачи — изучения доступа посредством итератора, — мы объявили конструктор копирования и операцию присваивания закрытыми. Да и нет особой необходимости (пока) присваивать деки. Наличие объявления приводит к тому, что компилятор не будет создавать эти функции по умолчанию. Таким образом, мы запретили создавать копии контейнера-дека и присваивать один дек другому. Следствием является так же и то, что контейнер нельзя передавать по значению в качестве параметра и возвращать в качестве результата.
Далее объявлены поля класса TDeque: счетчик элементов контейнера, реальные указатели на начало и конец списка. Счетчик увеличивается при каждом добавлении элемента и уменьшается при каждом удалении элемента. Поля-указатели никогда не равны 0, так как даже в пустом контейнере присутствует запредельный фиктивный элемент
А вот программе-клиенту указатели недоступны — она работает с итераторами. Следовательно, нужны аналогичные поля для класса-итератора, которые этим классом и инициализируются. Сам класс-итератор (листинг 3.20) прописан в открытой части класса TDeque.
Единственный закрытый элемент класса — указатель на элемент контейнера-дека. Именно это должен скрывать итератор, предоставляя пользователю более надежный способ доступа. Однако для первоначальной установки указателя нашему деку требуется конструктор с указателем. Поэтому реализован приватный конструктор, и класс-дек сделан другом класса-итератора.
В операции разыменования operator * указатель на элемент проверяется на ноль. Эта проверка необходима, так как в классе-итераторе есть конструктор по умолчанию, обнуляющий этот указатель — программа-клиент ведь может объявить итератор, но не инициализировать его.
ПРИМЕЧАНИЕ
Вообще-то говоря, мы можем сделать этот конструктор приватным — тогда пользовательская программа не сможет создавать нулевые итераторы. Естественно, и проверка на ноль тогда будет тоже не нужна.
Все методы удобнее реализовать именно внутри класса, так как при реализации вне класса (и вне класса TDeque), придется писать слишком длинные префиксы.
С учетом всех этих соображений класс TDeque, представленный в листинге 3.21, выглядит следующим образом:
Однако мы не можем этого сделать, так как закрыли операцию присваивания.
Рассмотрим теперь реализацию операций вставки и удаления в начале дека (листинг 3.22).