スタンダード・テンプレート・ライブラリ.
テンプレートを使ったライブラリとか.
ここに分類すべきでない気もするけれど, いろんなものの基本になってるのが, iterator.
ここでの説明は割と語弊があるというか, 真実でない事も含むが, まぁだいたいそんな感じと思っていてもそんなに問題ないという感じ.
日本語では反復子とか言う.
要素を指していて, ++で次, --で前の要素に移り, 単項の*でその要素自体にアクセスする.
ポインタに似てる.
#include <algorithm> とかすると, イテレータを使ったいくつかのアルゴリズムを使える.
例えば,
- int data[10] = {2, 1, 3, 7, 6, 0, 9, 4, 5, 8};
- sort(data, data+10);
でソート出来る.
後述するvectorとか使うなら,
- vector<int> v;
- // vに対して色々操作して, 要素入れたりとかする.
- sort(v.begin(), v.end());
STLコンテナは, 基本的に, begin() で最初の要素を指すイテレータ, end() で最後の要素の後ろを指すイテレータが取れる.
つまり, v[0] == *v.begin() で, v[v.size()-1] == *(v.end()-1) 的な関係になっている.
ややこしいが, ++で前の要素を指し, --で後ろの要素を指すという, 逆順のイテレータもあって, rbegin() で一番後ろ, rend() で一番前の前を指すイテレータが取れる.
これで何が便利かというと,
- vector<int> v;
- // vにいろいろ操作する
- sort(v.rbegin(), v.rend());
で, vを逆順ソート出来たりするところである.
他にもいくつかのアルゴリズムが使えるので, 詳しくはリンクの所とか, ググったりとかしてください.
よく使うのは, ソート済みのものを二分探索する, upper_bound, lower_boundとか, next_permutationとか.
よく使う.
pair<T, U> で型Tと型Uのペアを型にした感じのものが扱える.
first と second で要素にアクセス出来る.
要素間には, 大小関係が定義されていて, a < b は (a.first < b.first) or (*1)と同値.(すなわち, 辞書順).
ソートとかするときに便利.
make_pair(a, b) で, pair<aの型, bの型> なる型の, first == a; second == b になるペアを作れる.
- #include<utility>
- using namespace std;
- int main(void){
- pair<string, int> b("foo", 20);
- cout << b.first << ", " << b.second;
- b.first = "bar";
-
- typedef pair<int, int> pii; //pair<int, int> を pii 型として定義しなおした
- pii a(1, 2), b(3, 4);
- pii c = make_pair(5, 6);
- }
データを格納するやつら. リンクのProgramming Placeとか見ると良い. 一応超基本的な所だけ書いておく.
配列に似た何か.
動的配列とか言われたりするみたい.
要素の個数を最初にしていしなくてもよい配列と思えば, 大体あっている.
普通の配列よりは遅いので, 時間がシビアな時は配列に書き換えた方がよい.(が, あんまり気にしないで大丈夫)
コピーとかはなるべくしない方がよい.
ランダムアクセスと, 最後に要素を追加する / 最後の要素を削除する操作が, 比較的高速に出来る.
- #include <vector> // こいつが必要
- #include <iostream>
- using namespace std; // 本当は std::vectorだが, これでvectorだけで良くなる.
- int main(void){
- vector<int> v; //中身がint型のvector
- vector<int> v1(10); //要素が10個すでにあるvector(要素は0で初期化されている)
- vector<int> v2(10, -1); //要素が10個で, 全部-1なvector
- vector<int> v3(v1.begin(), v1.end()) // v1と中身が同じvector
- int data[3] = {2, 1, 3};
- vector<int> v4(data, data+3); //中身が2, 1, 3なvector
-
- for(int i = 0; i < 10; ++i) v.push_back(i); // v1の末尾に0, 1, ..., 9を追加.
- for(int i = 0; i < v1.size(); ++i) cout << v[i] << ", "; // v1の要素を出力
- cout << endl;
- while(v1.size() != 0) v.pop_back(); //v1の要素を後ろから順に削除
-
- vector<string> vs; //要素がstring型のvector.
- vs.push_back("Hello");
- vs.push_back("world!");
- for(int i = 0; i < vs.size(); ++i) cout << vs[i] << ", ";
- cout << endl;
- return 0;
- }
とか.
配列の, 添字(v[0]の0みたいなやつ) が, 自然数でなくても良くなったバージョン的な感じ.
中身はともかくとして, 他の言語で連想配列とか, ハッシュとか, ハッシュマップとか言われているのと同じようなもの.
同じ添字に複数のアイテムを入れることは出来ない. (それが可能なmultimapというのもあるが, 僕は使ったことない)
- #include <map>
- #include <iostream>
- using namespace std; //mapもstd::map.
- int main(void){
- map<string, int> msi; //添字がstringで, 要素がintなmap
- msi["hoge"] = 0;
- msi["foo"] = 1;
- msi.insert(pair<string, int>("fizz", 2)); //こんな要素の追加のしかたもある.(pairの項を見よ)
- cout << msi.count("hoge") << endl; // "hoge" がキーになっている要素は1つあるので, 1.(mapは1か0しか返さないはず)
- cout << msi.count("aaa") << endl; // 0になる.
- for(map<string, int>::iterator it = msi.begin(); it != msi.end(); ++it) { //map<string, int> のイテレータは, map<string, int>::iterator型.
- cout << (*it).first << ": " << (*it).second << endl; //mapのイテレータは, firstにキー, secondに値を格納している. (pairの項を見よ)
- }
- }
mapのイテレータによるアクセスでは, 常に順序がソート順になっている.
基本的な操作は, 要素数をnとして, O(log n) なので, ちょっとだけ遅いが, そんなに気にする程度ではない.
キーになるクラスには, 大小関係が定義されている(具体的には, 全順序関係で, operator<が定義されている) 必要がある.
集合型.
mapと同様, 常に中身はソートされている.
xを要素として含むか否か, 要素の追加, 削除が出来る.
- #include<set>
- #include<iostream>
- using namespace std; //setもstd::set
- int main(void){
- set<int> s;
- s.insert(0); //sに0が追加される
- s.insert(1); //sに1が追加される
- cout << s.count(2) << endl; // 0
- cout << s.count(0) << endl; // 1
- if(s.count(1)) s.insert(10); //sが1を含むなら, sに10が追加される
- s.erase(0); //0を削除する
- }
mapと同じく, 基本的な操作はO(log n).
要素のクラスには, 大小関係が定義されている(具体的には, 全順序関係で, operator<が定義されている) 必要がある.
