提出練習

プログラミングの文法の説明に入る前に、自動採点システム（ジャッジ）の使い方を確認しましょう。

このページの一番下の「ソースコード」と書かれた場所の隣にテキストを入力できるところがあると思います。
そこに次のプログラムをコピー＆ペーストしてみましょう。

コピー＆ペーストの仕方：
↓の右上にある「Copy」ボタンをクリック→「ソースコード」のテキストを入力する場所で右クリック→「貼り付け」をクリック

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

int main() {
  cout << "Hello, world!" << endl;
}

コピー＆ペーストができたら、「言語」と書かれた場所の隣に「C++ (GCC 9.2.1)」と表示されていることを確認し、「提出」ボタンを押してください。

ページが切り替わり、 WJ と表示されているところが AC に変われば提出成功です。

• WAと表示されてしまった場合、正しくコピー＆ペーストできているか確認し、再提出してください。
• CEと表示されてしまった場合、「言語」として「C++ (GCC 9.2.1)」が選択されているか確認してください。「C++ (GCC 9.2.1)」以外のものが表示されている場合は、「C++ (GCC 9.2.1)」を選択し、再提出してください。

次のページ

main関数

C++のプログラムはmain関数から始まります。上のプログラムでは4行目から5行目までがmain関数です。

int main() {
}

C++のプログラムを起動すると、main関数の{の次の行から実行され、それに対応する}に辿り着くとプログラムを終了します。
このプログラムではmain関数の{ }の中に何も書いていないので、何もせずにプログラムは終了します。

今後のプログラムでは基本的にmain関数の中だけを考えれば良いです。自分でプログラムを書く場合、main関数の外の部分はコピー＆ペーストしましょう。

main関数の外の部分についての詳細は第4章で説明しますが、このページの末尾の「細かい話」で簡単に説明しています。気になる人は読んでみてください。
読むのが面倒な人は「プログラムの最初にとりあえず書く必要があるもの」くらいの認識で良いです。

出力

最初に提出したプログラムの詳細を見てみましょう。
このプログラムは「Hello, world!」という文字列を出力する（画面に表示する）プログラムです。

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

int main() {
  cout << "Hello, world!" << endl;
}

実行結果

Hello, world!

先程述べた通り、main関数の中だけに注目しましょう。このプログラムのmain関数の中には次の1行のプログラムが書かれています。

  cout << "Hello, world!" << endl;

この行が出力を行うプログラムです。この行について以下で詳しく説明します。

cout

C++で文字列を出力するには cout（しーあうと） を使います。

出力する文字列を指定している部分は"Hello, world!"の部分です。
C++プログラムの中で文字列を扱う場合、" "で囲う必要があります。endlは改行を表しています。

"Hello, world!"とendlというデータを、<<でcoutに送っていくイメージと覚えると良いでしょう。

endlはの4文字目は「数字の1」ではなく「アルファベットのl（小文字のL）」です。
文字列 という言葉は聞き馴染みが無いかもしれませんが、単に文字のことだと思っておけば良いです。詳しくは「1.12.文字列と文字」で扱います。

セミコロン

行の一番最後には;（セミコロン）が必要です。C++では、大抵の行の一番最後にはセミコロンが必要になります。どの行にセミコロンが必要でどの行に不要なのかは新しい文法を学んだ際に適宜見ていって下さい。
セミコロンが必要なところで書き忘れるとエラーになるので、注意しましょう。

別の文字列の出力

別の文字列を出力したい場合、次のように" "の中身を変えます。

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

int main() {
  cout << "こんにちは世界" << endl;
}

実行結果

こんにちは世界

複数の出力

出力を複数回行うこともできます。

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

int main() {
  cout << "a";
  cout << "b" << endl;
  cout << "c" << "d" << endl;
}

実行結果

ab
cd

このプログラムのポイントは2点です。
まず、5行目で改行を表すendlを出力していないため、aの後に改行がされずにabと出力されます。
次に、7行目でcout << "c" << "d"と書くことで、cdと出力することができます。この書き方を知っているとプログラムを短く書けることがあるので覚えておきましょう。

数値の出力

数値を出力するときは、" "を使わずに、直接書くことでも出力できます。

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

int main() {
  cout << 2525 << endl;
}

実行結果

2525

コメント

コメントは人間が「プログラムがどういう動作をしているか」等のメモ書きをプログラム中に残しておくための機能です。
プログラムとしての意味はないので、書いても動作に影響はありません。

例を見てみてみましょう。

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

int main() {
  cout << "Hello, world!" << endl; //Hello, worldと表示
  /*ここも
  コメント*/
}

実行結果

Hello, world!

コメントには二種類の書き方があります。

コメントを使わなくてもプログラムは書けますが、今後プログラム例の中で使うことがあるため、覚えておいて下さい。

コメントアウト

一時的に実行させたくない部分をコメントにしてしまうことで、その部分のプログラムを無効化するというテクニックがあります。このテクニックは コメントアウト と呼ばれ、よく使われています。

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

int main() {
  cout << "Hello" << endl;
  // cout << "World" << endl;
}

実行結果

Hello

6行目の処理はコメント扱いされるので、"World"は出力されません。

  // cout << "World" << endl;

"World"と出力させたくなった場合もコメントを解除する（//を消す）だけなので、書き直す手間が省けます。

注意点

半角文字と全角文字

基本的にC++プログラムの中に「全角文字」（あいう１２　等）が入り込むとエラー（AtCoderではCE）になってしまいます。
プログラムを書くときは必ず「半角文字」（abc12 等）で書くようにしましょう。
特に全角スペース「　」が入り込んでしまった場合、発見が難しくなってしまうので気をつけましょう。

ただし、" "の中とコメント内では全角文字を使うことができます。
コメントで全角文字を使った後、半角入力に戻し忘れて全角文字を紛れ込ませてしまう、というミスに気をつけましょう。

細かい話

細かい話なので、飛ばして問題を解いても良いです。

#include <bits/stdc++.h>

#include <bits/stdc++.h>はC++の機能を「全て」読み込むための命令です。例えばすでに紹介したcoutやendlは#include <bits/stdc++.h>によって読み込まれた機能です。 今後の解説で出てくるC++の機能の多くは#include <bits/stdc++.h>と書くことで利用できるようになります。これを書かずに読み込みが必要な機能を使った場合、エラーが発生します。

機能は個別に読み込むこともできます。このページで用いたcoutとendlだけであれば、#include <iostream>と書くことによって読み込めます。
ただし、はじめのうちは機能の読み込み忘れによるエラーで詰まってしまうことがよくあるので、#include <bits/stdc++.h>を使って一括で読み込むことをおすすめします。

なお、#include <bits/stdc++.h>は業務におけるプログラミングでは推奨されないことがありますが、競技プログラミングやAPG4bで利用する場合は全く問題ありません。
bits/stdc++.hに関して詳しくは4.01.includeディレクティブおよびトップページの「bits/stdc++.hに関するQ&A」を読んでください。

using namespace std;

using namespace std;はプログラムを短く書くための機能です。#includeで読み込んだC++の機能を利用するためには、通常はstd::coutやstd::endlのようにstd::をはじめに付ける必要があります。 using namespace std;を利用すると、このstd::を省略して書くことができます。

なお、using namespace std;も業務におけるプログラミングでは推奨されないことがありますが、競技プログラミングやAPG4bで利用する場合は全く問題ありません。
これについて詳しくは4.02.名前空間を読んでください。

問題

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

EX1.コードテストと出力の練習

前のページ | 次のページ

スペースと改行

C++では、基本的にスペースと改行は同じ意味になります。
また、どちらも省略できることが多いです。

以下の2つプログラムは全く同じ意味になります。

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

int main() {
  cout << "a";
  cout << "b" << endl;
  cout << "c" << "d" << endl;
}

#include <bits/stdc++.h>
using namespace std;int main(){cout<<"a";cout<<"b"<<endl;cout<<"c"<<"d"<<endl;}

実行結果

ab
cd

詰め込んであるプログラムは読みづらいので、スペースと改行を多く使って読みやすく書くのが一般的です。
スペースと改行の使い方に決まったルールはありません。一例としてサンプルプログラムを参考にしてください。

インデント

行のはじめにある連続したスペースのことをインデントと言います。
スペースとインデントでプログラムの動作が変わることはありません。プログラムを見やすくするために行います。

インデントはキーボードのTabキーを押して行います。TabキーはQキーの隣にあります。

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

int main() {
  //←インデント
  cout << "こんにちは世界" << endl;
}

基本的に{が出てきたら一段インデントし、}が出てきたら一段戻します。
また、元々一行に書いていたプログラムが長くなった場合は、改行してインデントすることがあります。

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

int main() {
  cout << "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    << "abcdefghijklmnopqrstuvwxyz" // 長いので改行してインデント
    << endl;
}

インデントの幅はプログラムを書いている環境により異なり、スペース2個から8個分であることが多いです。
どの程度の幅を使うかは基本的に自由ですが、プログラムを読みやすくするにはインデントの幅が統一されていることが重要です。

この教材では、AtCoderのコードテストページの設定に合わせて、インデントの幅をスペース2個分にしています。

今後複雑なプログラムを書くようになった場合、インデントをしているかどうかで大きく読みやすさが変わってきます。
サンプルプログラムを参考にしっかりインデントをするようにしましょう。

プログラムのエラー

プログラムは書き終わったら完成ではありません。動かしてみてその動作が正しいことを確認して、はじめて完成と言えます。
しかし書き終えたばかりのプログラムを実行しようとすると、たいてい何らかのエラーが発生します。そのときにエラーの原因を理解して修正できることもプログラマーの重要なスキルです。

プログラムには主に3つのエラーがあります。

• コンパイルエラー
• 実行時エラー
• 論理エラー

それぞれについて説明します。

コンパイルエラー

コンパイルエラーとは、書いたプログラムの文法にミスがあるときに発生するエラーです。
全角文字がプログラム中に入り込んだり、文末の;を忘れたときなどにはコンパイルエラーになります。

プログラミング言語では「文法」が厳密に決められています。
日本語などの人間が使う言語では、文法的に少し崩れた文でも意図が通じますが、プログラミング言語ではそうはいきません。

コンパイルエラーが起きた場合、プログラムは一切動作しません。

実行時エラー

「プログラムを動かす」ことを「プログラムを実行する」といいます。

実行時エラーとは、プログラムの文法に間違いはなかったが、内容に致命的な間違いがあったときに発生するエラーです。
具体的には3÷0のように、0で割り算を行ってしまった場合などに発生します。
スマホアプリやゲーム等が強制終了してしまったとき、多くの場合実行時エラーが発生しています。

実行時エラーが起きた場合、実行時エラーが起きる直前までプログラムは動作しますが、エラー以降は動かなくなってしまいます。

論理エラー

論理エラーとは、プログラムは一見正しく動作しているが、その動作が実は正しくないときに発生するエラーです。
例えば、「300円のクッキーと100円のアメを買ったときに払うお金」を計算するプログラムでは300 + 100と計算するべきですが、間違って300 - 100としてしまった場合などは論理エラーに当たります。
論理エラーは勘違いで生まれたり、タイピングのミスで発生したりと様々です。

論理エラーは一見問題なくプログラムが動作してしまうため、発見することが難しくなりやすいです。

エラーの直し方

実行してエラーや出力を確認→プログラムを修正→実行してエラーや出力を確認→... を繰り返すことが基本的な流れです。

エラーメッセージが表示される場合は、そのメッセージをコピー＆ペーストしてWeb検索してみるのも手です。
特にコンパイルエラーに関しては、エラーメッセージで検索すると分かることが多々あります。

調べてみてもよくわからない場合は、わかりそうな人に質問するのも良いでしょう。

コンパイルエラーの例

コンパイルエラーのうち、よくある3つの例を紹介します。

コンパイルエラーの内容は英語で表示されますが、英語が読める必要はありません。
エラーメッセージのパターンからなんとなく原因が推測できれば十分です。

全角スペース

全角スペースを紛れ込ませてしまうケースです。

次のプログラムでは、coutの前に全角スペースが紛れ込んでいます。

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

int main() {
//↓に全角スペース
　cout << "Hello, world!" << endl;
}

コンパイルエラー

./Main.cpp:6:1: error: stray ‘\343’ in program
 　cout << "Hello, world!" << endl;
 ^
./Main.cpp:6:1: error: stray ‘\200’ in program
./Main.cpp:6:1: error: stray ‘\200’ in program

error: stray ‘\343’ in program（エラー： ‘\343’がプログラム中に紛れ込んでいます）というエラーメッセージが表示されています。

全角スペースのコンパイルエラーでは、stray ‘\343’ in programやstray ‘\200’ in programと表示されるのが特徴です。
多くの場合、エラーメッセージがどこに全角スペースが入っているのかも教えてくれます。

上記のケースでは./Main.cpp:6:1:と書いてあり、6行目の1文字目にエラーがあることがわかります。
このように、エラーの発生箇所は./Main.cpp:行:文字目: errorを読めば特定できます。

また、エラーメッセージの2行目に

 　cout << "Hello, world!" << endl;
 ^

と書いてあり、coutの前に全角スペースがあることが視覚的にもわかります。

ただし、エラーメッセージが示す位置は少しずれることもあるので注意してください。

セミコロン忘れ

セミコロン;が必要な行の末尾にセミコロンを付け忘れるケースです。

次のプログラムでは、endlの後にセミコロンを付けるのを忘れてしまっています。

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

int main() {
  cout << "Hello, world!" << endl
}

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:6:1: error: expected ‘;’ before ‘}’ token
 }
 ^

error: expected ‘;’ before ‘}’ token（エラー： ‘}’トークンの前に‘;’が予期されます）というエラーメッセージが表示されています。

セミコロン忘れのコンパイルエラーでは、expected ‘;’ before ...というメッセージが表示されるのが特徴です。
少しわかりにくいですが、このエラーメッセージは「エラーが発生した次の行」を指し示しています。

上記のケースでは./Main.cpp:6:1: error:とあり、セミコロンを忘れた次の行である6行1文字目}の位置を指し示しています。

大量のエラー・謎のエラー

一つのミスで大量のエラーメッセージが出てくることもあります。また、エラーメッセージが直接的な原因を示していないことがあります。
その場合は一番最初のエラーが指し示している場所を見て、原因を推測しましょう。

次のプログラムではendlの直前の<<を<と書いてしまっただけのミスにより、大量に謎のエラーメッセージが表示されています。

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

int main() {
  cout << "hello" < endl;
}

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:5:19: error: no match for ‘operator<’ (operand types are ‘std::basic_ostream<char>’ and ‘<unresolved overloaded function type>’)
   cout << "hello" < endl;
                   ^
In file included from /usr/include/c++/5/regex:61:0,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:108,
                 from ./Main.cpp:1:
/usr/include/c++/5/bits/regex.h:1426:5: note: candidate: template<class _Bi_iter> bool std::operator<(const std::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)
     operator<(const sub_match<_Bi_iter>& __lhs,
     ^
/usr/include/c++/5/bits/regex.h:1426:5: note:   template argument deduction/substitution failed:
./Main.cpp:5:21: note:   ‘std::basic_ostream<char>’ is not derived from ‘const std::sub_match<_BiIter>’
   cout << "hello" < endl;
                     ^
In file included from /usr/include/c++/5/regex:61:0,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:108,
    ...

大量のエラーメッセージが表示された場合、とりあえず一番最初のエラーメッセージだけを見ると良いです。

一番最初のエラーメッセージだけを抜き出すと次のように表示されています。

./Main.cpp: In function ‘int main()’:
./Main.cpp:5:19: error: no match for ‘operator<’ (operand types are ‘std::basic_ostream<char>’ and ‘<unresolved overloaded function type>’)
   cout << "hello" < endl;
                   ^

error: no match for ‘operator<’...と書いてありますが、このエラーメッセージはあまり参考になりません。
このように、エラーメッセージが直接的な原因を示していないこともあります。

エラーメッセージの内容がよくわからない場合でも、エラーの発生箇所は参考になることが多いです。
この場合は./Main.cpp:5:19: error:と書いてあるので、5行目19文字目である次の部分でエラーが発生していることがわかります。

   cout << "hello" < endl;
                   ^

エラーの発生箇所をよく見ると、<<を<と書き間違えていることがわかります。
コンパイルエラーを直す際は、エラーの発生箇所から原因を推測することも大切です。

コンパイルエラー集

付録3.コンパイルエラー集にその他のよくあるエラーについてまとめました。
コンパイルエラーの原因がわからない時に見てみてください。

問題

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

EX2.エラーの修正

前のページ | 次のページ

剰余演算

もう一つ重要な算術演算子として % があります。この演算子は「割ったときの余り」を計算します。

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

int main() {
  cout << 7 % 3 << endl; // 1
  cout << 4 % 5 << endl; // 4
}

実行結果

1
4

7 ÷ 3 = 2 あまり 1
4 ÷ 5 = 0 あまり 4
となるため、このプログラムの出力は1と4になります。

演算子の優先順位

演算子には優先順位があります。

例えば1 + 2 * 3のような式を計算する場合、先に2 * 3が計算された後、1が足され、計算結果は7になります。
1 + 2 * 3 → 1 + 6 → 7
*は+よりも優先順位が高いというわけです。

C++の算術演算子の優先順位は、一般的な数学の優先順位と同じです。%は*や/と同じ優先順位になります。

( )を使って優先順位を変えることもできます。

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

int main() {
  cout << (1 + 2) * 3 << endl; // 9
}

実行結果

9

( )の中が先に計算され、(1 + 2) * 3 → 3 * 3となり結果は9になります。

なお、5 / 2 * 3のように同じ優先順位の演算子が並んでいる式は、基本的に左の演算子から順に計算されます。

注意点

除算の順序

割り算/のある整数同士の計算では、切り捨てが行われるタイミングの違いで結果が異なることがあります。

例えば3÷2×4を計算する場合、書き方によって2つの計算結果が考えられます。

• 3 / 2 * 4 → 1 * 4 → 4
• 3 * 4 / 2 → 12 / 2 → 6

多くの場合、割り算はできるだけ後の方で行うようにしたほうが正しい結果になります。

ゼロ除算

0で割ると実行時エラーが発生します。

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

int main() {
  cout << 3 / 0 << endl;
}

終了コード

136

3 % 0のように0で剰余演算%をした場合も同様に実行時エラーになります。

コードテスト上で表示される終了コードは136になります。
コードテスト以外の環境で実行した場合、Floating point exceptionと表示されることもあります。

なお、0 / 3や0 % 3のように、割られる数が0の場合は問題なく計算できることに注意してください。どちらも結果は0になります。

細かい話

細かい話なので、飛ばして問題を解いても良いです。

負の数の剰余

剰余演算A % Bを行う時にAまたはBが負の数の場合、計算結果は以下のようになります。|A|, |B|はそれぞれの絶対値を表すとします。

• Aが正のとき：|A|%|B|
• Aが負のとき：-(|A|%|B|)

つまりBの正負に関わらず、計算結果はAの正負と一致します。

より正確に言うと、C++の剰余演算子は(A / B) * B + (A % B)とAが等しくなるように定義されており、結果的にAの正負と一致します。

問題

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

EX3.計算問題

前のページ | 次のページ

変数の初期化

変数の宣言と代入は同時に行うこともできます。

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

int main() {

  int name = 10;

  cout << name << endl;
}

実行結果

10

変数を宣言した後の最初の代入を初期化といいます。上のプログラムで変数nameは10に初期化されています。

変数はコピーされる

変数1 = 変数2と書いた場合、変数の値そのものがコピーされます。
その後にどちらかの変数の値が変更されても、もう片方の変数は影響を受けません。

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

int main() {

  int a = 10;
  int b;
  b = a; // aの値がコピーされ、bに10が代入される
  a = 5; // aの値は5に書き換わるが、bは10のまま

  cout << a << endl; // 5
  cout << b << endl; // 10
}

実行結果

5
10

変数bが10のままであることに注意してください。
7行目から9行目の処理を図で説明すると以下のようになります。

変数を同時に宣言

変数の宣言時に,を間に入れることで複数の変数を同時に宣言することもできます。

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

int main() {

  int a = 10, b = 5;

  cout << a << endl;
  cout << b << endl;
}

実行結果

10
5

上のプログラムは次のように書いた場合と同じ意味になります。

int a = 10;
int b = 5;

変数名のルール

変数名は基本的に自由につけることができますが、一部の名前を変数名にしようとするとコンパイルエラーになります。

利用できない変数名

以下の条件に該当する名前は変数名にできません。

• 数字で始まる名前
• _以外の記号が使われている名前
• キーワード（C++が使っている一部の単語）

以下は変数名にできない名前の例です。

int 100hello; // 数字で始まる名前にはできない
int na+me; // 変数名に+を使うことはできない
int int; // intはキーワードなので変数名にできない

以下のような名前は変数名にできます。

int hello10; // 2文字目以降は数字にできる
int hello_world; // _ は変数名に使える

無意識にキーワードを変数名にしてしまうことはあまり無いので、キーワードに関してはあまり気にしなくても良いです。気になる人は「C++ キーワード」等でWebで検索してみてください。

同じ名前の変数は宣言できない

同じ名前の変数を複数宣言することはできません。

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

int main() {
  int a = 0;

  int a = 5; // この行でコンパイルエラーになる

  cout << a << endl;
}

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:7:9: error: redeclaration of ‘int a’
     int a = 5; // この行でコンパイルエラーになる
         ^
./Main.cpp:5:9: note: ‘int a’ previously declared here
     int a = 0;
         ^

error: redeclaration of ‘int a’（エラー： ‘int a’の再宣言）というエラーメッセージが表示されています。

例外的に同じ名前の変数を宣言する方法もありますが、それについては「1.08.変数のスコープ」で説明します。

型

int以外にもC++には様々な型があります。ここでは重要な3つの型だけを紹介します。

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

int main() {
  int i = 10;
  double d = 0.5;
  string s = "Hello";

  cout << i << endl;
  cout << d << endl;
  cout << s << endl;
}

実行結果

10
0.5
Hello

異なる型同士の計算

異なる型同士の計算では型変換が行われます。
例えば、int型とdouble型の計算結果はdouble型になります。

ただし、変換できない型同士は計算はコンパイルエラーになります。

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

int main() {
  int i = 30;
  double d = 1.5;
  string s = "Hello";

  cout << i + d << endl; // 31.5
  cout << i * d << endl; // 45
  cout << 45 / 2 << endl; // 22 小数点以下切り捨て
  cout << i * d / 2 << endl; // 22.5 小数点以下も残る
  /*
  以下の処理はコンパイルエラー
  cout << s + i << endl; // string型とint型
  cout << s * i << endl; // string型とint型
  cout << s + d << endl; // string型とdouble型
  */
}

実行結果

31.5
45
22
22.5

計算の途中にdouble型のデータが入ってくるかどうかで、小数点以下を切り捨てるかどうかが変わってきます。
string型とint型、string型とdouble型は変換できない型の組み合わせなのでコンパイルエラーになります。

異なる型同士の代入

異なる型同士の代入でも型変換は行われます。
計算と同様、変換できない型同士の代入はコンパイルエラーになります。

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

int main() {
  int i = 10;
  double d = i; // doubleとintは互いに代入できる（小数点以下切り捨て）
  string s = "Hello";

  i = s; // int型とstring型は互いに代入できない

  cout << i << endl;
}

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:9:5: error: cannot convert ‘std::string {aka std::basic_string<char>}’ to ‘int’ in assignment
   i = s; // int型とstring型は互いに代入できない
     ^

「エラー：代入時に‘string’を‘int’に変換できません」というような内容のエラーメッセージが表示されています。

double型とint型は変換できる型同士なので互いに代入できます。double型をint型に変換したときは小数点以下切り捨てになります。
int型やdouble型の型変換については3.01.数値型で詳しく説明します。

細かい話

細かい話なので、飛ばして問題を解いても良いです。

初期化する前の変数の値

初期化する前のint型やdouble型の変数の値を読み込んだ場合、どのような値になっているか分かりません。

次のプログラムは初期化する前の変数の値を読み込む例です。

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

int main() {
  int name;
  cout << name << endl; //なにが出力されるかわからない
}

変数の初期化をし忘れてしまい、このプログラムのような状況になることがしばしばあります。
変数の初期化し忘れによるバグ（プログラムのミス）を防ぎたい場合、すべての変数を宣言時に適当な値で初期化しておくのも一つの手です。

より厳密には、初期化する前の変数の値は基本的に宣言するより前の処理内容で決まります。
その関係で、単純なプログラムでは初期化しなくても変数の値は0になっていることが多いです。

なお、string型の変数は初期化を行わなかった場合は自動的に""で初期化されます。

問題

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

EX4.◯年は何秒？

前のページ | 次のページ

整数以外のデータの入力

整数以外のデータを受け取りたいときは、そのデータの種類に合わせた型の変数を使います。

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

int main() {
  string text;
  double d;
  cin >> text;
  cin >> d;
  cout << text << ", " << d << endl;
}

入力

Hello
1.5

実行結果

Hello, 1.5

このプログラムが実行される様子を表したのが次のスライドです。

繋げて入力

coutと同じように、cinも>>を繋げて入力を受け取ることができます。

入力が複数ある場合は、スペースか改行で区切られていれば分解して入力してくれます。

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

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  cout << a * b * c << endl;
}

入力

2 3
4

実行結果

24

aに2、bに3、cに4が入力されています。

問題

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

EX5.A足すB問題

AtCoder Beginner Contestの問題

AtCoderではAtCoder Beginner Contest (ABC)というコンテストを定期的に開催しています。
そのコンテストで出題される問題の中には、ここまでで学んだ知識だけで解けるものもあります。
ここではその中からいくつか紹介します。練習問題では物足りない人は解いてみてください。

易しめ

• A - New Year
• A - Rating Goal
• A - Bichrome Cells

難しめ

• A - Round Up the Mean
• A - Placing Marbles

「難しめ」の問題はもっとプログラムの知識がつくと簡単になりますが、ここまでで学んだ知識のみで解こうとすると少し工夫が必要になります。

前のページ | 次のページ

else句

else句は、if文の後に書くことで「if文の条件が偽の時」に処理を行えるようになります。
書き方は次のようになります。

