Range for and common algorithms

Lesson 12 of 30 · Part 3 · Containers · about 15 minutes

Last lesson you went through a vector with an index: for (std::size_t i = 0; i < v.size(); i++). When you just want to look at every element, there is a shorter way, called range for:

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> scores{90, 85, 77, 68};6    int total = 0;7    for (int s : scores) {8        total += s;9    }10    std::cout << "Total: " << total << '\n';11    return 0;12}

Total: 320

Read for (int s : scores) as "for each s in scores": on the first pass s is 90, on the second 85, and so on to the last one. No index, so no way to go out of range.

Range for

Left of the colon is the variable each pass gets; right of it is the container to go through. A std::string is a container too, so you can go through it one character at a time:

1#include <iostream>2#include <string>3#include <vector>4 5int main() {6    std::vector<std::string> list{"milk", "eggs", "bread"};7    for (std::string item : list) {8        std::cout << "- " << item << '\n';9    }10    std::string code = "A7B";11    for (char c : code) {12        std::cout << "[" << c << "]";13    }14    std::cout << '\n';15    return 0;16}

- milk
- eggs
- bread
[A][7][B]

When you need the index (to show numbers, say), use last lesson's loop; when you only need the elements, use range for.

Changing elements through a reference

Each pass of a range for gets a copy of the element. If you change it, does the vector change?

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> prices{10, 20, 30};6    for (int p : prices) {7        p = p + 5;8    }9    std::cout << prices[0] << '\n';10    return 0;11}

To change the element itself, put & after the type so that p is a reference to the element (lesson 10). Press Step and watch the numbers in the boxes grow one at a time:

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> prices{10, 20, 30};6    for (int& p : prices) {7        p = p + 5;8    }9    for (int p : prices) {10        std::cout << p << " ";11    }12    std::cout << '\n';13    return 0;14}

15 25 35 

const auto&: no copy, no changes

When the elements are big things like strings, copying one on every pass is a waste. As with parameters, use a const reference: no copy, and a promise not to change it. Write the type as auto and let the compiler work it out:

1#include <iostream>2#include <string>3#include <vector>4 5int main() {6    std::vector<std::string> cities{"Paris", "Lima", "Oslo"};7    for (const auto& city : cities) {8        std::cout << city << ": " << city.size() << " letters\n";9    }10    return 0;11}

Paris: 5 letters
Lima: 4 letters
Oslo: 4 letters

Here auto becomes std::string, so city.size() works. How to choose between the three:

Sorting

<algorithm> has a set of ready-made tools called algorithms. The one you'll use most is std::sort, which puts things in order from smallest to largest:

1#include <algorithm>2#include <functional>3#include <iostream>4#include <vector>5 6int main() {7    std::vector<int> scores{77, 95, 68, 88};8    std::sort(scores.begin(), scores.end());9    for (int s : scores) {10        std::cout << s << " ";11    }12    std::cout << '\n';13    std::sort(scores.begin(), scores.end(), std::greater<int>());14    for (int s : scores) {15        std::cout << s << " ";16    }17    std::cout << '\n';18    return 0;19}

68 77 88 95 
95 88 77 68 

scores.begin() and scores.end() tell sort where to start and stop: from the beginning to the end. They are really iterators, which lesson 27 covers; for now, just write them like this. For largest first, add std::greater<int>() (from <functional>). Press Step and see the boxes change places after the sort line.

Strings sort too, in dictionary order:

1#include <algorithm>2#include <iostream>3#include <string>4#include <vector>5 6int main() {7    std::vector<std::string> names{"Zoe", "adam", "Lily"};8    std::sort(names.begin(), names.end());9    for (const auto& n : names) {10        std::cout << n << '\n';11    }12    return 0;13}

Lily
Zoe
adam

Note: Strings compare by character codes, and every uppercase letter comes before every lowercase one. That is why adam ends up last.

Reverse, find, count

1#include <algorithm>2#include <iostream>3#include <vector>4 5int main() {6    std::vector<int> rolls{3, 6, 2, 6, 1};7    std::reverse(rolls.begin(), rolls.end());8    for (int r : rolls) {9        std::cout << r << " ";10    }11    std::cout << '\n';12    std::cout << "6 came up " << std::count(rolls.begin(), rolls.end(), 6) << " times\n";13    if (std::find(rolls.begin(), rolls.end(), 5) == rolls.end()) {14        std::cout << "No 5\n";15    }16    return 0;17}

1 6 2 6 3 
6 came up 2 times
No 5

When find finds nothing it gives you end(), just as a string's find gives you npos.

Largest and smallest

std::max_element and std::min_element find the largest and smallest elements. They give you an iterator pointing at that element; put * in front to get the value:

1#include <algorithm>2#include <iostream>3#include <vector>4 5int main() {6    std::vector<double> temps{18.5, 23.0, 16.5, 21.0};7    std::cout << "High: " << *std::max_element(temps.begin(), temps.end()) << '\n';8    std::cout << "Low: " << *std::min_element(temps.begin(), temps.end()) << '\n';9    return 0;10}

High: 23
Low: 16.5

Note: An empty vector has no largest element. Then they give you end(), and putting * in front of that is undefined behavior. Make sure it isn't empty first.

Adding up

std::accumulate (from <numeric>) adds up all the elements. The third argument is the starting value, usually 0:

1#include <iostream>2#include <numeric>3#include <vector>4 5int main() {6    std::vector<double> prices{1.5, 2.5, 3.25};7    std::cout << std::accumulate(prices.begin(), prices.end(), 0) << '\n';8    return 0;9}

The type of the starting value is the type of the result. To add doubles, write 0.0:

1#include <iostream>2#include <numeric>3#include <vector>4 5int main() {6    std::vector<double> prices{1.5, 2.5, 3.25};7    double total = std::accumulate(prices.begin(), prices.end(), 0.0);8    std::cout << "Total: " << total << '\n';9    std::cout << "Average: " << total / prices.size() << '\n';10    return 0;11}

Total: 7.25
Average: 2.41667

Practice

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

40
96
28.4

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<double> prices{50, 120, 35.5};6 7    return 0;8}

#1: 95
#2: 91
#3: 88

1#include <algorithm>2#include <functional>3#include <iostream>4#include <vector>5 6int main() {7    std::vector<int> scores{78, 95, 62, 88, 91};8 9    return 0;10}

Total: 25.25

1#include <iostream>2#include <numeric>3#include <vector>4 5int main() {6    std::vector<double> prices{9.5, 12.25, 3.5};7    std::cout << "Total: " << std::accumulate(prices.begin(), prices.end(), 0) << '\n';8    return 0;9}

What you learned

• Range for, for (int x : v), goes through every element without an index; a std::string works the same way.
• x is a copy: write int& x to change the elements, and const auto& x to read big ones.
• std::sort(v.begin(), v.end()) sorts smallest first; add std::greater<int>() for largest first. Uppercase letters sort before lowercase.
• std::reverse turns the order around, std::count counts, and std::find equals v.end() when it finds nothing.
• *std::max_element(...) and *std::min_element(...) are the largest and smallest values; not on an empty vector.
• std::accumulate(v.begin(), v.end(), 0.0) adds up; the starting value's type is the result's type.