← 返回题目列表

AtCoder · APG4b_aa

AA. 3.03.STL容器

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

上一页 | 下一页

关键点

地图

  • 連想配列呀 名为辞書的数据结构
  • map允许您处理特定值链接到特定值的数据。
  • map声明
map<Keyの型, Valueの型> 変数名;
  • map操作
操作 記法 計算量
增加价值 変数[key] = value; O(\log N)
删除值 変数.erase(key); O(\log N)
访问值 変数.at(key) O(\log N)
所属判定 変数.count(key) O(\log N)
获取元素数量 変数.size() O(1)

队列

  • 队列呀 名为队列 通过使用的数据结构
  • queue,您可以执行诸如“逐一添加值并按照添加顺序提取值”之类的过程。
  • queue声明
queue<型> 変数名;
  • queue操作
操作 記法 計算量
添加元素 変数.push(値); O(1)
访问第一个元素 変数.front() O(1)
删除第一个元素 変数.pop(); O(1)
获取元素数量 変数.size() O(1)

优先队列

  • 优先队列的数据结构
  • priority_queue可用于执行“提取迄今为止添加的元素中最大的元素”的过程。
  • priority_queue声明
priority_queue<型> 変数名;
  • priority_queue操作
操作 記法 計算量
添加元素 変数.push(値) O(\log N)
获取最大元素 変数.top() O(1)
删除最大元素 変数.pop(); O(\log N)
获取元素数量 変数.size() O(1)
  • 按降序检索值priority_queue声明
priority_queue<型, vector<型>, greater<型>> 変数名;

STL容器

1.14.STL函数正如我提到的, STL 包括有用的函数和数据类型。 这次我们将介绍其中一些容器类型。 它是一种称为

地图

map是連想配列呀 名为辞書的数据类型。

map允许您轻松处理特定值与特定值关联的数据。

例如,假设您正在处理如下表这样的数据,其中名称(字符串类型的值)与成绩(int 类型的值)链接。

氏名 成績
“爱丽丝” 100
“鲍勃” 89
“查理” 95

这些数据 用map表示,则变为如下。

#include <bits/stdc++.h>
using namespace std;

int main() {
  map<string, int> score;  // 名前→成績
  score["Alice"] = 100;
  score["Bob"] = 89;
  score["Charlie"] = 95;

  cout << score.at("Alice") << endl;   // Aliceの成績
  cout << score.at("Bob") << endl;     // Bobの成績
  cout << score.at("Charlie") << endl; // Daveの成績
}
実行結果
100
89
95

对于以下解释,map处理的数据中,上表中的“名称”是钥匙,“等级”值 我们称之为。

宣言

map声明如下。

map<Keyの型, Valueの型> 変数名;

操作

在下面的每个操作的说明中,使用如下表的数据。 假设它位于一个名为score的变量中。

氏名 成績
“爱丽丝” 100
“鲍勃” 89
“戴夫” 这是将新成绩数据“Charlie→70”添加到 95
#include <bits/stdc++.h>
using namespace std;

int main() {
  // 初期状態
  map<string, int> score;
  score["Alice"] = 100;
  score["Dave"] = 95;
  score["Bob"] = 89;

  // (scoreに対する処理)
}

增加价值

変数[key] = value;
例

score的示例。

score["Charlie"] = 70;

添加“查理→70”后立即score的内容如下表所示。 删除

操作前
氏名 成績
“爱丽丝” 100
“鲍勃” 89
“戴夫” 这是将新成绩数据“Charlie→70”添加到 95
操作後
氏名 成績
“爱丽丝” 100
“鲍勃” 89
“查理” 70
“戴夫” 这是将新成绩数据“Charlie→70”添加到 95

删除值

変数.erase(key);

key对应的关系。 要从

例

score中删除“Bob→89”:

score.erase("Bob");

删除“Bob→89”后立即score的内容如下表所示。 删除

