迭代器

第 27 课，共 30 课 · 第 7 部分 · 再往前 · 约 15 分钟

第 12 课排序时写过 std::sort(v.begin(), v.end())，第 13 课 find 给过一个 it，当时都说「第 27 课再讲」。这一课就讲它们：迭代器。你可以把迭代器想成一根手指，指着容器里的某一个元素。

main.cpp

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() 是指着第一个元素的迭代器；*it 取出它指着的值；++it 让它往后挪一格。迭代器的类型写出来是 std::vector<int>::iterator，很长，所以一般写 auto。

begin 和 end

每个容器都有这两个：

写法	指着哪里
`v.begin()`	第一个元素
`v.end()`	最后一个元素的后面一格，那里没有元素

end() 不指着最后一个，而是指着「已经走完了」的位置。这样「从 begin() 走到 end() 之前」正好是全部元素；空的容器上 begin() 就等于 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}

end() 指着最后一个元素后面的那一格，--it 往回退一格，正好是最后一个元素 16。直接写 *v.end() 才是错的：那一格没有元素。

输出

注意： *v.end() 是未定义行为，和下标越界一样。用 *it 之前，先确定 it != v.end()。

用迭代器走一遍

从 begin() 开始，每次 ++it，碰到 end() 就停：

main.cpp

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

输出

- 牛奶
- 鸡蛋
- 面包
20 40 60

*it 不只能读，也能改：*it = *it * 2 改的就是 vector 里的那个元素。条件写 it != list.end()，不写 <：有的容器（比如 map）的迭代器不能比大小，只能比「是不是同一个位置」。

vector 的迭代器还能一次跳好几格，也能相减：v.begin() + 2 指着下标 2 的元素，it - v.begin() 是 it 的下标。find 找到以后想知道在第几个，就这样算：

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    auto it = std::find(rolls.begin(), rolls.end(), 2);8    if (it != rolls.end()) {9        std::cout << "2 在下标 " << 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 在下标 2
2 3 6 6 1

std::sort(rolls.begin(), rolls.begin() + 3) 只排前三个：算法要的就是「从哪个迭代器到哪个迭代器」，不一定是整个容器。

范围 for 背后

范围 for 其实就是迭代器循环的简写。你写的

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

编译器大致把它变成

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

所以只要一个东西有 begin() 和 end()，就能用范围 for：vector、string、map、set 都是这样。for (int& s : scores) 就是 int& s = *it;，所以能改元素。

map 的迭代器

map 的迭代器指着一对。*it 是那一对，取键要写 (*it).first，括号不能少；更常见的写法是 it->first，意思一样：

main.cpp

1#include <iostream>2#include <map>3#include <string>4 5int main() {6    std::map<std::string, int> stock{{"苹果", 5}, {"梨", 3}, {"橙子", 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("梨");11    if (found != stock.end()) {12        found->second += 10;13        std::cout << "梨现在有 " << stock["梨"] << '\n';14    }15    return 0;16}

输出

梨：3
橙子：0
苹果：5
梨现在有 13

found->second += 10 通过迭代器直接改了表里的值。map 的键不能这样改：键决定了这一对排在哪里，要换键就删掉再加。

边走边删

v.erase(it) 删掉 it 指着的元素，后面的元素往前挪一格。删掉以后 it 就不能再用了；erase 会返回下一个元素的迭代器，接着用它就行。下面删掉所有缺货（数量是 0）的：

main.cpp

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

关键是：删了就 it = stock.erase(it)，没删才 ++it。点单步，看格子一个一个少下去。

先猜一猜

这段程序想删掉所有的 0。它显示什么？

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}

删掉第一个 0 后，erase 返回的迭代器已经指着第二个 0 了，可循环接着又 ++it，把它跳了过去。所以只删了一个 0，剩下 1、0、2 三个。删了就别再 ++it。

输出

map 也一样，it = m.erase(it)：

main.cpp

1#include <iostream>2#include <map>3#include <string>4 5int main() {6    std::map<std::string, int> stock{{"苹果", 5}, {"梨", 0}, {"橙子", 0}, {"桃", 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}

输出

桃：2
苹果：5

这次的 for 第三部分空着，++it 放进了 else。

练一练

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

练习 1

用迭代器加起来

不用下标、也不用范围 for，用迭代器 it 走一遍 prices，把价格加起来，显示 合计：66。

要显示

合计：66

exercise1.cpp

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        // 把 it 指着的价格加进 total9    }10    std::cout << "合计：" << total << '\n';11    return 0;12}

输出

点「运行」或按 Ctrl+Enter

练习 2

不及格的排在第几

用迭代器循环找到 scores 里第一个小于 60 的分数，显示它的下标和分数，像这样：下标 2：55。

要显示

下标 2：55

exercise2.cpp

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        // 小于 60 就显示下标和分数，然后停下8    }9    return 0;10}

输出

点「运行」或按 Ctrl+Enter

练习 3

删掉过期的

days 是每样食物还剩几天过期。用迭代器和 erase 删掉所有小于等于 0 的，再显示剩下的，空格隔开。

要显示

3 5 7

exercise3.cpp

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}

输出

点「运行」或按 Ctrl+Enter

这一课学会了

迭代器指着容器里的一个元素：begin() 指着第一个，end() 指着最后一个后面的那一格。
*it 取值（也能改），++it 往后走，循环条件写 it != v.end()；*v.end() 是未定义行为。
vector 的迭代器能 + n，it - v.begin() 是下标；算法要的是「从哪个迭代器到哪个迭代器」。
范围 for 背后就是 begin() 到 end() 的迭代器循环。
map 的迭代器指着一对：it->first 是键，it->second 是值，值可以通过它改。
边走边删：it = v.erase(it)，删了就不要再 ++it。