← 返回题目列表

AtCoder · APG4b_ai

AI. 4.04.迭代器

中文机器翻译题面 查看原题
page_url:https://atcoder.jp/contests/apg4b/tasks/APG4b_ai 任务ID:3781

上一页 | 下一页

关键点

  • 数组或者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,使用成员函数版本。


上一页 | 下一页