操作前
氏名 成績
“爱丽丝” 100
“鲍勃” 89
“戴夫” 这是将新成绩数据“Charlie→70”添加到 95
操作後
氏名 成績
“爱丽丝” 100
“戴夫” 这是将新成绩数据“Charlie→70”添加到 95

访问

変数.at(key)  // keyに対応するvalueが存在しない場合はエラーになる
変数[key]     // keyに対応するvalueが存在しない場合はValueの型の初期値が追加される

仅通过访问来添加新数据可能是错误的来源,所以基本上 我们建议使用.at,但是 您可以通过使用 []访问它来编写更短的程序。 这是使用

例

.at访问的示例。

cout << score.at("Alice") << endl;  // 100
cout << score.at("Taro") << endl;   // "Taro"に対応する値が存在しないためエラー

[]访问的示例。

score["Bob"] = 90;  // "Bob"の成績を90点に変更
cout << score["Alice"] << endl;  // 100
cout << score["Taro"] << endl;   // 0 (scoreに"Taro"というkeyは存在しないため、0で初期化される)

[]中不存在的密钥 作为访问"Taro"的结果,添加了数据“Taro→0”。 此外,鲍勃的等级已更改,太郎的物品已添加。

操作前
氏名 成績
“爱丽丝” 100
“鲍勃” 89
“戴夫” 这是将新成绩数据“Charlie→70”添加到 95
操作後
氏名 成績
“爱丽丝” 100
“鲍勃” 90
“戴夫” 这是将新成绩数据“Charlie→70”添加到 95
“太郎” 0

所属判定

要确定某个Key对应的Value是否存在,请执行以下操作:

if (変数.count(key)) {
  // keyに対応する関係が存在する
}
else {
  // keyに対応する関係が存在しない
}
例
if (score.count("Alice")) {
  cout << "Alice: " << score.at("Alice") << endl;
}
if (score.count("Jiro")) {
  cout << "Jiro: " << score.at("Jiro") << endl;
}
出力
Alice: 100

score的关键是"Alice"存在;"Jiro"不存在,所以Alice: 100。

在此操作中score的内容保持不变。

操作前
氏名 成績
“爱丽丝” 100
“鲍勃” 89
“戴夫” 这是将新成绩数据“Charlie→70”添加到 95

获取元素数量

変数.size()

返回存在多少个对应关系。

例
cout << score.size() << endl;  // 3

score有如下表所示的三个数据,所以score.size()返回 3。

在此操作中score的内容保持不变。

操作前
氏名 成績
“爱丽丝” 100
“鲍勃” 89
“戴夫” 这是将新成绩数据“Charlie→70”添加到 95

循环 您可以使用

// Keyの値が小さい順にループ
for (pair<Keyの型, Valueの型> p : 変数名) {
  Keyの型 key = p.first;
  Valueの型 value = p.second;
  // key, valueを使う
}

auto简洁地编写它。

// Keyの値が小さい順にループ
for (auto p : 変数名) {
  auto key = p.first;
  auto value = p.second;
  // key, valueを使う
}

在循环中,按升序(成对比较顺序)检索Key值。请注意,这不是您添加信件的顺序。 这是输出

例

score所有内容的示例。

for (auto p : score) {
  auto k = p.first;
  auto v = p.second;
  cout << k << " => " << v << endl;
}
出力
"Alice" => 100
"Bob" => 89
"Dave" => 95

計算量

元素数量 设置N时每个操作的计算量如下。

操作 計算量
增加价值 [] O(\log N)
删除值 erase(key) O(\log N)
访问值 at O(\log N)
所属判定 count O(\log N)
获取元素数量 size O(1)

队列

创建一个数据结构,执行诸如“逐一添加值并按照添加顺序检索值”等处理。 它被称为队列呀 名为队列 通过使用。 在C++中,STL提供了 可以使用queue。

队列用于常用算法,例如广度优先搜索。