if (条件式1) {
  処理1
}
else {
  処理2
}

次のプログラムは入力の値が10より小さければ「xは10より小さい」と出力し、そうでなければ「xは10より小さくない」と出力します。

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

int main() {
  int x;
  cin >> x;

  if (x < 10) {
    cout << "xは10より小さい" << endl;
  }
  else {
    cout << "xは10より小さくない" << endl;
  }
}

入力1

5

実行結果1

xは10より小さい

入力2

15

実行結果2

xは10より小さくない

else if

else ifは「『前のif文の条件が偽』かつ『else ifの条件が真』」の時に処理が行われます。

書き方は次のようになります。

if (条件式1) {
  処理1
}
else if (条件式2) {
  処理2
}

処理2が実行されるのは「条件式1が偽 かつ 条件式2が真」のときになります。

else ifの後に続けてelse ifやelseを書くこともできます。次のプログラムはその例です。

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

int main() {
  int x;
  cin >> x;

  if (x < 10) {
    cout << "xは10より小さい" << endl;
  }
  else if (x > 20) {
    cout << "xは10より小さくなくて、20より大きい" << endl;
  }
  else if (x == 15) {
    cout << "xは10より小さくなくて、20より大きくなくて、15である" << endl;
  }
  else {
    cout << "xは10より小さくなくて、20より大きくもなくて、15でもない" << endl;
  }
}

入力1

5

実行結果1

xは10より小さい

入力2

30

実行結果2

xは10より小さくなくて、20より大きい

入力3

15

実行結果3

xは10より小さくなくて、20より大きくなくて、15である

入力4

13

実行結果4

xは10より小さくなくて、20より大きくもなくて、15でもない

注意点

よくあるミス

==のつもりで=とだけ書いてしまわないように注意しましょう。

次のプログラムは「xが10と等しいか」を判定するプログラムの典型的なミスです。

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

int main() {
  int x = 5;

  if (x = 10) {
    cout << "xは10" << endl;
  }
}

実行結果

xは10

if (x = 10)のif文はxがどんな数値でも真だと判定されます。ハマりどころなので覚えておきましょう。なぜそうなるかは次の節で説明します。

細かい話

細かい話なので、飛ばして問題を解いても良いです。

{ } の省略

処理の部分が1文しか無い場合は、{ }を省略することができます。

if (x < 10)
  cout << "xは10より小さい" << endl;

「1文」とは、「セミコロンが1つだけで十分な処理」だと思えば良いです。
つまり、以下のような書き方は思った通りには動きません。

if (x < 10)
  cout << "xは10より小さい" << endl; cout << "Hello!" << endl;

これは次のように書いたのと同じ意味になります。

if (x < 10) {
  cout << "xは10より小さい" << endl;
}
cout << "Hello!" << endl;

if文のネスト

if文の中にif文を入れることをif文のネストと言います。

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

int main() {
  int x, y;
  cin >> x >> y;

  if (x == 10) {
    cout << "xは10" << endl;
    if (y == 10) {
      cout << "yも10" << endl;
    }
  }

  cout << "終了" << endl;
}

入力

10 10

実行結果

xは10
yも10
終了

入力

5 10

実行結果

終了

問題

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

EX6.電卓をつくろう

ABCの問題

ここまでの知識だけで解ける問題をAtCoder Beginner Contestから再び紹介します。練習問題だけでは物足りない人は解いてみてください。

• A - Infinite Coins
• A - Product
• A - Libra
• A - Parking
• A - Good Integer

前のページ | 次のページ

bool型を使う場面

今まで学んできたものと違い、「bool型がないと書けないプログラム（計算）」はありません。
bool型は基本的に「条件式の結果」や「状態が2つしか無いもの」を扱っていることを明示するために使います。

これができることによる恩恵は今はわかりにくいかもしれませんが、1.15.関数で紹介する機能を使う場合など、bool型を使うことでプログラムがわかりやすくなることがあります。
なお、今後は「真」や「偽」という言葉の代わりにtrueやfalseという言葉を使って説明することがあるので、これらの意味はしっかりと覚えておいてください。

細かい話

細かい話なので、飛ばして問題を解いても良いです。

bool型と数値

実は、0と1以外の数値もbool型の値のように扱うことができます。
その場合、0のときだけfalse、それ以外の数値はすべてtrueになります。

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

int main() {
  bool a = 10; // 10はtrue
  bool b = 0; // 0はfalse
  cout << a << endl; // 1
  cout << b << endl; // 0

  // 100はtrue
  if (100) {
    cout << "hello" << endl;
  }
}

実行結果

1
0
hello

if文の節で紹介した==と=を書き間違える典型的なミスは、この「trueとfalse以外の値もbool型のように受け入れてしまう」という性質によって引き起こされています。
a = bという式の「計算結果」はbになります。そのため、if (a = b)はif (b != 0)とほとんど同じ意味になってしまいます。

問題

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

EX7.bool値パズル

前のページ | 次のページ

同じ名前の変数

変数を宣言するブロックが異なれば、同じ名前の変数を宣言することができます。

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

int main() {
  int x = 10;

  if (x == 5) {
    int y = 10;
    cout << x + y << endl;

    // string y = "hello" 同じブロックに変数yがあるので宣言できない
  }

  if (x == 10) {
    string y = "hello"; // ブロックが違うので変数yを宣言できる
    cout << x << y << endl;
  }
}

実行結果

10hello

スコープがある理由

スコープがある理由はいくつかありますが、その中から一つ説明します。

スコープがない場合、一度宣言した変数等の名前は別の場所で使えなくなってしまいます。
プログラムの規模が大きくなってくると、その分多くの変数が用いられます。そのため、新しく変数を宣言しようとしたとき、まだ使われていない名前を考えることに手間がかかってしまいます。

スコープがあることで、プログラムの別の部分でどのような名前が使われているかをあまり考えること無く、変数等の名前を決められるようになります。

細かい話

細かい話なので、飛ばして問題を解いても良いです。

スコープが重なっている場合

変数を使える条件は次の2つです。

1. 変数を使っている場所より前で宣言されている
2. 変数を使っている場所と同じか、より外側のブロックで宣言されている

同じ名前の変数のスコープが重なっていて、候補が複数考えられる場合は次の条件で使う変数が決められます。

3. 候補の変数のうち最も内側で宣言されている

例を見てみましょう。

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

int main() {
  int x = 5;
  cout << x << endl; // 5

  if (x == 5) {
    cout << x << endl; // 5

    string x = "hello"; // int x = 5;のスコープと重なっている
    cout << x << endl; // hello
  }

  cout << x << endl; // 5
}

実行結果

5
5
hello
5

次の図はこのプログラムの動作を説明したものです。

上のプログラムの8行目のxにおいて、条件1.と条件2.に当てはまるxはint x = 5;だけなので、出力は5になります。

9行目のxにおいて、条件1.と条件2.に当てはまるxはint x = 5;だけなので、出力は5になります。

12行目のxにおいて、条件1.と条件2.に当てはまるのはint x = 5;とstring x = "hello";の2つがありますが、条件3.からstring x = "hello";が選ばれ、出力はhelloになります。

15行目のxにおいて、条件1.と条件2.に当てはまるのは再びint x = 5;だけになるなので、出力は5になります。

この挙動はしばしばバグの原因になります。注意してください。

問題

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

EX8.たこ焼きセット

前のページ | 次のページ

+=以外の複合代入演算子

他の算術演算子についても同様のことができます。

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

int main() {
  int a = 5;
  a -= 2;
  cout << a << endl; // 3

  int b = 3;
  b *= 1 + 2;
  cout << b << endl; // 9

  int c = 4;
  c /= 2;
  cout << c << endl; // 2

  int d = 5;
  d %= 2;
  cout << d << endl; // 1
}

実行結果

3
9
2
1

インクリメントとデクリメント

x = x + 1はx++または++xと書くことができます。このような「1増やす操作」をインクリメントと言います。

x = x - 1はx--または--xと書くことができます。このような「1減らす操作」をデクリメントと言います。

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

int main() {
  int x = 5;
  x++;
  cout << x << endl; // 6

  int y = 5;
  y--;
  cout << y << endl; // 4
}

実行結果

6
4

このように、プログラムを短く書くための記法のことをシンタックスシュガーと言います。

問題

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

EX9.複合代入演算子を使おう

前のページ | 次のページ

補足

この説明を読む前に付録4.ループの裏技repマクロを読んだほうが理解しやすいです。ただし、必須の知識では無いので読まなくても問題ありません。

キーポイント

• while文を使うと繰り返し処理ができる
• 条件式が真のとき処理を繰り返す

while (条件式) {
  処理
}

• 「N回処理する」というプログラムを書く場合、「カウンタ変数を0からはじめ、カウンタ変数がNより小さいときにループ」という形式で書く

int i = 0; // カウンタ変数
while (i < N) {
  処理
  i++;
}

while文

while文を使うと、プログラムの機能の中でも非常に重要な「繰り返し処理」（ループ処理）を行うことができます。

無限ループ

次のプログラムは、「"Hello"と出力して改行した後、"AtCoder"と出力する処理」を無限に繰り返すプログラムです。

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

int main() {

  while (true) {
    cout << "Hello" << endl;
    cout << "AtCoder" << endl;
  }

}

実行結果

Hello
AtCoder
Hello
AtCoder
Hello
AtCoder
Hello
AtCoder
Hello
AtCoder
...(無限に続く)

while文は次のように書き、条件式が真のとき処理を繰り返し続けます。

while (条件式) {
  処理
}

先のプログラムでは条件式の部分にtrueと書いているため、無限に処理を繰り返し続けます。
このように、無限に繰り返し続けることを無限ループと言います。

1ずつカウントする

次プログラムは、1から順に整数を出力し続けます。

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

int main() {

  int i = 1;

  while (true) {
    cout << i << endl;
    i++; //ループのたびに1増やす
  }

}

実行結果

1
2
3
4
5
6
7
8
...(無限に1ずつ増えていく)

途中で負の値になったかもしれませんが、なぜそうなるかは3.01.数値型で説明します。

ループ回数の指定

1ずつカウントするプログラムを「1から5までの数を出力するプログラム」に変える場合、次のようにします。

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

int main() {

  int i = 1;

  // iが5以下の間だけループ
  while (i <= 5) {
    cout << i << endl;
    i++;
  }

}

実行結果

1
2
3
4
5

カウンタ変数は0からN未満まで

5回Helloと出力するプログラムを考えます。
まず一般的でない書き方（やめておいた方が良い書き方）を紹介し、次に一般的な書き方（推奨される書き方）を紹介します。

一般的でない書き方

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

int main() {

  // iを1からはじめる
  int i = 1;

  // iが5以下の間ループ
  while (i <= 5) {
    cout << "Hello" << endl;
    i++;
  }

}

実行結果

Hello
Hello
Hello
Hello
Hello

「N回処理をする」というプログラムをwhile文で書く場合、今までは「iを1からはじめ、N以下の間ループする」という形式で書いてきました。

int i = 1;
while (i <= N) {
  処理
  i++;
}

この形式は一見わかりやすいと感じるかもしれません。
しかし、この書き方はあまり一般的ではなく、次のように書いたほうが良いです。

一般的な書き方

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

int main() {

  // iを0からはじめる
  int i = 0;

  // iが5未満の間ループ
  while (i < 5) {
    cout << "Hello" << endl;
    i++;
  }

}

実行結果

Hello
Hello
Hello
Hello
Hello

「N回処理する」というプログラムを書く場合、次のように「iを0からはじめ、iがNより小さいときにループする」という形式で書くのが一般的です。

int i = 0;
while (i < N) {
  処理
  i++;
}

最初は分かりづらく感じるかもしれませんが、こう書いた方がプログラムをシンプルに書けることが後々増えてくるので、慣れるようにしましょう。

なお、このプログラムの変数iのように、「何度目のループか」を管理する変数のことをカウンタ変数と呼ぶことがあります。 カウンタ変数は基本的にiを使い、iが使えない場合はj, k, l...と名前をつけていくのが一般的です。

応用例

N人の合計点を求めるプログラムを作ってみましょう。
次のプログラムは「入力の個数N」と「点数を表すN個の整数」を入力で受け取り、点数の合計を出力します。

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

int main() {
  int N;
  cin >> N;

  int sum = 0; // 合計点を表す変数
  int x;       // 入力を受け取る変数
  int i = 0;   // カウンタ変数

  while (i < N) {
    cin >> x;
    sum += x;
    i++;
  }

  cout << sum << endl;
}

入力

3
1 10 100

実行結果

111

合計点を表す変数sumを作っておき、ループするたびに入力を変数xに入れ、sumに足しています。

このプログラムが実行される様子を表したのが次のスライドです。

このように、繰り返し処理を使えば様々な処理が行えるようになります。
ループ構文を使って様々な処理を書く方法は2.01.ループの書き方や2.02.多重ループで詳しく説明します。

細かい話

細かい話なので、飛ばして問題を解いても良いです。

2ずつ増やす

今まではiを1ずつだけ増やしてきましたが、2ずつ増やすこともできます。

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

int main() {

  int i = 0;

  while (i < 10) {
    cout << i << endl;
    i += 2;
  }

}

実行結果

0
2
4
6
8

次のように書くことで2ずつ増やしています。

i += 2;

同様にして、より多く飛ばしてループすることもできます。

逆順ループ

5から0までの数を出力したい場合は以下のようにします。

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

int main() {

  int i = 5;

  while (i >= 0) {
    cout << i << endl;
    i--;
  }

}

実行結果

5
4
3
2
1
0

こちらはデクリメントを使うことで1ずつ減らしています。

i--;

無限ループをコードテストで実行した場合

AtCoderのコードテストでは実行時間が長すぎるとプログラムが中断されます。また、出力が長すぎる場合も途中から省略されます。
そのため、はじめに紹介した「"Hello"と出力して改行した後、"AtCoder"と出力する処理」を無限に繰り返すプログラムをコードテストで実行しても無限には出力されず、次のように表示されます。

標準出力

Hello
AtCoder
（中略）
Hello
AtCoder
He...

終了コード

9

無限ループが発生した場合、終了コードは実行時間が長すぎることを表す9となります。

問題

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

EX10.棒グラフの出力

前のページ | 次のページ

補足

この説明を読む前に付録4.ループの裏技repマクロを読んだほうが理解しやすいです。ただし、必須の知識では無いので読まなくても問題ありません。

キーポイント

• for文は繰り返し処理でよくあるパターンをwhile文より短く書くための構文
• 「初期化」→「条件式」→「処理」→「更新」→「条件式」→「処理」→...という順で実行され、条件式が真のとき繰り返し続ける

for (初期化; 条件式; 更新) {
  処理
}

• N回の繰り返し処理は次のfor文で書くのが一般的

for (int i = 0; i < N; i++) {
  処理
}

• breakを使うとループを途中で抜けられる
• continueを使うと後の処理を飛ばして次のループへ行ける

for文

for文は「N回処理する」というような繰り返し処理でよくあるパターンをwhile文より短く書くための構文です。

3回繰り返すプログラムをwhile文とfor文で書くと次のようになります。

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

int main() {

  int j = 0;
  while (j < 3) {
    cout << "Hello while: " << j << endl;
    j++;
  }

  for (int i = 0; i < 3; i++) {
    cout << "Hello for: " << i << endl;
  }

}

実行結果

Hello while: 0
Hello while: 1
Hello while: 2
Hello for: 0
Hello for: 1
Hello for: 2

for文は次のように書き、条件式が真のとき処理を繰り返し続けます。

for (初期化; 条件式; 更新) {
  処理
}

実行される順序は次のとおりです。

はじめのプログラムのfor文が実行される様子を表したのが次のスライドです。

forとwhileの対応関係

for文とwhile文の対応関係を見てみましょう。

int i = 0; // 初期化
while (i < 3 /* 条件式 */ ) {

  cout << "Hello while: " << j << endl; // 処理

  i++; //更新
}

for (int i = 0 /* 初期化 */ ; i < 3 /* 条件式 */ ; i++ /* 更新 */) {

  cout << "Hello for: " << i << endl; // 処理

}

処理される順序はwhile文で書いたときと全く同じで、「初期化」→「条件式」→「処理」→「更新」→「条件式」→「処理」→...という順で実行されます。

while文とfor文は機能面ではほとんど差がありませんが、次の「N回の繰り返し処理」等、for文で簡潔に書ける処理はfor文で書くのが一般的です。

N回の繰り返し処理

for文を使うとき、ほとんどは「N回の繰り返し処理」のパターンです。
動作の細かい部分がわからない人は、とりあえずこのパターンを覚えるところから始めましょう。

for (int i = 0; i < N; i++) {
  処理
}

for文を使うときのコツ

「N回の繰り返し処理」のfor文を使うときは、「初期化」「条件式」「更新」の細かい動作を考えないようにしましょう。
よりおおざっぱに、for文はiが1ずつ増えながらN回処理を繰り返す機能と考えた方が、for文を使うプログラムを書きやすくなります。

また、ループでどう書けばよいかわからなくなったときは、まずループを使わずにプログラムを書いてみて、その後ループで書き直すという方法が有効です。
以下の2つのプログラムはその例です。これに関しては2.01.ループの書き方でより詳しく説明します。

ループを使わないプログラム

cout << "hello for :" << 0 << endl;
cout << "hello for :" << 1 << endl;
cout << "hello for :" << 2 << endl;

ループで書き直したプログラム

for (int i = 0; i < 3; i++) {
  cout << "hello for :" << i << endl;
}

breakとcontinue

while文とfor文を制御する命令として、breakとcontinueがあります。

break

breakはループを途中で抜けるための命令です。

breakを使ったプログラムの例です。

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

int main() {

  // breakがなければこのループは i == 4 まで繰り返す
  for (int i = 0; i < 5; i++) {

    if (i == 3) {
      cout << "ぬける" << endl;
      break; // i == 3 の時点でループから抜ける
    }

    cout << i << endl;
  }

  cout << "終了" << endl;
}

実行結果

0
1
2
ぬける
終了

if文で i == 3 が真になったとき、break;の命令を実行することでforループを抜け、終了と出力しています。

continue

continueは後の処理をとばして次のループへ行くための命令です。

continueを使ったプログラムの例です。

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

int main() {

  for (int i = 0; i < 5; i++) {

    if (i == 3) {
      cout << "とばす" << endl;
      continue; // i == 3 のとき これより後の処理をとばす
    }

    cout << i << endl;
  }

  cout << "終了" << endl;
}

実行結果

0
1
2
とばす
4
終了

上のプログラムでは、if文で i == 3 が真になったとき、continue;の命令を実行することでcontinueより下の部分を飛ばし、次のループに入ります。

細かい話

細かい話なので、飛ばして問題を解いても良いです。

for文とwhile文の違い

for文とwhile文の違いは主に2点あります。「カウンタ変数のスコープ」と「continueをしたときの動作」です。

カウンタ変数のスコープ

for文のカウンタ変数はwhile文よりスコープが狭くなります。
次の例では、for文のカウンタ変数であるiがスコープの範囲外で使われているため、コンパイルエラーが発生しています。

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

int main() {

  int j = 0; // jのスコープはmain関数の終わりまで
  while (j < 3) {
    cout << "Hello while" << endl;
    j++;
  }

  for (int i = 0; i < 3; i++) { // iのスコープはforの終わりまで
    cout << "Hello for" << endl;
  }

  cout << j << endl;

  cout << i << endl;
}

コンパイルエラー

In function ‘int main()’:
18:13: error: ‘i’ was not declared in this scope
   cout << i << endl;
           ^

「変数のスコープ」で見たエラーと同じく、‘i’ was not declared in this scope（'i'はこのスコープで宣言されていません）というエラーが出ています。

while文で使っている変数jのスコープは6行目からmain関数の終わりまでですが、 for文の「初期化」の場所で宣言している変数iのスコープは、for文の{ }中（12行目から14行目）だけになります。

continueをしたときの動作

while文でcontinueをすると更新処理を飛ばしてしまう事があるので、注意が必要です。
例を見てみましょう。

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

int main() {

  for (int i = 0; i < 5; i++) {

    if (i == 3) {
      cout << "forとばす" << endl;
      continue;
    }

    cout << "for" << i << endl;
  }

  cout << "for終了" << endl;

  int j = 0;
  while(j < 5) {

    if (j == 3) {
      cout << "whileとばす" << endl;
      continue;
    }

    cout << "while" << j << endl;
    j++;
  }

  cout << "while終了" << endl;
}

実行結果

for0
for1
for2
forとばす
for4
for終了
while0
while1
while2
whileとばす
whileとばす
whileとばす
(無限に続く)

for文のcontinueは先に説明したとおりですが、while文では無限ループになってしまっています。
j == 3のとき、12行目のcontinue;より後を飛ばして次のループに行っていますが、よく見てみるとj++の処理も飛ばされてしまっています。
そのため、変数jの値は永遠に3のままとなり、無限ループになってしまいます。

省略したfor文

for文の「初期化」「条件式」「更新」の部分は、必要が無い場合省略できます。

次のように書いた場合、for文の動作はwhile文と完全に同じものになります。

int i = 0;
for (; i < n;) {
  i++;
}

「条件式」の部分を省略した場合、trueと書いたときと同じ動作になります。
次のプログラムは無限ループになります。

for (int i = 0; ; i++) {
  cout << i << endl;
}

{ } の省略

if文と同様に、for文やwhile文の処理が一文のみの場合も{ }を省略できます。

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

int main() {

  for (int i = 0; i < 3; i++)
    cout << "Hello!" << endl;

}

for文のネスト

if文と同様、for文とwhile文もネストさせることができます。そのような書き方は多重ループと呼ばれます。
詳しくは2.02.多重ループで説明します。

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

int main() {

  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      cout << "i: " << i << ", j:" << j << endl;
    }
  }

}

実行結果

i:0, j:0
i:0, j:1
i:1, j:0
i:1, j:1

問題

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

EX11.電卓をつくろう2

ABCの問題

ここまでの知識だけで解ける問題をAtCoder Beginner Contestから再び紹介します。練習問題だけでは物足りない人は解いてみてください。
「易しめ」と書いてあるものも今までのABCの問題よりも難易度が高いことに注意してください。
解けない場合、2.01.ループの書き方や2.02.多重ループを読んでから再挑戦してみてください。

易しめ

• B - Hina Arare
• B - Theater
• B - Harshad Number
• B - Addition and Multiplication
• B - Collecting Balls (Easy Version)

難しめ

• B - Palindromic Numbers
• B - Shift only

前のページ | 次のページ

文字列の長さ

文字列の長さ（文字数）は文字列変数.size()で取得できます。

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

int main() {
  string str = "Hello";
  cout << str.size() << endl;
}

実行結果

5

この書き方は「メンバ関数」という機能を使ったものですが、詳しくは後の章で扱います。ここではとりあえず文字列変数.size()とすると文字列の長さが取得できることを覚えておきましょう。

i番目の文字

次のように書くとi文字目が取得できます。

文字列.at(i)

このiのことを添字と言います。

添字は0から始まる

添字は0から始まることに注意しましょう。

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

int main() {
  string str = "hello";
  cout << str.at(0) << endl; // h
  cout << str.at(4) << endl; // o
}

実行結果

h
o

str.at(0)で1文字目、str.at(4)で5文字目を取得しています。

"hello"という文字列の場合、添字の値と文字の対応は次の表のとおりです。

ループのカウンタ変数を0から始めるのと同じように、添字が0から始まることにも慣れていきましょう。

文字（char型）

string型は「文字列型」ですが、「文字型」というのもあります。それはchar型です。
string型と違い、char型は一文字のデータしか保持することができません。

string型を表すために" "で囲ったように、char型を表すためには' 'で囲います。

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

int main() {
  char c = 'a';
  cout << c << endl; // a
}

実行結果

a

文字列変数.at(i)の型

文字列変数.at(i)で取得されるデータはchar型です。

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

int main() {
  string str = "Hello";

  char c = str.at(0); // char型の値が得られる

  cout << c << endl; // H
}

実行結果

H

文字列の書き換えと比較

文字列の一部を書き換えるときや比較をするときはchar型を使う必要があります。

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

int main() {
  string str = "Hello";

  str.at(0) = 'M'; // char型の'M'
  cout << str << endl; // Mello

  if (str.at(1) == 'e') {
    cout << "AtCoder" << endl;
  }
}

実行結果

Mello
AtCoder

応用

ループ構文との組み合わせ

文字列はループ構文を組み合わせることで様々な処理が記述できるようになります。
次のプログラムでは、入力された文字に何文字'O'が含まれているかを数えています。

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

int main() {
  string str;
  cin >> str;

  int count = 0;
  for (int i = 0; i < str.size(); i++) {
    if (str.at(i) == 'O') {
      count++;
    }
  }

  cout << count << endl;
}

入力

LOOOOL

実行結果

4

実行環境によっては次のような警告文が表示されることがありますが、動作には影響がないのでこれに関してはひとまず気にしなくて良いです。
warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
この警告が出る理由に関しては3.01.数値型の「符号なし整数のオーバーフロー」で説明します。

注意点

範囲外エラー

添字の値が正しい範囲内に無いと実行時エラーになります。
次のプログラムは"hello"という5文字の文字列（有効な添字の値は0～4）に対し、at(10)で存在しない文字数目にアクセスしようとしているため、実行時エラーが発生します。

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

int main() {
  string x = "hello";
  cout << x.at(10) << endl;
}

実行時エラー

terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::at: __n (which is 10) >= this->size() (which is 5)

終了コード

134

添字が範囲外のときのエラーでは、1行目の最後で'std::out_of_range'（範囲外）というエラーメッセージが表示されることが特徴です。
2行目の__n (which is 10) >= this->size() (which is 5)では、「添字の値(10) ≧ 文字列のサイズ(5)」であるためエラーが発生したということを伝えています。

全角文字の扱い

string型やchar型は全角文字を正しく扱えません。

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

int main() {
  string s = "こんにちは";
  cout << s.at(0) << endl;

  char c = 'あ';
  cout << c << endl;
}

実行結果

�
�

どちらの出力も文字化けしてしまっています。

