map

• 連想配列や辞書と呼ばれるデータ構造
• mapを用いると「特定の値に、ある値が紐付いている」ようなデータを扱うことができる
• mapの宣言

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

• mapの操作

queue

• キューや待ち行列と呼ばれるデータ構造
• queueを用いると「値を1つずつ追加していき、追加した順で値を取り出す」ような処理を行うことができる
• queueの宣言

queue<型> 変数名;

• queueの操作

priority_queue

• 優先度付きキューと呼ばれるデータ構造
• priority_queueを用いると「それまでに追加した要素のうち、最も大きいものを取り出す」という処理を行うことができる
• priority_queueの宣言

priority_queue<型> 変数名;

• priority_queueの操作

• 値が小さい順に取り出されるpriority_queueの宣言

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

STLのコンテナ

1.14.STLの関数でも触れましたが、 STLには便利な関数やデータ型が含まれています。 今回はこの中からいくつかのコンテナ型を紹介します。

map

mapは連想配列や辞書と呼ばれるデータ型です。

mapを用いると「特定の値に、ある値が紐付いている」ようなデータを簡単に扱うことができます。

例えば、氏名(string型の値)に成績(int型の値)が紐付いた次の表のようなデータを扱うとします。

これらのデータを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で扱うデータのうち、上の表でいう「氏名」の方をKey、「成績」の方をValueと呼ぶことにします。

宣言

mapは以下のように宣言します。

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

操作

以下の各操作の説明において、次の表のようなデータがscoreという変数に入っているとします。

#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に新しい成績のデータ「Charlie→70」を追加する例です。

score["Charlie"] = 70;

「Charlie→70」を追加した直後のscoreの中身は次の表のようになっています。

操作前

操作後

値の削除

変数.erase(key);

keyに対応している関係を削除します。

例

scoreから「Bob→89」を削除するには次のようにします。

score.erase("Bob");

「Bob→89」を削除した直後のscoreの中身は次の表のようになっています。

操作前

操作後

アクセス

変数.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で初期化される)

[]で存在しないkey"Taro"をアクセスした結果、「Taro→0」というデータが追加されます。 また、Bobの成績が変更され、Taroの項目が追加されています。

操作前

操作後

所属判定

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のKeyには、"Alice"は存在し、"Jiro"は存在しないので、Alice: 100だけ出力されます。

この操作ではscoreの内容は変化しません。

操作前

要素数の取得

変数.size()

いくつの対応関係が存在しているかを返します。

例

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

scoreには次の表のように3つのデータがあるので、score.size()は3を返します。

この操作ではscoreの内容は変化しません。

操作前

ループ

// 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の値が小さい順(pairの比較順)で取り出されます。対応関係を追加した順ではないことに注意してください。

例

scoreの内容をすべて出力する例です。

for (auto p : score) {
  auto k = p.first;
  auto v = p.second;
  cout << k << " => " << v << endl;
}

出力

"Alice" => 100
"Bob" => 89
"Dave" => 95

計算量

要素数をNとしたときの各操作の計算量は以下の通りです。

queue

「値を1つずつ追加していき、追加した順で値を取り出す」ような処理を行うデータ構造をキューや待ち行列といいます。 C++では、STLに用意されているqueueを用いることができます。

キューは幅優先探索などのよく用いられるアルゴリズムに利用します。

キューの動作のイメージを次のスライドに示します。

1枚の図にすると次のようになります。数字はpushした順番を表しています。

使用例

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を返す

計算量

各操作の計算量は以下の通りです。

priority_queue

「それまでに追加した要素のうち、最も大きいものを取り出す」という処理を行うときには、優先度付きキューというデータ構造を用います。 C++ではSTLのpriority_queueを用いることができます。

優先度付きキューはダイクストラ法などで用いられます。 他にも優先度付きキューをうまく用いることで、計算量を減らすことが出来るケースがよくあります。

使用例

#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とすると、各操作の計算量は以下の通りです。

最小の要素を取り出す

次のようにして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

setは重複の無いデータのまとまりを扱うためのデータ型です。 「Keyだけの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としたときの各操作の計算量は以下の通りです。

stack

「新しく追加したものほど先に取り出される」ような処理を行うデータ構造をスタックといいます。 C++では、STLのstackを用いることができます。

スタックの動作のイメージを次の図に示します。

上の図の数字はpushした順番を表しています。

使用例

#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としたときの各操作の計算量は以下の通りです。

deque

「最初に追加したものを取り出す」というキューの操作と 「最後に追加した要素を取り出す」というスタックの操作を同時に行えるデータ構造を両端キューといいます。 C++では、STLのdequeを用いることができます。（「デック」と読みます。）

先頭と末尾に対して追加・削除が行える配列のようなイメージです。 「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としたときの各操作の計算量は以下の通りです。

unordered_map

C++のSTLのunordered_mapは、基本的な機能はmapと同じですがアクセスや検索を高速に行うことができるデータ構造です。 ただし、Keyとしてpairを直接用いることができないなどの制約もあります。

制約

• pairやtupleなどのハッシュ関数が定義されていない型をKeyとして用いることができない
• ループで取り出すときに、どのような順番で取り出されるかが分からない

APG4bでこれまでに紹介した型のうち、pair/tuple以外の型であればKeyとして使用可能です。

ハッシュ関数についてはここでは説明しませんが、詳しく知りたい人は調べてみてください。

計算量

要素数をNとしたときの各操作の計算量は以下の通りです。

オーダー記法の上ではすべて平均で定数時間となっていますが、定数倍の関係で実際の速度がmapより速いとは限らないということに注意してください。

unordered_set

C++のSTLのunordered_setは、unordered_mapと同様に、制約がある代わりに高速なsetです。

制約

• pairやtupleなどのハッシュ関数が定義されていない型をKeyとして用いることができない
• ループで取り出すときに、どのような順番で取り出されるかが分からない
• 最大値や最小値を取り出すことができない

計算量

要素数をNとしたときの各操作の計算量は以下の通りです。

オーダー記法の上ではすべて平均で定数時間となっていますが、定数倍の関係で実際の速度がsetより速いとは限らないということに注意してください。

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）をプログラムの1行目に書くことによって、このような操作を行ってしまった際に実行時エラーにすることができます。

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

int main() {
  // ...
}

演習問題

リンク先の問題を解いてください。

EX23.最頻値

前のページ | 次のページ