標準ライブラリ

十分です
string
文字列を扱う。
string str; 空の文字列を宣言
str[i] i番目の文字を参照
str = str2 文字列の代入
str + str2 文字列の連結
str.size() 文字列の長さ
str == str2 文字列の比較
str <= str2 str > str2 文字列の辞書順比較
str.find(str2) 文字列の検索（strの中にstr2が見つかればその位置を示す数値を、見つからなければ-1を返す）
str.rfind(str2) 文字列を後ろから検索
str.substr(i, len) i番目からlen文字分の部分文字列を取得

```
#include <iostream>
#include <string>
// #include <string.h>
using namespace std;

int main() {
  string str = "abcde";
  // char str[256] = "abcde";

  str = "hoge";
  // strcpy(str, "hoge");

  str += "fuga";
  // strcat(str, "fuga");

  str.size();
  // strlen(str);
  
  if (str == "bar") {}
  // if (strcmp(str, "bar") == 0) {}

  if (str < "piyo") {}
  // if (strcmp(str, "piyo") < 0) {}
  
  str = "fghij";
  cout << str << endl; // #=> fghij
  cout << str[3] << endl; // i

  str.find("hi"); // 2
  str.find("f"); // 0
  str.find("a"); // -1
  
  str.substr(2); // hij
  str.substr(2, 1); // h

    return 0;
}
```
vector
動的配列を作る。
動的配列とはサイズが決まっていない配列のこと。要素を追加すれば（push_back()を使えば）自動的にサイズが大きくなる。
主な関数：
vector<int> vec; int型の配列を宣言＋空の配列を生成
vector<int> vec(n); int型の配列を宣言。要素数はn
vector<int> vec(n, i); int型の配列を宣言。要素数はnで、要素の値はすべてi
vec[i] i番目の要素を参照
vec = vec2 配列の代入（vec2の中身が全てvecにコピーされる）
vec.size() 配列の要素数
vec.push_back(some_number) 配列の末尾に要素を追加
vec.insert(it, sume_number) イテレータが示す位置の直前に要素を追加
vec.erase(it) イテレータが示す位置の要素を削除
vec.begin() 配列の先頭を示すイテレータを返す
vec.end() 配列の終端を示すイテレータを返す

```
#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> vec(5,0); // 要素数5、初期値0の配列を宣言
  for (int i = 0; i < vec.size(); i++) {
    vec[i] = i*2;
  }
  // この時点でのvecの中身： [0, 2, 4, 6, 8]

  vec[2] = 100;
  vec.push_back(999); // 末尾に追加
  // この時点でのvecの中身： [0, 2, 100, 6, 8, 999]

  vec.insert(vec.begin() + 3, 5555); // 4番目の要素（vec[3]）の直前に追加
  vec.erase(vec.begin() + 1); // 2番目の要素（vec[1]）を消す
  
  for (int i = 0; i < vec.size(); i++) {
    cout << vec[i] << " ";
  }
  cout << endl; // "0 100 5555 6 8 999 " と表示される
  return 0;
}
```
イテレータ
コンテナ（vectorや後述のmapなど）の中身を統一的に扱うための機能。 上記のinsertやeraseのほか、後述のアルゴリズム系の処理で使われる。
vectorのイテレータは配列のポインタとほぼ同等に扱うことができる（ポインタがイテレータの一種として扱えるように設計されている）。
vector<int> vec(10,0);
*(vec.begin() + 3) = 999;
vec[5] = 6666;
cout << vec[3] << endl; // => 999
cout << *(vec.begin() + 5) << endl; // => 6666

///////