C++で全角文字を扱う場合、string型ではない別の文字列型（u32string等）が用いられます。
しかし、それらの扱いはstring型より面倒な部分があり、この教材の目的はC++を使いこなすことではないので詳しくは説明しません。

文字列のメンバ関数や演算子を利用するとき

.size()や後述する==演算子等を利用する場合、一度変数に格納するか、"文字列"s.size()のように" "の末尾にsをつける必要があります。
単に"文字列".size()と書いた場合はコンパイルエラーになります。

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

int main() {
  string str = "Hello";
  cout << str.size() << endl; // 5
  cout << "Hello"s.size() << endl; // 5（sを末尾につける）
  cout << "Hello".size() << endl; // できない
}

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:8:19: error: request for member ‘size’ in ‘"Hello"’, which is of non-class type ‘const char [6]’
   cout << "Hello".size() << endl; // できない
                   ^

細かい話

細かい話なので、飛ばして問題を解いても良いです。

文字列の比較

string型にも数値型のような比較演算子が定義されています。

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

int main() {
  string s1 = "ABC";
  string s2 = "ABC";
  string s3 = "XY";

  if (s1 == s2) {
    cout << "ABC == ABC" << endl;
  }
  if (s1 < s3) {
    cout << "ABC < XY" << endl;
  }
}

実行結果

ABC == ABC
ABC < XY

string型に定義されている比較演算子は次の表の通りです。

「辞書順」というのは簡単に言うと「辞書に載っている順番」のことです。
上の例ではs1 = "ABC"はs3 = "XY"よりも先に載っているので、s1 < s3 == trueとなります。

ただし、C++の順序では'0'～'9'→'A'～'Z'→'a'～'z'の順になっていることに注意しましょう。
つまり、"012"s < "ABC"s == trueであり"ABC"s < "xyz"s == trueです。

「辞書順」の定義について詳しく知りたい人はABC007 B - 辞書式順序の問題文を参照してください。

文字列の連結

+演算子を使うと文字列同士を連結できます。+=を使うこともできます。

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

int main() {
  string hello = "Hello";

  // +演算子による連結
  cout << hello + ", world!" << endl; // Hello, world!

  // +=演算子による連結
  hello += ", AtCoder!";
  cout << hello << endl; // Hello, AtCoder!
}

実行結果

Hello, world!
Hello, AtCoder!

ただし、数値型のように-,*,/,%はできないので注意しましょう。

stringとcharの比較

string型とchar型は==で比較できません。

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

int main() {
  string str = "a";
  char c = 'a';
  bool b = str == c; // できない
}

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:7:16: error: no match for ‘operator==’ (operand types are ‘std::string {aka std::basic_string<char>}’ and ‘char’)
   bool b = str == c; // できない
                ^
この後延々とエラー文が続く...

文字列と文字の連結

string型とchar型を+すると、文字列同士と同様に連結できます。

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

int main() {
  string str = "Hello";

  char c = str.at(0);
  cout << str + c << endl; // HelloH
}

実行結果

HelloH

char型の変数への入力

char型の変数にcinで入力すると一文字ずつ取り出すことができます。

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

int main() {
  char a, b;
  cin >> a >> b;

  cout << a << endl;
  cout << b << endl;
}

入力

OK

実行結果

O
K

エスケープシーケンス

「改行」などの特殊な文字をプログラム中で表現する場合、エスケープシーケンスを利用します。
次のプログラムでは改行を表すエスケープシーケンスである\nを使い、こんにちはとAtCoderの間で改行して出力をしています。

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

int main() {
  cout << "こんにちは\nAtCoder";
}

実行結果

こんにちは
AtCoder

基本的には\nだけ覚えておけば良いですが、他にも代表的なエスケープシーケンスとして以下のものがあります。

行単位での入力

cinを使うと空白や改行区切りの入力を簡単に扱えますが、空白で区切らずに行単位で入力を受け取りたいこともあります。
その場合はgetlineを使います。

次のプログラムは2行の入力を行単位で受け取っています。

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

int main() {
  string s, t;
  getline(cin, s); // 変数sで入力を一行受け取る
  getline(cin, t); // 変数tで入力を一行受け取る

  cout << "一行目 " << s << endl;
  cout << "二行目 " << t << endl;
}

入力

I have a pen.
I have an apple.

実行結果

一行目 I have a pen.
二行目 I have an apple.

getline関数は次の形式で利用します。

getline(cin, 文字列変数);

この書き方は「関数」という機能を使ったものです。詳しくは1.14.STLの関数で扱います。

問題

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

EX12.足したり引いたり

ABCの問題

ここまで学んだ内容だけで、おそらく全てのAtCoder Beginner ContestのA問題を解くことができます。
その中から文字列を扱う問題を一部紹介します。

• A - 居合を終え、青い絵を覆う / UOIAUAI
• A - AtCoder *** Contest
• A - Addition and Subtraction Easy
• A - 添字
• A - お茶
• A - 複数形
• A - 高橋くんの研修
• A - ハンドルネーム

文字列の知識があれば解けるB問題も紹介します。こちらは難易度が高めなので、 解けない場合は2.01.ループの書き方や2.02.多重ループを読んでから再挑戦してみてください。なお、この問題は1.13.配列の知識があると少し解きやすくなります。

• B - Minesweeper

前のページ | 次のページ

配列変数の宣言

配列変数は次の形式で宣言します。

vector<型> 配列変数名;

vector<int> vec;と書いた場合、int型のデータ列を扱う配列変数vecが宣言されます。

配列変数への代入

配列変数に値を代入する方法はいくつかありますが、その一つが次の形式です。

配列変数 = { 要素1, 要素2, ... };

配列が持つデータの1つ1つのことを要素と呼びます。

vec = { 25, 100, 64 };と書いた場合、「25, 100, 64」というデータ列が配列変数vecに代入されています。

i番目の要素

文字列と同様に、配列も.at(i)を使ってi番目の要素へアクセスできます。

配列変数.at(i)

配列でも添字は0から始まります。

vector<int> vec = {25, 100, 64};という配列変数vecの場合、添字の値と文字の対応は次の表のとおりです。

配列の要素数

文字列と同様に、配列も.size()を使って要素数（長さ）を取得できます。

配列変数.size()

vector<int> vec = {25, 100, 64};という配列変数vecの場合、vec.size()の値は3になります。

配列と変数

配列は「複数の変数を一度に宣言する方法」のように使うことができます。

次のプログラムは、3つの整数を入力から受け取り、それらの合計を出力します。

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

int main() {
  int a1, a2, a3;
  cin >> a1 >> a2 >> a3;

  cout << a1 + a2 + a3 << endl;
}

次のプログラムは上のプログラムとほとんど同じ意味です。

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

int main() {
  // 3個の入力を受け取れるように 3要素の配列 {0, 0, 0} で初期化
  vector<int> vec(3);

  // atを使って1つずつ入力
  cin >> vec.at(0) >> vec.at(1) >> vec.at(2);

  // 和を出力
  cout << vec.at(0) + vec.at(1) + vec.at(2) << endl;
}

配列の初期化

次のように書くと、指定した要素数で配列を初期化できます。

vector<型> 配列名(要素数);

vector<int> vec(3);はvector<int> vec = {0, 0, 0}とほとんど同じ意味です。

vector<int>の場合は全ての要素が0で初期化されます。
どんな値で初期化されるかは型によって変わります。例えばvector<string> vec(3)と書いた場合、空の文字列の配列{"", "", ""}で初期化されます。

配列変数への入力

配列変数で入力を受け取るには、十分な大きさで配列を初期化した後、.at(i)を使って一つずつ受け取っていく必要があります。

// 3個の入力を受け取れるように 3要素の配列 {0, 0, 0} で初期化
vector<int> vec(3);

// atを使って1つずつ入力
cin >> vec.at(0) >> vec.at(1) >> vec.at(2);

for文を使った入力

入力を配列変数で受け取る場合、for文を使って入力処理を書くのが一般的です。

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

int main() {
  // 100要素の配列で初期化
  vector<int> vec(100);

  // 100個の入力を受け取る
  for (int i = 0; i < 100; i++) {
    cin >> vec.at(i);
  }

}

入力の個数が多いときでも、for文を使えば簡潔に入力処理を書くことができます。

配列の使い所

配列とfor文を組み合わせると、大量のデータを扱うプログラムを書くことができます。
次の例題を見て下さい。

例題

N人の数学と英語のテストの点数が与えられます。
それぞれの人について、数学と英語の点数の合計点を計算してください。

制約

0≦N≦1000

入力

N
1人目の数学の点数 2人目の数学の点数 ... N人目の数学の点数
1人目の英語の点数 2人目の英語の点数 ... N人目の英語の点数

出力

1人目の数学と英語の合計点
2人目の数学と英語の合計点
\vdots
N人目の数学と英語の合計点

入力例

3
20 100 30
100 5 40

出力例

120
105
70

解答例

Nが小さい場合、配列を使わずにint型の変数だけでこの問題を解くことも可能です。
しかし、Nが大きい場合は配列を使わずに書くのは非常に大変になります。
例えばN=1000だったとき、変数を1000個宣言しなければなりません。

配列とfor文を使えば、Nの大きさに関わらず簡潔に処理を書くことができます。

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

int main() {
  int N;
  cin >> N;

  vector<int> math(N); // N個の数学の点数データ
  vector<int> english(N); // N個の英語の点数データ

  // 数学の点数データを受け取る
  for (int i = 0; i < N; i++) {
    cin >> math.at(i);
  }

  // 英語の点数データを受け取る
  for (int i = 0; i < N; i++) {
    cin >> english.at(i);
  }

  // 合計点を出力
  for (int i = 0; i < N; i++) {
    cout << math.at(i) + english.at(i) << endl;
  }
}

その他の機能

初期値の指定

次のように書くと、配列の各要素の初期値を指定できます。

vector<型> 配列名(要素数, 初期値);

例えばvector<int> vec(3, 5);と書いた場合、配列変数vecは{5, 5, 5}で初期化されます。

要素の追加

配列は文字列のように+=で要素を追加することはできません。
代わりに配列変数.push_backを使えば、配列の末尾に要素を追加することができます。

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

int main() {
  vector<int> vec = { 1, 2, 3 };

  vec.push_back(10); // 末尾に10を追加

  // vecの全要素を出力
  for (int i = 0; i < vec.size(); i++) {
    cout << vec.at(i) << endl;
  }
}

実行結果

1
2
3
10

push_backの後の配列変数vecは次の表の通りになっています。

注意点

範囲外エラー

文字列と同様に、配列も添字の値が正しい範囲内に無いと実行時エラーになります。

次のプログラムは{ 1, 2, 3 }という3要素の配列（有効な添字の値は0～2）に対し、vec.at(10)で存在しない要素にアクセスしようとしているため、実行時エラーが発生します。

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

int main() {
  vector<int> vec = { 1, 2, 3 };
  cout << vec.at(10) << endl;
}

実行時エラー

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 10) >= this->size() (which is 3)

終了コード

134

文字列と同様に、1行目の最後で'std::out_of_range'（範囲外）というエラーメッセージが表示されます。
2行目の__n (which is 10) >= this->size() (which is 3)では、「添字の値(10) ≧ 配列のサイズ(3)」であるためエラーが発生したということを伝えています。

細かい話

細かい話なので、飛ばして問題を解いても良いです。

vector以外の配列

C++にはvector以外にも配列の書き方があります。次の3つの配列の書き方はほとんど同じ意味です。

vector<int> data(3); // vectorによる配列
int data[3]; // Cの配列
array<int, 3> data; // arrayによる配列

他の人のソースコードを見ると、2つ目の書き方をよく見かけるかもしれません。
しかし、この書き方で宣言した配列は多くの落とし穴があります。基本的にはvectorによる配列を使った方が良いです。

APG4bではvectorによる配列の使用を推奨していますが、AtCoderのコンテストの模範解答ではCの配列が使われることもあります。コンテストに参加する人はどちらも読めるようにしておくと良いでしょう。

atを使わないi番目の要素へのアクセス

今まで配列の要素を指定するときは配列変数.at(添字)と書いてきましたが、配列変数[添字]でも同じことができます。
ただし、この書き方は範囲外の添字を指定してしまったときにエラーメッセージを表示してくれず、何が原因でプログラムが正しく動いていないのかがわかりにくいので、配列変数.at(添字)の書き方を使うようにしましょう。

次のプログラムは、配列{ 1, 2, 3 }の最初の要素に2つの方法でアクセスしています。

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

int main() {
  vector<int> vec = { 1, 2, 3 };

  cout << vec.at(0) << endl;
  cout << vec[0] << endl; // .at(0)と同じ
}

実行結果

1
1

安全に[]でi番目の要素へのアクセスする方法

ABC/ARCで他の人の提出を見ると[]を使っている人が多いです。これは[]のほうが短くて読み書きしやすい、または最初に[]を学んで慣れているという理由からです。
先に述べたとおり[]はエラーが発見しにくいですが、#define _GLIBCXX_DEBUGとコードの最初に書くことで.atと同程度に安全に使うことができるようになります。

2021/11/10追記　注意：_GLIBCXX_DEBUGを使用することで、後に登場するpriority_queueなど、一部の処理の実行速度が遅くなってしまうことが確認されています。使用の際はご注意ください。

次のプログラムは{ 1, 2, 3 }という3要素の配列（有効な添字の値は0～2）に対し、vec[10]で存在しない要素にアクセスしようとしているため、実行時エラーが発生します。

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

int main() {
  vector<int> vec = { 1, 2, 3 }; 
  cout << vec[10] << endl; // 実行時エラーが起きる
}

実行時エラー

/usr/include/c++/5/debug/vector:409:
Error: attempt to subscript container with out-of-bounds index 10, but 
container only holds 3 elements.

