关键点
- 数组或者
map等容器的各个元素进行顺序处理时迭代器可以使用 - 当将迭代器放入变量中时
auto使用 - 迭代器操作
| 操作 | 記法 |
|---|---|
| 获取指向容器第一个元素的迭代器 | コンテナ.begin() |
| 集装箱最后一个元素旁边 获取指向的迭代器 | コンテナ.end() |
| 迭代器比较 | イテレータ1 == イテレータ2, イテレータ1 != イテレータ2 |
| 迭代器之间的距离 | distance(イテレータ1, イテレータ2) |
| 移动迭代器 | advance(イテレータ, k);(迭代器
提前k次), イテレータ++;, イテレータ--; |
| 获取上一个和下一个迭代器 | next(イテレータ, k)(k项目的迭代器。
如果省略k,将被视为1),prev(イテレータ, k)(k迭代器)イテレータ + k,イテレータ - k(map/set无法使用) |
| 访问迭代器指向的元素 | *イテレータ(map/set迭代器是只读的) |
| 访问迭代器指向的元素的成员 | イテレータ->メンバ(map/set迭代器是只读的) |
| 删除迭代器指向的元素 | コンテナ.erase(イテレータ) |
- 删除或添加元素可能会使迭代器无效
- 注意不要使用无效的迭代器 您可以使用
迭代器
数组或者map等容器的各个元素进行顺序处理时迭代器。
使用迭代器通常可以概括处理,
事实上,在STL中,“对一系列元素做某事”的函数是通过将迭代器作为参数来实现的。
例如,在对数组进行排序时使用sort采用迭代器作为参数。
它被给予
sort正在把它给配列.begin()呀配列.end()表示迭代器。
数组的迭代器可以被认为是指向每个元素的东西,如下图所示。