下一张幻灯片显示了队列如何工作的图像。

如果将其制作成单个图像,它将如下所示: 数字代表推送顺序。 这是如何使用

使用例

queue的示例。这与上面幻灯片中描述的行为不同。

#include <bits/stdc++.h>
using namespace std;

int main() {
  queue<int> q;
  q.push(10);
  q.push(3);
  q.push(6);
  q.push(1);

  // 空でない間繰り返す
  while (!q.empty()) {
    cout << q.front() << endl;  // 先頭の値を出力
    q.pop();  // 先頭の値を削除
  }
}
実行結果
10
3
6
1

宣言

您可以声明一个空队列,如下所示:

queue<型> 変数名;

操作

添加元素

変数.push(値);

访问第一个元素

変数.front()

删除第一个元素

変数.pop();  // 先頭の要素が削除される

获取元素数量

変数.size()

要检查队列是否为空,请执行以下操作: 您还可以使用.empty()。

変数.empty()  // キューが空ならtrueを返す

計算量

每次操作的计算量如下。

操作 計算量
添加元素 push O(1)
访问第一个元素 front O(1)
删除第一个元素 pop O(1)
获取元素数量 size O(1)

优先队列

执行“提取目前添加的元素中最大元素”的过程时, 我们使用数据结构优先队列。 在 C++、STL 中priority_queue。

优先级队列用于Dijkstra算法等。 还有很多其他情况可以通过充分利用优先级队列来减少计算量。

使用例

#include <bits/stdc++.h>
using namespace std;

int main() {
  priority_queue<int> pq;
  pq.push(10);
  pq.push(3);
  pq.push(6);
  pq.push(1);

  // 空でない間繰り返す
  while (!pq.empty()) {
    cout << pq.top() << endl;  // 最大の値を出力
    pq.pop();  // 最大の値を削除
  }
}
実行結果
10
6
3
1

宣言

空 可以声明priority_queue。 与

priority_queue<型> 変数;

操作

添加元素

変数.push(値);

获取最大元素

変数.top()

queue不同, 请注意,它不是.front()。 另外,请注意它不能被重写。

删除最大元素

変数.pop()

获取元素数量

変数.size()

要检查它是否为空,请执行以下操作:.empty()。

変数.empty()  // 空ならtrueを返す

計算量

priorty_queue中的元素数量为N,每次操作的计算量如下。

操作 計算量
添加元素 push O(\log N)
获取最大元素 top O(1)
删除最大元素 pop O(\log N)
获取元素数量 size O(1)

提取最小元素

如下 如果声明priority_queue,则将按降序检索值。

priority_queue<型, vector<型>, greater<型>> 変数;

使用例

#include <bits/stdc++.h>
using namespace std;

int main() {
  // 小さい順に取り出される優先度付きキュー
  priority_queue<int, vector<int>, greater<int>> pq;
  pq.push(10);
  pq.push(3);
  pq.push(6);
  pq.push(1);

  // 空でない間繰り返す
  while (!pq.empty()) {
    cout << pq.top() << endl;  // 最小の値を出力
    pq.pop();  // 最小の値を削除
  }
}
実行結果
1
3
6
10

复制和比较的计算量 复制诸如

vector, string, map, queue, priority_queue之类的容器时, 比较vector呀 名为string所需的计算量为O(N)。

请小心频繁复制包含许多元素的容器的代码,因为计算量可能会增加。


详情

设置

set是一种用于处理一组唯一数据的数据类型。 “仅钥匙map”。实际上 您也可以使用map代替。

set在执行以下处理时很有用。

  • 数组中出现的值的类型数量(集合中不重复的元素数量)
  • 快速计算某个值是否包含在集合中
  • 查找集合中包含的最小值(最大值)

下面是 这是如何使用set的示例。

#include <bits/stdc++.h>
using namespace std;

