C++のSTL標準ライブラリまとめ

業務で使うレベルのアルゴリズムは95%以上網羅されている気がする(知らんけど・・)(クソでか主語)

目次

・swap

・rand

・clock

・string

・vector

・min/max

・queue

・stack

・list

・deque

・priority_queue

・tuple

・set

・unordered_set

・map

・pair

・array

・sort

・reverse

・lower_bound

・assert

・count

・find

・next_permutation

・__builtin_popcount

・bitset

今日プロ向けSTL標準ライブラリ

swap

swap(a, b)で変数aとbの値を入れ替えられる

rand

ctimeをインクルードする

rand()

0以上2^31-1以下のランダムな整数を返す

srand((unsigned)time(NULL));

おまじないで、main関数の冒頭にこれをつけると実行ごとに乱数生成結果が変わる

clock

時間を計測する関数

clock()

プログラム実行開始から何単位時間経過したかを整数で返す関数

CLOCKS_PER_SEC：定数、環境によって1秒が何単位時間か異なるので、秒数を知りたいときに使える

string

s = s + t;

s += c：文字列sにchar型の文字cを連結する

s == t;

s.size();

s.substr(l)：文字列sのl文字目から最後の文字までの部分文字列を返す

s.substr(i, k)：i番目以降k文字を抽出して得られる文字列

s.find(t)：sの中に文字列tがあればその先頭のアドレスを返す．なければs.nopsを返却

s.replace(i, k, t)：i番目以降k文字を文字列tで置換する．tを空文字列にすれば削除の動作

s.insert(i, t)：i番目の文字の前に文字列tを挿入

vector：可変配列、動的に記憶域を確保

vector<int> a(5)

a.size()

a.front()

a.back()

a.push_back()：末尾に要素を追加、高速

a.pop_back()：末尾の要素を削除、高速

sortする時はsort(a, a+N)ではなく、sort(a.begin(), a.end())

sort(a.begin() + l, a.begin()+r)でソートする

reverseも同様

逆にソートしたい時は

sort(p.rbegin(), p.rend())という風にリバースイテレータを使う！

min/max

algorithmをインクルードする

複数の値の最小値、最大値を返す

min({a1,a2,,,,})：a1,,,,の中で最小のものを返す

queue

empty()

size()

front()

back()

push()

emplace()：直接構築で要素を追加

pop()：次の要素を削除

swap()：他のqueueオブジェクトと値を入れ替える

stack

push()

pop()

empty()

size()

top()

list：双方向リスト、片方向はforward_list

list<int> li;

list<int>::iterater p;

list<int>::reverse_iterater r;

li.push_front(); //先頭に挿入

li.front(); //先頭の要素を参照

li.pop_front(); //先頭の要素を削除

li.push_back(); //末尾に挿入

li.back(); //末尾の要素を参照

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

li.begin(); //最初の要素を指すイテレーター

li.end(); //末尾の次の要素を指すイテレーター

li.rbegin(); //逆順にした時の最初の要素を指すイテレーター

li.rend(); //逆順にした時の末尾の次の要素を指すイテレーター

li.insert(p, x); //pのさす要素の直前にｘを挿入

li.erase(p); //pの指す要素を削除

li.erase(p, q); //pの指す要素からqの指す要素まで削除

li.clear(); //リストの全要素を削除

*p; //イテレーターの指す要素

p++; //走査方向に向かって次の要素を指すイテレーター

p--; //走査方向に向かって前の要素を指すイテレーター

for (p=li.begin(); p!=li.end(); p++) { *p = ...} //前から走査

for (r=li.rbegin(); r!=li.rend(); r++) { *r = ...} //後ろから走査

deque：stackとqueueの両方の働きを持つ

deque<int> d;

d.push_front(); //先頭に挿入

d.front(); //先頭の要素を参照

d.pop_front(); //先頭の要素を削除

d.push_back(); //末尾に挿入

d.back(); //末尾の要素を参照

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

priority_queue：ヒープ

priority_queue<int> que; //最大値から出てくるヒープ

priority_queue< int, vector<int>, greater<int> > que; //最小値から出てくるヒープ

que.push(); //要素の追加

que.top(); //先頭をみる

que.pop(); //先頭を削除

tuple

３つ以上の要素からなる組みを持てる型

型v1, v2, v3,,vnを持つtuple型変数を定義したい場合

tuple<v1,v2,,vn> a;とかく

tuple型変数aのi個目の要素にアクセスしたい場合get<i>(a)とかく

set：平衡二分探索木を用いた集合、重複を許す場合はmultisetを使う

setに対する操作の計算量はO(logN)

set内では小さい順に要素が並んでいる

イテレーターitrに対して、itr++とすると、set内の１つ大きい要素を指すようになる

a.begin()でset内の先頭のイテレーター、a.end()で末尾のイテレーターを指す

set<int> s;

multiset<int> ms;

s.insert()

s.erase()

a.erase(x)：集合aから要素xを削除する

a.erase(y)：集合aからイテレータyの要素を削除する

s.find()：発見したらその要素へのイテレータを返す

s.count()：要素の数を返す

s.empty()：空ならtrue

s.size()

s.clear()

