標準ライブラリ（STL）でよく使う機能について紹介します。
文字列を扱う。
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;
}動的配列を作る。
動的配列とはサイズが決まっていない配列のこと。要素を追加すれば（push_back()を使えば）自動的にサイズが大きくなる。
主な関数：
vector<int> vec; int型の配列を宣言＋空の配列を生成vector<int> vec(n); int型の配列を宣言。要素数はnvector<int> vec(n, i); int型の配列を宣言。要素数はnで、要素の値はすべてivec[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コンテナ（主に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) - プログラミング関係のメモとか
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同士の比較
#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<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
以下のヘッダも使うと便利なことあるから覚えておくといいです
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;
}参照渡しを使う利点は以下の通り。
*演算子によるアドレスの解決が不要）
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;
}AIZU ONLINE JUDGEの問題1173「世界の天秤」
ICPCは1年に一度行うプログラミングコンテストですが、他にもコンテストやオンライン判定システムは色々あります。 アルゴリズム関係のもののうち、代表的なもの（というか僕が知っているもの）は次の通り。
TopCoder部というページでTopCoder SRMなどの参加方法やコンテストの日程を確認できます。
結構頻繁にコンテストがあるので、暇なときに参加してみましょう。