int main() {
  set<int> S;

  S.insert(3);
  S.insert(7);
  S.insert(8);
  S.insert(10);
  // 既に3は含まれているのでこの操作は無視される
  S.insert(3);

  // 集合の要素数を出力
  cout << "size: " << S.size() << endl;

  // 7が含まれるか判定
  if (S.count(7)) {
    cout << "found 7" << endl;
  }
  // 5が含まれるか判定
  if (S.count(5)) {
    cout << "found 5" << endl;
  }
}
実行結果
size: 4
found 7

宣言

set<値の型> 変数名;

操作

增加价值

変数.insert(値);

如果相同的值已存在,则不会添加。

删除值

変数.erase(値);

所属判定

if (変数.count(値)) {
  //「値」が含まれる
}
else {
  //「値」は含まれない
}

获取元素数量

変数.size()

要检查它是否为空,请执行以下操作:.empty()。

変数.empty()  // 空ならtrueを返す

获取最小值

*begin(変数)

在顶部*为必填项。这个表示法将在第 4 章“迭代器”中介绍。

天空 不要对set执行此操作。 请注意,这可能不会导致运行时错误。

获取最大值

*rbegin(変数)

在顶部*为必填项。这个表示法将在第 4 章“迭代器”中介绍。

天空 不要对set执行此操作。 请注意,这可能不会导致运行时错误。

循环 您可以使用

for (auto value : 変数名) {
  // valueを使う
}

循环按升序检索值。请注意,这些值并不按照您添加的顺序排列。

計算量

元素数量 设置N时每个操作的计算量如下。

操作 計算量
增加价值 O(\log N)
删除值 O(\log N)
所属判定 O(\log N)
获取元素数量 O(1)
获取最小值 O(1)
获取最大值 O(1)

堆栈

创建一个执行处理的数据结构,以便“首先检索新添加的项目”。堆栈 它被称为。 在 C++ 中,STLstack。

下图显示了堆栈的工作原理。

上图中的数字代表推送的顺序。

使用例

#include <bits/stdc++.h>
using namespace std;

int main() {
  stack<int> s;
  s.push(10);
  s.push(1);
  s.push(3);

  cout << s.top() << endl;  // 3 (最後に追加した値)
  s.pop();
  cout << s.top() << endl;  // 1 (その前に追加した値)
}

宣言

stack<値の型> 変数名;

操作

增加价值

変数.push(値);

访问下一个值

変数.top()

删除值

変数.pop();

获取元素数量

変数.size()

要检查它是否为空,请执行以下操作:.empty()。

変数.empty()  // 空ならtrueを返す

計算量

元素数量 设置N时每个操作的计算量如下。

操作 計算量
增加价值 O(1)
访问下一个值 O(1)
删除值 O(1)
获取元素数量 O(1)

双端队列

队列操作“检索第一个添加的项目” 创建一个数据结构,允许您同时执行堆栈操作,例如“检索最后添加的元素”。双端队列 可以使用。 在 C++ 中,STLdeque。 (发音为“甲板”)

是一个类似数组的图像,可以从头到尾添加和删除。 ” 您还可以访问第i个值。

#include <bits/stdc++.h>
using namespace std;

int main() {
  deque<int> d;
  d.push_back(10);
  d.push_back(1);
  d.push_back(3);

  // この時点で d の内容は { 10, 1, 3 } となっている

  cout << d.front() << endl; // 10 (先頭の要素)
  d.pop_front();  // 先頭を削除

  // この時点で d の内容は { 1, 3 } となっている

  cout << d.back() << endl;  // 3 (末尾の要素)
  d.pop_back();  // 末尾を削除

  // この時点で d の内容は { 1 } となっている

  d.push_front(5);
  d.push_back(2);

  // この時点で d の内容は { 5, 1, 2 } となっている

  cout << d.at(1) << endl; // 1
}

宣言

deque<値の型> 変数名;

操作

增加价值

変数.push_back(値);   // 末尾への値の追加
変数.push_front(値);  // 先頭への値の追加