a.lower_bound(x)：集合aの中でx以上である最小の要素を指すイテレーターを返す

unorderd_set：ハッシュテーブルで管理される集合、基本こっちを使う

unordered_set<int> s;

unordered_multiset<int> ms;

s.insert(); //要素の追加

s.erase(); //要素の削除

s.find(); //発見したらその要素へのイテレータを返す

s.count(); //要素の数を返す

s.empty(); //空ならtrue

s.size(); //要素数を返却

s.clear(); //空にする

map：連想配列、任意のキーでアクセスできる、アクセス時間はO(logn)

どんな番地にも書き込める無限配列のようなデータ構造

map<string, int> m：キーがstring型，要素がint型

m.find(10)：要素へのイテレーターを返す．なければm.end()を返却

m.erase(p)：イテレーターの指す要素を削除

a.clear()：マップaを初期化

最初は全て値が0で初期化

アクセスにかかる計算量はO(logN)

map<string,int>::iterator p：イテレーターを用いた走査

for (p=semester.begin(); p!=semester.end(); p++) {

cout << p->first << ": " << p->second << std::endl; //firstがキー，secondが値

型 1. ランダム アクセスの 時間 2. 挿入・削除の 時間 3. 検索の時間 4. メモリ量

vector O(1) O(1)（末尾） O(n)（他） O(n) 0～ST

deque O(1) O(1)（先頭か末尾） O(n)（他） O(n) 2*ST/512*SP

list O(n) O(1) O(n) 2*SP

forward_list O(n) O(1) O(n) SP

unordered_set unordered_multiset 不可能 O(1) O(1) 2*SP

set multiset 不可能 O(log n) O(log n) 3*SP

unordered_map unordered_multimap O(1) O(1) O(n) 2*SP

map multimap O(log n) O(log n) O(n) 3*SP

pair：値をペアで保存

２つの異なる型を１つの変数で持つことができる組みを表現できる型

１つ目の要素はa1.first,２つ目はa1.secondで表す

pair<v1, v2> a;という感じで定義する

pair<int int> p;

p.first;

p.second;

array：固定長配列

通常配列では、size()やback()などが使えないが、それらを使いたいが、サイズは固定でよくvectorを使うまでもない時に利用する

sort：STLのソートは簡単にかけて超高速O(nlogn)

配列のある区間を小さい順などに並び替える

計算量はO(NlogN)

string型のソートでは、辞書式順列で早い方が小さいとみなされる

greater<int>()を使う場合はfunctionalおもインクルード

sort(a,b,cmp)でcmpに近い順にソートしてくれる！

reverse

配列のある区間を逆順に並び替える

計算量は0(N)

文字列を逆順にしたい場合はreverse(str.begin(),str.end())

二分探索：

lower_bound

二分探索ができる関数

aがl番目からr-1番目の要素が小さい順にソートされていたとする

計算量はO(logN)

binary_search(vc.begin(), vc.end(), x); //trueかfalseを返す

lower_bound(vc.begin(), vc.end(), x); //x以上の値が初めて現れる位置のイテレータを返す

upper_bound(vc.begin(), vc.end(), x); //xより大きい値が初めて現れる位置のイテレータを返す

equal_range(vc.begin(), vc.end(), x); //上記２カ所のイテレータのペアを返す

assert

条件を決めて、それを満たさない場合ランタイムエラーを起こす関数

デバッグに使える

assert(条件)とかくことで、条件を満たさない場合にランタイムエラーを起こす関数

count

配列やvectorのある区間の要素の中でxがいくつ含まれるかを返す関数

vectorの場合count(v.begin(), v.end(), x)と書けば良い

計算量はO(r-l)

find

配列やvectorのある区間の要素の中にxが含まれるか含まれる場合はどこにあるかを返す関数

find(a+l, a+r,x)は以下のイテレータを返す

vectorの場合はfind(a.begin(), a.end(),x)とすると、xが含まれない場合a.end()を返す

初めて現れるいちを知りたい場合は、find(a+l, a+r, x)-aと書けば良い

next_permutation

次の順列を生成する関数

while文は、次の順列が存在しない時（それより辞書順で大きいような順列が存在しない時）ぬける

次の順列の生成するのに計算量O(N)

__builtin_popcount

整数xを二進数で表した時、1であるようなビットの個数を返す関数

この関数はgccでは利用可能ですがVisualStudio2019などでは使えない

__builtin_popcountll(x)はlong long型に対応している

bitset

ビット集合を表す型である

N桁の二進数だと思うことができる

ビット演算を高速に行いたい時などに使える

a = (a∧b)など、ビット演算を考えられる

a.set(x)：aのx桁目を1に変更する

a.reset(x)：aのx桁目を0に変更する

使い方

1 バブルソートの実装(swap)

2 高速なソート(sort)

3 バグらない二分探索(lower_bound)

4 グラフを隣接リストで持つ(vector)

5 幅優先探索(queue, pair)

6 最短経路問題・ダイクストラ法(priority_queue)

7 乱択アルゴリズム・モンテカルロ法(rand)

8 O(N*N!)の順序全探索(next_permutation)

9 部分和問題の高速化(bitset)

10 実行時間を計測する(clock)

11 問題の制約が本当にあっているか確認する(assert)