Iterators
With a vector, you can reach an element by its index, like waits[0]. A set has no index, and the square brackets of a map take a key, not a position. There is no cities[0]. But a range-based for loop can still visit every element of all three. It can do this because all three give you iterators. You have already used one: nums.begin() + 1 in the Vector Operations lesson. Now you will see what it really is.
An iterator is a position in a container. It points at one element, much like a pointer points at one value. Vectors, maps and sets have two methods that return iterators:
begin()is the position of the first element.end()is the position just after the last element. There is no element there.
waits: 40 10 25
^ ^
begin() end()
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> waits = {40, 10, 25};
vector<int>::iterator it = waits.begin();
cout << *it << "\n";
++it;
cout << *it << "\n";
return 0;
}
Output:
40
10
vector<int>::iterator is the type of an iterator into a vector of ints. *it reads the element at that position, the same way * reads the value behind a pointer. ++it moves the iterator one step forward, to the next element. A vector iterator can also jump several steps at once: waits.begin() + 2 is the position of the third element. That is the kind of position that insert and erase take.
Looping with iterators
The type name is long, so most code writes auto and lets the compiler work it out. A loop starts at begin(), moves with ++, and stops when it reaches end():
vector<int> waits = {40, 10, 25};
for (auto it = waits.begin(); it != waits.end(); ++it) {
cout << *it << " ";
}
cout << "\n";
Output:
40 10 25
This is why end() is one step past the last element. When it becomes equal to end(), every element has been visited, and the loop stops. Never read *waits.end(), because there is no element at that position.
A range-based for loop does this same work for you, so use it when you just want every element. You need iterators when you want to hold on to a position, or pass positions to a function. The algorithm functions in the next lesson take their input this way.
Stacks, queues and priority queues have no iterators and no begin(). That is why you could not loop over them with a range-based for loop.
Maps and sets
The same loop works on a map. Each element is a key-value pair, so you read its parts with ->, which you met in the lesson on this and const methods. it->first means (*it).first:
map<string, int> stock;
stock["pens"] = 12;
stock["ink"] = 3;
stock["paper"] = 40;
for (auto it = stock.begin(); it != stock.end(); ++it) {
cout << it->first << ": " << it->second << "\n";
}
Output:
ink: 3
paper: 40
pens: 12
A set keeps its values sorted, so begin() points at the smallest value. To get the largest, start at end() and move one step back with --:
set<int> seats = {12, 4, 9};
cout << *seats.begin() << "\n";
auto last = seats.end();
--last;
cout << *last << "\n";
Output:
4
12
Changing a value through an iterator
Through a vector iterator, you can change the element: *it = 0; works. A set does not allow it:
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> seats = {12, 4, 9};
auto it = seats.begin();
*it = 100;
return 0;
}
Output:
main.cpp: In function ‘int main()’:
main.cpp:8:9: error: assignment of read-only location ‘it.std::_Rb_tree_const_iterator<int>::operator*()’
The compiler stops at line 8, because the values in a set are read-only. If you could change 4 into 100 in place, the set would no longer be sorted. To change a value, erase the old one and insert the new one.
In the exercise, finish an iterator loop that prints a set of numbers in order, then print the largest number.