Objects involved in the operation:
    sequence "this" @ 0x0x401350 {
      type = 

Error: attempt to subscript container with out-of-bounds index 10, but container only holds 3 elements.で3要素の配列に対して境界外の添字10でアクセスしようとしたことを表しています。

.at()を使うか#define _GLIBCXX_DEBUG＋[]を使うかは好みですが、APG4bでは.at()を統一して使用します。

#define _GLIBCXX_DEBUGはGCC特有の機能です。Clang環境では代わりに#define _LIBCPP_DEBUG 0と書く必要があります。

要素の削除

配列変数.pop_backを使えば配列の末尾の要素を削除することもできます。

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

int main() {
  vector<int> vec = { 1, 2, 3 };

  vec.pop_back(); // 末尾の要素を削除

  // vecの全要素を出力
  for (int i = 0; i < vec.size(); i++) {
    cout << vec.at(i) << endl;
  }
}

実行結果

1
2

pop_backの後の配列変数vecは次の表の通りになっています。

配列同士の比較

配列変数同士は==で比較することができます。
==では2つの配列の全要素が一致していたとき、条件式は真になります。

ただし、比較する際はどちらも「配列変数」である必要があり、vec == { 1, 2, 3 }のようには書けないことに注意しましょう。

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

int main() {
  vector<int> vec1 = { 1, 2, 3 };
  vector<int> vec2 = { 1, 2, 3 };

  if (vec1 == vec2) {
    cout << "OK" << endl;
  }

  /*
  ↓これはコンパイルエラーになる
  if (vec1 == { 1, 2, 3 }) {
    cout << "NG" << endl;
  }
  */
}

配列の初期化その2

配列の初期化は次のように書くこともできます。

vector<型> 配列変数 = vector<型>(要素数, 初期値);

この書き方はすでに宣言してある配列変数を上書きするときにも使えます。 次の例では{10, 10, 10}で初期化してある変数を100要素の配列{2, 2, ... , 2, 2}で上書きしています。

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

int main() {
  vector<int> vec(3, 10); // {10, 10, 10} で初期化
  vec = vector<int>(100, 2); // 100要素の配列 {2, 2, ... , 2, 2} で上書き
  cout << vec.at(99) << endl;
}

実行結果

2

大きすぎる配列

配列の要素数が多すぎると、実行時エラーになることがあります。
次の例は要素数が10億の配列を確保しようとして実行時エラーが発生しています。

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

int main() {
  vector<int> v(1000000000);
  cout << v[0] << endl;
}

終了コード

134

どの程度までの大きさの配列が確保できるかは実行環境によります。

AtCoderの問題の回答として提出してこのエラーが出た場合、REまたはMLEと表示されます。

問題

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

EX13.平均点との差

ABCの問題

ここまでの知識だけで解ける問題をAtCoder Beginner Contestから再び紹介します。練習問題だけでは物足りない人は解いてみてください。
「易しめ」と書いてあるものも今までのABCの問題よりも難易度が高いことに注意してください。
解けない場合、2.01.ループの書き方や2.02.多重ループを読んでから再挑戦してみてください。

易しめ

• B - Picture Frame
• B - Counting Roads
• B - Trained?

難しめ

• B - Two Colors Card Game
• B - Card Game for Two
• B - Kagami Mochi

配列とループ構文がわかっていれば、AtCoderのコンテストに参加するのに最低限の知識を持っていると言えます。
ぜひリアルタイムでコンテストに挑戦してみてください。

前のページ | 次のページ

関数の使い方

「2つの変数の値のうち小さい方を出力するプログラム」を例として見てみましょう。

関数を使わないで書く場合、次のようになります。

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

int main() {
    int a = 10, b = 5;

    int answer;
    if (a < b) {
        answer = a;
    }
    else {
        answer = b;
    }

    cout << answer << endl;
}

実行結果

5

「min関数」を使えば次のように書くことができます。

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

int main() {
    int a = 10, b = 5;

    int answer = min(a, b); // min関数

    cout << answer << endl;
}

実行結果

5

プログラム中で出てくるminは2つの値のうち小さい方を求める関数です。
min(a, b)の「計算結果」としてaとbの小さい方の値が取得できるので、それを変数answerに代入しています。

STLとは

C++ではminの他にも様々な関数が用意されており、多くの機能を自分でプログラムを書くこと無く利用できます。
C++で用意されている、関数等がまとまっているもののことをSTL (Standard Template Library)といいます。

関数を自分で作る事もできます。それについては「1.15.関数」で説明します。

関数の呼び出し方

関数を使うことを関数呼び出しと言います。

関数呼び出しの記法は以下のとおりです。

関数名(引数1, 引数2, ...)

引数(ひきすう)とは、関数に渡す値のことです。min(a, b)では変数aと変数bがそれに当たります。
min関数では2つの引数がありましたが、引数の数は関数によって異なります。

関数の計算結果の値のことを返り値（かえりち）または戻り値（もどりち）と言います。
int answer = min(a, b);ではmin関数の返り値を変数answerに代入しています。

引数と返り値の型

引数と返り値は関数によって型のルールが決まっており、間違うとコンパイルエラーになります。

次のプログラムは、min関数の引数にint型とstring型を渡そうとして、コンパイルエラーが発生しています。

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

int main() {
    string s = "hello";

    int a = min(10, s); // min関数にint型とstring型のペアは渡せない

    cout << a << endl;
}

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:7:22: error: no matching function for call to ‘min(int, std::string&)’
     int a = min(10, s); // min関数にint型とstring型のペアは渡せない
                      ^
（この後長々とエラー文が続く）

STLの関数の使い方を間違えると、非常に長いコンパイルエラー文が出ることがあります。

関数の例

STLの関数の中から3つの関数を紹介します。
これらを暗記しておく必要はありませんが、「この処理はSTLの関数でできた気がする」と思い出して調べられることが大切です。

min関数

min関数は、2つの引数のうち小さい方の値を返します。

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

int main() {
    int answer = min(10, 5);

    cout << answer << endl; // 5
}

実行結果

5

引数と返り値の型

引数と返り値の型はintやdoubleのような数値型(または大小比較が出きる型)ならなんでも良いです。

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

int main() {
    double answer = min(1.5, 3.1);

    cout << answer << endl; // 1.5
}

実行結果

1.5

ただし、2つの引数の型は同じである必要があります。

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

int main() {
    double a = 1.5;
    int b = 10;
    int answer = min(a, b); // 引数の型がdouble型とint型なのでエラーになる
}

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:7:26: error: no matching function for call to ‘min(double&, int&)’
     int answer = min(a, b); // 引数の型がdouble型とint型なのでエラーになる
                          ^
（この後長々とエラー文が続く）

max関数

max関数は、2つの引数のうち大きい方の値を返します。

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

int main() {
    int answer = max(10, 5);

    cout << answer << endl; // 10
}

実行結果

10

引数と返り値の型

引数と返り値の型についてはminと同様です。

swap関数

swap関数は、2つの引数の値を交換します。

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

int main() {
    int a = 10, b = 5;

    swap(a, b);

    cout << a << endl; // 5
    cout << b << endl; // 10
}

実行結果

5
10

引数と返り値の型

2つの引数の型は同じである必要があります。
また、swap関数に返り値はありません。このように、返り値が無い関数もあります。

配列を引数にする関数

STLの関数の中から、配列を引数に渡す2つの関数を紹介します。
STLの関数に配列を渡す場合、少し特殊な形式で書く必要があることに注意してください。

reverse関数

reverse関数を使うと、配列の要素の並びを逆にできます。

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

int main() {
    vector<int> vec = {1, 5, 3};
    reverse(vec.begin(), vec.end()); // {3, 5, 1}

    for (int i = 0; i < vec.size(); i++) {
        cout << vec.at(i) << endl;
    }
}

実行結果

3
5
1

reverse関数は次の形式で呼び出します。

reverse(配列変数.begin(), 配列変数.end());

reverse関数に返り値はありません。

sort関数

データ列を順番に並び替えることをソートといいます。
sort関数を使うと、配列の要素を小さい順に並び替えることができます。

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

int main() {
    vector<int> vec = {2, 5, 2, 1};
    sort(vec.begin(), vec.end()); // {1, 2, 2, 5}

    for (int i = 0; i < vec.size(); i++) {
        cout << vec.at(i) << endl;
    }
}

実行結果

1
2
2
5

sort関数は次の形式で呼び出します。

sort(配列変数.begin(), 配列変数.end());

sort関数に返り値はありません。

sort関数とreverse関数の組合せ

sort関数を使ってからreverse関数を使うと、大きい順にソートできます。

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

int main() {
    vector<int> vec = {2, 5, 2, 1};
    sort(vec.begin(), vec.end()); // {1, 2, 2, 5}
    reverse(vec.begin(), vec.end()); // {5, 2, 2, 1}

    for (int i = 0; i < vec.size(); i++) {
        cout << vec.at(i) << endl;
    }
}

実行結果

5
2
2
1

ソートは様々な計算で使われる非常に重要な処理なので、使い方を覚えておきましょう。

配列を渡す形式

STLの関数に配列を渡す場合、次の形式で渡すことが多いです。

関数名(配列変数.begin(), 配列変数.end())

この記法について完全に理解するにはイテレータという機能の知識が必要ですが、それについては後の章で扱います。
とりあえず今の段階では、こう書けば関数の機能を利用できるということだけ理解しておきましょう。

細かい話

細かい話なので、飛ばして問題を解いても良いです。

引数で関数を呼び出した場合

次のプログラムのように、引数で関数を呼び出した場合は内側の関数から実行されます。

min(max(1, 2), 3)
↓
min(2, 3)
↓
2

引数の実行順序

引数の実行順序は環境によって異なります。APG4bの推奨環境である「GCC, C++」では、次のように最後の引数の式から順に実行されます。

min(1 + 1, 2 + 2)
↓
min(1 + 1, 4)
↓
min(2, 4)
↓
2

その他の環境（Clang等）では、次のように最初の引数の式から順に実行されることがあります。

min(1 + 1, 2 + 2)
↓
min(2, 2 + 2)
↓
min(2, 4)
↓
2

このことを気にする必要がある場面は少ないですが、次の節のように自分で関数を定義する場合はハマりどころになりうるので、頭の片隅においておきましょう。

問題

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

EX14.三人兄弟の身長差

ABCの問題

AtCoder Beginner Contestからソートを活用できる問題を紹介します。
次の2問は「1.13.配列」で「難しめ」として紹介したものですが、ソートを使えばもっと簡単に解くことができます。

• B - Card Game for Two
• B - Kagami Mochi

前のページ | 次のページ

関数の動作

次のスライドは上のプログラム全体の動作を説明したものです。

関数の定義

関数の定義はmain関数より前で行います。

関数定義の記法は次のとおりです。

返り値の型 関数名(引数1の型 引数1の名前, 引数2の型 引数2の名前, ...) {
  処理
}

前の節で見たとおり、引数は「関数に渡す値」、返り値は「関数の結果の値」のことです。
my_min関数はint型の引数を2つ受け取り、計算結果としてint型の値を返すので、定義は次のようになります。

int my_min(int x, int y) {
}

呼び出し方はSTLの関数と同様です。
次のように呼び出した場合、引数xに10が代入され、引数yに5が代入されます。

my_min(10, 5);

返り値の指定

関数の返り値は、return文で指定します。

return 返り値;

my_min関数では2つの引数x,yのうち小さい方を返すので、次のように書きます。

if (x < y) {
  return x;
}
else {
  return y;
}

返り値が無い関数

関数の返り値は無いこともあります。その場合は返り値の型にvoidを指定します。

次のプログラムのhello関数は、引数の文字列の始めに"Hello, "をつけて出力します。
返り値は必要ないのでvoid型を指定しています。

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

// 返り値が無いのでvoidを指定
void hello(string text) {
  cout << "Hello, " << text << endl;
  return;
}

int main() {
  hello("Tom");
  hello("C++");
}

実行結果

Hello, Tom
Hello, C++

返り値がvoid型である関数のreturn文は次のように書きます。

return;

引数が無い関数

関数の引数が不要な場合は、定義と呼び出しでは()だけを書きます。

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

// 整数の入力を受け取って返す関数
// 引数なし
int input() {
  int x;
  cin >> x;
  return x;
}

int main() {
  int num = input(); // 引数なし
  cout << num + 5 << endl;
}

入力

10

実行結果

15

関数を自分で定義する理由

関数を自分で定義する理由はいくつかありますが、その中から3つを紹介します。

1. プログラムの重複が避けられる
2. 処理のかたまりに名前をつけられる
3. 再帰関数が書ける

大規模なプログラムを書く際は1.と2.による恩恵が大きいです。
APG4bでは主に3.のために関数の紹介をしています。詳しくは「2.04.再帰」で説明します。

注意点

return文の動作

処理がreturn文の行に到達した時点で関数の処理は終了します。

一つの関数の中にreturn文が複数あっても問題ありませんが、return文より後に書いた処理は実行されないことに注意しましょう。

次のプログラムでは、"Hello, "を出力した次の行でreturn;と書いているため、その後の処理は実行されません。

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

void hello() {
  cout << "Hello, ";
  return; // この行までしか実行されない

  cout << "world!" << endl;
  return;
}

int main() {
  hello();
}

実行結果

Hello, 

返り値の指定忘れ

返り値がある関数でreturn文を忘れると、どんな値が返ってくるかは決まっていません。

次のプログラムのmy_min関数は、if文の中が実行されない場合に返り値を指定していないので、0が返ってきています。

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

int my_min(int x, int y) {

  if (x < y) {
    return x;
  }

  // x >= y のときのreturn忘れ
}

int main() {
  int answer = my_min(10, 5);
  cout << answer << endl;
}

実行結果

0

このプログラムでは0が返ってきますが、0でない値が返ってくることもあります。

返り値がある関数では、どのような引数のパターンでも必ずreturnするように注意しましょう。

引数はコピーされる

他の変数に値を代入したとき同様に、基本的に引数に渡した値はコピーされます。

次のプログラムのadd5関数は関数内で引数に5を足していますが、呼び出し元の変数numの値は変化しません。

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

// 引数の値に5を足して出力する関数
void add5(int x) {
  x += 5;
  cout << x << endl;
  return;
}

int main() {
  int num = 10;
  add5(num); // numの値は引数xにコピーされる

  cout << num << endl; // numは10のまま
}

実行結果

15
10

関数add5を呼び出す処理は次のプログラムと同じだと考えれば良いです。よくわからない人は1.04.変数と型の「変数はコピーされる」を読んでください。

int x = num; // xにnumの値10をコピー
x += 5; // xとnumは別の変数なのでnumの値は変わらない
cout << x << endl;

なお、vectorやstringを引数にした場合も同様にコピーされます。

関数が呼び出せる範囲

関数は宣言した行より後でしか呼び出せません。

次のプログラムでは、hello関数を定義した行より前でhello関数を呼び出しているため、コンパイルエラーが発生しています。

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

int main() {
  hello();
}

void hello() {
  cout << "hello!" << endl;
  return;
}

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:5:9: error: ‘hello’ was not declared in this scope
   hello();
         ^

「5:11: error: ‘hello’ was not declared in this scope（5行11文字目 エラー: 'hello'はこのスコープでは宣言されていません）」というエラー文が表示されています。
このエラーが発生した場合、コンパイルエラーが起きない順番に関数の定義を並び替えるか、後述する「プロトタイプ宣言」を利用しましょう。

細かい話

細かい話なので、飛ばして問題を解いても良いです。

プロトタイプ宣言

プロトタイプ宣言をすれば関数を定義する前に呼び出すことができます。
プロトタイプ宣言とは、「関数の名前」と「引数と返り値の型」だけを先に宣言することです。

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

// プロトタイプ宣言
void hello();

int main() {
  // プロトタイプ宣言をしたので呼び出せる
  hello();
}

void hello() {
  cout << "hello!" << endl;
  return;
}

実行結果

hello!

プロトタイプ宣言の記法は次のようになります。

返り値の型 関数名(引数1の型 引数1の名前, 引数2の型 引数2の名前, ...);

引数名の省略

引数の名前は省略することもできます。
例えば、my_min関数のプロトタイプ宣言は次のように書くこともできます。

int my_min(int, int);

returnの省略

返り値がない場合、関数の末尾ではreturnを省略できます。

void hello(string text) {
  cout << "Hello, " << text << "!" << endl;
}

main関数

はじめのプログラムから出てきていたmain関数も関数の一つです。
ただし、main関数は特別扱いされていて、returnを省略した場合は必ず0が返るようになっています。

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

int main() {
  cout << "Hello, world!" << endl;
  // return 0; と書くのと同じ
}

実行結果

Hello, world!

関数のオーバーロード

「引数の型」または「引数の数」が異なる場合は、同じ名前の関数を定義することができます。これを関数のオーバーロードと言います。
次のプログラムでは「2つの引数を取るmy_min関数」と「3つの引数を取るmy_min関数」を定義しています。

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

// 2つの引数のうち最も小さい値を返す
int my_min(int x, int y) {
  if (x < y) {
    return x;
  }
  else {
    return y;
  }
}

// 3つの引数のうち最も小さい値を返す
int my_min(int x, int y, int z) {
  if (x < y && x < z) {
    return x;
  }
  else if (y < x && y < z) {
    return y;
  }
  else {
    return z;
  }
}

int main() {
  int answer = my_min(10, 5); // 2つの引数
  cout << answer << endl; // 5

  answer = my_min(3, 2, 5); // 3つの引数
  cout << answer << endl; // 2
}

ただし、返り値の型が異なるだけではオーバーロードできないことに注意してください。

複雑な引数の条件の指定

STLのmin関数は、引数としてint型でもdouble型でも指定できます。
これと似た挙動は関数のオーバーロードでも再現できますが、STLのmin関数は関数のオーバーロードではなく後の章で説明するテンプレートという機能を使って実装されています。
テンプレートを用いると、引数の条件として「大小比較ができる型なら何でも良い」などの複雑なものを指定できます。

変数のスコープ

関数内の変数のスコープは、呼び出し元とは完全に分けられています。

次のプログラムでは、test関数とmain関数の両方でnumという名前の変数を定義していますが、その2つは完全に別の変数として扱われます。

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

void test() {

  // test関数のスコープで変数numを宣言
  int num = 5;
  cout << num << endl; // 5

  return;
}

int main() {
  // main関数のスコープで変数numを宣言
  int num = 10; 
  test();
  cout << num << endl; // 10
}

実行結果

5
10

2章の内容の紹介

2章で扱う内容で、関数と関わりが深いものについて2つだけ簡単に紹介します。

飛ばして問題を解いても良いです。読む場合も、今はしっかりと理解する必要はありません。

参照

引数の値をコピーさせないようにすることもできます。
その場合は参照という機能を引数で利用します。これについては2.04.参照で詳しく説明します。

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

// 型に&をつけると参照になる
void change(int &n, vector<int> &vec) {
  n = 1;
  vec.at(0) = 1;
  return;
}

int main() {
  int x = 5;
  vector<int> v = {10, 10, 10};

  change(x, v);

  cout << x << endl;
  cout << v.at(0) << endl;
}

実行結果

1
1

再帰関数

関数の中で同じ関数を呼び出すこともできます。
このような関数を再帰関数と言います。これについては2.05.再帰で詳しく説明します。

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

// 0からnまでの和を求める関数sum
int sum(int n) {
  if (n == 0) {
    return 0;
  }
  return n + sum(n - 1);
}

int main() {
  cout << sum(3) << endl;
}

実行結果

6

問題

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

EX15.三人兄弟へのプレゼント

前のページ | 次のページ

例題

整数aと5個の整数x_1, x_2, x_3, x_4, x_5が与えられます。
5個の整数のうちaと等しいものの個数をfor文を使って求めてください。

入力

a
x_1 x_2 x_3 x_4 x_5

出力

aと等しいものの個数

入力例

3
1 3 2 5 3

出力例

2

次のプログラムを元に説明していきます。

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

int main() {
  int a;
  cin >> a;
  vector<int> data(5);
  for (int i = 0; i < 5; i++) {
    cin >> data.at(i);
  }

  // ここにプログラムを追記
}

解答例

まずはループを使わないでプログラムを書きます。

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

int main() {
  int a;
  cin >> a;
  vector<int> data(5);
  for (int i = 0; i < 5; i++) {
    cin >> data.at(i);
  }

  // 答えを保持する変数
  int answer = 0;

  if (data.at(0) == a) {
    answer++;
  }

  if (data.at(1) == a) {
    answer++;
  }

  if (data.at(2) == a) {
    answer++;
  }

  if (data.at(3) == a) {
    answer++;
  }

  if (data.at(4) == a) {
    answer++;
  }

  cout << answer << endl;
}

ループで書けそうなパターンが見つからないか探してみると、次のパターンが続いていることがわかります。

if (data.at(数値) == a) {
  answer++;
}

これを元に、ループを使って書き直してみましょう。

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

int main() {
  int a;
  cin >> a;
  vector<int> data(5);
  for (int i = 0; i < 5; i++) {
    cin >> data.at(i);
  }

  // 答えを保持する変数
  int answer = 0;

  for (int i = 0; i < 5; i++) {

    if (data.at(i) == a) {
      answer++;
    }

  }

  cout << answer << endl;
}

入力

3
1 3 2 5 3

実行結果

2

範囲for文

配列の全ての要素に対して何かしらの処理を行ないたいとき、for文を用いて書くことができました。

例えば「配列の全ての要素を出力する」処理は次のように書くことができます。

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

int main() {
  vector<int> a = {1, 3, 2, 5};
  for (int i = 0; i < a.size(); i++) {
    cout << a.at(i) << endl;
  }
}

実行結果

1
3
2
5

C++には配列の要素に対する処理を簡潔に書くことができる範囲for文という構文が用意されています。

範囲for文を用いると上のプログラムは次のように書き直せます。

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

int main() {
  vector<int> a = {1, 3, 2, 5};
  for (int x : a) {
    cout << x << endl;
  }
}

実行結果

1
3
2
5

この例では、「配列変数aから要素を1つ取り出してxという変数にコピー→xの値を出力→次の要素をxにコピー→xの値を出力→…」 のように動作します。すべての要素を取り出し終わるとループを抜けます。

範囲for文は基本的に次の構文です。

for (配列の要素の型 変数名 : 配列変数) {
  // 各要素に対する処理
}

全ての要素を取り出し終わるとループを抜けます。

範囲for文でも、for文・while文と同様にbreakやcontinueを使うことができます。
いずれもfor文・while文のときと同じ動作(breakでループを抜け、continueで次のループまで処理をスキップ)をします。

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

int main() {
  vector<int> a = {1, 3, 1, 2, 5, 10};
  for (int x : a) {
    if (x == 1) {
      continue;
    }

    if (x == 5) {
      break;
    }

    cout << x << endl;
  }
}

実行結果

3
2

範囲for文はコンテナと呼ばれるデータ型に対して使うことができます。
配列はコンテナの一種です。 その他にも文字列型(string型)はコンテナの一種なので、範囲for文を用いることができます。
string型の変数に対して、1文字ずつ処理したい場合に便利です。

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

int main() {
  string str = "hello";
  for (char c : str) {
    if (c == 'l') {
      c = 'L';
    }
    cout << c;
  }
  cout << endl;
}

実行結果

heLLo

細かい話

ループ構文の使い分け

ループ構文には1.10で扱ったwhile文、1.11で扱ったfor文、今回紹介した範囲for文がありますが、どのように使い分ければ良いのでしょうか。

for文は1.11で見たように「N回処理する」というようなパターンをwhile文より短く書くための構文でした。 今回紹介した範囲for文は配列に対する処理をfor文よりも簡潔に書くための構文でした。 よって、以下のように使い分けると良いでしょう。

• 配列の全ての要素に対する処理を行なう場合 → 範囲for文
• それ以外で一定回数繰り返し処理する場合 → for文
• それ以外の場合 → while文

ただし、例えば配列の要素に対する処理でも、範囲for文を用いるよりもfor文やwhile文を用いた方が簡潔に書ける場合もあるので、 必ずしも上のように使い分ける必要はありません。

while文が適しているケース

「整数Nがあるとき、Nが2で最大で何回割り切れるかを求める」という処理を考えます。 この処理は配列の要素に対する処理ではありませんし、具体的に何回処理を繰り返せば良いのかということも分かりません。 この処理にはwhile文が適しているでしょう。

次のサンプルプログラムは、入力で与えられた整数Nが2で割り切れる回数を出力するプログラムです。

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

int main() {
  int N;
  cin >> N;

  int count = 0;
  while (N > 0) {
    // 2で割り切れなければループを抜ける
    if (N % 2 > 0) {
      break;
    }
    N = N / 2;
    count++;
  }
  cout << count << endl;
}

入力1

8

実行結果1

3

入力2

5

実行結果1

0

問題

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

EX16.隣り合う同じ値を探す

前のページ | 次のページ

多重ループのbreak/continue

for文やwhile文にはbreak/continueという命令がありました。多重ループはループ文の中にループ文を入れた物なので、 通常のfor文と同様にbreak/continue命令を使うことができます。
多重ループでbreak命令を使うと1段階ループを抜けることができます。 内側のループの中でbreakすると内側のループを抜けることができますが、このbreakによって外側のループを抜けることはできません。

  for (int i = 0; i < ... ; i++) {  // ループ1
    for (int j = 0; j < ... ; j++) {  // ループ2
      if (/* 条件 */) {
        break;  // (＊)
      }
    }
    // (＊)のbreakでループ2を抜けてここに来る
  }
  // (＊)のbreakでループ1を抜けてここに来ることはできない

多重ループを抜けるときは、ループを抜けるかどうかを持つ変数(フラグ変数)を用意して、フラグ変数の値に応じてループを抜けるように書きます。

処理の大まかな流れは次の通りです。

  bool finished = false;  // 外側のループを抜ける条件を満たしているかどうか(フラグ変数)

  for (int i = 0; i < ... ; i++) {
    for (int j = 0; j < ... ; j++) {

      /* 処理 */

      if (/* 2重ループを抜ける条件 */) {
        finished = true;
        break;  // (＊)
        // finishをtrueにしてからbreakすることで、
        //   内側のループを抜けたすぐ後に外側のループも抜けることができる
      }
    }
    // (＊)のbreakでここに来る

    if (finished) {
      break;  // (＊＊)
    }
  }
  // (＊＊)のbreakでここに来る

例

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

int main() {
  int sum = 0;
  bool finished = false;

  for (int i = 0; i < 10 ; i++) {
    for (int j = 0; j < 10 ; j++) {

      sum += i * j;

      if (sum > 1000) {
        cout << i << ", " << j << endl;
        finished = true;
        break;
      }
    }

    if (finished) {
      break;
    }
  }

  cout << sum << endl;
}

7, 4
1015

他の方法

多重ループの部分を関数化し、関数の内部で使えるreturnを使って一気に抜けるという方法もあります。

void func( /* 処理に必要な変数 */ ) {
  for (int i = 0; i < ... ; i++) {
    for (int j = 0; j < ... ; j++) {

      /* 処理 */

      if (/* 2重ループを抜ける条件 */) {
        return;  // 関数のreturnはループに関係なく抜けることができる
      }
    }
  }
}

int main() {
  func();
}

この方法ではループ内の処理を行なうために必要な変数を引数で渡す必要があり、 余計な処理が必要になることがあるので、基本的にはフラグ変数を用意する方針で処理するようにしましょう。

例

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

void func() {
  int sum = 0;
  for (int i = 0; i < 10 ; i++) {
    for (int j = 0; j < 10 ; j++) {

      sum += i * j;

      if (sum > 1000) {
        cout << i << ", " << j << endl;
        cout << sum << endl;
        return;
      }
    }
  }
}
int main() {
  func();
}

7, 4
1015

注意点

添え字のミス

多重ループを書いているときによくあるミスにforの中の添字ミスがあります。
次のプログラムのどこにミスがあるか考えてみてください。

for (int i = 0; i < 3; i++) {
  for (int j = 0; j < 3; i++) {
    cout << "i: " << i << ", j: " << j << endl;
  }
}

正解は内側のループの更新処理の部分です。j++とするべきところをi++としてしまっています。

  for (int j = 0; j < 3; i++) {

正しくは

  for (int j = 0; j < 3; j++) {

添字のミスは発生しやすく、ミスをした時も発見しにくい(コンパイルエラーにならない)ので、気をつけましょう。

多重ループ中のカウンタ変数の名前はi, j, k, l...としていくのが一般的なのでここでもそうしています。しかし、「iとjは形が似ていて間違えやすい」「名前から意図が伝わりにくい」という意見もあります。
もしカウンタ変数に明確な意味がある場合は、i, j, k, l...にこだわらず、自由に名前を付けるのも良いでしょう。

問題

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

EX17.果物屋さんでお買い物

前のページ | 次のページ

例題

縦3行、横4列の整数が書かれた表があります。この表に何個の0が含まれているかを求めてください。

表の例を次に示します。

入力

7 4 0 8
2 0 3 5
6 1 7 0

実行結果

3

このようなデータの表を2次元配列で扱うときは次のように書けます。

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

int main() {

  // int型の2次元配列(3×4要素の)の宣言
  vector<vector<int>> data(3, vector<int>(4));

  // 入力 (2重ループを用いる)
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 4; j++) {
      cin >> data.at(i).at(j);
    }
  }

  // 0の個数を数える
  int count = 0;

  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 4; j++) {

      // 上からi番目、左からj番目の画素が0かを判定
      if (data.at(i).at(j) == 0) {
        count++;
      }

    }
  }

   cout << count << endl;

}

宣言

2次元配列の宣言は次の形式になります。

vector<vector<要素の型>> 変数名(要素数1, vector<要素の型>(要素数2, 初期値));
vector<vector<要素の型>> 変数名(要素数1, vector<要素の型>(要素数2));  // 初期値を省略

初期値は省略することができます。省略した場合は「要素の型」に対応するゼロ値で初期化されます。
例えば要素の型がintなら、初期値は0で、stringなら空文字列("")です。

表のようなデータを扱う場合、一般的には次のようにします。

vector<vector<要素の型>> 変数名(縦の要素数, vector<要素の型>(横の要素数));

例題で扱ったデータは、

• 要素が整数
• 縦に3行
• 横に4列

の表であるため、次のように宣言しています。

vector<vector<int>> data(3, vector<int>(4));

アクセス

2次元配列の要素にアクセスする場合は次のように書きます。

変数名.at(添字1).at(添字2)

宣言時にvector<vector<要素の型>> 変数名(縦の要素数, vector<型>(横の要素数))としている場合、より具体的には次のようになります。

変数名.at(上から何番目か).at(左から何番目か)

例題では、入力の部分で「上からi番目、左からj番目」の要素に入力するため、

cin >> data.at(i).at(j)

と書いています。
また、上からi番目、左からj番目のマスが0かどうかを判定するため、

if (data.at(i).at(j) == 0)

と書いています。

大きさの取得

vector<vector<int>> data(3, vector<int>(4));

data.size();  // 3 (縦の要素数) (12ではないことに注意!)
data.at(0).size();  // 4 (横の要素数)

縦の要素数を取得するには変数名.size()として、横の要素数を取得するには変数名.at(0).size()とします。

変数名.size()とした時に、すべての要素の個数ではなく縦の要素数が返ってくることに注意してください。
すべての要素数が必要なときは縦の要素数 * 横の要素数で求める必要があります。

2次元配列の考え方

説明のために、これまで扱ってきた通常の配列を"1次元配列"と呼ぶことにします。

ここで、1次元配列の復習をします。"要素数"個の"初期値"からなる配列は次のように宣言しました。(1.13 配列の細かい話を参照)

vector<要素の型> 変数名(要素数, 初期値);

2次元配列は「"1次元配列"の配列」と考えると分かりやすいと思います。

2次元配列の宣言の考え方

1次元配列を表す型はvector<要素の型>でした。
2次元配列を表す型は、「"1次元配列"の配列」なのでvector<vector<要素の型>>となります。("外側の配列の要素の型"が1次元配列を表す型になっています。)
また、2次元配列の"初期値"は"1次元配列"なのでvector<vector<要素の型>> 変数名(要素数1, 初期値)の"初期値"の部分にはvector<要素の型>(要素数2))を指定します。("要素数2"個の要素から成る1次元配列です。)

要素へのアクセスは次のように考えられます。

変数名.at(i)  // i番目の1次元配列
変数名.at(i).at(j)  // i番目の1次元配列 のj番目の要素

2次元配列の添字を「上から何番目か」と「左から何番目か」で表すことが直感的に感じられない人もいると思いますが、慣れましょう。たて×よこ と覚えると良いです。
例題の入力と配列の添字は次の表のように対応しています

このデータが入力されたとき、以下の要素が何になっているかを考えてみてください。

• data.at(0).at(1)
• data.at(1).at(3)
• data.at(2).at(2)

答え

• data.at(0).at(1) → 4 (0番目の1次元配列 の1番目の要素)
  0番目の1次元配列は {7, 4, 0, 8} です。

• data.at(1).at(3) → 5 (1番目の1次元配列 の3番目の要素)
  1番目の1次元配列は {2, 0, 3, 5} です。

• data.at(2).at(2) → 7 (2番目の1次元配列 の2番目の要素)
  2番目の1次元配列は {6, 1, 7, 0} です。

N×0の二次元配列

後から配列に要素を追加して使う場合などに、N×0の配列を宣言することがあります。

以下のように書くと、N×0の二次元配列になります。

vector<vector<型>> 変数名(N);  // 「要素数0の配列」の配列

外側のvectorの初期値を省略することで、N個の配列の要素数はそれぞれ0になります。

長方形にならない二次元配列(ジャグ配列)

N×0の二次元配列に後から要素を追加していく場合などに「行毎に要素数の違う二次元配列」ができることがあります。
このような配列はジャグ配列と呼ばれることがあります。

具体例

以下のdataはジャグ配列の例です。

vector<vector<int>> data(3);  // 3×0の配列

data.at(0).push_back(1);
data.at(0).push_back(2);
data.at(0).push_back(3);
// data.at(0)は3要素の配列

data.at(1).push_back(4);
data.at(1).push_back(5);
data.at(1).push_back(6);
data.at(1).push_back(7);
// data.at(1)は4要素の配列

data.at(2).push_back(8);
data.at(2).push_back(9);
// data.at(2)は2要素の配列

dataのイメージを以下に示します。

多次元配列

2次元配列をさらに拡張して、3次元配列や4次元配列といったより高次元の配列を作ることもできます。
1次元より次元の大きい配列をまとめて多次元配列と呼びます。

3次元配列を使った例を見てみましょう。

例題

まるばつゲームの状態がN個与えられます。マルは'o'、バツは'x'、空白は'-'で表されます。すべての状態の'o'の個数の和を求めてください。

1つ目の状態

2つ目の状態

入力

2
- - -
- x -
- o -

x o -
- o -
x - -

実行結果

3

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

int main() {
  int N;
  cin >> N;
  // N × (3 × 3)要素の配列を宣言
  vector<vector<vector<char>>> data(N, vector<vector<char>>(3, vector<char>(3)));

  // 入力
  for (int i = 0; i < N; i++) {
    // i番目の状態を読む
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {
        cin >> data.at(i).at(j).at(k);
      }
    }
  }

  // 'o'の数を数える
  int count = 0;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {

        // 「i番目の状態」「上からj番目」「左からk番目」の要素が'o'か判定
        if (data.at(i).at(j).at(k) == 'o') {
          count++;
        }

      }
    }
  }

   cout << count << endl;
}

3次元以上の配列も2次元配列とほとんど変わりません。

宣言

3次元配列の場合の宣言方法を次に示します。

vector<vector<vector<要素の型>>> 変数名(要素数1, vector<vector<要素の型>>(要素数2, vector<要素の型>(要素数3, 初期値)));
vector<vector<vector<要素の型>>> 変数名(要素数1, vector<vector<要素の型>>(要素数2, vector<要素の型>(要素数3)));  // 初期値を省略

ギョッとしてしまうかもしれませんが、基本的な考え方は2次元配列のときと同じです。
3次元配列を「"2次元配列"の配列」つまり「"1次元配列の配列"の配列」と考えます。分かりやすくするために改行を入れてみます。

vector<
  vector<vector<要素の型>> /* 2次元配列の型 */
> 変数名(要素数1,
  vector<vector<要素の型>>(要素数2, vector<要素の型>(要素数3, 初期値)) /* 2次元配列の値 */
);

4次元以上の場合も同様に宣言します。N次元配列を「"N-1次元配列"の配列」と考えましょう。

アクセス

N次元配列の要素にアクセスするには次のように書きます。

変数名.at(添字1).at(添字2).at(添字3) ... .at(添字N)

.at(添字)をN回繰り返します。

注意点

多次元配列を扱う際の基本的な注意点は1次元配列と同様です。

多次元配列ではさらに、添字の順番に注意しましょう。
また、変数名.size()では1次元目の要素数が取得できますが、すべての要素の個数が取得できる訳ではないという点に注意しましょう。

vector<vector<vector<int>>> data = {
  {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12},
  },
  {
    {13, 14, 15, 16},
    {17, 18, 19, 20},
    {21, 22, 23, 24},
  },
};

int size1 = data.size();
cout << size1 << endl;  // 2

int size2 = data.at(0).size();
cout << size2 << endl;  // 3

int size3 = data.at(0).at(0).size();
cout << size3 << endl;  // 4

cout << size1 * size2 * size3 << endl;  // 24

細かい話

要素を指定して初期化する

// 2次元配列の初期化
vector<vector<int>> data1 = {
  {7, 4, 0, 8},
  {2, 0, 3, 5},
  {6, 1, 7, 0}
};

// 3次元配列の初期化
vector<vector<vector<char>>> data2 = {
  {
    {'-', '-', '-'},
    {'-', 'x', '-'},
    {'-', 'o', '-'}
  },
  {
    {'x', 'o', '-'},
    {'-', 'o', '-'},
    {'x', '-', '-'}
  }
};

あらかじめ要素の値とサイズが決まっている場合に、要素を指定して初期化することができます。

1次元の配列を多次元配列として使う

「データの表」を扱いたいときは多次元配列が適していることを紹介しました。しかし「データの表」は一列に"ならす"ことで「データの列」として見ることができるので、1次元の配列で扱うこともできます。

2次元の表を1次元に変換する方法はいろいろ考えられますが、表を行ごとに分割して「1列目のデータ→2列目のデータ→3列目のデータ→...」という1次元の列に変換するのがシンプルです。
例えば縦H行、横W列の表を扱いたい時、データの個数はH×W個なので、vector<型> 変数名(H * W);と表現することができます。この場合、上からy個目、左からx個目の要素にアクセスするときは変数名.at(y * W + x)とします。

