范围 for 和常用算法

第 12 课，共 30 课 · 第 3 部分 · 容器 · 约 15 分钟

上一课用下标走遍 vector：for (std::size_t i = 0; i < v.size(); i++)。只是想把每个元素看一遍的时候，有更短的写法，叫范围 for：

main.cpp

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 << '\n';11    return 0;12}

输出

总分：320

for (int s : scores) 读作「对 scores 里的每一个 s」：第一圈 s 是 90，第二圈是 85……直到最后一个。不用下标，也就不会越界。

范围 for

冒号左边是每一圈拿到的变量，右边是要走遍的容器。std::string 也是一个容器，能一个字符一个字符地走：

main.cpp

1#include <iostream>2#include <string>3#include <vector>4 5int main() {6    std::vector<std::string> list{"牛奶", "鸡蛋", "面包"};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}

输出

- 牛奶
- 鸡蛋
- 面包
[A][7][B]

要用到下标（比如显示编号）的时候，还是用上一课的写法；只要元素本身，就用范围 for。

用引用改元素

范围 for 每一圈拿到的是元素的一份复制。改它，会改到 vector 里吗？

先猜一猜

这段程序显示什么？

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}

p 是复制出来的，改的是复制品，prices 里的数没变。

输出

要改元素本身，在类型后面加 &，让 p 成为元素的引用（第 10 课）。点单步，看格子里的数一个一个变大：

main.cpp

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&：不复制，也不改

元素是字符串这样的大东西时，每一圈都复制一份很浪费。和传参数一样，用 const 引用：不复制，也保证不会改到它。类型写 auto，让编译器自己推出来：

main.cpp

1#include <iostream>2#include <string>3#include <vector>4 5int main() {6    std::vector<std::string> cities{"上海", "成都", "西安"};7    for (const auto& city : cities) {8        std::cout << city << "：" << city.size() << " 个字节\n";9    }10    return 0;11}

输出

上海：6 个字节
成都：6 个字节
西安：6 个字节

一个汉字在 std::string 里占 3 个字节，所以 size() 是 6。三种写法怎么挑：

写法	什么时候用
`for (int x : v)`	元素是 `int`、`double` 这样的小东西，只读
`for (int& x : v)`	要改元素
`for (const auto& x : v)`	元素是字符串这样的大东西，只读

排序

<algorithm> 里有一批现成的工具，叫算法。最常用的是 std::sort，从小到大排好：

main.cpp

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() 和 scores.end() 告诉 sort 从哪儿排到哪儿：从头到尾。它们其实是迭代器，第 27 课再细讲，现在照着写就行。要从大到小，多给一个 std::greater<int>()（在 <functional> 里）。点单步，看 sort 那一步之后格子换了位置。

字符串也能排，按字典顺序：

main.cpp

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

输出

张伟
李雷
王芳

注意： 汉字按编码比大小，不是按拼音或笔画。按拼音，「李」应该在最前面。

翻转、查找、数个数

写法	做什么
`std::reverse(v.begin(), v.end())`	把顺序倒过来
`std::count(v.begin(), v.end(), x)`	`x` 出现了几次
`std::find(v.begin(), v.end(), x)`	找 `x`；找不到时等于 `v.end()`

main.cpp

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 出现了 " << std::count(rolls.begin(), rolls.end(), 6) << " 次\n";13    if (std::find(rolls.begin(), rolls.end(), 5) == rolls.end()) {14        std::cout << "没有 5\n";15    }16    return 0;17}

输出

1 6 2 6 3 
6 出现了 2 次
没有 5

find 找不到时给你 end()，就像字符串的 find 找不到时给你 npos。

最大和最小

std::max_element 和 std::min_element 找最大和最小的元素。它们给的是一个指向那个元素的迭代器，前面加 * 才是值：

main.cpp

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 << "最高：" << *std::max_element(temps.begin(), temps.end()) << '\n';8    std::cout << "最低：" << *std::min_element(temps.begin(), temps.end()) << '\n';9    return 0;10}

输出

最高：23
最低：16.5

注意： 空的 vector 没有最大的元素，这时它们给的是 end()，再加 * 就是未定义行为。先确认不是空的。

加起来

std::accumulate（在 <numeric> 里）把所有元素加起来。第三个参数是起点，通常写 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}

起点 0 是 int，accumulate 就一路用 int 存结果：0 + 1.5 存成 1，1 + 2.5 存成 3，3 + 3.25 存成 6。每一步都把小数丢了。

输出

起点的类型就是结果的类型。加 double 就写 0.0：

main.cpp

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 << '\n';9    std::cout << "平均：" << total / prices.size() << '\n';10    return 0;11}

输出

总价：7.25
平均：2.41667

练一练

写好代码，点检查。提示随便看，实在想不出来再看答案。

练习 1

全场八折

用范围 for 把 prices 里的每个价格都改成原来的 0.8 倍，再一行一个显示出来。

要显示

40
96
28.4

exercise1.cpp

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

输出

点「运行」或按 Ctrl+Enter

练习 2

前三名

把 scores 从大到小排好，显示前三个，格式见下面。

要显示

第 1 名：95
第 2 名：91
第 3 名：88

exercise2.cpp

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}

输出

点「运行」或按 Ctrl+Enter

练习 3

修好它：丢了零头的总价

这段程序算出来的总价不对。改好它，让它显示 总价：25.25。

要显示

总价：25.25

exercise3.cpp

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 << "总价：" << std::accumulate(prices.begin(), prices.end(), 0) << '\n';8    return 0;9}

输出

点「运行」或按 Ctrl+Enter

这一课学会了

范围 for for (int x : v) 走遍每个元素，不用下标；std::string 也能这样走。
x 是复制品；要改元素写 int& x，只读大东西写 const auto& x。
std::sort(v.begin(), v.end()) 从小到大排，加 std::greater<int>() 从大到小；汉字按编码排。
std::reverse 倒过来，std::count 数个数，std::find 找不到时等于 v.end()。
*std::max_element(...)、*std::min_element(...) 是最大和最小的值；空的不能用。
std::accumulate(v.begin(), v.end(), 0.0) 求和，起点的类型就是结果的类型。