在上图中,迭代器 1 是指向第三个元素 5 的迭代器,迭代器 2 是指向第七个元素 4 的迭代器。
对迭代器的操作包括“获取下一个位置的迭代器”和“访问迭代器指向的元素”。
以下示例程序是访问数组第二个元素的示例。
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> a = {3, 1, 5, 6, 7, 2, 4};
auto itr1 = a.begin(); // aの先頭を指すイテレータ
itr1 = itr1 + 2; // a[2]を指すイテレータ
auto itr2 = itr1 + 4; // 末尾の要素(a[6])を指すイテレータ
cout << *itr1 << endl; // itr1が指す要素(a[2])へのアクセス
cout << *itr2 << endl; // itr2が指す要素(a[6])へのアクセス
}
実行結果
5 4
以下示例程序是使用 for 语句顺序访问数组元素的示例。
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> a = {1, 2, 3};
// a.begin() .. 先頭の要素を指すイテレータ
// a.end() .... 終端を指すイテレータ
// it++ ....... イテレータを1つ分進める (it = it + 1と同じ)
for (auto it = a.begin(); it != a.end(); it++) {
cout << *it << endl;
}
}
実行結果
1 2 3
通过指定索引访问数组的元素。
可以写成a[1],所以
您实际上可能不会编写类似于上面示例程序的内容。
然而,迭代器的优点是能够以相同的方式处理数组以外的数据结构。
例如,这使得不需要准备“专用于数组的排序函数”。
对于任何支持迭代器的数据结构,具有相同的排序功能
现在可以使用sort。
迭代器类型
迭代器类型是为每个容器定义的,并且很复杂。
手写很难,所以通常
使用auto。
vector<int> a = {1, 2, 3};
auto itr1 = a.begin();
set<int> b = {4, 5, 6};
auto itr2 = b.begin();
// itr1とitr2は別の型
如果您需要确切的类型cppreference.com 参见等。
第一个元素的迭代器
コンテナ.begin()
返回一个指向容器第一个元素的迭代器。 如果容器为空,则返回一个指向“最后一个元素旁边”的迭代器。
终端迭代器
コンテナ.end()
集装箱终止(在最后一个元素之后)
返回一个指向的迭代器。请注意,它不是指向最后一个元素的迭代器。
虽然乍一看似乎很难使用,但在确定 for 语句的结束时它可能很有用。
另外,
请注意,不得访问end返回的迭代器所指向的位置。
访问这样的迭代器,如果它指向的位置不存在任何元素,则会导致未定义的行为。
迭代器比较
イテレータ1 == イテレータ2
当两个迭代器指向同一位置时true。
イテレータ1 != イテレータ2
当两个迭代器指向不同位置时true。
迭代器之间的距离
distance(イテレータ1, イテレータ2)
返回“迭代器 1 必须前进多少次才能匹配迭代器 2?” 对于
map呀set的迭代器,如果迭代器 1 指向迭代器 2 之后的元素,则行为未定义。
移动迭代器
这些操作修改迭代器变量本身。
前进一步
イテレータ++;
前进 k 步
要将迭代器前进k次,也可以这样写。
advance(イテレータ, k);
向后移动一步
イテレータ--;
向后移动 k 步 通过向
advance传递负值,您可以向后移动指定的次数。
advance(イテレータ, -k); // k回分後ろに進める
获取上一个和下一个迭代器
复制迭代器后,
您可以使用++呀advance执行相同的操作。
次
next(イテレータ) // 次の要素を指すイテレータ next(イテレータ, k) // k個先の要素を指すイテレータ イテレータ + k // k個先の要素を指すイテレータ (map/setでは使えない)
一回
prev(イテレータ) // 1つ後ろの要素を指すイテレータ prev(イテレータ, k) // k個後ろの要素を指すイテレータ イテレータ - k // k個後ろの要素を指すイテレータ (map/setでは使えない)
next呀prev返回上一个和下一个迭代器作为返回值。
作为参数传递的迭代器本身不会被重写。
访问迭代器指向的元素
*イテレータ
コンテナ.end()返回的迭代器,
访问空のコンテナ.begin()返回的迭代器将导致未定义的行为。
访问迭代器指向的元素的成员
イテレータ->メンバ変数 イテレータ->メンバ関数() // メンバ関数の呼び出し
具体例
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<pair<int, int>> a = {{1, 4}, {2, 5}, {3, 6}};
auto itr = a.begin() + 1;
// cout << (*itr).first << ", " << (*itr).second << endl; と書くのと同じ
cout << (itr->first) << ", " << (itr->second) << endl;
}
実行結果
2, 5
迭代器使用示例
指向第 i 个元素的迭代器
next(コンテナ.begin(), i)
每个元素的流程
for (auto it = コンテナ.begin(); it != コンテナ.end(); it++) {
// 各要素に対する処理
}
删除元素
还可以删除迭代器指向的元素。
コンテナ.erase(イテレータ); // イテレータが指す要素を削除
删除元素会使其迭代器失效。详细内容将在注释部分进行说明。
要在使用 for 语句处理每个元素时删除元素,请执行以下操作:
for (auto it = コンテナ.begin(); it != コンテナ.end()) {
if (要素を削除する条件) {
// eraseは削除後の次の要素のイテレータを返します。
it = コンテナ.erase(it); // itの指す要素を削除
} else {
it++;
}
}
指向最后一个元素的迭代器 我们解释过
end返回一个指向末尾的迭代器,但是
如果你想要一个指向最后一个元素的迭代器,你可以这样做:
prev(コンテナ.end())
请注意,您不应在空容器上执行此操作。
迭代器操作的复杂性
操作迭代器所需的计算量因容器而异。
配列
操作数组迭代器时的计算量如下。 通过
| 操作 | 計算量 |
|---|---|
begin(), end() |
O(1) |
next, prev, +, - |
O(1) |
advance, ++, -- |
O(1) |
distance |
O(1) |
*呀->访问 |
O(1) |
| 删除元素 | 要删除的元素后面的元素数量 作为N, 操作O(N) |
map/set
map/set迭代器时的计算量如下。
| 操作 | 計算量 |
|---|---|
begin(), end() |
O(1) |
next, prev, ++, -- |
移动次数N作为O(N) |
advance, ++, -- |
移动次数N作为O(N) |
distance |
将迭代器之间的距离设置为N作为O(N) |
*呀->访问 |
O(1) |
| 删除元素 | 折旧计算金额O(1) |
“折旧计算金额O(1)”表示相同的过程。N次,每次计算量为 这意味着成为O(1)。
注意点
迭代器无效
删除或添加元素到容器可能会使前一个迭代器无效。 使用无效的迭代器将导致未定义的行为。
保存迭代器并稍后重用时需要小心。
下面是迭代器失效的示例。 了解更多详情cppreference.com 参见等。
vector
删除元素会使该元素后面的元素的迭代器无效。
根据需要erase您可以使用函数的返回值。
如果容器的容量发生更改,例如
另外,
请注意,不得访问push_back,则所有元素的迭代器都将失效。
访问元素不会使迭代器失效。
map/set
删除元素会使该元素上的迭代器无效。
根据需要erase您可以使用函数的返回值。
如果容器的容量发生更改,例如
读取或添加元素不会使迭代器无效。
映射/集合迭代器是只读的 您无法更改
map呀set迭代器指向的元素。
详细信息
STL函数简介
我们将介绍一些与迭代器相关的STL函数。
排序
正如我已经介绍过的,这是一个用于对齐数据的函数。
sort(イテレータ1, イテレータ2);
对齐迭代器 1 和迭代器 2 之间的元素。 您可以使用
sort(配列.begin(), 配列.end());来对齐整个数组,
如果你像sort(配列.begin() + 1, 配列.end());一样使用它,你可以对齐除开头之外的所有内容。
查找
匹配迭代器范围内的指定值第一个元素 查找并返回该元素的迭代器。 如果未找到,则返回范围的末尾。
对于数组
find(イテレータ1, イテレータ2, 値) // 見つからなかった場合はイテレータ2を返す
计算量就是迭代器的距离。N作为O(N)。
map/set对于
map/set,使用成员函数版本如下:
使用find速度更快。
オブジェクト.find(イテレータ1, イテレータ2, 値) // 見つからなかった場合はイテレータ2を返す
计算量取决于容器中元素的数量。N作为O(\log N)。
具体例
这是在数组中搜索 3 的示例。
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> a = {1, 2, 3, 5};
// 3の要素を指すイテレータ
auto itr = find(a.begin(), a.end(), 3);
// もし存在しなければ、a.end()が返る
if (itr == a.end()) {
cout << "not found" << endl;
} else {
// itrが添字の何番目を指すかを求める
int idx = distance(a.begin(), itr);
cout << "a[" << idx << "] = " << *itr << endl;
}
}
実行結果
a[2] = 3
find_if
在迭代器范围内满足条件第一个元素 查找并返回该元素的迭代器。 如果未找到,则返回范围的末尾。
find_if(イテレータ1, イテレータ2, 条件の関数) // 見つからなかった場合はイテレータ2を返す
为条件函数指定一个“接收元素作为参数并返回布尔值”的函数。
find_if表示该函数
返回第一个返回true的迭代器。
您还可以在条件中使用 lambda 表达式。
计算量就是迭代器的距离。N作为O(N)。
具体例
这是在数组中查找偶数个元素的示例。
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> a = {1, 3, 4, 5, 9, 10};
// 偶数であるような最初の要素を指すイテレータ
auto itr = find_if(a.begin(), a.end(), [](int x) { return (x % 2 == 0); });
if (itr == a.end()) {
cout << "not found" << endl;
} else {
cout << *itr << endl;
}
}
実行結果
4
下限
来自迭代器的范围内大于或等于指定值的最小元素 使用并返回该元素的迭代器。 如果未找到,则返回范围的末尾。
lower_bound时,必须对指定范围进行排序。
对于数组
lower_bound(イテレータ1, イテレータ2, 値) // 見つからなかった場合はイテレータ2を返す
计算量就是迭代器的距离。N作为O(\log N)。
map/set对于
map/set,使用成员函数版本如下:
使用lower_bound速度更快。
オブジェクト.lower_bound(値) // 見つからなかった場合はオブジェクト.end()を返す
计算量取决于容器中元素的数量。N作为O(\log N)。
具体例
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> a = {8, 5, 3};
sort(a.begin(), a.end()); // lower_boundを使うためにソートする
// 5以上の最小の要素を指すイテレータ
auto itr = lower_bound(a.begin(), a.end(), 5);
if (itr == a.end()) {
cout << "not found" << endl;
} else {
cout << *itr << endl;
}
// 6以上の最小の要素を指すイテレータ
itr = lower_bound(a.begin(), a.end(), 6);
if (itr == a.end()) {
cout << "not found" << endl;
} else {
cout << *itr << endl;
}
}
実行結果
5 8
上限
来自迭代器的范围内大于指定值的最小元素并返回该元素的迭代器。 如果未找到,则返回范围的末尾。
使用方法及金额计算
与lower_bound相同。
这里也是,
对于map/set,使用成员函数版本。