y * Wの部分は、目的要素のある行の先頭の位置を表しています。一行のデータは並んでいるので、x列目のデータを得るには、行の先頭からxだけ進んだ位置にあるというわけです。

vector以外を用いた多次元配列

「1.13配列」の細かい話でも紹介しましたが、C++にはvector以外にも配列を表現する方法があります。

vector<int> data(3); // vectorによる要素数3の配列
int data[3]; // Cの要素数3の配列
array<int, 3> data; // arrayによる要素数3の配列

このページではvectorを使った多次元配列を紹介しましたが、vector以外の配列で多次元配列を表現することもできます。

// vector を用いた2次元配列
vector<vector<int>> data(3, vector<int>(4));  // 縦3 x 横4 の2次元配列
data.at(1).at(2)  // 上から2番目、左から3番目の要素へのアクセス　(1番目から数えていることに注意)

// array を用いた2次元配列
array<array<int, 4>, 3> data = {};  // 縦3 × 横4 の2次元配列
data.at(1).at(2)  // 上から2番目、左から3番目の要素へのアクセス

// Cの配列を用いた2次元配列
int data[3][4] = {};  // 縦3 × 横4 の2次元配列
data[1][2]  // 上から2番目、左から3番目の要素へのアクセス

arrayやCの配列は要素数に変数を用いることができなかったり、Cの配列では範囲外アクセスをしてもエラーにならずにバグを埋め込んでしまうという点に注意する必要があります。慣れるまではvectorの多次元配列を使うようにしましょう。

問題

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

EX18.ゲーム大会

ABCの問題

ここまでの知識で解ける問題をAtCoder Beginner Contestの過去問題から紹介します。練習問題だけでは物足りない人は挑戦してみてください。

ABC107 B - Grid Compression

前のページ | 次のページ

参照の宣言

参照は次のように宣言します。

参照先の型 &参照の名前 = 参照先;

基本的には宣言時に参照先を指定して初期化する必要がある点に注意してください。
また、あとから参照先を変更することはできません。

例:

int a = 123;
int &b = a;  // int型変数aへの参照

string s = "apg4b";
string &t = s;  // string型変数sへの参照

vector<int> v = {1, 2, 3, 4, 5};
vector<int> &w = v;  // vector<int>型変数vへの参照

int &c;  // 参照先が指定されていないためコンパイルエラーになる

参照のアクセス

参照に対して行った操作が、参照先に対して行ったように扱われます。

例1: 整数の場合

int a = 0;
int &b = a;

b = b + 1;  // a = a + 1; と同じ結果になる

cout << a << endl;  // "1"が出力される

例2: 文字列の場合

string s = "apg4b";
string &t = s;

// 以下の操作で参照先のsが書き換わる
t.at(0) = 'A';
t.at(1) = 'P';
t.at(2) = 'G';

cout << s << endl;  // "APG4b"が出力される
cout << t << endl;  // 参照先のsの値"APG4b"が出力される

参照の複製

既にある参照と同じ参照先をもつ参照を作ることもできます。

int a = 123;
int &b = a;  // 変数aへの参照
int &c = b;  // 変数aへの参照

「参照への参照」のようにならない点に注意してください。

関数の引数での参照

関数の引数を参照にすることもできます。

関数の引数を参照にすると、関数の中で呼び出す側の変数を書き変えることができます。

通常の関数(値渡し)

まずは参照を用いない関数の例です。

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

int f(int x) {
  x = x * 2;  // 2. xを2倍
  return x;   // 3. xの値を返す
}

int main() {
  int a = 3;  // "呼び出す側の変数"
  int b = f(a);  // 1. aの値をfに渡し、4. 結果をbに代入
  cout << "a: " << a << endl;
  cout << "b: " << b << endl;
}

実行結果

a: 3
b: 6

順を追ってプログラムの動きを確認します。

1. f(a)でfにaを渡します。このとき、fの引数のxにint x = a;のようにaの値がコピーされます。つまり、x = 3です。
2. fの内部ではxを2倍します。
3. 変更後の値を返します。x = 3なので、2倍されてx = 6となり、6が返されます。
4. int b = f(a);で結果をbにコピーします。
5. a = 3, b = 6となります。

int b = f(a);の呼び出しを展開してみると次のプログラムのようになります。

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

int main() {
  int a = 3;  // "呼び出す側の変数"
  int b;
    // int b = f(a); を展開
    {
      int x = a;  // aの値がxにコピーされる(引数)
      x *= 2;     // xが2倍される
      b = x;      // xの値がbに代入される(返り値)
    }
  cout << "a: " << a << endl;  // "a: 3"
  cout << "b: " << b << endl;  // "b: 6"
}

このように、渡した変数の値がコピーされるような渡し方を値渡しといいます。

引数が参照になっている関数(参照渡し)

次に、引数を参照にした関数の例です。

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

int g(int &x) {
  x = x * 2;  // xを2倍 (参照によって"呼び出す側の変数"が変更される)
  return x;
}

int main() {
  int a = 3;  // 関数を呼び出す側の変数
  int b = g(a);  // xの参照先がaになる
  cout << "a: " << a << endl;
  cout << "b: " << b << endl;
}

実行結果

a: 6
b: 6

gの呼び出しの前後で、変数aの値が変わっていることが分かります。
「参照の宣言」では宣言時に参照先を指定して初期化する必要があると書きましたが、引数を参照にした場合は、 呼び出し時に渡した変数が参照先となります。
上のプログラムでは引数のxが参照であり、参照先が呼び出す側のaになるので、関数内でxを書き換えるとaの値が変更されます。

int b = g(a);の呼び出しを展開してみると次のプログラムのようになります。

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

int main() {
  int a = 3;  // "呼び出す側の変数"
  int b;
    // int b = g(a); を展開
    {
      int &x = a; // xの参照先がaになる
      x *= 2;     // xが2倍される(つまりaが2倍される)
      b = x;      // xの値(aの値)がbに代入される
    }
  cout << "a: " << a << endl;  // "a: 6"
  cout << "b: " << b << endl;  // "b: 6"
}

このように、渡した変数が参照引数の参照先になるような呼び出し方を参照渡しといいます。

参照渡しの利点

参照渡しが便利な例を紹介します。

関数の結果を複数返したい

通常は関数の結果を返り値を使って呼び出し元に返します。 返り値は1つしか返すことができませんが、関数によっては結果を複数返したい場合があります。
このような場合の1つの実現方法として配列に結果を入れて返すという方法があります。

別の方法として、参照の引数を用いて結果を返す方法があります。

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

// a,b,cの最大値、最小値をそれぞれminimumの参照先、maximumの参照先に代入する
void min_and_max(int a, int b, int c, int &minimum, int &maximum) {
  minimum = min(a, min(b, c));  // 最小値をminimumの参照先に代入
  maximum = max(a, max(b, c));  // 最大値をmaximumの参照先に代入
}

int main() {
  int minimum, maximum;
  min_and_max(3, 1, 5, minimum, maximum);  // minimum, maximumを参照渡し
  cout << "minimum: " <<  minimum << endl;  // 最小値
  cout << "maximum: " <<  maximum << endl;  // 最大値
}

実行結果

minimum: 1
maximum: 5

無駄なコピーを減らす

関数に引数を渡す場合、無駄なコピーが発生することがあります。

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

// 配列の先頭100要素の値の合計を計算する
int sum100(vector<int> a) {
  int result = 0;
  for (int i = 0; i < 100; i++) {
    result += a.at(i);
  }
  return result;
}

int main() {
  vector<int> vec(10000000, 1);  // すべての要素が1の配列

  // sum100 を500回呼び出す
  for (int i = 0; i < 500; i++) {
    cout << sum100(vec) << endl;  // 配列のコピーが生じる
  }
}

実行結果

100
100
100
100
100
(省略)
...

実行時間

7813 ms
※一例なので異なる結果になることがあります。

上のプログラムでは関数sum100を呼び出すたびに配列の要素がコピーされるので、1000万要素の配列のコピーが500回生じています。
この実行結果では全体で7秒以上の時間がかかっていて、配列を1回コピーするのに約15ミリ秒(0.015秒)程かかっていることになります。

ここで、引数のvector<int> aをvector<int> &aとして参照渡しするように変更します。

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

// 配列の先頭100要素の値の合計を計算する (参照渡し)
int sum100(vector<int> &a) {
  int result = 0;
  for (int i = 0; i < 100; i++) {
    result += a.at(i);
  }
  return result;
}

int main() {
  vector<int> vec(10000000, 1);  // すべての要素が1の配列

  // sum100 を500回呼び出す
  for (int i = 0; i < 500; i++) {
    cout << sum100(vec) << endl;  // 参照渡しなので配列のコピーは生じない
  }
}

実行結果

100
100
100
100
100
(省略)
...

実行時間

15 ms
※一例なので異なる結果になることがあります。

こちらのプログラムでは、配列を参照渡ししているので呼び出し時に配列の要素がコピーされず、 実行時間が約15ミリ秒に収まっています。
値渡しを用いたsum100では1回あたりの呼び出しに約15ミリ秒かかっていたことを踏まえれば、 約500倍程高速に動作するようになったことになります。

これらのサンプルプログラムはあまりない意味の無い極端な例ですが、現実的なプログラムでも、 複数回呼び出される関数で配列の値渡しを行うと上の例のように実行時間が遅くなってしまうことがあります。
詳しくは2.06.計算量で扱いますが、プログラムを高速化したい場合には配列のコピーについて特に気をつける必要があります。 コピーが必要のない場合は参照渡しを用いるのが良いでしょう。

注意点

参照先の指定が必要

参照を宣言するときは基本的に参照先を指定して初期化する必要があります。
参照先が定まっていない参照を作ることはできないということに注意しましょう。

関数の引数に用いる参照は呼び出し時に自動的に参照先が決まります。

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

int main() {
  int a = 0;
  int &b;  // コンパイルエラー
}

エラー出力

./Main.cpp: In function ‘int main()’:
./Main.cpp:6:8: error: ‘b’ declared as reference but not initialized
   int &b;
        ^

「bが参照として宣言されているのに初期化されていない」というエラーです。

参照先を変更することはできない

一度宣言した参照の参照先を後から変更することもできません。

細かい話

&の位置

参照の宣言を以下のように紹介しました。

参照先の型 &参照の名前 = 参照先;

実は、&の位置は参照の名前の直前である必要はなく、次のようにすることもできます。

参照先の型& 参照の名前 = 参照先;  // 型の直後
参照先の型 & 参照の名前 = 参照先;  // 中間

しかし、複数の参照を同時に宣言しようとした場合には注意が必要です。

int a = 123;
int& b = a, c = a;

例えば、上のようにした場合に、bとcはどちらもaへの参照になるように見えてしまいますが、 実際にはcは参照ではなく、「aの値で初期化されたint型の変数」になります。(bはaの参照になります。)

cを参照にするには、cの前にも&をつける必要があります。

&の位置は参照の名前の直前でも型名の直後でもいいのですが、このような問題があるため、名前の直前に書くのが良いでしょう。

int a = 123;
int &b = a, &c = a;  // bとcはどちらもaへの参照

範囲for文での参照

2.02 ループの書き方では、範囲for文を用いて配列の要素の値を読み取る場合についてのみ紹介しました。

vector<int> a = {1, 3, 2, 5};
for (int x : a) {
  x = x * 2;
}
// aは{1, 3, 2, 5}のまま

例えば上のように書いても、x自体は2倍になるものの、対応する配列の要素は変更されません。

参照は範囲for文でも用いることができ、これによって配列の要素を書き換える処理を簡潔に書くことができます。

vector<int> a = {1, 3, 2, 5};
for (int &x : a) {
  x = x * 2;
}
// aは{2, 6, 4, 10}となる

参照を用いた範囲for文の書き方

for (配列の要素の型 &変数名 : 配列変数) {
  // 変数名 を使う(変数を経由して配列の要素を書き換え可能)
}

変数以外の参照

参照先を変数以外にすることもできます。

vector<int> v = {1, 2, 3};

// 以下の操作で参照先のvの要素が書き換わる
int &e = v.at(1);
e = -2;

cout << v.at(0) << ", " << v.at(1) << ", " << v.at(2) << endl;  // "1, -2, 3"が出力される

この例では、配列の2番目の要素を参照先とする参照を宣言しています。
ただし、この例のようにvectorの要素に対する参照を作る場合には注意が必要です。

vectorの要素への参照を作った後に、vectorに対して要素を追加したり要素を削除するような操作を行うと、参照先が無効になり、意図しない動作をすることがあります。
vectorの要素への参照を生成した後は元のvectorの要素数が変わるような操作を行わないように注意しましょう。

具体的には、要素への参照を生成した後に、たくさんの要素をpush_backで追加するようなケースです。
次のプログラムでは、たくさんの要素をpush_backした結果、参照が期待した動作をしていないことが分かります。

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

int main() {
  vector<int> v = {1, 2, 3};
  int &e = v.at(1);
  // 大量のpush_backで要素数を大幅に増やす
  for (int i = 0; i < 1000; i++) {
    v.push_back(i + 4);
  }
  cout << "e: " << e << endl;  // "e: 2"とならないことがある
}

実行結果

e: 32734

※一例なので異なる結果になることがあります。

参照型の返り値

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

// int型の参照を返す関数f
int &f() {
  int x = 12345;
  return x;  // xを参照として返そうとする
}

int main() {
  int &y = f();
  cout << y << endl;  // "12345"が出力される？
}

実行結果

(※何も出力されない)

終了コード: 139

※一例なので異なる結果になることがあります。

このようなプログラムは未定義動作(どのように動作するか決まっていない)であり、避けなければなりません。

1.08 変数のスコープでスコープについて説明したとおり、関数fの中の変数xは、関数fの中でのみ使用可能ですが、このプログラムでは変数xの参照を関数の外側に返しています。
参照を用いても、スコープの制約を超えて変数を使用することはできません。

3章で説明するグローバル変数への参照を返り値として返すことは可能です。

扱わなかった機能のリスト

このページで紹介しきれなかった機能のリストを次に示します。 より詳しく勉強したい人は調べてみてください。

• 右辺値参照
• など

問題

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

EX19.九九の採点

前のページ | 次のページ

再帰関数の動作

次のスライドは上のsum関数をsum(3)として呼び出したときの動作を説明したものです。

再帰関数は関数名が同じなので自分自身を呼び出しているように感じられて動作が分かりにくく思えるかもしれません。
その場合は「引数の異なる呼び出しでは別の関数を呼んでいる」と考えるといいです。

上の例でsum(3)を呼び出したときの動作を書き出してみます。

• sum(3)ではsum(2)を呼び出してその結果に3を足して返します。
• sum(2)ではsum(1)を呼び出してその結果に2を足して返します。
• sum(1)ではsum(0)を呼び出してその結果に1を足して返します。
• sum(0)は0を返します。

ここで、呼び出されるsum(3), sum(2), sum(1), sum(0)をそれぞれ別々の関数に切り出して考えてみると次のようになります。

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

// 0~0の総和を求める
int sum0() {
  return 0;
}
// 0~1の総和を求める
int sum1() {
  int s = sum0();
  return s + 1;  // (0~0の総和) + 1 = 1
}
// 0~2の総和を求める
int sum2() {
  int s = sum1();
  return s + 2;  // (0~1の総和) + 2 = 3
}
// 0~3の総和を求める
int sum3() {
  int s = sum2();
  return s + 3;  // (0~2の総和) + 3 = 6
}

int main() {
  cout << sum3() << endl;  // 6
}

実行結果

6

sum1, sum2, sum3は同じような処理をしていますが、sum0だけは異なる処理をしています。 繰り返しの処理をwhile文やfor文を用いてまとめられたように、 このような繰り返しの呼び出しを再帰呼出しでまとめることができます。

もう一度元の再帰関数を見てみましょう。

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

// 0 ~ nの総和を求める
int sum(int n) {
  if (n == 0) {
    // sum0のケースを場合分け
    return 0;
  }

  // それ以外のケース
  int s = sum(n - 1);  // 1~(n-1)の総和を計算
  return s + n;  // nを足して返す
}

int main() {
  cout << sum(3) << endl;  // 6
}

実行結果

6

再帰関数が正しく動作するのは再帰呼び出しの連鎖に終わりがあるからです。 この例ではnが初めに呼び出されたときの値から1ずつ減っていき、0になるとif文によって分岐され、それ以上再帰呼出しが起こらなくなり、 呼び出しの連鎖が終わるのでうまく動きます。

再帰関数の性質

実装法を紹介する前に再帰関数の性質をまとめておきます。

再帰関数の内容は大きく分けると以下の2つの処理に分類できます。

• ベースケース：再帰呼び出しを行わずに完了できる処理
• 再帰ステップ：再帰呼出しを行い、その結果を用いて行う処理

sum関数の例では、ベースケース・再帰ステップはそれぞれ次のようになります。

// n を受け取って、0~n の総和を計算して返す関数
int sum(int n) {
  // ベースケース
  if (n == 0) {
    return 0;
  }

  // 再帰ステップ
  int s = sum(n - 1);
  return s + n;
}

また、再帰関数が正しく動作するためには次の条件を満たす必要があります。

• 再帰呼び出しの連鎖に終わりがある

これを言い換えると、「再帰ステップでの再帰呼び出しを繰り返すうちに必ずベースケースに到達する」ということになります。

この条件を満たさない場合、無限ループになってしまいます。

再帰関数の実装法

初めのうちは、そもそも再帰関数でどのような処理を行うことができるのかが分からず、 使いこなすのが難しいかもしれませんが、再帰関数の実装を追いかけたり、実際に実行してみるうちに分かってくるはずです。

ここでは、再帰関数の実装の方法をできるだけ丁寧に説明します。

1.「引数」「返り値」「処理内容」を決める

関数では、処理に必要な変数を引数として受け取り、関数の内部で処理を行い、結果を返すという流れで処理を行うので、 「引数」「返り値」「処理内容」を決める必要があります。

「処理内容」は「返り値」を計算するという内容になり、結局同じことを示すことも多いです。

sum関数での例

ここで関数の概形が決まります。sum関数の例を次に示します。

// 0 ~ n の総和を返す
int sum(int n) {
  // 処理内容 : 0 ~ n の総和を計算する
}

2. 再帰ステップの実装

次に、「具体的にどのような再帰呼び出しを使って処理を実現できるのか」つまり、再帰ステップの内容を考えます。

「処理内容」を実装するために、「引数を変えて再帰呼び出しした結果」を利用できないかを考えましょう。 ここは実装したい処理によって異なるので慣れるまで難しいかもしれません。

sum関数での例

「0 \sim nの総和」は「0 \sim (n-1)の総和」にnを足すことで計算できます。 ここで「0 \sim (n-1)の総和」はsum(n - 1)という再帰呼出しによって得られます。

// 0 ~ n の総和を返す
int sum(int n) {
  // 処理内容 : 0 ~ n の総和を計算する

  // 再帰ステップ
  int s = sum(n - 1);  // 0 ~ (n-1) の総和
  return s + n;  // 0 ~ n の総和
}

3. ベースケースの実装 （再帰呼び出しを行わずに完了できる処理）

まず、どのような場合がベースケースなのか、つまり「再帰呼び出しを行わずに完了できる」かを考えます。

次に、ベースケースをif文で場合分けして、処理を実装します。

適当な引数を与えたときに、再帰ステップでの再帰呼び出しが最終的にベースケースに到達することを確認しておきましょう。今考えたベースケースに到達しない場合は再帰ステップもしくはベースケースが間違っています。もう一度考え直してみましょう。

ベースケースは複数あることもあるという点に注意してください。

sum関数での例

sum関数は「0 \sim nの総和」を計算する関数なので、n == 0の場合はすぐに結果が0だと分かります。従ってこのケースがベースケースに相当します。

また、2で実装した再帰ステップでの再帰呼出しsum(n - 1)は、最終的にn == 0のケースに到達するので、必ずベースケースに到達することが分かります。

// n を受け取って、0~n の総和を計算して返す関数
int sum(int n) {
  // 処理内容 : 0 ~ n の総和を計算する

  // ベースケース
  if (n == 0) {
    return 0;  // 再帰呼び出しをせずとも 0 という結果が確定している
  }

  // 再帰ステップ
  int s = sum(n - 1);  // 0 ~ (n-1) の総和
  return s + n;  // 0 ~ n の総和
}

これで再帰関数sumは完成です。

もう一度再帰関数の書き方まとめます。

1. 「引数」「返り値」「処理内容」を決める
2. 再帰ステップの実装
3. ベースケースの実装

はじめのうちは再帰関数の実装は難しく感じると思います。 しかし、何度も再帰関数を読んだり書いたりしているうちに、直感的に納得できるときが来るはずです。

なお、再帰ステップを考えてからベースケースを考える流れで説明しましたが、 必ずしも先に再帰ステップを考えるのがよいとは限りません。 場合によってはベースケースを先に考えた方が考えやすかったり、再帰ステップで使う関係式を考えているうちにベースケースを思いつくこともあるかもしれません。 「再帰呼び出しの連鎖に終わりがある」という条件さえ満していれば大丈夫ですので、自由な発想で書いてみてください。

再帰関数の実装例

再帰関数のいくつかのパターンを紹介します。 for文やwhile文を用いた方が簡潔に書けるようなものもありますが、再帰関数の例として挙げています。

AからBまでの総和を求める関数： sum_range

// a ~ bの総和を計算する (a ≦ b)という前提
int sum_range(int a, int b) {
}

// a ~ bの総和を計算する (a ≦ b)という前提
int sum_range(int a, int b) {
  // 再帰ステップ
  return sum_range(a, b - 1) + b;  //「a~bの総和」=「a~(b-1)の総和」+ b
}

// a ~ bの総和を計算する (a ≦ b)という前提
int sum_range(int a, int b) {
  // ベースケース
  if (a == b) {
    return a;
  }
  // 再帰ステップ
  return sum_range(a, b - 1) + b;  //「a~bの総和」=「a~(b-1)の総和」+ b
}

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

// a ~ bの総和を計算する (a ≦ b)という前提
int sum_range(int a, int b) {
  // ベースケース
  if (a == b) {
    return a;
  }
  // 再帰ステップ
  return sum_range(a, b - 1) + b;  //「a~bの総和」=「a~(b-1)の総和」+ b
}

int main() {
  cout << sum_range(0, 4) << endl; // 0 + 1 + 2 + 3 + 4 = 10
  cout << sum_range(5, 8) << endl; // 5 + 6 + 7 + 8 = 26
}

10
26

// a ~ bの総和を計算する (a ≦ b)という前提
int sum_range(int a, int b) {
  // ベースケース
  if (a == b) {
    return a;
  }
  // 再帰ステップ
  return a + sum_range(a + 1, b);  //「a~bの総和」= a +「(a+1)~bの総和」
}

配列の要素の総和： array_sum

// dataの要素の総和を計算する
int array_sum(vector<int> &data) {
}

「配列の要素の総和」=「配列の先頭の要素」+「配列の2番目以降の要素の総和」

「1番目以降の要素の総和」=「1番目の要素」+「2番目以降の要素の総和」

「2番目以降の要素の総和」=「2番目の要素」+「3番目以降の要素の総和」
「3番目以降の要素の総和」=「3番目の要素」+「4番目以降の要素の総和」
...

「i番目以降の要素の総和」=「i番目の要素」+「i+1番目以降の要素の総和」

// (補助関数)
// dataのi番目以降の要素の総和を計算する
int array_sum_from_i(vector<int> &data, int i) {
}

// dataの全ての要素の総和を計算する
int array_sum(vector<int> &data) {
  return array_sum_from_i(data, 0);
}

// (補助関数)
// dataのi番目以降の要素の総和を計算する
int array_sum_from_i(vector<int> &data, int i) {
  // 再帰ステップ
  int s = array_sum_from_i(data, i + 1);  // i+1番目以降の要素の総和
  return data.at(i) + s;  // 「i番目以降の要素の総和」=「i番目の要素」+ s
}

// (補助関数)
// dataのi番目以降の要素の総和を計算する
int array_sum_from_i(vector<int> &data, int i) {
  // ベースケース
  if (i == data.size()) {
    return 0;  // 対象の要素がないので総和は0
  }
  // 再帰ステップ
  int s = array_sum_from_i(data, i + 1);  // i+1番目以降の要素の総和
  return data.at(i) + s;  // 「i番目以降の要素の総和」=「i番目の要素」+ s
}

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

// (補助関数)
// dataのi番目以降の要素の総和を計算する
int array_sum_from_i(vector<int> &data, int i) {
  // ベースケース
  if (i == data.size()) {
    return 0;  // 対象の要素がないので総和は0
  }
  // 再帰ステップ
  int s = array_sum_from_i(data, i + 1);  // i+1番目以降の要素の総和
  return data.at(i) + s;  // 「i番目以降の要素の総和」=「i番目の要素」+ s
}

// dataの全ての要素の総和を計算する
int array_sum(vector<int> &data) {
  return array_sum_from_i(data, 0);
}

int main() {
  vector<int> a = {0, 3, 9, 1, 5};
  cout << array_sum(a) << endl;   // 0 + 3 + 9 + 1 + 5 = 18
}

18

Nが素数であるかを判定する関数 is_prime

// i ~ N-1の範囲にNの約数が存在するか
bool has_divisor(int N, int i) {
}

// i ~ N-1の範囲にNの約数が存在するか
bool has_divisor(int N, int i) {
  // ベースケース1
  if (i == N) {
    // そもそも対象となる整数が無いのでfalse
    return false;
  }
  // ベースケース2
  if (N % i == 0) {
    // 実際にiはNの約数なので、i ~ N-1の範囲に約数が存在する
    return true;
  }

  // 再帰ステップ
  // i+1 ~ N-1の範囲の結果がi ~ N-1の範囲の結果となる
  // (ベースケース2によって、iがNの約数の場合は取り除かれているので、あとはi+1 ~ N-1の範囲を調べればよい)
  return has_divisor(N, i + 1);
}

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