int arr[10];
*(arr + 3) = 999;
arr[5] = 6666;
cout << arr[3] << endl; // => 999
cout << *(arr + 5) << endl; // => 6666
algorithm
コンテナ（主にvectorと普通の配列）を操作する簡単なアルゴリズム集。
色々なデータ構造で使えるようにしているため、イテレータを使っている。
主な関数：
sort(begin, end) イテレータが示す範囲をソートする
lower_bound(begin, end, value) upper_bound(begin, end, value) イテレータが示す範囲で2分探索 
二分探索はソート済みの配列から効率よく値を検索するアルゴリズムのこと
戻り値はイテレータとなる
next_permutation(begin, end) イテレータが示す範囲の次の順列を生成する
find(begin, end, value) 値の検索。値がvalueになる最初の要素のイテレータを返す
count(begin, end, count) 値の個数を数える
min(a,b) max(a,b) 最大最小
min_element(begin, end) max_element(begin, end) イテレータが示す範囲で最小値/最大値となる要素のイテレータを返す
swap(a, b) 値の入れ替え

```
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define all(c) (c).begin(), (c).end()

int main() {
  vector<int> vec(10); // 要素数10個の配列宣言
  for (int i = 0; i < vec.size(); i++)
    vec[i] = (10*i + 3) % 14; // 適当に初期化


  cout << "ソート前：";
  for (int i = 0; i < vec.size(); i++) cout << " " << vec[i];
  cout << endl; // => ソート前： 3 13 9 5 1 11 7 3 13 9

  sort(vec.begin(), vec.end());

  cout << "ソート後：";
  for (int i = 0; i < vec.size(); i++) cout << " " << vec[i];
  cout << endl; // => ソート後： 1 3 3 5 7 9 9 11 13 13

  cout << *lower_bound(vec.begin(), vec.end(), 3) << endl; // => 3
  // vec.begin()で戻り値のイテレータを引けば配列の何番目かがわかる
  cout << (upper_bound(vec.begin(), vec.end(), 11) - vec.begin()) << endl; // => 8

  // all というマクロを用意しておくとbeginとendを毎回書く必要がなく便利
  cout << "3の個数: " << count(all(vec), 9) << endl; // => 3の個数: 2

  return 0;
}
```
next_permutationの例：

```
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  // 最初にソート済みの配列を作る
  vector<int> perm(4, 0);
  for (int i = 0; i < perm.size(); i++) perm[i] = i;

  // do {...} while(next_permutation(perm.begin(), perm.end()))
  // とすると、doループ内のperm配列に順列が辞書順で格納されていく
  do {
    cout << "[";
    for (int i = 0; i < perm.size(); i++) cout << " " << perm[i];
    cout << " ]" << endl;
  } while(next_permutation(perm.begin(), perm.end()));

  return 0;
}
```
出力：
[ 0 1 2 3 ]
[ 0 1 3 2 ]
[ 0 2 1 3 ]
[ 0 2 3 1 ]
...8個省略...
[ 3 1 0 2 ]
[ 3 1 2 0 ]
[ 3 2 0 1 ]
[ 3 2 1 0 ]
参考ページ：競技プログラミングで使えそうなSTLまとめ (Competitive Programming Advent Calendar) - プログラミング関係のメモとか
pair
2つの要素をペアにする。
自分で構造体を作れば同じことができるが、pairを使うと構造体を自作する必要がないので便利。
pair<char, double> p; 文字と実数のペアを保持するペアを宣言
make_pair(a, b) aとbのペアを作成
pair<char, double>(s,d) sとdのペアを作成。ほぼmake_pairと同じだが、typedefを使うとこちらのがタイプ数が少なくなる
p.first 1つ目の要素にアクセス
p.second 2つめの要素にアクセス
p < p2 p >= p2 p == p2 pair同士の比較 
1つ目の要素の要素と2つ目の要素を順に大小比較する