值访问

変数.front()  // 先頭の値へのアクセス
変数.back()   // 末尾の値へのアクセス
変数.at(i)  // i番目へのアクセス

访问不存在的元素将导致运行时错误。 对于

天空 不要对deque调用.front()呀 名为.back()时的行为未定义。 请注意,这可能不会导致运行时错误。

删除值

変数.pop_front();  // 先頭の要素の削除
変数.pop_back();   // 末尾の要素の削除

获取元素数量

変数.size()

要检查它是否为空,请执行以下操作:.empty()。

変数.empty()  // 空ならtrueを返す

計算量

元素数量 设置N时每个操作的计算量如下。

操作 計算量
增加价值 O(1)
值访问 O(1)
删除值 O(1)
获取元素数量 O(1)

unordered_map

C++ STLunordered_map基本功能是 它与map相同,但它是一种可以快速访问和搜索的数据结构。 但是,存在一些限制,例如不能直接使用对作为键。

制約

  • 没有定义哈希函数的类型(例如pair和tuple)不能用作键。
  • 使用循环提取时,我不知道它们将以什么顺序被检索。

在APG4b中迄今为止引入的类型中,除pair/tuple之外的任何类型都可以用作键。

这里我不会解释哈希函数,但如果你想了解更多,请查阅它们。

計算量

元素数量 设置N时每个操作的计算量如下。

操作 計算量
增加价值 [] 平均O(1)
删除值 erase 平均O(1)
访问值 at 平均O(1)
所属判定 count 平均O(1)
获取元素数量 size O(1)

用顺序表示法来说,一切都是平均恒定的时间,由于不断的乘法,实际速度不一定比地图快 请注意。


unordered_set

C++ STLunordered_set是 与unordered_map类似,它速度快但有局限性。set。

制約

  • 没有定义哈希函数的类型(例如pair和tuple)不能用作键。
  • 我不知道使用循环时它们将以什么顺序提取。
  • 无法检索最大值或最小值

計算量

元素数量 设置N时每个操作的计算量如下。

操作 計算量
增加价值 insert 平均O(1)
删除值 erase 平均O(1)
访问值 at 平均O(1)
所属判定 count 平均O(1)
获取元素数量 size O(1)

用顺序表示法来说,一切都是平均恒定的时间,由于常量乘法,实际速度不一定比设置快。


lower_bound / upper_bound(STL 函数)

按升序排序要在数组中查找“大于或等于 x 的最小元素”,请使用 STL 您可以使用lower_bound。同样,在求“超过x的最小元素”时, 您可以使用upper_bound。

计算量由数组中元素的数量决定。N然后两者O(\log N)。

使用例
#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> a = {0, 10, 13, 14, 20};
  // aにおいて、12 以上最小の要素は 13
  cout << *lower_bound(a.begin(), a.end(), 12) << endl; // 13

  // 14 以上最小の要素は 14
  cout << *lower_bound(a.begin(), a.end(), 14) << endl; // 14

  // 10 を超える最小の要素は 13
  cout << *upper_bound(a.begin(), a.end(), 10) << endl; // 13
}

如何使用

*lower_bound(配列.begin(), 配列.end(), 値)  // 「値」以上の最小の値
*upper_bound(配列.begin(), 配列.end(), 値)  // 「値」を超えるの最小の値

在顶部*为必填项。这个表示法将在第 4 章“迭代器”中介绍。


对空容器的操作

天空 不要对queue调用.front()或空 对于set我们解释说,执行*変数.begin()等操作时的行为是未定义的,并不一定会导致运行时错误。

1.13.配列如中所述#define _GLIBCXX_DEBUG(在 Clang 环境中 可以将#define _LIBCPP_DEBUG 0)写入程序的第一行,以在执行此类操作时生成运行时错误。

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

int main() {
  // ...
}

演習問題

请解决链接目的地的问题。