// i ~ N-1の範囲にNの約数が存在するか
bool has_divisor(int N, int i) {
  // ベースケース1
  if (i == N) {
    return false;
  }
  // ベースケース2
  if (N % i == 0) {
    // 実際にiはNの約数なので、i ~ N-1の範囲に約数が存在する
    return true;
  }

  // 再帰ステップ
  // i+1 ~ N-1の範囲の結果がi ~ N-1の範囲の結果となる
  // (ベースケース2によって、iがNの約数の場合は取り除かれているので、あとはi+1 ~ N-1の範囲を調べればよい)
  return has_divisor(N, i + 1);
}

bool is_prime(int N) {
  if (N == 1) {
    // 1は素数ではない
    return false;
  }
  else if (N == 2) {
    // 2は素数
    return true;
  }
  else {
    // 2~(N-1)の範囲に約数が無ければ、Nは素数
    return !has_divisor(N, 2);
  }
}

int main() {
  cout << is_prime(1) << endl;  // 0
  cout << is_prime(2) << endl;  // 1
  cout << is_prime(12) << endl; // 0
  cout << is_prime(13) << endl; // 1
  cout << is_prime(57) << endl; // 0
}

0
1
0
1
0

配列の操作 reverse_array

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

// dataのi番目以降の要素を逆順にした配列を返す
vector<int> reverse_array_from_i(vector<int> &data, int i) {
  // ベースケース
  if (i == data.size()) {
    vector<int> empty_array(0);  // 要素数0の配列
    return empty_array;
  }

  // 再帰ステップ
  vector<int> tmp = reverse_array_from_i(data, i + 1);  // dataのi+1番目以降の要素を逆順にした配列を得る
  tmp.push_back(data.at(i));  // 末尾にdataのi番目の要素を追加
  return tmp;
}

// 配列を逆順にしたものを返す
vector<int> reverse_array(vector<int> &data) {
  return reverse_array_from_i(data, 0);
}

int main() {
  vector<int> a = {1, 2, 3, 4, 5};
  vector<int> b = reverse_array(a);
  for (int i = 0; i < b.size(); i++) {
    cout << b.at(i) << endl;
  }
}

5
4
3
2
1

例題 報告書の伝達時間

次の問題はこれまで紹介した例と違い、再帰関数で実装しないと煩雑になるような例です。

難易度が高めなので、少し考えて分からなかったらヒントや解答例を見るようにしてください。

問題文

あなたはA社を経営する社長です。 A社はN個の組織からなり、それぞれに0番からN - 1番の番号が付いています。 0番の番号が付いた組織はトップの組織です。

組織間には親子関係があり、0番以外のN - 1個の組織には必ず1つの親組織があります。 子組織は複数になることがあります。 また、それぞれの組織は直接的または間接的にトップの組織と関係があるものとします。

あなたは全ての組織に報告書を提出するように求めました。
混雑を避けるために、「各組織は子組織の報告書がそろったら、自身の報告書を加えて親組織に送る」ことを繰り返します。 子組織が無いような組織は自身の報告書だけをすぐに親組織に送ります。

ある組織から報告書を送ってから、その親組織が受け取るときにかかる時間を1分とします。
あるタイミングで一斉に報告書の伝達を開始したときに、トップの組織の元に全ての組織の報告書が揃う時刻（伝達を始めてから何分後か）を求めてください。 なお、各組織の報告書は既に準備されているため、報告書の伝達以外の時間はかからないこととします。

制約

• 1 \leq N \leq 50
• 0 \leq p_i < i (1 \leq i \leq N - 1)

入力

N
p_1 p_2 \ldots p_{N - 1}

p_iはi番の組織の親組織がp_i番の組織であることを示します。 0番の組織はトップの組織であり、親組織が存在しないことに注意してください。

出力

T

一斉に報告書の伝達を開始したときに、トップの組織の元に全ての組織の報告書が揃う時刻T（開始からT分後）を1行に出力してください。

入力例1

6
0 0 1 1 4

実行結果

3

この入力例では、組織は次のような関係になっています。

• 1番の組織の親組織は0番
• 2番の組織の親組織は0番
• 3番の組織の親組織は1番
• 4番の組織の親組織は1番
• 5番の組織の親組織は4番

この関係は次のような図になります。（子組織から親組織の向きに矢印が向いています。）

次の図は、子組織からの報告書が揃った時刻（集まった報告書を親組織へ送った時刻）を青い文字で、各子組織から受け取った時刻を赤い文字で書き込んだものです。

この図から分かるように、トップの組織の元に全ての組織の報告書が揃う時刻は3となります。

この問題における組織のような構造を木構造といいます。 木構造に関する処理を行う際には再帰関数が有用なことが多いです。

サンプルプログラム

下記のサンプルプログラムを書き換え、次のスライドのような動作をするようにプログラムを完成させてください。
スライドは入力例1のイメージを示したものです。

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

// x番の組織について、子組織からの報告書が揃った時刻を返す
// childrenは組織の関係を表す2次元配列(参照渡し)
int complete_time(vector<vector<int>> &children, int x) {
  // (ここに追記して再帰関数を実装する)
}

// これ以降の行は変更しなくてよい

int main() {
  int N;
  cin >> N;

  vector<int> p(N);  // 各組織の親組織を示す配列
  p.at(0) = -1;  // 0番組織の親組織は存在しないので-1を入れておく
  for (int i = 1; i < N; i++) {
    cin >> p.at(i);
  }

  // 組織の関係から2次元配列を作る(理解しなくてもよい)
  vector<vector<int>> children(N);  // ある組織の子組織の番号一覧  // N×0の二次元配列
  for (int i = 1; i < N; i++) {
    int parent = p.at(i);  // i番の親組織の番号
    children.at(parent).push_back(i);  // parentの子組織一覧にi番を追加
  }

  // 0番の組織の元に報告書が揃う時刻を求める
  cout << complete_time(children, 0) << endl;
}

push_backは配列に要素を追加する操作です。これについては「1.13.配列」で扱っています。

関数complete_timeの引数childrenは二次元配列で、 x番の組織の子組織の番号一覧の配列はchildren.at(x)とすることで得ることができます。

入力例1の場合のchildrenの中身は以下の表のようになります。

次のようにすることでx番の組織の子組織についての処理が行えます。

for (int c : children.at(x)) {
  // (cについての処理)
}

ヒント

解答例

自分で考えてみたあと、必ず確認してください。

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

// x番の組織について、子組織からの報告書が揃う時刻を返す
// childrenは組織の関係を表す2次元配列(参照渡し)
int complete_time(vector<vector<int>> &children, int x) {
  // ベースケース
  if (children.at(x).size() == 0) {
    return 0;  // 子組織が無いような組織について、報告書が揃う時刻は0
  }

  // 再帰ステップ
  int max_receive_time = 0;  // 受け取った時刻の最大値
  // x番の組織の子組織についてループ
  for (int c : children.at(x)) {

    // (子組織 c のもとに揃った時刻 + 1) の時刻に c からの報告書を受け取る
    int receive_time = complete_time(children, c) + 1;

    // 受け取った時刻の最大値 = 揃った時刻 なので最大値を求める
    max_receive_time = max(max_receive_time, receive_time);
  }
  return max_receive_time;
}

// これ以降の行は変更しなくてよい

int main() {
  int N;
  cin >> N;

  vector<int> p(N);  // 各組織の親組織を示す配列
  p.at(0) = -1;  // 0番組織の親組織は存在しないので-1を入れておく
  for (int i = 1; i < N; i++) {
    cin >> p.at(i);
  }

  // 組織の関係から2次元配列を作る
  vector<vector<int>> children(N);  // ある組織の子組織の番号一覧
  for (int i = 1; i < N; i++) {
    int parent = p.at(i);  // i番の親組織の番号
    children.at(parent).push_back(i);  // parentの子組織一覧にi番を追加
  }

  // 0番の組織の元に報告書が揃う時刻を求める
  cout << complete_time(children, 0) << endl;
}

6
0 0 1 1 4

3

8
0 1 2 1 4 3 1

4

10
0 0 1 3 2 5 3 4 6

4

注意点

スタックオーバーフロー

再帰呼び出しは複雑な処理を簡潔に書くことできる便利な機能ですが、 「再帰呼出しの連鎖があまりにも多く続くと実行時エラーが起こる」 という点に注意しなければなりません。

例えば、再帰関数の実装を間違えて、無限に再帰呼出しが起こってしまうようなケースでは実行時エラーが起こります。 また、再帰関数が正しく実装できていたとしても、数千万回ほどの大量の再帰呼出しを行うようなプログラムでは 実行時エラーが発生することがあります。

次のプログラムは、ベースケースを実装していないため正しく動作しない例です。

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

// 0からnまでの総和を計算し、途中結果を出力する
int sum(int n) {
  // ベースケースが実装されていないので止まらない！

  // 再帰ステップ
  int result = sum(n - 1) + n;
  cout << "sum(" << n << ") = " << result << endl;  // 途中結果を出力する
  return result;
}

int main() {
  // 無限に再帰呼び出しが起こる
  cout << sum(100) << endl;
}

実行結果の例

終了コードの139はプログラムが正しく終了しなかったことを意味しています。

高度な話になりますが、関数呼び出しを行うときにメモリを消費します。 プログラムを実行しているコンピュータのメモリには限りがあるので、再帰呼び出しが多すぎるとメモリが足りなくなってしまいます。 メモリが足りなくなるとそれ以上プログラムを実行できなくなり、実行時エラーが起こります。 この現象をスタックオーバーフローといいます。 コードテストで実行したときに終了コードが139となった場合は、スタックオーバーフローを疑いましょう。

再帰関数を実装するときは、再帰呼び出しをしすぎると実行時エラーが起こる可能性があることを頭の片隅に置いておくようにしましょう。 スタックオーバーフローを避けるために、ループ構文で繰り返し処理を書き直す必要がある場合もあります。

細かい話

相互再帰

2つ以上の関数が相互に呼び出しあって再帰の形になっているものを相互再帰といいます。

次のプログラムを見てください。

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

// プロトタイプ宣言 (1.15.関数「細かい話」を参照)
bool is_even(int);
bool is_odd(int);

// nが偶数かを判定する
bool is_even(int n) {
  // ベースケース
  if (n == 0) {
    return true;
  }
  // 再帰ステップ
  return is_odd(n - 1);  // n-1 が奇数なら、nは偶数
}
// nが奇数かを判定する
bool is_odd(int n) {
  // ベースケース
  if (n == 0) {
    return false;
  }
  // 再帰ステップ
  return is_even(n - 1);  // n-1 が偶数なら、nは奇数
}

int main() {
  cout << is_even(4) << endl;  // 1
  cout << is_odd(5) << endl;   // 1
  cout << is_even(3) << endl;  // 0
}

実行結果

1
1
0

まず、is_evenを見てください。再帰ステップでis_oddを呼び出しています。 一方is_oddの再帰ステップではis_evenを呼び出しています。

相互再帰では、「その関数の後ろで定義される別の関数」を呼び出すことになるので、プロトタイプ宣言が必須です。 プロトタイプ宣言については、1.15.関数の「細かい話」を参照してください。

上のプログラムの場合はis_evenを先に定義しているので、is_oddのプロトタイプ宣言があれば十分ですが、分かりやすさのために両方のプロトタイプ宣言を書いています。

相互再帰はプログラムの動作が複雑になりますが、 通常の再帰関数と同様に「再帰呼出しの連鎖に終わりがある」という条件を満たしていれば動作します。

発展的な例

途中で出力する例

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

// num個分のスペースからなる文字列を返す (字下げに用いる)
string space(int num) {
  string ret = "";
  for (int i = 0; i < num; i++) {
    ret += " ";
  }
  return ret;
}

// 呼び出しの深さに応じて字下げし、関数の開始時点であるというメッセージを出力
void print_in(int n, int depth) {
  cout << space(depth * 4) << "func(" << n << ", " << depth << ") in" << endl;
}

// 呼び出しの深さに応じて字下げし、関数の終了時点であるというメッセージを出力
void print_out(int n, int depth) {
  cout << space(depth * 4) << "func(" << n << ", " << depth << ") out" << endl;
}

// n: 何回の再帰呼出しを行うか
// depth: 呼び出しの深さ(何回目の再帰呼び出しか)
void func(int n, int depth) {
  // ベースケース
  if (n == 0) {
    print_in(n, depth);   // 開始
    print_out(n, depth);  // 終了
    return;
  }

  // 再帰ステップ
  print_in(n, depth);  // 開始
  func(n - 1, depth + 1);  // 残り回数を1減らし、呼び出しの深さを1増やす
  print_out(n, depth); // 終了
}

int main() {
  func(3, 0);  // 3回の再帰呼び出しを行う, 初めの深さを0とする
}

func(3, 0) in
    func(2, 1) in
        func(1, 2) in
            func(0, 3) in
            func(0, 3) out
        func(1, 2) out
    func(2, 1) out
func(3, 0) out

引数の配列を変化させる例

3
.##
...
##.

Yes

4
.###
.###
.###
#...

No

3
...
##.
##.

Yes

5
....#
...#.
..#..
.#...
#....

No

10
..#.#..###
.###.#.##.
.##....#..
.##..#....
....#.##..
#####.....
##.#.###.#
#..#.##..#
...####.##
#.#.###...

Yes

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

// 正しい移動かを調べる (y, x)が移動先
bool is_valid_move(vector<string> &board, vector<vector<bool>> &checked, int x, int y) {
  int N = board.size();

  // 移動先がマス目の外である場合
  if (x <= -1 || x >= N || y <= -1 || y >= N) {
    return false;
  }
  // 移動先が壁マス
  if (board.at(y).at(x) == '#') {
    return false;
  }
  // 既に調べているマスへの移動は調べないのでfalseを返す
  if (checked.at(y).at(x)) {
    return false;
  }

  // それ以外なら正しい移動
  return true;
}

// (y, x)にいる状態からゴールに到達できるか
// board: マス目の種類
// checked: そのマスを既に調べたかを持つ二次元配列
bool reachable(vector<string> &board, vector<vector<bool>> &checked, int x, int y) {
  int N = board.size();

  // ベースケース
  if (x == N - 1 && y == N - 1) {
    // ゴールにいる状態
    return true;
  }

  // 再帰ステップ

  checked.at(y).at(x) = true;  // 既に調べているという状態に変えておく

  // 「上」「右」「下」「左」のいずれかの移動でゴールに到達できるか？
  bool result = false;

  // 上へ移動したマスからゴールに到達できるか？
  if (is_valid_move(board, checked, x, y - 1) && reachable(board, checked, x, y - 1)) {
    result = true;
  }
  // 右へ移動したマスからゴールに到達できるか？
  if (is_valid_move(board, checked, x + 1, y) && reachable(board, checked, x + 1, y)) {
    result = true;
  }
  // 下へ移動したマスからゴールに到達できるか？
  if (is_valid_move(board, checked, x, y + 1) && reachable(board, checked, x, y + 1)) {
    result = true;
  }
  // 左へ移動したマスからゴールに到達できるか？
  if (is_valid_move(board, checked, x - 1, y) && reachable(board, checked, x - 1, y)) {
    result = true;
  }

  return result;
}

int main() {
  int N;
  cin >> N;
  // マス目の状態を受け取る
  vector<string> board(N);
  for (int i = 0; i < N; i++) {
    cin >> board.at(i);
  }

  // 既にそのマスを調べたかを保持する二次元配列
  vector<vector<bool>> checked(N, vector<bool>(N, false));  // false(まだ調べていない)で初期化しておく

  // (0, 0) からゴールまで到達できるか？
  if (reachable(board, checked, 0, 0)) {
    cout << "Yes" << endl;
  }
    else {
    cout << "No" << endl;
  }
}

  if (x == N - 1 && y == N - 1) {
    // ゴールにいる状態
    return true;
  }

  checked.at(y).at(x) = true;  // 既に調べているという状態に変えておく

  // 「上」「右」「下」「左」のいずれかの移動でゴールに到達できるか？
  bool result = false;

  // 上へ移動したマスからゴールに到達できるか？
  if (is_valid_move(board, checked, x, y - 1) && reachable(board, checked, x, y - 1)) {
    result = true;
  }
  // 右へ移動したマスからゴールに到達できるか？
  if (is_valid_move(board, checked, x + 1, y) && reachable(board, checked, x + 1, y)) {
    result = true;
  }
  // 下へ移動したマスからゴールに到達できるか？
  if (is_valid_move(board, checked, x, y + 1) && reachable(board, checked, x, y + 1)) {
    result = true;
  }
  // 左へ移動したマスからゴールに到達できるか？
  if (is_valid_move(board, checked, x - 1, y) && reachable(board, checked, x - 1, y)) {
    result = true;
  }

  return result;

演習問題

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

EX20.報告書の枚数

ABC/ARCの問題

ここまでの知識で解ける問題をAtCoder Beginner Contest / AtCoder Regular Contestの過去問題から紹介します。 練習問題だけでは物足りない人は是非挑戦してみてください。

ヒントと解答例を用意しました。参考にしてください。

• ARC031 B - 埋め立て

vector<vector<bool>> checked(10, vector<bool>(10, false));

// 陸地マスを1つ探す
int y, x;
for (int i = 0; i < 10; i++) {
  for (int j = 0; j < 10; j++) {
    if (board.at(i).at(j) == 'o') {
      y = i;
      x = j;
      break;
    }
  }
}
/* 引数： 盤面, チェック二次元配列, y座標, x座標*/
fill_island(board, checked, y, x);  // (y, x)から到達できるすべての陸地マスのcheckedをtrueにする

bool ok = true;
for (int i = 0; i < 10; i++) {
  for (int j = 0; j < 10; j++) {
    if (board.at(i).at(j) == 'o') {
      if (!check.at(i).at(j)) {
        // 到達できていない陸地マスがある
        ok = false;
      }
    }
  }
}

// ok == true なら全ての陸地マスは繋がっている

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

// (y, x)から到達できるすべての陸地マスのcheckedをtrueにする
void fill_island(vector<vector<char>> &board, vector<vector<bool>> &checked, int y, int x) {
  if (y < 0 || x < 0 || y >= 10 || x >= 10) return;
  if (board.at(y).at(x) == 'x') return;
  if (checked.at(y).at(x)) return;

  checked.at(y).at(x) = true;  // 既に調べているという状態に変えておく
  fill_island(board, checked, y - 1, x    );  // 上
  fill_island(board, checked, y    , x + 1);  // 右
  fill_island(board, checked, y + 1, x    );  // 下
  fill_island(board, checked, y    , x - 1);  // 左
}

bool check_connected(vector<vector<char>> &board) {
  vector<vector<bool>> checked(10, vector<bool>(10, false));

  // 陸地マスを1つ探す
  int y, x;
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      if (board.at(i).at(j) == 'o') {
        y = i;
        x = j;
        break;
      }
    }
  }
  /* 引数： 盤面, チェック二次元配列, y座標, x座標*/
  fill_island(board, checked, y, x);  // (y, x)から到達できるすべての陸地マスのcheckedをtrueにする

  bool ok = true;
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      if (board.at(i).at(j) == 'o') {
        if (!checked.at(i).at(j)) {
          // 到達できていない陸地マスがある
          ok = false;
        }
      }
    }
  }

  // ok == true なら全ての陸地マスは繋がっている
  return ok;
}

int main() {
  vector<vector<char>> board(10, vector<char>(10));
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      cin >> board.at(i).at(j);
    }
  }

  for (int y = 0; y < 10; y++) {
    for (int x = 0; x < 10; x++) {
      if (board.at(y).at(x) == 'o') continue;
      // (y, x)は海のマス
      // ここを埋め立てたと仮定して、島が1つになるかを判定

      board.at(y).at(x) = 'o';  // 埋め立てたと仮定する

      if (check_connected(board)) {
        cout << "YES" << endl;
        return 0;
      }

      board.at(y).at(x) = 'x';  // 戻す
    }
  }

  cout << "NO" << endl;
}

「グリッド上の迷路の探索」とほとんど同じ問題です。

• ATC001 A - 深さ優先探索

これ以降の問題は例題で扱った問題とは少し異なっています。 3.05.ビット演算で説明しているビット全探索を用いることで、再帰関数無しで解くこともできます。

• ARC061 C - たくさんの数式 / Many Formulas
• ABC079 C - Train Ticket
• ABC104 C - All Green
• ARC029 A - 高橋君とお肉
• ABC002 D - 派閥

前のページ | 次のページ

時間計算量

「プログラムの実行に必要な計算のステップ数が入力に対してどのように変化するか」という指標を時間計算量といいます。 計算ステップ数とは、四則演算や数値の比較などの回数です。

空間計算量

「プログラムの実行に必要なメモリの量が入力に対してどのように変化するか」という指標を空間計算量といいます。

計算量の例

次のプログラムは1からNまでの総和(1+2+3+ \cdots +N)を計算するものです。

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

int main() {
  int N;
  cin >> N;
  int sum = 0;
  for (int i = 1; i <= N; i++) {
    sum += i;
  }
  cout << sum << endl;
}

このプログラムではfor文でN回の繰り返し処理を行っているので、計算ステップ数は入力のNに応じて変わります。 N回の繰り返しを行うので、計算ステップ数はおおよそN回になります。 このときの時間計算量は次で紹介するオーダー記法を用いてO(N)と表します。

このプログラムで使用している変数は入力のNに関わらずint Nとint sumとint iの3つです。 このときの空間計算量はオーダー記法を用いてO(1)と表します。

オーダー記法

厳密な計算ステップ数や必要な記憶領域の量は実装に用いるプログラミング言語や実装方法などによって変わるので、 計算量を厳密に見積もるのは大変です。

そこで時間計算量や空間計算量の表現として、オーダー記法 O(\cdot)が用いられることが多いです。

例えば、3 N^2 + 7N + 4という式はオーダー記法ではO(N ^ 2)と表されます。

以下の手順によってオーダー記法による表記を得ることができます。

• ステップ1：係数を省略する。ただし定数については1とする。
• ステップ2：Nを大きくしたときに一番影響が大きい項を取り出し、O(項)と書く。

  補足：N^2 + N + 1という式の場合「N^2」「N」「1」それぞれを項といいます。

「一番影響が大きい項」というのは、Nを大きくしていったときに「大きくなるスピードが最も速い項」と考えてください。 例えばNとN^2を比較すると、以下の表のようになるので3N^2の方が影響が大きいといえます。

3 N^2 + 7N + 4という式をオーダー記法で表す場合の手順以下の通りです。

• ステップ1：係数を省略してN^2 + N + 1とします。
• ステップ2：N^2 + N + 1で一番影響が大きい項はN^2なのでO(N^2)とします。

同じように2N + 10ならO(N)となります。

例題

次の式をそれぞれオーダー記法で表してください。

1. N + 100
2. 10N + N^3
3. 3 + 5
4. 2^N + N^2

   補足：2^N = \underbrace{2 \times 2 \times \cdots \times 2}_{N個}

答え

計算量(オーダー記法)の求め方

計算量を求めるには計算ステップ数がどうなるかを式で表す必要があります。

次のプログラムは意味の無いものですが、計算量がどうなるかを考えてみましょう。

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

int main() {
  int N;
  cin >> N;

  int sum = 0;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      sum += i * j;
    }
  }

  for (int i = 0; i < N; i++) {
    sum += i;
  }

  for (int i = 0; i < N; i++) {
    sum *= i;
  }

  cout << sum << endl;
}

1つの2重ループと2つの1重ループがあるので計算ステップ数はN^2 + 2Nくらいになります。 これをオーダー記法で表すとO(N^2)となります。 よってこのプログラムの時間計算量はO(N^2)です。

このように、 簡単なアルゴリズムであれば厳密な式を求めなくても 「N回の繰り返し処理があるからO(N)」や「0からNまで回す2重ループがあるからO(N^2)」 などと見積もることができます。

例

いくつかの計算量オーダーについて、具体的なプログラムの例を挙げます。

O(1)

次のプログラムは、1からNまでの総和を公式を使って計算するものです。 このプログラムの計算量はO(1)です。

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

int main() {
  int N;
  cin >> N;
  int sum = N * (N + 1) / 2;
  cout << sum << endl;
}

入力

10

実行結果

55

O(N)

次のプログラムは要素数Nの配列の中に含まれる偶数の個数を数えるものです。 このプログラムの計算量はO(N)です。

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

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++) {
    cin >> a.at(i);
  }

  int cnt = 0;
  for (int i = 0; i < N; i++) {
    if (a.at(i) % 2 == 0) {
      cnt++;
    }
  }
  cout << cnt << endl;
}

入力

5
1 4 2 5 9

実行結果

2

O(N ^ 2)

次のプログラムは九九の要領でN×Nマスを埋めるものです。 このプログラムの計算量はO(N^2)です。

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

int main() {
  int N;
  cin >> N;

  vector<vector<int>> table(N, vector<int>(N));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      table.at(i).at(j) = (i + 1) * (j + 1);  // N×N回実行される
    }
  }

  // 出力
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cout << table.at(i).at(j);
      if (j != N - 1) {
        cout << " ";
      }
      else {
        cout << endl;
      }
    }
  }
}

入力

9

実行結果

1 2 3 4 5 6 7 8 9
2 4 6 8 10 12 14 16 18
3 6 9 12 15 18 21 24 27
4 8 12 16 20 24 28 32 36
5 10 15 20 25 30 35 40 45
6 12 18 24 30 36 42 48 54
7 14 21 28 35 42 49 56 63
8 16 24 32 40 48 56 64 72
9 18 27 36 45 54 63 72 81

N \times N要素の二次元配列を使っているので空間計算量もO(N^2)となります。

O(\log N)

初めに簡単に\logを説明します。

\log_x Nという式は「xを何乗したらNになるか」を表します。 例えば、2^4 = 16なので、\log_2 16 = 4です。

次の図を見てください。長さ8の棒を長さが1になるまで半分に切る(2で割る)ことを繰り返したときに切る回数は\log_2 8回です。

このように計算量に出てくる\logは「半分にする回数」を表すことが多いです。

\log NはNに対して非常に小さくなるので、計算量の中にO(\log N)が出てきた場合でも実行時間にそこまで影響しないことが多いです。 具体的な値が知りたい場合は、Google検索で「log_2 値」のように検索することで確認できます。