```
#include <iostream>
#include <map>  // pairはutilityヘッダにあり、mapヘッダから読み込まれる
#include <vector>
using namespace std;

typedef pair<int, int> PII;  // typedefしておくと型の記述量が減って便利

int main() {
  pair<int, double> p = make_pair(2, 3.2);  // 整数と実数のペアを宣言
  cout << p.first << ", " << p.second << endl;  // firstとsecondで要素にアクセス。  => 2, 3.2
  p.second += 10;  // ペアの各値は変更可能
  cout << p.second << endl;  // => 13.2

  // pairは比較可能。1つ目の要素の大小関係が優先される
  cout << (p < make_pair(1, 3.2))   << endl;  // => 0
  cout << (p < make_pair(1, 100.0)) << endl;  // => 0
  cout << (p < make_pair(2, 0.1))   << endl;  // => 0
  cout << (p < make_pair(2, 100.0)) << endl;  // => 1
  cout << (p < make_pair(3, 1.5))   << endl;  // => 1

  // vectorやmapにも入れられる
  // まとめてソートするときにも便利
  vector<pair<int, char> > pair_vec;
  pair_vec.push_back(make_pair(5, 'a'));
  cout << pair_vec[0].second << endl; // => a
  
  // typedefしておくと型の記述量が減って便利
  PII pii = PII(3,7);
  cout << pii.second << endl;  // => 7
  pii = PII(-4,9);  // `PII(-4,9)`は`pair<int,int>(-4,9)`と等価で、この場合`make_pair(-4,9)`とも等価
  cout << pii.first  << endl;  // => -4

  return 0;
}
```
map
二分探索木を使った連想配列を作る。
連想配列は、添字に自然数以外のものでも使える配列のこと。
後の講習会で解説するメモ化再帰を実装するときに使われることがある。
map<int, double> p; 数値をキーとして実数を保持するmapを宣言＋空のmapを作成
map[key] キーに該当する要素にアクセス
サンプルコード：

```
#include <iostream>
#include <string>
#include <map>
using namespace std;

int main() {
  map<string, int> str_map; // 文字列をキーとして整数値を格納するマップを宣言
  str_map["hoge"] = 5; // 文字列が添え字になる
  str_map["fuga"] = 8;
  cout << str_map["hoge"] << endl; // => 5

  map<int, int> num_map; // 整数をキーとして整数値を格納するマップを宣言
  num_map[2] = 7;
  num_map[-888] = 5000; // 負数や大きな数を添え字にしても無問題
  num_map[100000000] = 3;
  
  // 要素の存在判定にはfind()を使う
  // 要素が見つからないときfind()は終端を示すイテレータを返す
  if (num_map.find(44) == num_map.end()) cout << "44は見つかりません" << endl;
  
  // mapに格納されている要素が全て偽でなければ、要素にアクセスするだけで存在判定できる
  // 細かいことだが、存在しない要素に[]演算子でアクセスするとその要素にデフォルトコンストラクタの
  // 戻り値が格納され、find()関数による存在判定と併用するのが難しいことに注意
  if (num_map[2])  cout << "2が見つかりました" << endl;
  if (!num_map[2]) cout << "2は見つかりません" << endl;

  // 要素の全列挙にはイテレータを使う　とてもややこしい
  // イテレータの中身はpairで、キーと値はそれぞれfirstとsecondで得られる
  for (map<int, int>::iterator it = num_map.begin(); it != num_map.end(); ++it) {
    int key = it->first;
    int value = it->second;
    cout << "key: " << key << ", value: " << value << endl;
  }
  return 0;
}
```
サンプルコードの出力：
5
44は見つかりません
2が見つかりました
key: -888, value: 5000
key: 2, value: 7
key: 100000000, value: 3
その他の標準ライブラリ
以下のヘッダも使うと便利なことあるから覚えておくといいです
complex：複素数。平面幾何で使う
list：連結リスト
deque：デック（キューとスタックの両方の機能をあわせ持つデータ構造）
set：集合
functional：テンプレートを使った関数オブジェクト
numeric：数値計算用関数
math.h：数学関数（三角関数、指数関数etc.）
C++の文法について
C++の文法で重要そうな部分を
ローカル変数宣言の位置
C言語では「ローカル変数宣言はブロックの先頭にまとめておかないといけない」と習ったかもしれませんが、 C++では関数の途中で宣言しても大丈夫です。（というか最近のC言語（C99）でもOKなはず）

```
int main() {
    int a = 0;
    a += 1;
    int b = 3; // OK
    return 0;
}
```
参照渡し
int&のように変数宣言の型の後ろに&をつけると、その変数は参照渡しとなる。
参照渡しを使うと、ポインタを使ったときと同じような効果を得ることができる。

