Как написать свой итератор c

Итераторы

При обсуждении алгоритмов стандартной библиотеки C++ мы постоянно использовали итераторы. Из контекста мы поняли, что итераторы используются для указывания на элементы контейнеров. Пришло время сформировать более полное представление об этих объектах, узнать какие типы итераторов существуют, рассмотреть еще несколько ситуаций, в которых полезно использование итераторов.

Определение и классификация итераторов

Итератор — это объект, который указывает на элемент в диапазоне элементов (например, в массиве), с помощью итератора можно перебирать элементы диапазона, используя определенный набор операций. Для итератора определены по крайней мере операторы инкремента ( ++ ) и разыменовывания ( * ).

Существует пять типов итераторов, организованных следующим образом:

• Input Iterator
  • Forward Iterator
    • Bidirectional Iterator
      • Random access Iterator

      Output итераторы можно разыменовывать в левой части выражений:

      Input итераторы можно сравнивать с помощью операторов == и != . Каждый следующий подкласс Input итератора расширяет функционал:

      • Forward Iterator могут выполнять роль Output итератора. Итераторы этого типа используются для перебора элементов с помощью оператора инкремента.
      • Bidirectional Iterator позволяет дополнительно к функциональности Forward Iterator использовать оператор декремента — и перебирать последовательность в обратном направлении. Итератор двусвязного списка из стандартной библиотеки list::iterator является Bidirectional Iterator.
      • Random access Iterator позволяет получить доступ к произвольному элементы диапазона по индексу, поддерживают операторы сравнения < , <= , > , >= и арифметические операторы + и — . Итератор vector::iterator является Random access Iterator.

      Если открыть документацию алгоритмов, которые мы рассматривали раньше, то можно уточнить наше понимание работы алгоритмов с итераторами: каждый алгоритм предъявляет требования к итератору, с которым его можно использовать. Например, один из вариантов алгоритма find определен так:

      т.е. для работы с этим алгоритмом итератор должен всего лишь обладать возможностями Input Iterator. А вот как выглядит один из вариантов алгоритма sort :

      Сортировка за “линеарифмическое” время требует доступа к элементам диапазона по индексу, поэтому алгоритм sort требует Random access Iterator.

      Теперь, когда мы разобрались с основными понятиями, рассмотрим несколько ситуаций, в которых полезно использовать итераторы.

      Итераторы и цикл for

      Перебрать в цикле все элементы контейнера set , как мы знаем, можно с помощью range-based цикла:

      А что, если у нас есть два контейнера set одинакового размера, и мы хотим синхронно пройти по ним в цикле. В подобных ситуациях на помощь приходят итераторы:

      Стандартные контейнеры предоставляют обратные итераторы reverse_iterator , которые позволяют перебрать элементы диапазона в обратном порядке, например:

      Наконец, если мы работаем с константным объектом, либо если мы хотим избежать случайной модификации элементом диапазона, то следует использовать константный итератор const_iterator и методы cbegin() и cend() :

      Конструирование контейнеров с помощью итераторов

      Практически все стандартные контейнеры могут быть сконструированы с помощью двух итераторов, указывающих на границы диапазона элементов. Это позволяет, например, одной строчкой создавать и наполнять новый контейнер элементами другого контейнера, даже если типы контейнеров отличаются:

      Еще один пример, который выглядит несколько непривычно, позволяет с помощью итератора istream_iterator прочитать все объекты из стандартного потока ввода в vector , а затем с помощью итератора ostream_iterator и алгоритма copy передать все элементы вектора в стандартный поток вывода:

      Отметим, что istream_iterator<int>() , как и нулевой указатель для списков, является универсальной меткой конца всех потоков данного типа.

      Вставка объектов с помощью back_inserter

      Последний пример, который мы рассмотрим, использует итератор back_insert_iterator , который позволяет добавлять элементы в конец контейнера:

      Функция back_inserter создает для нас нужный итератор. Без этой функции нам пришлось бы написать back_insert_iterator<std::vector<int>>(v) .

      Резюме

      Мы обсудили типы итераторов, рассмотрели использование итераторов в цикле for , конструирование контейнеров с помощью диапазона, заданного итераторами, и вставку элементов в контейнер с помощью итератора back_inserter . Знание различных итераторов и их возможностей позволяет использовать контейнеры и алгоритмы стандартной библиотеки наиболее полно.

      A short introduction

      If you took some time to learn about design patterns you will most likely run into a reference to or people just saying to look over the “gang of 4” book, which refers to the book: Design Patterns Elements of Reusable Object-Oriented Software by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides and, as you can tell, this a mouth full, thus the “gang of 4” expression was born.

      What is an iterator?

      The definition of the iterator is kind of vague and doesn’t explain much: “Provide a way to access the elements of an aggregate object sequentially without exposing the underlining representation”.

      We can understand from the first part of this definition that the iterator will access elements of an aggregate and the aggregate would be something that holds data in a sequence of some sort, for example, an array of integers is an aggregate that holds integers in a sequence. Why would you even care about creating a different way of accessing elements within an array when you could simply increment the pointer, you might ask, well, complex aggregates like trees, graphs and lists are not that simple to iterate over. Not everything needs to have an iterator implementation and it’s up to you to know when you should create one.

      So what about the second part: “without exposing the underlining representation”, what does this mean? For a simple array that holds integers we know that the memory allocated for each element is contiguous and we simply have to increment the pointer starting with the first element to traverse the array and to do this you wouldn’t care about how the array was constructed because you know that for any array you could just use a for-loop to go over each element.

      Now getting back to the question, when the data structure is complex to know how to iterate over it you would have to understand how it was written, which can be difficult, not to mention the testing time you would spend to make sure you got it right, but an iterator is easy to use and you don’t care how the structure was written as all iterators are used in the same manner.

      example:

      The vector class exposes an iterator:

      The great thing about an iterator is that with the above code you could simply change the data structure from a vector to a set or a list or even a map (any structure you can think about) and it will work the exact same way.

      How to write an iterator?

      Now that, hopefully, we can understand what an iterator is, we can take a look at an example that implements an iterator over a singly linked list.

      Just as a refresher a singly linked list is a linear data structure, however, unlike arrays, the elements are NOT stored in a contiguous block of memory, they can be stored anywhere there is room in memory and each element keeps a pointer to the next one.

      Note that in this exercise we will be using smart pointers (specifically unique_ptr) so that we don’t have to worry about freeing the memory manually for the stored data. If you’re not familiar with smart pointers there is a lot of great information out there about them.

      Alright, what do we need to do first?

      We need to have some sort of a structure where we can store some data and the link to the next element:

      We then need to write a class that will represent our list and because we don’t care too much about what type our data is we will create a template class that can accept all sorts of data.

      In the code below I’ve added the Node as an inner class and in most cases, this is fine because the node is rather specific to our structure:

      As you might have noticed I’ve added a head that will always be the first node in the list and size where we keep track of the number of elements in the list. Keeping track of the number of elements in the list is useful to find out if the list is empty without having to go through the list, for this, we can build these two methods:

      Now we can think about what can the list do and like any data structure, the list should be able to add an element to the list which can be the following operations: adding to the front of the list, adding to the back of the list and inserting an element at a certain position.

      Adding to the front is simple enough, we just have to check if the list is empty in which case we create the head and if the list is not empty we create a new node that points to the head and then we reset the head to the new node and increment size:

      Adding to the back involves going through the list because we can’t access any elements directly except for the head:

      We will talk about inserting an element later on when we get to the Iterator implementation.

      A list should also be able to remove an element and clear the entire list.

      I’ll add here only the clear method, you can think about how to remove an element based on this example:

      Something that can be useful in certain situations is to reverse the list. Reversing the list is not something that is straightforward for many people, I’ve struggled to grasp the idea myself. What happens when we need to reverse the list, or at least how this made sense in my head, is to change the direction of the links, which means that head will now link to null, the next node from head will point to head and so on until we reach the last node that will be set back to head:

      We talked about some interesting stuff, but we also have to talk about some of the necessary things that we have to write in our list so that it functions properly and I’m referring to the rule of 5 which we cannot escape from because our data is not trivial. The rule of 5 states that if you create either of these: a copy constructor, copy assignment operator, move constructor, move assignment operator, or a destructor then you have to create all 5.

      Aside from the rule of 5 semantics, I would like to add a special constructor that can make life easier for most people to use our structure. The constructor will create a list of elements from an initializer list.

      An initializer list is one of the great things in C++ and it looks like this: — and you probably have seen this a lot. So let’s see how we can implement it:

      You would ask yourself: “why didn’t we just use push_front or push_back?” — well, push front will give us back the list but in the reverse order which will not resemble the given initializer list. Push_back will be an O(n²) operation because we have to reposition to the back for each element in the list.

      Now, before we move on to actually implement the iterator let’s talk about what would be your first thought on just printing each element in the list. The first go-to, would be to build up a simple method that will go through the list and print each element since we already know how to traverse it.

      So let’s do that! Here is a simple method that just prints out each node:

      I’ll add that to successfully convert a node to string I’ve added a conversion operator to the Node structure that will use a custom to_string function which can convert anything convertible to string:

      The helper namespace looks like this:

      Using the printList list method will be easy:

      This works fine, but what if we want to print just “two”? We will then need to create another method that will look for it and then print it, which isn’t all that bad, just two methods, now, what if we want to print all elements that start with the letter “o” or if we want to create a big string out of all of them… I think you get the picture now!

      Wouldn’t it be nice to have something that can access elements and perhaps also be used with great implementation from the <algorithm> standard header? For that, we need the iterator.

      Let’s see how we can build one!

      We have to think about how we can traverse the list, how to expose a certain element and how to compare elements. Now, when you think about it, traversing the list is just accessing the next element until we reach a nullptr, plus we can’t traverse the list in either direction because we only have one-way access. Accessing an element means accessing its data member and eventually comparing elements means if an element is the same or not as another element.

      Because we move only one way, overloading the “++” operator should be sufficient and accessing an element basically means dereferencing a pointer, hence overloading the “*” operator is also needed. Comparison can be either “==” or “!=” for pointers, but we will just overload “!=” operator so that we can use it to see if we have reached the end of the list.

      We will need to create an iterator class (or struct) that takes a pointer to the head element from the list:

      The Iterator struct will be nested as part of the LinkedList class like we did with the node since this is an iterator for this LinkedList. (it doesn’t have to be)

      The list will have to implement two important methods:

      1. begin() — will return an iterator initialized with the head element

      2. end() — will return nullptr and this will represent the end

      Now we can use our iterator to traverse the list as we would normally do with a simple vector:

      At this point, the iterator we created cannot modify the list and all elements return is const, thus this can be considered and const iterator. But we can make a few simple modifications to the iterator class so that we could also insert an element while we iterate:

      We have to add LinkedList as a friend class to the Iterator so that it can access its private members: friend class LinkedList and remove const from Iterator::previous_node and Iterator::current_node.

      As a final thing we will be adding a new method that inserts a new element before a specified position:

      Just as an overview of the method we can see that because we’re moving the next node from current to newNode->next we can no longer return this position thus we have to return a new iterator from this position. This way we don’t invalidate the iterator and we can move on with the traversal.

      The entire code can be viewed here:

      Conclusion

      Building an iterator will simplify the code for the given data structure just because the iterator is responsible for traversing the structure and not the structure itself, the structure’s only responsibility is to supply the start and the end for the iterator.

      You can build various types of traversals (ex: forward, reverse, in-order, pre-order) and you can switch between these types of traversal by just changing the iterator.

      More than one traversal can be applied on the same data structure at a time because the iterator keeps track of its own traversal state. If needed you can delay an iteration and continue later on.

      Урок №198. Итераторы STL

      Итератор — это объект, который способен перебирать элементы контейнерного класса без необходимости пользователю знать реализацию определенного контейнерного класса. Во многих контейнерах (особенно в списке и в ассоциативных контейнерах) итераторы являются основным способом доступа к элементам этих контейнеров.

      Функционал итераторов

      Об итераторе можно думать, как об указателе на определенный элемент контейнерного класса с дополнительным набором перегруженных операторов для выполнения четко определенных функций:

      Оператор * возвращает элемент, на который в данный момент указывает итератор.

      Оператор ++ перемещает итератор к следующему элементу контейнера. Большинство итераторов также предоставляют оператор −− для перехода к предыдущему элементу.

      Операторы == и != используются для определения того, указывают ли оба итератора на один и тот же элемент или нет. Для сравнения значений, на которые указывают оба итератора, нужно сначала разыменовать эти итераторы, а затем использовать оператор == или оператор != .

      Оператор = присваивает итератору новую позицию (обычно начальный или конечный элемент контейнера). Чтобы присвоить значение элемента, на который указывает итератор, другому объекту, нужно сначала разыменовать итератор, а затем использовать оператор = .

      Каждый контейнерный класс имеет 4 основных метода для работы с оператором = :

      метод begin() возвращает итератор, представляющий начальный элемент контейнера;

      метод end() возвращает итератор, представляющий элемент, который находится после последнего элемента в контейнере;

      метод cbegin() возвращает константный (только для чтения) итератор, представляющий начальный элемент контейнера;

      метод cend() возвращает константный (только для чтения) итератор, представляющий элемент, который находится после последнего элемента в контейнере.

      Может показаться странным, что метод end() не указывает на последний элемент контейнера, но это сделано в целях упрощения использования циклов: цикл перебирает элементы до тех пор, пока итератор не достигнет метода end(), и тогда уже всё — «Баста!».

      Наконец, все контейнеры предоставляют (как минимум) два типа итераторов:

      container::iterator — итератор для чтения/записи;

      container::const_iterator — итератор только для чтения.

      Рассмотрим несколько примеров использования итераторов.

      Итерация по вектору

      Заполним вектор 5-ю числами и с помощью итераторов выведем значения вектора:

      Делаем свой итератор

      Не часто возникает необходимость создать свой итератор и хотелось бы иметь под рукой небольшой 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

      Это шаблонный класс, первый параметр шаблона — тип итератора, так как собираемся использовать со стандартной библиотекой, то тип выбирается из следующих типов: input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag, random_access_iterator_tag. Второй параметр тип значения которое хранится и возвращается операторами * и ->, теретий параметр — тип который может описывать растояние между итераторами, четвртый шаблонный параметр — тип указателя на значение, пятый — тип ссылки на значения. Обязательными являются первые два параметра.

      Самый просто итератор — это InputIterator (input_iterator_tag), он должен поддерживать префиксную форму инкремента, оператор !=, оператор* и оператор -> (его реализовывать не буду, так как в примере итератор используется для типа int, и в этом случае operator-> бессмысленен). Помимо этого понадобится конструктор и конструктор копирования. В примере не предполагается создание итератора кроме, как методами begin и end класса контейнера, поэтому конструктор итератора будет приватным, а класс контейнера объявлен как дружественный. И добавим оператор ==, во-первых хорошая практика добавлять поддержку != и == вместе, а во-вторых без этого не будет работать BOOST_FOREACH.

      const_iterator не сильно отличается от iterator, поэтому объявим iterator как шаблонный класс с одним параметром — тип возвращаемого значения для операторов * и ->.

      В конструктор будем передавать указатель на элемент массива хранящийся в 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 смысла нет.

      Читать:

      Firefox suggest как убрать