補足：厳密な定義は高校数学の範囲なので詳しく知りたい人は別で勉強してください。
また、オーダー記法ではlogの底は省略して書かれることが多いです。この場合は2が省略されていると考えましょう。
実はlogの底の違いは定数倍の違いだけとみなすことができるので、係数を省略するオーダー記法では省略されます。

次のプログラムはNが2で何回割れるかを数えるものです。 このプログラムの計算量はO(\log N)です。

上に挙げたイメージと同じような処理を行うプログラムなので、ループする回数が大体\log_2 N回になることが分かります。

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

int main() {
  int N;
  cin >> N;
  int cnt = 0;
  while (N > 0) {
    cnt++;
    N /= 2;
  }
  cout << cnt << endl;
}

計算量のおおまかな大小

主な計算量の大まかな大小は次のようになります。

O(1) < O(log N) < O(N) < O(N log N) < O(N ^ 2) < O(2 ^ N)

時間計算量ならO(1)側ほど高速に計算可能で、O(2^N)側ほど時間が掛かります。

これらの関係をグラフに示すと次のようになります。

入力Nと実行時間の感覚の対応を次の表に示します。

1秒くらいで計算が終わるようなプログラムを作ろうというときは、 入力の大きさの上限を見積もった上で1秒以内に収まるような計算量のアルゴリズムを選択する必要があります。

例えば、N=10^6くらいまでの入力で1秒以内に計算を終えるプログラムを作成するのであれば、 O(N^2)のアルゴリズムでは間に合わないので、O(N)のアルゴリズムを用いて実装する必要があります。

AtCoderの問題では実行時間制約が2秒くらいであることが多いです。 コンテストに参加する人は、1秒あたり10^8回くらいの計算ができることを覚えておきましょう。

複数の入力がある場合のオーダー記法

プログラムの入力が複数ある場合もオーダー記法で計算量を表すことができます。 この場合それぞれの変数を残して書きます。 例えば、2つの入力NとMを受け取る場合はO(N + M), O(NM), O((N + M) \log N)のように書きます。

N^2 M + NM + NM^2という計算ステップ数になった場合は、影響が一番大きくなりうる項のみ残すのでO(N^2M + NM^2)となります。

どの項を残すのかが分からなくても計算量が比較できればよいので問題無いです。複数の入力が計算量に影響することがあるということは頭に入れておきましょう。

細かい話

オーダー記法の落とし穴

計算量をオーダー記法で表記すると比較しやすくなりますが、オーダー記法は大まかな比較しかできない点に注意する必要があります。

オーダー記法では影響の一番大きな項のみを残して係数を省略して書きます。 これによって、例えば計算ステップ数が20Nになるアルゴリズムと2Nになるアルゴリズムを比較しようとしたときに、 実際には10倍もの差があるのに、オーダー記法ではどちらもO(N)となってしまいます。

同様の理由で、O(N)のアルゴリズムAとO(N \log N)のアルゴリズムBを比較するときに、 計算量上はアルゴリズムAの方が高速でも、実際に動かしてみるとアルゴリズムBの方が高速だったということも起こり得ます。

正確に比較する必要がある場合は、実際に時間を計測して比較する必要があります。

STLの関数の計算量

1.14 STLの関数で紹介した関数の計算量は以下のようになります。

次のプログラムは入力される配列をソートして出力するものです。

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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);

  // O(N)
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }

  // O(N log N)
  sort(A.begin(), A.end());

  // O(N)
  for (int i = 0; i < N; i++) {
    cout << A.at(i) << endl;
  }
}

N回のループが2つあるので全体の計算量がO(N)であるように思えますが、 sort関数の計算量はO(N \log N)でループ部分のO(N)より大きいので、このプログラム全体の計算量はO(N \log N)となります。

logの性質

• O(\log 5N) → O(\log N)　logの中の係数は省略します。

• O(\log NM) → O(\log N + \log M)　どちらで書いてもよいですが、大きさを考えるときにこの関係を知っていると見積もりやすいかもしれません。

• O(\log N^2) → O(\log N)

• O(\log 2^N) → O(N)

演習問題

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

EX21.計算量の見積もり

前のページ | 次のページ

int64_t型

今まで整数を扱う場合はint型を使ってきましたが、int型が表せる範囲は以下の通りに限られています。

• 最小値：-2147483648
• 最大値：2147483647

計算の途中でこの範囲を超えてしまうことをオーバーフローと言います。オーバーフローすると正しく計算が行えなくなります。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int a = 2000000000;
  int b = a * 2;
  cout << b << endl;

  int c = (a * 10 + 100) / 100;
  cout << c << endl;
}

実行結果

-294967296
-14748363

2000000000 * 2の結果として4000000000が出力されてほしいところですが、-294967296という値が出力されてしまっています。
また、(2000000000 * 10 + 100) / 100の結果は正しく計算できていれば200000001となるので、オーバーフローせずに済むように思えますが、2000000000 * 10の時点で計算結果がint型の範囲を超えてしまうので、最終的な計算結果も正しくない-14748363という値が出力されています。

もっと広い範囲の値を扱いたい場合、int64_t型を使うのが一般的です。
int64_t型で扱える値の範囲は以下のとおりです。

• 最小値：-9223372036854775808
• 最大値：9223372036854775807

#include <bits/stdc++.h>
using namespace std;
int main() {
  int64_t a = 2000000000;
  int64_t b = a * 2;
  cout << b << endl;
}

実行結果

4000000000

int型は20億(2 * 10^9)くらいまでと覚えておき、それより大きな値が出てきそうであればint64_t型を使うようにしましょう。
int64_t型よりも大きな値を扱う方法もありますが、ここでは説明しません。気になる人は調べてみてください。

プログラム中に直接10のように値を書くと、それはint型の数値として扱われます。
int64_t型として扱ってほしい場合は10LLのように末尾にLLをつけましょう。

また、int型とint64_t型の計算結果はint64_t型になります。

#include <bits/stdc++.h>
using namespace std;
int main() {
  cout << 2000000000 * 2 << endl;     // int * int         -> int
  cout << 2000000000LL * 2LL << endl; // int64_t * int64_t -> int64_t
  cout << 2000000000LL * 2 << endl;   // int64_t * int     -> int64_t
}

実行結果

-294967296
4000000000
4000000000

double型の出力

double型を出力する場合、通常通りcoutで出力してしまうと適当な桁で四捨五入されて表示されてしまいます。
途中の桁まで四捨五入せずに確実に表示したい場合、以下のように書きます。

cout << fixed << setprecision(桁数);

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

int main() {
  cout << 3.14159265358979 << endl;

  // 小数点以下10桁まで
  cout << fixed << setprecision(10);

  cout << 3.14159265358979 << endl;
}

実行結果

3.14159
3.1415926536

明示的な数値型同士の変換

int型とint64_t型の計算結果がint64_t型であったり、int型とdouble型の計算結果がdouble型であったりするように異なる型同士でも計算できることがありました。
計算せずに、ただ型の変換だけを行うこともできます。型変換のことをキャストと言います。

C++には様々なキャスト方法がありますが、ここでは最も原始的なものを紹介します。
キャストの記法は以下のとおりです。

(型)値

以下は数値型を変換する例です。

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

int main() {
  // 小数点以下5桁まで
  cout << fixed << setprecision(5);

  int a = 5;
  cout << (double)a << endl; // int型の値をdouble型に変換

  double b = 3.141592;
  cout << (int)b << endl; // double型の値をint型に変換
}

実行結果

5.00000
3

1行目の出力では、int型の値をdouble型にキャストしたことで、出力時に小数点以下の数も表示されています。
2行目の出力では、double型の値をint型にキャストしたことで、小数点以下が切り捨てられて整数として表示されています。
double型をint型にキャストすると小数点以下切り捨てになることは重要なので覚えておきましょう。

int型とdouble型に限らず、様々な型同士がキャストできます。
ただし、int型からstring型への変換のように、数値型以外への変換は基本的にはできないということに注意してください。

int N = 12345;
string S = (string)N;  // コンパイルエラー

暗黙的な数値型同士の変換

計算の際に自動的にキャストが起こることもあります。

異なる数値型同士で計算を行う場合、以下の表のようにキャストされてから計算されます。

また以下のような場合にも自動的にキャストが起こります。

• 別の型の変数へ代入しようとした場合
• 関数の引数に別の型の値を渡す場合

次のプログラムは暗黙的なキャストが生じる例です。

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

void print_int(int x) {
  cout << "x = " << x << endl;
}

int main() {
  double a = 1.2345;
  int b = 1;

  // aがdouble型に変換されてからbとの足し算が行われる
  // cout << a + (double)b << endl; と同じ結果
  cout << a + b << endl;

  int c = 2000000000;
  int64_t d = 100;
  // 初めにcがint64_t型へ変換されてからdとの掛け算が行われる
  // cout << (int64_t)c * d << endl; と同じ結果
  cout << c * d << endl;

  double e = 3.141592;
  int f = e;  // ここでdouble型からint型への変換が起こる(小数点以下が切り捨てられて3になる)
  cout << f << endl;

  // int型を引数に取る関数にdouble型を渡す
  print_int(e);  // int型に変換されてから関数が実行される
}

実行結果

2.2345
200000000000
3
x = 3

なお、上の条件を満たす場合でも、キャストが行えない場合はコンパイルエラーとなります。

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

void print_int(int x) {
  cout << "x = " << x << endl;
}

int main() {
  string s = "12345";

  int x = s;     // コンパイルエラー
  print_int(s);  // コンパイルエラー
}

関数の引数に別の型の値を渡す場合でも、STLのmin関数やmax関数のように暗黙的な型変換が行われない関数もあるという点に注意してください。 詳しくは4章の「テンプレート」で扱います。

細かい話

double型の精度と誤差

double型の内部について簡単に説明します。 double型では小数を扱うために「数字の並び」と「小数点の位置」を持っています。 そして、「数字の並び」で保持できる桁数はint型などと同じように上限があります。 double型では約16桁の並びを保持できます。逆に16桁を超える小数を正確に扱うことはできません。

表現できる桁数に限りがあるので、計算を行ったときに誤差が生じることがあります。

実際には精度を気にしなければならない場面は少ないかもしれませんが、ここでは情報落ちと桁落ちについて説明します。

情報落ち

差が極端に大きい2つの数を足し算することを考えます。 次のプログラムをみてください。

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

int main() {
  double x = 1000000000;
  double y = 0.000000001;

  // 1000000000.000000001 を表現するには19桁分必要 → 扱えない
  double z = x + y;  // yの分が消えてしまう

  cout << fixed << setprecision(16);
  cout << "x: " << x << endl;
  cout << "y: " << y << endl;
  cout << "z: " << z << endl;
}

実行結果

x: 1000000000.0000000000000000
y: 0.0000000010000000
z: 1000000000.0000000000000000

足す数それぞれがdoubleの精度で扱うことができても、それを足した後の値が表現できないことがあり、 そのような場合には桁が消えてしまいます。 このような現象を情報落ちといいます。

なるべく小さい数から順に足し算を行うことで、情報落ちの影響を減らすことができます。

桁落ち

差が極端に小さい2つの数を引き算することを考えます。

x, yは本来無限に桁が続く小数とします。 これらをコンピュータで扱おうとしたときに6桁までしか表現できず、それ以降の桁は0になってしまっているとします。

double型を用いた場合は約16桁まで扱えますが、説明のために6桁までしか表現できないとしています。

ここで、z = x - yを考えます。

zの真の値は0.0001111111111...ですが、計算した結果は0.000111となっています。 5桁までの精度の数で計算を行ったにも関わらず、計算結果は3桁（3つの数字の並び）の精度になってしまっていることが分かります。

このように差が極体に小さい数同士の引き算を行うことによって値の精度が落ちてしまうことを桁落ちといいます。

桁落ちによって精度が落ちたまま計算を続けてしまうと最終的な計算結果の誤差が大きくなってしまうことがあります。

引き算を行う際にはなるべく差が大きくなるように計算順序を工夫したり、そもそも引き算をなるべく行わないように工夫する必要があります。

printfでの出力

printfという関数を呼ぶことでも出力することができます。

精度指定を行う場合やたくさんの値を出力する場合にはcoutよりもprintf関数を使う方が便利です。

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

int main() {
  int x = 12345;
  double pi = 3.14159265358979;
  printf("x = %d, pi = %lf\n", x, pi);
}

実行結果

x = 12345, pi = 3.141593

printfの使い方は次の通りです。

printf(フォーマット文字列, 埋め込みたい値1, 埋め込みたい値2, ...)

「フォーマット文字列」の部分は後で説明するフォーマット指定子を含む文字列を自由に指定できます。 フォーマット指定子を書いた部分に「埋め込みたい値」が順番に埋め込まれます。

上のサンプルプログラムでは"x = %d, pi = %lf\n"と指定しています。 %dや%lfの部分がフォーマット指定子です。 1つ目の%dの部分にはxの内容が埋め込まれ、2つ目の%lfの部分にはpiの内容が埋め込まれます。 なお、\nは改行を意味します。

フォーマット指定子

埋め込みたい値の型によって対応するフォーマット指定子を使う必要があります、代表的なものは次の表のようになっています。

32ビットシステム上でint64_tをprintfで出力する場合、フォーマット指定子は%lldとする必要があります。

なお、string型の文字列を出力する場合、次のように書く必要があります。

#include <bits/stdc++.h>
using namespace std;
int main() {
  string s = "hello";
  // フォーマット指定子 %s を用い s.c_str() を渡す
  printf("%s\n", s.c_str());
}

実行結果

hello

さらにフォーマット指定子の部分を変更することで出力する小数の桁数などの出力の仕方を変更することができます。

#include <bits/stdc++.h>
using namespace std;
int main() {
  double pi = 3.14159265358979;
  // %.桁数f とすると小数点以下「桁数」だけ出力される
  printf("%.10lf\n", pi);

  int x = 1;
  int y = 99;
  int z = 123;
  // %0桁数d とすると表示桁数が「桁数」に満たない場合に0埋めされる
  printf("%03d, %03d, %03d\n", x, y, z);
}

実行結果

3.1415926536
001, 099, 123

printfにはここで紹介していない機能がたくさんあります。詳しく知りたい人は調べてみてください。

scanfでの入力

scanfという関数で入力を受け取ることもできます。

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

int main() {
  int x;
  double pi;
  // scanfによる入力
  scanf("x = %d, pi = %lf", &x, &pi);

  printf("x = %d, pi = %lf\n", x, pi);
}

入力

x = 12345, pi = 3.141593

実行結果

x = 12345, pi = 3.141593

scanfの使い方は次のとおりです。

scanf(フォーマット文字列, &変数1, &変数2, &変数3, ...);

引数に渡す変数の前に&が必要なことに注意してください。

この記号の意味については「4.05.ポインタ」で扱います。

フォーマット文字列は基本的にはprintfのものと同じです。

ただし、string型の文字列を直接入力することはできません。 この場合はcinを使ってください。

空白文字の扱い

%dなどのフォーマット指定子を指定した場合、直前に連続する空白文字を読み飛ばします。空白文字とはスペース()、改行文字(\n)、タブ文字(\t)などのことです。

以下のような呼び出しに対し、123 456という文字列を入力した場合、xは123となり、yは456となります。

scanf("%d%d", &x, &y);

文字列との変換

to_string関数

数値型から文字列に変換するには、to_string関数を用います。

to_string関数は、引数の数値をstring型に変換します。

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

int main() {
  int number = 100;
  string s = to_string(number);
  cout << s + "yen" << endl;
}

実行結果

100yen

stoi関数

文字列からint型に変換するには、stoi関数を用います。

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

int main() {
  string s = "100";
  int n = stoi(s);
  cout << n << endl;
}

実行結果

100

文字列から他の数値型への変換はそれぞれの型に対応する関数を用います。 対応表を次に示します。

これらの関数の使い方はstoi関数と同じです。

その他の型専用の関数も用意されていますが、基本的にint64_t型かdouble型にしてからキャストすればよいです。

他の数値型

int型やdouble型以外にも様々な数値型が用意されています。 これらは扱える値の範囲や精度、使用するメモリの量が異なります。

整数型

主な符号付き整数型

主な符号無し整数型

int??_t系やuint??_t系以外については、環境によっては上の表と異なることがあります。

使用するメモリについては、たとえば「long long型は64bitなので、変数1つに対してint型変数2つ分のメモリが必要」のように考えてください。

たくさんあってどう使い分けるのか分からなくなるかもしれませんが、 int??_t系やuint??_t系を使うことをおすすめします。 極端な話ですが、使用するメモリ量をそこまで気にしないのであれば全てint64_t型かuint64_t型を使ってしまうという手もあります。

実数型

環境依存の仕様

環境によって扱える範囲が変わる整数型としてlongがあります。 longの扱える範囲は次の表のとおりです。

AtCoder上で実行した場合は、longが扱える範囲はint64_tと同じになります。

プログラム中に直接書いた数値をlong型として扱うには、10Lのように末尾に1つのLをつけて書きます。

AtCoder上ではint64_tはlong型として扱われるため、厳密にはプログラム中に直接書いた数値をint64_tとして扱いたい場合には10Lのようにlong型に合わせて書いた方が正確ですが、他のシステム上でも同様に動くようにするために、「int64_t型として扱うためにはLLと書く」と説明しています。

size_t

配列や文字列のsize()で返ってくる要素数の値はsize_tという符号なしの整数型です。 C++ (GCC 9.2.1)においてsize_tはunsigned long（単なる別名）として定義されています。

実行環境によって、for文でfor (int i = 0; i < 配列.size(); i++)と書いたときに警告が出るのは、int型（符号付き）とsize_t型（符号無し）を比較しているためです。 しかし、暗黙的にキャストが行われるので動作には影響ありません。

符号なし整数のオーバーフロー

符号なし整数は負の数を扱えないため、例えばunsigned char型の0から1を引くと255となってしまいます。

size_t型は符号なしの整数型であるため、次のようなプログラムは意図した挙動になりません。

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

int main() {
  vector<int> data(0);  // サイズ0
  cout << data.size() - 1 << endl;  // -1ではない

  // 配列のサイズ-1回だけループしたい
  for (int i = 0; i < data.size() - 1; i++) {
    cout << i << endl;
  }
}

実行結果の例

18446744073709551615
0
1
2
3
4
5
6
7
8
(省略)

この例では、ループ回数のdata.size() - 1がオーバーフローして18446744073709551615という値になってしまっています。

配列のサイズ-1回だけループしたい場合は、次のようにsize()の結果を符号付きにキャストする必要があります。

// 配列のサイズ-1回のループ(ただし、空の場合はループ内は実行されない)
for (int i = 0; i < (int)配列.size() - 1; i++) {
  // 適当な処理
}

演習問題

今回は演習問題はありません。

次のAtCoder Beginner Contestの問題を解いてみてください。

• ABC079 B - Lucas Number

前のページ | 次のページ

pair

pairは2つの値の組を表す型です。

サンプルコード

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

int main() {
  pair<string, int> p("abc", 3);
  cout << p.first << endl;  // abc

  p.first = "hello";
  cout << p.first << endl;  // hello
  cout << p.second << endl; // 3

  p = make_pair("*", 1);

  string s;
  int a;
  tie(s, a) = p;
  cout << s << endl;  // *
  cout << a << endl;  // 1
}

実行結果

abc
hello
3
*
1

宣言・初期化

pair<型1, 型2> 変数名;
pair<型1, 型2> 変数名(値1, 値2);

アクセス

変数名.first   // 1つ目の値
変数名.second  // 2つ目の値

pairの生成

make_pair(値1, 値2)

make_pairによってpair型の値を得ることができます。

また、次のようにすることでもpairを生成することができます。

pair<型1, 型2>(値1, 値2)

どちらを使っても構いませんが、make_pairでは型を明示的に書く必要がないのでmake_pairを使うとよいでしょう。

細かい話で扱う型エイリアスを用いてpairの型に簡単な名前を付ける場合、後者の方が楽に書ける場合もあります。

pairの分解

型1 変数1;
型2 変数2;
tie(変数1, 変数2) = pair型の値;

変数1、変数2にそれぞれpairの1番目の値、2番目の値が代入されます。

tuple

tupleはpairを一般化したもので、「複数個の値の組」を表す型です。

サンプルコード

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

int main() {
  tuple<int, string, bool> data(1, "hello", true);
  get<2>(data) = false;
  cout << get<1>(data) << endl;  // hello

  data = make_tuple(2, "WORLD", true);

  int a;
  string s;
  bool f;
  tie(a, s, f) = data;
  cout << a << " " << s << " " << f << endl;  // 2 WORLD 1
}

実行結果

hello
2 WORLD 1

宣言・初期化

tuple<型1, 型2, 型3, ...(必要な分だけ型を書く)> 変数名;
tuple<型1, 型2, 型3, ...(必要な分だけ型を書く)> 変数名(値1, 値2, 値3, ...); // 初期化

tupleでは0個以上の組を表現することができます。

アクセス

get<K>(tuple型の変数)  // K(定数)番目にアクセス

Kは定数でなければならないことと、Kは0から始まる数であることに注意してください。

次のように、Kとして変数を用いることはできません。

int i = 2;
tuple<int, int, int> data(1, 2, 3);
cout << get<i>(data) << endl;  // コンパイルエラー

tupleの生成

make_tuple(値1, 値2, 値3, ...)

以下のようにして生成することもできます。

tuple<型1, 型2, 型3, ...(必要な分だけ書く)>(値1, 値2, 値3, ...)

tupleの分解

型1 変数1;
型2 変数2;
型3 変数3;
︙
tie(変数1, 変数2, 変数3, ...) = tuple型の値;

pair/tupleの比較

型が同じpairやtuple同士は比較することができます。

例えばpair<int, int>を比較する場合、1番目の値を基準に比較され、もし1番目の値が等しい場合は2番目の値を基準に比較されます。

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

int main() {
  pair<int, int> a(3, 1);
  pair<int, int> b(2, 10);
  // 3 > 2 なので a < b は false
  if (a < b) {
    cout << "a < b" << endl;
  }
  else {
    cout << "a >= b" << endl;
  }

  pair<int, int> c(5, 1);
  pair<int, int> d(5, 10);
  // 5 == 5 であり 1 < 10 なので c < d は true
  if (c < d) {
    cout << "c < d" << endl;
  }
  else {
    cout << "c >= d" << endl;
  }
}

実行結果

a >= b
c < d

tupleを比較する場合もpairと同様に「1番目の値が最優先で比較され、等しい場合は2番目の値で比較する。もし2番目の値も等しい場合は3番目の値を比較する……」と、1番目の値から順に比較されます。

なお、==は全ての値が等しい場合、!=は1つ以上の異なる値が存在する場合にtrueとなります。

pairやtupleの配列をソートする場合も上記の比較順序でソートされます。

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

int main() {
  vector<tuple<int, int, int>> a;
  a.push_back(make_tuple(3, 1, 1));
  a.push_back(make_tuple(1, 2, 100));
  a.push_back(make_tuple(3, 5, 1));
  a.push_back(make_tuple(1, 2, 3));
  sort(a.begin(), a.end());

  for (tuple<int, int, int> t : a) {
    int x, y, z;
    tie(x, y, z) = t;
    cout << x << " " << y << " " << z << endl;
  }
}

実行結果

1 2 3
1 2 100
3 1 1
3 5 1

auto

初期化を伴って変数を宣言する場合や範囲for文において、型の部分にautoと書くことによって型を省略することができます。

サンプルコード

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

string concat(string a, string b) {
  return a + b;
}

int main() {
  string a = "Hello,";
  string b = "World";
  auto ab = concat(a, b);  // string型
  cout << ab << endl;

  vector<int> c = {1, 2, 3};
  auto d = c;  // vector<int>型

  for (auto elem : d) {
    // elemはint型
    cout << elem << endl;
  }
}

実行結果

Hello,World
1
2
3

変数宣言でのauto

auto 変数名 = 初期値;

範囲for文でのauto

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

参照でのauto

int a = 12345;
auto &ref = a;  // aへの参照 `int &ref = a;`と書くのと同じ

vector<int> b = {1, 2, 3};
// 範囲for文でも参照にすることができる
for (auto &elem : b) {
  elem *= 2;
}
cout << b.at(0) << endl;  // 2
cout << b.at(1) << endl;  // 4
cout << b.at(2) << endl;  // 6

細かい話

ignore

pairやtupleを分解する際に要らない要素を捨てたい場合、ignoreをtieの引数に渡すことで、対応する位置の値を捨てることができます。

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

int main() {
  pair<int, int> p(3, 5);
  int right;
  tie(ignore, right) = p;  // 2番目の値だけ取り出す
  cout << right << endl; // 5

  tuple<int, string, bool> tpl(2, "hello", false);
  int x;
  string s;
  tie(x, s, ignore) = tpl;  // 1番目の値、2番目の値だけ取り出す
  cout << x << " " << s << endl; // 2 hello
}

実行結果

5
2 hello

型エイリアス

型エイリアスを用いると型に別の名前をつけることができます。 pairやtupleなど型名が長くなってしまう場合に型エイリアスを使うと便利です。

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

int main() {
  using pii = pair<int, int>;
  // これ以降 pii という型名はpair<int, int> と同じ意味で使える

  pii p;
  p = make_pair(1, 2);
  cout << "(" << p.first << ", " << p.second << ")" << endl;
  p = pii(3, 4);  // 別のpairを作って代入
  cout << "(" << p.first << ", " << p.second << ")" << endl;
}

実行結果

(1, 2)
(3, 4)

次のようにして型エイリアスを宣言することができます。

型エイリアスの宣言

using 新しい型名 = 型名;

宣言した型エイリアスは型名として利用できます。

型エイリアスを用いることで、多次元配列の型を簡単に書くこともできます。

using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

int N = 10, M = 20;
vvi data(N, vi(M));  // N * M の2次元配列

これまでプログラムの2行目に書いていたusing namespace std;にもusingというキーワードが出てきますが、このusingと型エイリアスのusingは違う意味なので注意してください。using namespace std;については4章で説明します。

なお、C++では同様の機能としてtypedef宣言が用意されていますが、基本的にはusingを使うようにしましょう。

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

