Iterators walk the containers in C++ by behaving like a pointer that knows where it is and how to move to the next element. Every container defines its own iterator type, and the algorithms are written against those types rather than against the containers. Understanding the categories of the iterator explains why some algorithms work on a list and others do not.
The previous lesson in this module covered "When Do stack, queue and deque Beat vector?", and the next lesson in this module is about "Which STL Algorithms Replace Hand-Written Loops?".
What an iterator does
An iterator supports three things. The asterisk to read the element, the increment to move on, and a comparison with another iterator to test for equality.
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> parcels = {"p-001", "p-002", "p-003"};
auto it = parcels.begin();
while (it != parcels.end()) {
std::cout << *it << '\n';
++it;
}
return 0;
}The output shows the three parcels in order.
p-001
p-002
p-003And the end() iterator marks one past the last element. It is never dereferenced, it is only compared against.
The categories
The standard library sorts the iterators into five categories, and each one has more capabilities than the last.
the category what it can do
------------------------ ----------------------------------------------
the input iterators read only, and a single pass
the output iterators write only, and a single pass
the forward iterators read and write, and you can traverse
the sequence more than once
the bidirectional the forward ones plus the ability to move
backwards
the random access the bidirectional ones plus the ability to
jump to any position in constant time
A std::vector gives the random access iterators. A std::list gives the bidirectional ones. A std::forward_list gives the forward ones.
And that is why std::sort works on a vector but not on a list, because sorting needs the random access.
#include <algorithm>
#include <forward_list>
#include <iostream>
#include <list>
#include <vector>
int main() {
std::vector<int> parcels = {3, 1, 2};
std::sort(parcels.begin(), parcels.end());
std::cout << "vector sorted: " << parcels[0] << parcels[1] << parcels[2] << '\n';
std::list<int> route = {3, 1, 2};
route.sort(); // the list has its own sort, which works fine
auto it = route.begin();
std::cout << "list sorted: " << *it++;
std::cout << *it++;
std::cout << *it << '\n';
std::forward_list<int> chain = {3, 1, 2};
chain.sort();
std::cout << "forward_list sorted ok\n";
return 0;
}The output shows all three of them sorted, each with the algorithm that the container supports.
vector sorted: 123
list sorted: 123
forward_list sorted okA reference is not an iterator
A reference is bound to an object and it cannot be reseated. An iterator is a position that can be moved. They look similar, but they behave differently in the ways that matter.
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> parcels = {"p-001", "p-002", "p-003"};
auto& reference = parcels[0];
auto iterator = parcels.begin();
std::cout << "reference: " << reference << '\n';
std::cout << "iterator: " << *iterator << '\n';
++iterator;
std::cout << "after ++: " << *iterator << '\n';
std::cout << "reference still: " << reference << '\n';
return 0;
}The output shows the iterator moving on while the reference stays where it was.
reference: p-001
iterator: p-001
after ++: p-002
reference still: p-001Writing code that accepts any container
The most useful thing about the iterators is that a function written in terms of them works with every container.
#include <iostream>
#include <list>
#include <string>
#include <vector>
template <typename Container>
void print_all(const Container& container) {
for (auto it = container.begin(); it != container.end(); ++it) {
std::cout << *it << ' ';
}
std::cout << '\n';
}
int main() {
std::vector<std::string> parcels = {"p-001", "p-002"};
std::list<std::string> route = {"r-001", "r-002"};
print_all(parcels);
print_all(route);
return 0;
}The output shows one template handling two containers.
p-001 p-002
r-001 r-002And because the template takes the container type as a parameter and not the element type, it works for any container of any element type.
Iterator adapters
The standard library provides the adapters that turn a container into an iterator sequence or that reshape one.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
int main() {
std::vector<int> parcels = {1, 2, 3, 4, 5};
std::vector<int> doubled;
std::transform(parcels.begin(), parcels.end(),
std::back_inserter(doubled),
[](int weight) { return weight * 2; });
for (int weight : doubled) {
std::cout << weight << ' ';
}
std::cout << '\n';
std::vector<int> first_three(parcels.begin(), parcels.begin() + 3);
std::cout << "first three sum: "
<< std::accumulate(first_three.begin(), first_three.end(), 0) << '\n';
return 0;
}The output shows the transform writing into a new vector and the range being restricted.
2 4 6 8 10
first three sum: 6And the std::back_inserter is the important one. It turns an output iterator into a "push to the end" writer, and that is how an algorithm can fill a container whose size it does not know in advance.
Common iterator mistakes
- Comparing the iterators from two different containers. The behaviour is
undefined. - Dereferencing the
end(), which isundefined behaviour, because the end iterator points one past the last element. - Using an iterator after the container changed size. It may have been invalidated.
- Mixing the iterator types. A vector iterator and a vector const iterator can be compared, but a vector iterator and a list iterator cannot.
Quick reference
- An iterator is a position, and it supports the asterisk, the increment and the comparison with
end(). - There are five categories, and the category decides which algorithms can be used with a container.
- A reference is fixed to an object, and an iterator can be moved.
- The templates over the container type work with any container.
- The
std::back_inserterlets an algorithm write into a growing container.
Try it yourself: write a function that takes two iterators and gives back the number of the elements between them, and then call it with the begin() and the end() of a vector and of a list. Next, use std::transform with a std::back_inserter to double a vector into a second one. Finally, take an iterator, erase an element before it and use the old iterator again to see the invalidation.