# Iterators
Iterators are a means of navigating and operating on a sequence of elements and are a generalized extension of pointers. Conceptually it is important to remember that iterators are positions, not elements. For example, take the following sequence:
The sequence contains three elements and four positions
Elements are things within a sequence. Positions are places where meaningful operations can happen to the sequence. For example, one inserts into a position, before or after element A, not into an element. Even deletion of an element ( erase(A) ) is done by first finding its position, then deleting it.
# From Iterators to Values
To convert from a position to a value, an iterator is dereferenced:
One can think of an iterator as dereferencing to the value it refers to in the sequence. This is especially useful in understanding why you should never dereference the end() iterator in a sequence:
In all the sequences and containers found in the C++ standard library, begin() will return an iterator to the first position, and end() will return an iterator to one past the last position (not the last position!). Consequently, the names of these iterators in algorithms are oftentimes labelled first and last :
It is also possible to obtain an iterator to any sequence, because even an empty sequence contains at least one position:
In an empty sequence, begin() and end() will be the same position, and neither can be dereferenced:
The alternative visualization of iterators is that they mark the positions between elements:
and dereferencing an iterator returns a reference to the element coming after the iterator. Some situations where this view is particularly useful are:
- insert operations will insert elements into the position indicated by the iterator,
- erase operations will return an iterator corresponding to the same position as the one passed in,
- an iterator and its corresponding reverse iterator
# Invalid Iterators
An iterator becomes invalidated if (say, in the course of an operation) its position is no longer a part of a sequence. An invalidated iterator cannot be dereferenced until it has been reassigned to a valid position. For example:
The many algorithms and sequence member functions in the C++ standard library have rules governing when iterators are invalidated. Each algorithm is different in the way they treat (and invalidate) iterators.
# Navigating with Iterators
As we know, iterators are for navigating sequences. In order to do that an iterator must migrate its position throughout the sequence. Iterators can advance forward in the sequence and some can advance backwards:
Note, second argument of std::distance should be reachable from the first one(or, in other words first should be less or equal than second ).
Even though you can perform arithmetic operators with iterators, not all operations are defined for all types of iterators. a = b + 3; would work for Random Access Iterators, but wouldn’t work for Forward or Bidirectional Iterators, which still can be advanced by 3 position with something like b = a; ++b; ++b; ++b; . So it is recommended to use special functions in case you are not sure what is iterator type (for example, in a template function accepting iterator).
# Iterator Concepts
The C++ standard describes several different iterator concepts. These are grouped according to how they behave in the sequences they refer to. If you know the concept an iterator models (behaves like), you can be assured of the behavior of that iterator regardless of the sequence to which it belongs. They are often described in order from the most to least restrictive (because the next iterator concept is a step better than its predecessor):
- Input Iterators : Can be dereferenced only once per position. Can only advance, and only one position at a time.
- Forward Iterators : An input iterator that can be dereferenced any number of times.
- Bidirectional Iterators : A forward iterator that can also advance backwards one position at a time.
- Random Access Iterators : A bidirectional iterator that can advance forwards or backwards any number of positions at a time.
- Contiguous Iterators (since C++17) : A random access iterator that guaranties that underlying data is contiguous in memory.
Algorithms can vary depending on the concept modeled by the iterators they are given. For example, although random_shuffle can be implemented for forward iterators, a more efficient variant that requires random access iterators could be provided.
# Iterator traits
Iterator traits provide uniform interface to the properties of iterators. They allow you to retrieve value, difference, pointer, reference types and also category of iterator:
Category of iterator can be used to specialize algorithms:
Categories of iterators are basically iterators concepts, except Contiguous Iterators don’t have their own tag, since it was found to break code.
# Vector Iterator
begin returns an iterator to the first element in the sequence container.
end returns an iterator to the first element past the end.
If the vector object is const , both begin and end return a const_iterator . If you want a const_iterator to be returned even if your vector is not const , you can use cbegin and cend .
# Map Iterator
An iterator to the first element in the container.
If a map object is const-qualified, the function returns a const_iterator . Otherwise, it returns an iterator .
# Reverse Iterators
If we want to iterate backwards through a list or vector we can use a reverse_iterator . A reverse iterator is made from a bidirectional, or random access iterator which it keeps as a member which can be accessed through base() .
To iterate backwards use rbegin() and rend() as the iterators for the end of the collection, and the start of the collection respectively.
For instance, to iterate backwards use:
A reverse iterator can be converted to a forward iterator via the base() member function. The relationship is that the reverse iterator references one element past the base() iterator:
In the visualization where iterators mark positions between elements, the relationship is simpler:
# Stream Iterators
Stream iterators are useful when we need to read a sequence or print formatted data from a container:
The example program will print 1 — 2 — 3 — 4 — to standard output.
# C Iterators (Pointers)
This code would output the numbers 1 through 5, one on each line like this:
# Breaking It Down
This line creates a new integer array with 5 values. C arrays are just pointers to memory where each value is stored together in a contiguous block.
These lines create two pointers. The first pointer is given the value of the array pointer, which is the address of the first element in the array. The sizeof operator when used on a C array returns the size of the array in bytes. Divided by the size of an element this gives the number of elements in the array. We can use this to find the address of the block after the array.
Here we create a pointer which we will use as an iterator. It is initialized with the address of the first element we want to iterate over, and we’ll continue to iterate as long as i is less than afterLast , which means as long as i is pointing to an address within array .
Finally, within the loop we can access the value our iterator i is pointing to by dereferencing it. Here the dereference operator * returns the value at the address in i .
# Write your own generator-backed iterator
A common pattern in other languages is having a function that produces a "stream" of objects, and being able to use loop-code to loop over it.
We can model this in C++ as
We store the generated element early so we can more easily detect if we are already at the end.
As the function of an end generator iterator is never used, we can create a range of generator iterators by only copying the std::function once. A default constructed generator iterator compares equal to itself, and to all other end-generator-iterators.
Итератор на C++
Итератор — это поведенческий паттерн, позволяющий последовательно обходить сложную коллекцию, без раскрытия деталей её реализации.
Благодаря Итератору, клиент может обходить разные коллекции одним и тем же способом, используя единый интерфейс итераторов.
Сложность:
Популярность:
Применимость: Паттерн можно часто встретить в C++ коде, особенно в программах, работающих с разными типами коллекций, и где требуется обход разных сущностей.
Признаки применения паттерна: Итератор легко определить по методам навигации (например, получения следующего/предыдущего элемента и т. д.). Код использующий итератор зачастую вообще не имеет ссылок на коллекцию, с которой работает итератор. Итератор либо принимает коллекцию в параметрах конструктора при создании, либо возвращается самой коллекцией.
Концептуальный пример
Этот пример показывает структуру паттерна Итератор, а именно — из каких классов он состоит, какие роли эти классы выполняют и как они взаимодействуют друг с другом.
main.cc: Пример структуры паттерна
Output.txt: Результат выполнения
Итератор на других языках программирования
Купи книгу Погружение в Паттерны и получи архив с десятками детальных примеров, которые можно открывать прямо в IDE.
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.
Делаем свой итератор
Не часто возникает необходимость создать свой итератор и хотелось бы иметь под рукой небольшой 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 смысла нет.