int main() {
  typedef pair<int, int> pii;  // pair<int, int> に pii という別名を付ける

  pii p = make_pair(1, 2);
  cout << "(" << p.first << ", " << p.second << ")" << endl;
}

実行結果

(1, 2)

演習問題

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

EX22.2つ目の値でソート

ABCの問題

今回紹介した機能を用いて解くことができるAtCoder Beginner Contestの問題を紹介します。 練習問題だけでは物足りない人は是非挑戦してみてください。

• ABC128 B - Guidebook

前のページ | 次のページ

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.最頻値

前のページ | 次のページ

構造体の定義

次の形式で構造体を定義します。

struct 構造体名 {
  型1 メンバ変数名1
  型2 メンバ変数名2
  型3 メンバ変数名3
  ...(必要な分だけ書く)
};  // ← セミコロンが必要

構造体の定義は関数の外側、内側のどちらにも書くことができます。

構造体を定義することによって新しい型が使えるようになります。 例えば、上の例ではMyPairという構造体を定義したので、それ以降MyPairという型が使えるようになります。

宣言・初期化

構造体の変数を宣言するには、通常の変数の宣言と同じように次のように書きます。

構造体名 変数名;

また、次のように構造体名を用いて構造体の値を生成することもできます。

auto 変数名 = 構造体名();

構造体名を使う方法は一時変数を作りたい場合に便利です。

なお、構造体型の値のことをオブジェクトといいます。

例えば、はじめのサンプルプログラムのpはMyPair型のオブジェクトです。

宣言と同時に、メンバ変数の初期化を行う場合は次のようにします。

構造体名 オブジェクト名 = {メンバ変数1の値, メンバ変数2の値, メンバ変数3の値, ...(必要な分だけ書く)};

メンバ変数

構造体が持っている変数をメンバ変数といいます。

メンバ変数へのアクセスは次のようにします。

オブジェクト.メンバ変数

メンバ変数は、通常の変数と同じように使うことができます。

なお通常の変数と同様に、オブジェクトを宣言しただけではメンバ変数の値は未定である点に注意してください。

メンバ関数

構造体には、オブジェクトに関連した処理を行う関数を定義することができ、この関数をメンバ関数といいます。

メンバ関数は次のように定義します。

struct 構造体名 {
  返り値の型 メンバ関数名(引数の型1 引数名1, 引数の型2 引数名2, ...) {
    // 関数の内容
    //   (ここではメンバ変数に直接アクセスすることができる)
  }
};

メンバ関数を呼び出すには次のようにします。

オブジェクト.メンバ関数(引数1, 引数2, ...)

メンバ関数の特徴は「メンバ関数が紐付いているオブジェクトのメンバ変数」に関数内からアクセスする場合に、オブジェクトの指定なしに直接アクセスできることです。 この点を除けば、通常の関数と同じように使うことができます。

メンバアクセスの機能を使う場合には、メンバ関数と通常の関数では違いがありますが、 APG4bで扱う範囲内では基本的に通常の関数と同様に使うことができます。

次のサンプルプログラムで確認してください。

サンプルプログラム

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

struct MyPair {
  int x;
  string y;
  // メンバ関数
  void print() {
    // 直接x, yにアクセスできる
    cout << "x = " << x << endl;
    cout << "y = " << y << endl;
  }
};

int main() {
  MyPair p = { 12345, "Hello" };
  p.print();  // オブジェクト`p`の`print`を呼び出す

  MyPair q = { 67890, "APG4b" };
  q.print();  // オブジェクト`q`の`print`を呼び出す
}

実行結果

x = 12345
y = Hello
x = 67890
y = APG4b

細かい話

コンストラクタ

オブジェクトが作られるときに、独自の初期化処理などを行いたい場合にコンストラクタを使うことができます。

コンストラクタは次のように定義します。

struct 構造体名 {
  // コンストラクタ
  構造体名() {
    // コンストラクタの内容
  }
};

サンプルプログラム

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

struct MyPair {
  int x;
  string y;
  // コンストラクタ
  MyPair() {
    cout << "constructor called" << endl;
  }
};

int main() {
  MyPair p;  // ここでコンストラクタが呼ばれる
  p.x = 12345;
  p.y = "hello";
  cout << "p.x = " << p.x << endl;
  cout << "p.y = " << p.y << endl;
}

実行結果

constructor called
p.x = 12345
p.y = hello

コンストラクタはメンバ関数と同様に引数を取ることができます。

struct 構造体名 {
  // コンストラクタ
  構造体名(引数1の型 引数1の名前, 引数2の型 引数2の名前, ...) {
    // コンストラクタの内容
  }
};

コンストラクタが引数を取る場合、次のようにオブジェクトの宣言時にコンストラクタの引数に対応する値を渡す必要があります。

構造体名 オブジェクト名(引数1, 引数2, 引数3, ...);

サンプルプログラム

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

struct NumString {
  int length;
  string s;
  // コンストラクタ
  NumString(int num) {
    cout << "constructor called" << endl;

    // 引数のnumを文字列化したものをsに代入し、sの文字数をlengthに代入する
    s = to_string(num);  // (STLの関数)
    length = s.size();
  }
};

int main() {
  NumString num(12345);  // コンストラクタに 12345 が渡される
  cout << "num.s = " << num.s << endl;
  cout << "num.length = " << num.length << endl;
}

実行結果

constructor called
num.s = 12345
num.length = 5

コンストラクタは複数定義することができ、与える引数の型や引数の個数によって自動的に呼び分けることができます。

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

struct MyPair {
  int x;
  string y;
  // コンストラクタ1
  MyPair() {
    cout << "初期化無し" << endl;
  }
  // コンストラクタ2
  MyPair(int x_) {
    cout << "xのみ初期化" << endl;
    x = x_;
  }
  // コンストラクタ3
  MyPair(int x_, string y_) {
    cout << "x, y両方初期化" << endl;
    x = x_;
    y = y_;
  }
};

int main() {
  MyPair p;  // コンストラクタ1が呼ばれる
  cout << "p.x = " << p.x << endl;
  cout << "p.y = " << p.y << endl;

  MyPair q(6789);  // コンストラクタ2が呼ばれる
  cout << "q.x = " << q.x << endl;
  cout << "q.y = " << q.y << endl;

  MyPair r(11111, "good bye");  // コンストラクタ3が呼ばれる
  cout << "r.x = " << r.x << endl;
  cout << "r.y = " << r.y << endl;
}

実行結果(例)

初期化無し
p.x = 4198608
p.y = 
xのみ初期化
q.x = 6789
q.y = 
x, y両方初期化
r.x = 11111
r.y = good bye

なお、{}を使ったオブジェクトの初期化を行う場合、コンストラクタの引数に対応するものを{}で囲む必要があります。

構造体名 オブジェクト名 = {引数1, 引数2, 引数3, ...};

メンバ変数ではなく、コンストラクタの引数を{}で囲むことに注意してください。

コピーコンストラクタ

コンストラクタはオブジェクトが作られる際に呼ばれますが、 関数の引数としてオブジェクトを渡す場合などの条件を満たした場合には、コピーコンストラクタという特殊なコンストラクタが呼ばれます。

次のような場合にコピーコンストラクタが呼ばれます。

• 関数の引数としてオブジェクトを渡した場合
• オブジェクトを宣言する際にMyStruct new_obj = old_obj;で初期化する場合
• オブジェクトを宣言する際にMyStruct new_obj(old_obj);の形で初期化する場合
• など

コピーコンストラクタについては込み入った話が多くなるので、基本的なことのみ紹介します。

コピーコンストラクタは次のように定義します。

struct 構造体名 {
  // コピーコンストラクタ
  構造体名(const 構造体名 &old) {
    // コンストラクタの内容
    // (oldの内容を使って初期化などを行う)
  }
};

constは変数の内容を書き換えられなくなる機能です。この例では、oldのメンバ変数を書き換えることができなくなっています。 詳しくは3.07で扱います。

引数名をoldとしましたが、自由に名前をつけて良いです。

なお、コピーコンストラクタを定義しなかった場合には、 「全てのメンバ変数をそのままコピーして新しいオブジェクトを作る」 という動作をするコピーコンストラクタが自動的に作られるので、 ただコピーしたいだけならコピーコンストラクタを自分で書く必要はありません。

コピーコンストラクタの呼び出しはコンパイラの最適化によって省略される場合があるので注意が必要です。

サンプルプログラム

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

struct MyPair {
  int x;
  string y;
  // コンストラクタ
  MyPair() {
    cout << "normal constructor called" << endl;
  }
  // コピーコンストラクタ
  MyPair(const MyPair &old) {
    cout << "copy constructor called" << endl;
    x = old.x + 1;
    y = old.y + " new";
  }
};

int main() {
  MyPair p;  // ここでコンストラクタが呼ばれる
  p.x = 12345;
  p.y = "hello";
  cout << "p.x = " << p.x << endl;
  cout << "p.y = " << p.y << endl;

  MyPair q(p);  // コピーコンストラクタが呼ばれる
  cout << "q.x = " << q.x << endl;
  cout << "q.y = " << q.y << endl;

  MyPair r = q;  // コピーコンストラクタが呼ばれる
  cout << "r.x = " << r.x << endl;
  cout << "r.y = " << r.y << endl;
}

実行結果

normal constructor called
p.x = 12345
p.y = hello
copy constructor called
q.x = 12346
q.y = hello new
copy constructor called
r.x = 12347
r.y = hello new new

このサンプルプログラムのように、通常のコンストラクタとコピーコンストラクタを同時に定義することもできます。

演算子オーバーロード

新たに定義した構造体型のオブジェクトに対してC++の演算子を使えるようにすることができ、この機能を演算子オーバーロードといいます。

演算子オーバーロードを行える演算子は限られてはいますが、殆どの演算子をオーバーロードすることができます。

演算子オーバーロードの使用はプログラムがシンプルになる一方で、意味がわかりにくくなることもあるので注意しましょう。

極端な例では、+という演算子に引き算をさせるようなこともできてしまいますが、このような非自明な挙動はなるべく避けるべきです。

+演算子のオーバーロード

サンプルプログラム

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

struct MyPair {
  int x;
  string y;
  // 別のMyPair型のオブジェクトをとって、x, yにそれぞれ+したものを返す
  // +演算子をオーバーロード
  MyPair operator+(const MyPair &other) {
    MyPair ret;
    ret.x = x + other.x;  // ここではint型の+演算子が呼ばれる
    ret.y = y + other.y;  // ここではstring型の+演算子が呼ばれる
    return ret;
  }
};

int main() {
  MyPair a = {123, "hello"};
  MyPair b = {456, "world"};

  // MyPair型の+演算子が呼ばれる
  MyPair c = a + b;

  cout << "c.x = " << c.x << endl;
  cout << "c.y = " << c.y << endl;
}

実行結果

c.x = 579
c.y = helloworld

演算子オーバーロードをメンバ関数として定義しています。

+演算子をオーバーロードする場合は次のように定義します。

struct 構造体名 {
  返り値の型 operator+(引数の型 引数) {
    // 処理内容
  }
};

返り値や引数の型は自由に決めることができます。ただし、引数の個数は1つです。

+演算子のオーバーロードは構造体の外側で定義することもできます。 下の「外側で定義する場合」で説明します。

代入演算子のオーバーロード

=演算子(代入演算子)も他の演算子と同様にオーバーロードによって動作をカスタマイズすることができます。

オーバーロードを行わなかった場合、代入演算子は自動的に定義されます。 自動的に定義される代入演算子では、「全てのメンバ変数をそのまま代入していく」というような処理が行われます。

サンプルプログラム

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

struct MyPair {
  int x;
  string y;
  // 代入演算子をオーバーロード
  void operator=(const MyPair &other) {
    cout << "= operator called" << endl;
    x = other.x;
    y = other.y;
  }
};

int main() {
  MyPair a = {123, "hello"};

  MyPair b;
  b = a;  // 代入演算子が呼ばれる

  cout << "b.x = " << b.x << endl;
  cout << "b.y = " << b.y << endl;
}

実行結果

= operator called
b.x = 123
b.y = hello

代入演算子のオーバーロードは次のように定義します。

  void operator=(const 構造体名 &other) {
    // 処理内容
  }

その他の演算子のオーバーロード

他の演算子も同様にオーバーロードすることができます。 メンバ関数として演算子オーバーロードを定義する場合、次のようにします。

struct 構造体の型 {
  返り値の型 operator演算子(引数の型 引数) {
    // 処理内容
  }
};

「演算子」の部分には、+, -, *, /, %, <, >, ==, !=, &&, ||などを書きます。

外側で定義する場合

構造体の外側で演算子オーバーロードを行うと、 自分が定義していない構造体(例えばSTLのpairなど)に対しても演算子をオーバーロードすることができます。

構造体の外側で演算子オーバーロードを定義する場合は、次のようにします。

返り値の型 operator演算子(引数の型1 引数1, 引数の型2 引数2) {
  // 処理内容
}

以下はpair<int, int>に対する演算子オーバーロードのサンプルプログラムです。

pairに対して+演算子をオーバーロードする例

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

pair<int, int> operator+(pair<int, int> a, pair<int, int> b) {
  pair<int, int> ret;
  ret.first = a.first + b.first;
  ret.second = a.second + b.second;
  return ret;
}

int main() {
  pair<int, int> a = {1, 2};
  pair<int, int> b = {3, 4};
  auto c = a + b;
  cout << c.first << ", " << c.second << endl;  // 4, 6
}

実行結果

4, 6

pairの<演算子をオーバーロードして.secondを優先して比較するように変更する例

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

// .second → .first の順に比較
bool operator<(pair<int, int> l, pair<int, int> r) {
  if (l.second != r.second) {
    return l.second < r.second;
  } else {
    return l.first < r.first;
  }
}
// <演算子 を用いて定義
bool operator> (pair<int, int> l, pair<int, int> r) { return r < l; }
bool operator<=(pair<int, int> l, pair<int, int> r) { return !(r < l); }
bool operator>=(pair<int, int> l, pair<int, int> r) { return !(l < r); }

int main() {
  pair<int, int> a = {1, 5};
  pair<int, int> b = {3, 2};
  cout << (a < b) << endl;  // 0
  cout << (a > b) << endl;  // 1
}

実行結果

0
1

なお、複合代入演算子(+=, -=, *=, /=, %=など)は構造体の外側で定義することはできないことに注意してください。

STLのコンテナの要素として使う場合の注意

STLのコンテナや関数は、特定の演算子を要求することがあります。

次のような場合には比較演算子<をオーバーロードする必要があります。

• mapのKeyとして構造体を使う場合
• priority_queueの要素の型として構造体を使う場合
• 構造体の配列に対してsort関数を使う場合

比較演算子<は次のように定義します。

bool operator<(const 構造体名 &left, const 構造体名 &right) {
  // left < right の場合に true を返すように実装する
}

メンバ初期化子リスト

メンバ変数を初期化する方法として、メンバ初期化子リストを使う方法があります。

基本的にはコンストラクタ内で代入するのと変わりませんが、 例えばメンバ変数が参照型である場合のように、コンストラクタ内で初期化することができない場合には、 メンバ初期化子リストで初期化する必要があります。

サンプルプログラム

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

struct MyPair {
  int x;
  string y;
  // 初期化子リストを用いた初期化
  MyPair() : x(123), y("hello") {
  }
};

int main() {
  MyPair p;  // コンストラクタにより初期化される
  cout << "p.x = " << p.x << endl;
  cout << "p.y = " << p.y << endl;
}

実行結果

p.x = 123
p.y = hello

メンバ初期化子リストは次のようにコンストラクタに:を続けて書きます。

struct 構造体名 {
  型1 メンバ変数1;
  型2 メンバ変数2;
  ...(必要な分だけ書く)

  構造体名() : メンバ変数名1(初期化内容), メンバ変数名2(初期化内容), ...(必要な分だけ書く)
  {
  }
};

初期化の部分には、メンバ変数名{初期化内容1, 初期化内容2, ...}のように書くこともできます。

クラス

C++には構造体とほとんど同じ機能であるクラスがあります。

クラスと構造体の違いはメンバアクセスのデフォルトの挙動です。 メンバアクセスについてはAPG4bでは扱いませんが、メンバ変数やメンバ関数を使用できる範囲を制限する機能です。 「メンバ関数の中からしか扱えないメンバ変数」や「メンバ関数の中でしか呼べないメンバ関数」などを実現できます。

デフォルトのメンバアクセスが、クラスはプライベートメンバアクセス（private:を指定したときの挙動）で、構造体はパブリックメンバアクセス（public:を指定したときの挙動）です。

クラス(構造体)には継承という機能もあり、 オブジェクト指向プログラミングを行う際に便利なさまざまな機能が用意されています。 興味のある人は調べてみてください。

扱わなかった構造体関連の機能のリスト

このページで紹介しきれなかった機能のリストを次に示します。 より詳しく勉強したい人は調べてみてください。

• デストラクタ
• メンバアクセス
• 継承
• 静的メンバ変数/関数
• friend宣言
• union
• ビットフィールド
• など

演習問題

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

EX24.時計の実装

前のページ | 次のページ

ビット

「0」か「1」の2通りの状態を表現することができるデータの単位をビットといいます。

ビットをいくつか並べたものをビット列といいます。 例えば「0011」は4ビットのビット列で、「10101010」は8ビットのビット列です。

ビット演算

ビット列に関する演算をビット演算といいます。

以下の6つのビット演算を紹介します。

• AND演算
• OR演算
• XOR演算
• NOT演算
• 左シフト演算
• 右シフト演算

AND演算

下の表で定義される演算をAND演算（または論理積）といいます。 このAND演算をビット毎に適用する演算をビット毎のAND演算（bitwise AND）といいます。

AND演算ではx, yのビットが共に1の場合のみ結果が1になります。

具体例

0111 AND 0100 = 0100

縦に並べると次のようになります。

    0111
AND 0100
--------
  = 0100

OR演算

下の表で定義される演算をOR演算（または論理和）といいます。 ビット毎にOR演算を適用する演算をビット毎のOR演算（bitwise OR）といいます。

OR演算ではx, yのビットの少なくとも一方が1の場合に結果が1となります。 逆に言うと、共に0の場合のみ結果が0となります。

具体例

0111 OR 0100 = 0111

縦に並べると次のようになります。

    0111
 OR 0100
--------
  = 0111

XOR演算

下の表で定義される演算をXOR演算（または排他的論理和）といいます。 ビット毎にXOR演算を適用する演算をビット毎のXOR演算（bitwise XOR）といいます。

XOR演算ではx, yのビットの一方が1の場合に限り結果が1となります。 x, yのビットが等しい場合に0になると見ることもできます。

具体例

0111 XOR 0100 = 0011

縦に並べると次のようになります。

    0111
XOR 0100
--------
  = 0011

NOT演算

下の表で定義される演算をNOT演算といいます。 ビット毎にNOT演算を適用する演算をビット毎のNOT演算（bitwise NOT）といいます。

NOT演算は単にビットを反転する演算で、0のビットは1に、1のビットは0になります。

具体例

NOT 0111 = 1000

縦に並べると次のようになります。

NOT 0111
--------
  = 1000

左シフト演算

ビット列を左向きにずらす操作を論理左シフト演算や単に左シフトといいます。

論理左シフト演算ではずらした後にはみ出た部分のビットは捨てられ、足りない部分のビットは0で埋められます。

具体例

0111 を2ビット左シフトすると 1100

縦に並べると次のようになります。

2ビット左シフト
    |0111|
  01|11  |
----------
  = |1100|

はみ出た「01」の部分は切り捨てられ、右端の2ビット分は0で埋められます。

右シフト演算

ビット列を右向きにずらす演算を論理右シフト演算や単に右シフトといいます。

論理左シフト演算と同様に、ずらした後にはみ出た部分のビットは捨てられ、足りない部分のビットは0で埋められます。

具体例

0111 を2ビット右シフトすると 0001

縦に並べると次のようになります。

2ビット右シフト
    |0111|
    |  01|11
----------
  = |0001|

はみ出た「11」の部分は切り捨てられ、左端の2ビット分は0で埋められます。

ビット演算の使い道

ビット演算は集合の演算を行ったり、高速な演算が必要な場合に用いられます。

集合の操作

ビット列を用いると物の集まり(以下、集合と呼びます)を表現することができます。 ある要素を含むなら対応するビットを1にし、含まないなら対応するビットを0にすることで表現することができます。

具体例

例えば、1〜10の数が書かれたカードのうち、いくつかを手札として持っているとき、この手札を10ビットのビット列を用いて表現できます。 ここでは「カードに書かれた数に対応する位置のビットを1にする」というルールで手札をビット列に対応付けることにします。 例えば{2, 3, 7}という手札は「0110001000」というビット列に対応します。 2が書かれたカードは含まれるので、(左から)2ビット目が1になっています。 5が書かれたカードは含まれないので、5ビット目は0になっています。

このようにビット列で表現しておくと、 例えば「2人の手札に共通して含まれるカードを求めたい」ときに、 2人の手札のビット列に対してビット毎のAND演算を行うことで 「2人の手札に共通して含まれるカードの集合」に対応するビット列を一度に得ることができます。

集合の操作とビット演算の対応の例

もちろん、配列を用いて同様の集合演算を行うことは出来ます。 しかし、上の表に挙げたような単純な集合の操作であれば、 ビット演算を用いることでプログラムがシンプルになったり高速になったりするメリットがあります。

2つの集合から共通する要素を取り出す例

A = {1, 2, 3, 5, 7}とB = {1, 3, 5, 7, 9}という2つの集合に共通する要素は{1, 3, 5, 7}です。 Aに対応するビット列は「1110101000」で、Bに対応するビット列は「1010101010」です。 これらにビット毎のAND演算を適用すると、「1010101000」となり、これは集合{1, 3, 5, 7}を意味しており、共通する要素を取り出せていることが分かります。

高速化

ビット演算では複数のビットについての計算をまとめて行えるので、 この性質をうまく活かすとプログラムを高速化できることがあります。

STLのbitset

C++でビット列を扱うにはbitsetを用います。

宣言・初期化

bitset<ビット数> 変数名;  // すべてのビットが0の状態で初期化される
bitset<ビット数> 変数名("ビット列(長さはビット数に合わせる)");  // 指定したビット列で初期化される

「ビット数」の部分は定数でなければならず、変数を使うことはできないことに注意してください。

例

bitset<4> b("1010");

ビット演算

bitsetに対するビット演算はC++の演算子として定義されています。

対応は次の表の通りです。

これらのビット演算の末尾に=を付けることで複合代入演算子として用いることができます。

サンプルプログラム

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

int main() {
  bitset<8> a("00011011");
  bitset<8> b("00110101");

  auto c = a & b;
  cout << "1: " << c << endl;         // 1: 00010001
  cout << "2: " << (c << 1) << endl;  // 2: 00100010
  cout << "3: " << (c << 2) << endl;  // 3: 01000100
  cout << "4: " << (c << 3) << endl;  // 4: 10001000
  cout << "5: " << (c << 4) << endl;  // 5: 00010000

  c <<= 4;
  c ^= bitset<8>("11010000"); // XOR演算の複合代入演算子
  cout << "6: " << c << endl; // 6: 11000000
}

実行結果

1: 00010001
2: 00100010
3: 01000100
4: 10001000
5: 00010000
6: 11000000

bitsetの操作

bitsetにはビット列を扱うときに便利な関数が用意されています。 以下に主要なものを挙げます。

位置の指定についてですが、ビット列の右から左にかけて0, 1, 2, ...と対応します。 配列の位置の指定とは逆になっていることに注意してください。

サンプルプログラム

#include <bits/stdc++.h>
using namespace std;
int main() {
  bitset<4> S;
  S.set(0, 1);  // 0番目のビットを1にする
  cout << S << endl;

  if (S.test(3)) {
    cout << "4th bit is 1" << endl;
  } else {
    cout << "4th bit is 0" << endl;
  }
}

実行結果

0001
4th bit is 0

その他の関数については「細かい話」で紹介します。

整数とビット列の対応

実はこれまで扱ってきたintやint64_tなどの整数型は、 コンピュータの内部ではビット列で表現されています。

さらに言えば、通常のコンピュータで扱えるものは全てビット列です。

コンピュータはビット列の01のパターンに対して数値を割り当てることで数値を扱っています。 例えば「00000111」は7に、「00100100」は36に対応しています。

このようなビット列と数値の対応は、二進法というルールに基づいています。

以下、簡単のために符号なし整数を表現する場合について説明します。

多くのコンピュータでは負の数を2の補数表現という形式で表現します。 ビット演算の話から少しそれるので扱いませんが、興味のある人は調べてみてください。

二進法

二進法は整数を「1, 2, 4, 8, 16, 32, 64, ... (2の累乗)」の和で表す表し方で、足すか足さないかを0, 1に対応させます。

また、二進法で表記することを二進数表記といいます。 これに対して普段私達が使っている0〜9の数字の並びで表現したものを十進数といいます。

例えば、十進数の「7」は、7 = 4 + 2 + 1 なので、二進数表記は「111」となります。先頭に続く0は省略することが多いです。

以下にいくつか例を挙げます。ビット列の右端から順に 1, 2, 4, 8, ... と対応していることに注意してください。

0〜15の二進数表記は以下の通りです。二進数に不慣れな人は確認してみてください。

整数でのビット演算

C++には、整数をビット列として扱うための演算子が用意されています。 整数でのビット演算の演算子はbitsetのものと同じです。

ただし、整数型に応じてビット列の長さが固定されているので、bitsetほど柔軟には使えません。 例えば、uint32_tは32ビットのビット列として扱うことができ、uint8_tは8ビットのビット列として扱うことができます。 さらに、C++の標準で扱える最大の整数型はuint64_tであり、これは64ビットのビット列なので、 整数をビット列として扱えるのは64ビット以下の場合に限定されることになります。

また、coutで出力しようとした場合に10進数の整数として出力されてしまうため分かりにくいという欠点があります。

基本的にはbitsetを使うのが便利ですが、 「ありうる集合すべてを列挙する」ような処理を行う場合には整数をビット列として扱う方が簡潔に書けることがあります。 詳しくは「細かい話」の「ビット全探索」で説明します。

注意点