Iterators

Lesson 27 of 30 · Part 7 · Going further · about 15 minutes

In lesson 12 you sorted with std::sort(v.begin(), v.end()), and in lesson 13 find gave you an it. Both times we said "lesson 27 covers this." Here it is: iterators. Think of an iterator as a finger pointing at one element of a container.

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> scores{90, 85, 77};6    auto it = scores.begin();7    std::cout << *it << '\n';8    ++it;9    std::cout << *it << '\n';10    ++it;11    std::cout << *it << '\n';12    return 0;13}

90
85
77

scores.begin() is an iterator pointing at the first element; *it gets the value it points at; ++it moves it one box along. Written out, its type is std::vector<int>::iterator, which is long, so people usually write auto.

begin and end

Every container has these two:

end() doesn't point at the last element. It marks "done." That way "from begin() up to, but not including, end()" is exactly all the elements, and on an empty container begin() equals end().

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v{4, 8, 15, 16};6    auto it = v.end();7    --it;8    std::cout << *it << '\n';9    return 0;10}

Note: *v.end() is undefined behavior, just like an index out of range. Before you use *it, make sure it != v.end().

Looping with an iterator

Start at begin(), do ++it each time, and stop at end():

1#include <iostream>2#include <string>3#include <vector>4 5int main() {6    std::vector<std::string> list{"milk", "eggs", "bread"};7    for (auto it = list.begin(); it != list.end(); ++it) {8        std::cout << "- " << *it << '\n';9    }10    std::vector<int> prices{10, 20, 30};11    for (auto it = prices.begin(); it != prices.end(); ++it) {12        *it = *it * 2;13    }14    std::cout << prices[0] << " " << prices[1] << " " << prices[2] << '\n';15    return 0;16}

- milk
- eggs
- bread
20 40 60

*it can be changed as well as read: *it = *it * 2 changes that element of the vector. The condition is it != list.end(), not <: some containers (map, for one) have iterators you can't compare by size, only by "same place or not."

A vector iterator can also jump several boxes and be subtracted: v.begin() + 2 points at index 2, and it - v.begin() is the index of it. That's how you find where find found something:

1#include <algorithm>2#include <iostream>3#include <vector>4 5int main() {6    std::vector<int> rolls{3, 6, 2, 6, 1};7    auto it = std::find(rolls.begin(), rolls.end(), 2);8    if (it != rolls.end()) {9        std::cout << "2 is at index " << it - rolls.begin() << '\n';10    }11    std::sort(rolls.begin(), rolls.begin() + 3);12    for (int r : rolls) {13        std::cout << r << " ";14    }15    std::cout << '\n';16    return 0;17}

2 is at index 2
2 3 6 6 1 

std::sort(rolls.begin(), rolls.begin() + 3) sorts only the first three. Algorithms take "from this iterator to that one," not necessarily the whole container.

What range for really does

Range for is shorthand for an iterator loop. What you write,

1for (int s : scores) {2    std::cout << s << '\n';3}

the compiler turns into roughly this:

1for (auto it = scores.begin(); it != scores.end(); ++it) {2    int s = *it;3    std::cout << s << '\n';4}

So anything with begin() and end() works with range for: vector, string, map, set. And for (int& s : scores) means int& s = *it;, which is why it can change the elements.

Map iterators

A map iterator points at a pair. *it is the pair, so the key is (*it).first, parentheses required. The usual way to write it is it->first, which means the same:

1#include <iostream>2#include <map>3#include <string>4 5int main() {6    std::map<std::string, int> stock{{"apple", 5}, {"pear", 3}, {"orange", 0}};7    for (auto it = stock.begin(); it != stock.end(); ++it) {8        std::cout << it->first << ": " << it->second << '\n';9    }10    auto found = stock.find("pear");11    if (found != stock.end()) {12        found->second += 10;13        std::cout << "Pears now: " << stock["pear"] << '\n';14    }15    return 0;16}

apple: 5
orange: 0
pear: 3
Pears now: 13

found->second += 10 changes the value in the map through the iterator. You can't change a key that way: the key decides where the pair sits, so to change a key you erase the pair and add a new one.

Erasing while you loop

v.erase(it) removes the element it points at, and everything after it moves up one box. After that, it must not be used again; erase returns an iterator to the next element, so carry on with that. This removes every item that's out of stock (a count of 0):

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> stock{5, 0, 0, 3, 0, 8};6    auto it = stock.begin();7    while (it != stock.end()) {8        if (*it == 0) {9            it = stock.erase(it);10        } else {11            ++it;12        }13    }14    for (int s : stock) {15        std::cout << s << " ";16    }17    std::cout << '\n';18    return 0;19}

5 3 8 

The key part: after an erase, it = stock.erase(it); only when nothing was erased, ++it. Press Step and watch the boxes disappear one at a time.

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v{1, 0, 0, 2};6    for (auto it = v.begin(); it != v.end(); ++it) {7        if (*it == 0) {8            it = v.erase(it);9        }10    }11    std::cout << v.size() << '\n';12    return 0;13}

A map works the same way, it = m.erase(it):

1#include <iostream>2#include <map>3#include <string>4 5int main() {6    std::map<std::string, int> stock{{"apple", 5}, {"pear", 0}, {"orange", 0}, {"peach", 2}};7    for (auto it = stock.begin(); it != stock.end();) {8        if (it->second == 0) {9            it = stock.erase(it);10        } else {11            ++it;12        }13    }14    for (const auto& kv : stock) {15        std::cout << kv.first << ": " << kv.second << '\n';16    }17    return 0;18}

apple: 5
peach: 2

This time the third part of the for is empty, and ++it lives in the else.

Practice

Write the code, then press Check. A hint costs nothing; the answer is there when you need it.

Total: 66

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> prices{12, 30, 8, 16};6    int total = 0;7    for (auto it = prices.begin(); it != prices.end(); ++it) {8        // add the price it points to into total9    }10    std::cout << "Total: " << total << '\n';11    return 0;12}

Index 2: 55

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> scores{78, 92, 55, 61, 40};6    for (auto it = scores.begin(); it != scores.end(); ++it) {7        // below 60: show the index and score, then stop8    }9    return 0;10}

3 5 7 

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> days{3, -1, 0, 5, -2, 7};6 7    for (int d : days) {8        std::cout << d << " ";9    }10    std::cout << '\n';11    return 0;12}

What you learned

• An iterator points at one element: begin() at the first, end() at the box just after the last.
• *it gets the value (and can change it), ++it moves on, and the loop condition is it != v.end(); *v.end() is undefined behavior.
• A vector iterator can do + n, and it - v.begin() is its index; algorithms take "from this iterator to that one."
• Range for is an iterator loop from begin() to end() underneath.
• A map iterator points at a pair: it->first is the key, it->second the value, which you can change through it.
• Erasing while looping: it = v.erase(it), and no ++it after an erase.