【C++】STL for TopCoder
TopCoderを始めて、最初にSTLの使い方でつまづいたので、最低限必要なものを備忘録を兼ねて簡単に解説します
- コードとコメントをひと通り読めば、大体の使い方が分かる、ということを目指して書いています
- 間違いなどありましたら指摘をお願いします
詳しい使い方は http://www.cppll.jp/cppreference/ 等のリファレンス参照
更新記録
- 2011/2/16 algorithmのnext_permutationについて追記
- 2011/2/2 string ,algorithmについて追記(stringのソート)
目次
vector
- ある型の値を複数もつ
- 主な用途
- 可変長配列として
- 使い方
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 int main() {
6 /*
7 * vector<>の宣言
8 * 空のvector<>が作られる
9 */
10 vector<int> v;
11
12 /*
13 * 要素の追加
14 * v.push_back(val)
15 * vectorの最後尾に値が追加される
16 */
17 v.push_back(10);
18 for (int i = 0; i < 20; i++)
19 {
20 v.push_back(i);
21 }
22
23 /*
24 * vectorの要素数
25 * v.size()
26 */
27 cout << "v contains " << v.size() << " integers" << endl;
28
29 /*
30 * 要素へのアクセス
31 * v.at(i)
32 * nのi番目の要素が取り出される
33 */
34 int x = v.at(0);
35 cout << x << endl;
36
37 /*
38 * 配列のような書き方も出来る
39 */
40 for (int i = 1; i < v.size(); i++)
41 {
42 cout << v[i] << " ";
43 }
44 cout << endl;
45
46 return 0;
47 }
string
- 文字列
- 主な用途
- 可変長の文字列として
- 使い方
1 #include <iostream>
2 #include <string>
3 #include <algorithm>
4 using namespace std;
5
6 int main() {
7 /*
8 * stringの宣言
9 */
10 string str; //空文字列
11 string str2("Hello World!"); //初期値あり
12
13 /*
14 * stringの演算子
15 */
16 str = "I'm hungry"; //代入
17 cout << str << endl;
18
19 char ch = str[2]; //要素（char）へのアクセス（str.at(2)でも可）
20 putchar(ch);
21 cout << endl;
22
23 str = str + " and thirsty"; //結合（str += " and thirsty"; でも可）
24 cout << str << endl;
25
26 if (str == str2) //比較(完全一致)
27 {
28 cout << "str is equal to str2" << endl;
29 } else {
30 cout << "str is NOT equal to str2" << endl;
31 }
32
33 str = "abc";
34 str2 = "bac";
35 if (str < str2) //比較（辞書順）
36 {
37 cout << "str is less than str2" << endl;
38 } else {
39 cout << "str is NO less than str2" << endl;
40 }
41
42 /*
43 * stringの文字数
44 * str.size()
45 */
46 cout << "str contains " << str.size() << " characters" << endl; //str.length()も使える
47
48 /*
49 * stringのソート(要<algorithm>)
50 * ASCIIコードでソートされることに注意
51 */
52 str = "gfedcbagfedcba";
53 sort(str.begin(), str.end());
54 cout << str << endl;
55
56
57 /*
58 * その他、文字列の出現位置の検索、トリムなどの機能もある（詳細は割愛）
59 */
60 str = "abcdefg";
61 str2 = "cde";
62 cout << "found str2 in str (from index of " << str.find(str2) << ")" << endl;
63
64 cout << str.substr(3,3) << endl;
65
66 return 0;
67 }
map
- ある型の値からある型の値への写像
- 主な用途
- 連想配列として
- 使い方
1 #include <iostream>
2 #include <string>
3 #include <map>
4 using namespace std;
5
6 int main() {
7 /*
8 * map<,>の宣言
9 * 平衡二分木で実装されているらしい（のでけっこう遅い）
10 */
11 map<string,int> m; //空のmap（この場合stringからintへの対応）
12
13 /*
14 * 要素の追加
15 * おそらくメソッドを使ったほうが早いが、めんどくさいので[]演算子を使う
16 */
17 m["one"] = 1;
18 m["two"] = 2;
19 m["three"] = 3;
20
21 /*
22 * 要素へのアクセス
23 */
24 cout << m["two"] << endl;
25
26 /*
27 * 要素の削除
28 * m.erase(key);
29 */
30 m.erase("one");
31
32 /*
33 * mapの要素数
34 * m.size();
35 */
36 cout << "m contains " << m.size() << " elements" << endl;
37
38 /*
39 * 要素の検索
40 * m.find(key);
41 * keyが存在しない場合に、mapの最後尾へのイテレータが返ってくるので、
42 * keyの有無を確認する場合に使える
43 */
44 if (m.find("one") == m.end())
45 {
46 cout << "one does not exist as a key" << endl;
47 }
48
49 /*
50 * 要素の列挙
51 * イテレータを使用して、mapの要素を列挙する
52 */
53 m["five"] = 5;
54 m["four"] = 4;
55 m["ten"] = 10;
56 m["eight"] = 8;
57 map<string,int>::iterator it; //イテレータの宣言
58 for (it = m.begin(); it != m.end(); ++it)
59 {
60 cout << it->first << " -> " << it->second << endl; //ポインタのように使う
61 }
62
63 return 0;
64 }
stack,queue,priority_queue
- スタック、キュー、優先度付きキュー
- 主な用途
- そのままスタック、キュー、優先度付きキューとして
- 使い方
1 #include <iostream>
2 #include <stack>
3 #include <queue>
4 using namespace std;
5
6 int main() {
7 /**
8 * stack<>,queue,<>priority_queue<>の宣言
9 */
10 stack<int> st;
11 queue<int> qu;
12 priority_queue<int> pqu_desc; //デフォルトでは降順
13 priority_queue<int, vector<int>, greater<int> > pqu_asc; //昇順のpriority_queue
14
15 /*
16 * 要素の追加
17 * push(val);
18 */
19 st.push(1);
20 st.push(2);
21 st.push(3);
22
23 qu.push(1);
24 qu.push(2);
25 qu.push(3);
26
27 pqu_desc.push(2);
28 pqu_desc.push(3);
29 pqu_desc.push(1);
30
31 pqu_asc.push(2);
32 pqu_asc.push(3);
33 pqu_asc.push(1);
34
35 /**
36 * 一番上の要素にアクセス
37 * st.top();
38 * qu.front();
39 * pqu_desc.top();
40 *
41 * 一番上の要素を取り除く
42 * pop();
43 *
44 * 要素が空か判定（空ならtrue）
45 * empty();
46 */
47 cout << "stack (First In Last Out)" << endl;
48 while (!(st.empty()))
49 {
50 cout << st.top() << endl;
51 st.pop();
52 }
53
54 cout << "queue (First In First Out)" << endl;
55 while (!(qu.empty()))
56 {
57 cout << qu.front() << endl;
58 qu.pop();
59 }
60
61 cout << "priority_queue (DESC)" << endl;
62 while (!(pqu_desc.empty()))
63 {
64 cout << pqu_desc.top() << endl;
65 pqu_desc.pop();
66 }
67
68 cout << "priority_queue (ASC)" << endl;
69 while (!(pqu_asc.empty()))
70 {
71 cout << pqu_asc.top() << endl;
72 pqu_asc.pop();
73 }
74 return 0;
75 }
algorithm
- イテレータを使った各種アルゴリズムの実装
- 主な用途
- max,min関数、sortなど
- 使い方
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 using namespace std;
5
6 int main() {
7 int array[8]={4,7,1,2,6,5,8,3};
8 vector<int> v;
9 for (int i=0; i<8; i++)
10 {
11 v.push_back(array[i]);
12 }
13 /**
14 * min,max関数
15 */
16 cout << min(5,10) << endl;
17 cout << max(5,10) << endl;
18
19 /**
20 * 区間の中で最大/最小の値のイテレータを返す
21 * max_element(from, to)
22 * min_element(from, to)
23 * 区間の最初のイテレータ（ポインタ）と、最後（ソートする最後の要素の次）のイテレータを指定する。
24 */
25 cout << *(max_element(array, array + 8)) << endl;
26 cout << *(min_element(v.begin(), v.end())) << endl;
27
28 /**
29 * 値を（破壊的に）ソートする
30 * sort(from, to(, comp))
31 * 区間の最初のイテレータと最後のイテレータ（と比較関数のポインタ）を指定する。（デフォルトは昇順）
32 */
33 sort(array, array + 8);
34 cout << "sort array" << endl;
35 for (int i=0; i<8; i++)
36 {
37 cout << array[i] << " ";
38 }
39 cout << endl;
40
41 cout << "sort vector" << endl;
42 sort(v.begin(), v.end()); //vectorもok
43 for (int i=0; i<v.size(); i++)
44 {
45 cout << v[i] << " ";
46 }
47 cout << endl;
48
49 cout << "sort array (DESC)" << endl;
50 sort(array, array + 8, greater<int>()); //降順にする
51 for (int i=0; i<8; i++)
52 {
53 cout << array[i];
54 }
55 cout << endl;
56
57 /*
58 * stringのソート
59 * ASCIIコードでソートされることに注意
60 */
61 cout << "sort string" << endl;
62 string str = "gfedcbagfedcba";
63 sort(str.begin(), str.end());
64 cout << str << endl;
65
66 return 0;
67 }
next_permutation
- 順列を生成する関数
- 使い方
1 #include <iostream>
2 #include <vector>
3 #include <string>
4 #include <algorithm>
5
6 using namespace std;
7
8 int main(){
9 /*
10 * 配列のnext_permutation
11 * next_permutationを実行すると、配列の中身が辞書順で次の順列になる
12 * 一番最後の順列でnext_permutationを実行すると、一番初めの順列に戻る
13 * その際の関数の返り値だけfalseであるので、次のようにして全順列を列挙できる
14 */
15 int arr[3]={0,1,2};
16 do {
17 cout << arr[0] << "," << arr[1] << "," << arr[2] << endl;
18 } while (next_permutation(arr ,arr + 3));
19 cout << endl;
20
21 /*
22 * vectorのnext_permutation
23 */
24 vector<int> v;
25 for (int i=0; i<3; i++)
26 {
27 v.push_back(i);
28 }
29 do {
30 cout << v[0] << "," << v[1] << "," << v[2] << endl;
31 } while (next_permutation(v.begin() ,v.end()));
32 cout << endl;
33
34 /*
35 * stringのnext_permutation
36 */
37 string str="ABC";
38 do {
39 cout << str << endl;
40 } while (next_permutation(str.begin() ,str.end()));
41
42 return 0;
43 }