```
#include <iostream>
#include <vector>
using namespace std;

// 値渡し（普通の引数定義）
void func_val(int a, vector<int> v) {
  a += 1; // コピーされたint変数を書き換え（呼び出し元の変数の値は変化しない）
  v.push_back(1); // コピーされたvectorを書き換え
}

// 参照渡し
void func_ref(int& a, vector<int>& v) {
  a += 1; // 参照先にあるint変数を書き換え（呼び出し元の変数の値も変化する）
  v.push_back(1); // 参照先にあるvectorを書き換え
}

// ポインタ使用（参照渡しとほぼ同じ）
void func_pt(int* a, vector<int>* v) {
  *a += 1;
  v->push_back(1);
}

int main() {
  int a = 0;
  vector<int> v(10000);
  cout << a << ","  << v.size() << endl; // => 0,10000
  func_val(a, v);
  cout << a << ","  << v.size() << endl; // => 0,10000
  func_ref(a, v);
  cout << a << ","  << v.size() << endl; // => 1,10001
  func_pt(&a, &v);
  cout << a << ","  << v.size() << endl; // => 2,10002
  return 0;
}
```
参照渡しを使う利点は以下の通り。
ポインタと同様に関数から呼び出し元の変数の値を書き換えられる
ポインタと違い普通の変数と同じように扱える（*演算子によるアドレスの解決が不要） 
変数の変更がどこに影響するのかわかりにくくなるので諸刃の剣ではある（例えば2013年6月現在のGoogle C++ Style Guideは非constの参照渡しの使用を禁じている）
変数の不要なコピーをしなくて済む 
上記のコードでは要素数1万のvectorを関数に渡しているが、これを値渡しすると関数呼び出しの度に1万個の要素をコピーすることになる。コピーが必要な場合もあるが、多くの場合無駄である
structの関数定義
C++のstructは、関数を持てる。また、typedefなしでも型名だけでアクセスできる。 細かいことを書くと、C++のstructはデフォルトの可視範囲がpublicなclassと等価。
operator?という関数を定義する（?は何か演算子）と、そのstructに対する演算子の効果を変えることができる。 これを演算子オーバーロードという。
演算子オーバーロードは比較可能なクラスを使うときに使用される。

```
#include <iostream>
using namespace std;

// クラス定義。C++ではクラスと構造体はほぼ同等
struct SomeClass {
  int i;
  int j;
  double d;

  // 何か関数
  double get_sum() {
    return i + j + d;  // クラスのメンバ変数を参照できる
  }

  // コンストラクタ（初期化子リストを使用）
  SomeClass(int i, int j, double d) : i(i), j(j), d(d) {}

  // `<`演算子のオーバーロード
  bool operator<(const SomeClass& another) const {
    return i < another.i; // iの大小だけで比較
  }
};

int main() {
  SomeClass s(1,2,3);  // 変数宣言と初期化
  // SomeClass s = SomeClass(1,2,3);  // コピーコンストラクタ経由で初期化（上とほぼ等価）
  // SomeClass s = {1,2,3};  // 変数宣言時の初期化構文を使った方法（コンストラクタがない場合 / 上とほぼ等価）
  cout << s.get_sum() << endl; // => 6

  s = SomeClass(3,-88,5.5);  // コンストラクタを呼び出して再代入
  // s = (SomeClass){3,-88,5.5};  // C99風のCompound Literalを使った書き方（g++拡張 / コンストラクタ不要）
  // s = SomeClass({3,-88,5.5});  // C++0xの初期化子リストを使った書き方（コンストラクタ不要）
  cout << s.get_sum() << endl; // => -79.5

  s.i = 3;
  s.j = 2;
  s.d += 10.2;
  cout << s.get_sum() << endl; // => 20.7

  SomeClass s2(1,5,5);
  cout << (s < s2) << endl; // => 0
  s2.i = 10;
  cout << (s < s2) << endl; // => 1

  return 0;
}
```