My STL cheatsheet


一覧、逆引き向け。
サンプルはclang6.1.0(-std=c++1y)で動作確認。

## コンテナ
* 配列: array(固定長配列), vector(可変長配列), deque(フラグメンテーションを許した可変長配列)
* リンクリスト: list(双方向リンクリスト), forward_list(単方向リンクリスト)
* vector or deque のラッパ: queue, priority_queue, stack
* 二分探索木: set, multiset, map, multimap
* ハッシュテーブル: unordered_set, unordered_multiset, unordered_map, unordered_multimap
* basic_string

priority_queueは\<queue>に、multi*はmultiを外した名前のヘッダに入っている。

## イテレータ
InputIterator, OutputIterator <- ForwardIterator <-BidirectionalIterator <- RandomAccessIterator

* begin(), end() : ふつうのイテレータを返す
* cbegin(), cend() : const_iteratorを返す
* rbegin(), rend() : reverse_iteratorを返す
* crbegin(), crend() : const_reverse_iteratorを返す

## コンテナ操作
以下、xは値、argsは初期化パラメータ群、posはイテレータ、nは個数、iはインデクス、pairは(key, value)のペア。戻り値は基本iteratorだが、(重複不可な)map, setへのinsertだけはiteratorと成否boolのpairが返されるので注意。

### 追加

* push_front(x), emplace_front(args) : deque, list, forward_list
* push_back(x), emplace_back(args) : vector, deque, list
* insert(pos, x), insert(pos, n, x), emplace(pos, args) : vector, deque, list
* insert_after(pos, x), insert_after(pos, n, x), emplace(pos, args) : forward_list
* *pair\<iter, bool>* insert(x), insert(pos, x) : set, unordered_set
* *pair\<iter, bool>* insert(pair), insert(pos, x) : map, unordered_map
* insert(x), insert(pos, x) : multiset, unordered_multiset
* insert(pair), insert(pos, pair) : multimap, unordered_multimap

* push(x), emplace(args) : queue
* push(x), emplace(args) : priority_queue, stack

### 参照
* front() : forward_list, list, deque, vector, array, basic_string, queue
* top() : priority_queue, stack
* back() : list, deque, vector, array, basic_string
* [i], at(i) : vector, array, deque, basic_string
  * []は範囲外アクセスに対する動作が未定義。atはstd::out_of_range例外を投げる。
* [key], at(key) : map, unordered_map
  * []は暗黙のうちに拡張を行い、atはstd::out_of_range例外を投げる。

### 削除
* erase(pos), erase(first, last) : all bat queue, priority_queue, stack
* erase(key) : set, unordered_set, map, unordered_map
* erase_after(pos), erase_after(pos, last) : forward_list
* pop_front() : forward_list, list, deque
* pop_back() : all but queue, priority_queue, stack
* pop() : queue, priority_queue, stack

pop系はvoid型なので注意。

### サイズ参照・操作
* size() : all
* resize(n), resize(n, x) : deque, forward_list, list, vector, basic_string
* clear() : all
* empty() : all

### 領域確保
reserve(n) : vector, basic_string
shrink_to_fit() : vector, deque, basic_string

### C配列への変換
* c_str(), data() : basic_string, array, vector

## アルゴリズム
* for_each(first, last, function)
* fill(first, last, x)
* fill_n(first, n, x)
  * array はメンバ関数としてfill(x)を持つ。
* replace(first, last, old_value, new_value)
* replace_if(first, last, pred, new_value)
* reverse(first, last)
* reverse_copy(first, last, dest_iterator)
* reverse() : forward_list
* random_shuffle(first, last), random_shuffle(first, last, random_number_generator)
* random(first, last, random_number_generator)
* sort(first, last), sort(first, last, comp)
* stable_sort(first, last), stable_sort(first, last, comp)
* partial_sort(first, middle, last)
* partial_sort(first, middle, last, comp)
  * forward_list, list はメンバ関数としてsort()を持つ。
* count(first, last, x)
* count_if(first, last, pred)
* find(first, last, x)
* find_if(first, last, pred)
* find_if_not(first, last, pred)
* find_first_of(first1, last1, first2, last2)
* find_end(first1, last1, first2, last2)
  * set, unordered_set, map, unordered_mapはメンバ関数として二分探索またはハッシングに基づくfind(x), *pair\<first, last>* equal_range(x)を持つ。
* copy(first, last, dest), copy(first, n, dest)
* copy_if(first, last, dest, predicate)
* copy_backward(first, last, dest) 逆順にしながらコピーするわけではく、末尾からコピーを始める。
* transform(first, last, dest, op)
* transform(first1, last1, first2, dest, op)
* remove(first, last, value)
* remove_if(first, last, pred)
* unique(first, last), unique(first, last, pred)
* unique_copy(first, last, dest), unique_copy(first, last, dest, pred)
  * forward_list, listはメンバ関数としてunique()を持つ。
* is_sorted(first, last), is_sorted(first, last, comp)
* is_sorted_until(first, last), is_sorted_until(first, last, comp) ソート順を破った最初の位置を返す
* *bool* binary_search(first, last, x), binary_search(first, last, x, comp) boolを返すので注意
* lower_bound(first, last, x) lower_boundは指定された値"以上"の値が初めて現れた位置のイテレータを返す
* upper_bound(first, last, x) upper_boundは指定された値を"超える"値が初めて現れた位置のイテレータを返す
    if(lit != vc.end() && lit != uit)
* all_of(first, last, pred) AND条件
* any_of(first, last, pred) OR条件
* none_of(first, last, pred) !any_of
* *iter* min_element(first, last), min_element(first, last, comp)
* *iter* max_element(first, last), max_element(first, last, comp)
* *pair\<iter, iter>* minmax_element(first, last), minmax_element(first, last, comp)
* accumulate(first, last, init), accumulate(first, last, init, binary_op) なぜか\<numeric>ヘッダにあるので注意
* set_union(first1, last1, first2, last2, dest), set_union(first1, last1, first2, last2, dest, comp) 和集合
* set_intersection(first1, last1, first2, last2, dest), set_intersection(first1, last1, first2, last2, dest, comp) 積集合
* set_difference 差集合
* set_symmetric_difference XOR
* next_permutation(first, last), next_permutation(first, last, comp) ソートしてから始めると順列の全列挙ができる

## サンプル
### predicate

```cpp:copy_if.cpp
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> src = {0, 1, 2, 3};
  std::vector<int> dest;
  std::copy_if(src.begin(), src.end(), std::back_inserter(dest), [](int i) {return i%2 != 0;}); // 奇数を検出するpredicate
  std::for_each(dest.begin(), dest.end(), [](int i) {std::cout << i << std::endl;}); // 1, 3
}
```

### comparator

```cpp:comparator.cpp
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> vec = {3, 0, 2, 1};
  std::sort(vec.begin(), vec.end(), [](int a, int b) {return (a&1) < (b&1);}  ); // 最下位bitのみ見る比較関数
  std::for_each(vec.begin(), vec.end(), [](int i){std::cout << i << std::endl;}); // 0, 2, 3, 1
}
```


### binary_search

```cpp:binary_search.cpp
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> vec = {0, 1, 2, 2}; // 当然、ソートされていることが前提
  std::cout << std::boolalpha << std::binary_search(vec.begin(), vec.end(), 1) << std::endl; // true : binary_search は bool なので注意
  std::cout << std::lower_bound(vec.begin(), vec.end(), 2) - vec.begin() << std::endl; // 2 (先頭からの要素番号に相当)
  std::cout << std::upper_bound(vec.begin(), vec.end(), 2) - std::lower_bound(vec.begin(), vec.end(), 2) << std::endl; // 2 (値2の個数)
}
```

### binary_ops

``` cpp:accumulate.cpp
#include <iostream>
#include <vector>
#include <numeric>

int main() {
  std::vector<int> vec = {0, 1, 2};
  int result = std::accumulate(vec.begin(), vec.end(), 0, [](int a, int b){return a^b;}); // bitwise XOR
  std::cout << static_cast<std::bitset<3>>(result) << std::endl; // 011 = 000 ^ 001 ^ 010
}
```

### minmax

``` cpp:minmax.cpp
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> vec = {0, 1, 2};
  auto minmax = std::minmax_element(vec.begin(), vec.end());
  std::cout << *(minmax.first) << ", " << *(minmax.second) << std::endl; // 0, 2
}
```

### priority_queue

```cpp:pq.cpp
#include <iostream>
#include <queue>

int main() {
  std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
  pq.push(1);
  pq.push(3);
  pq.push(2);
  while(!pq.empty()) {
    std::cout << pq.top() << std::endl; // 1, 2, 3
    pq.pop();
  }
}
```

### next_permutation

```cpp:permutation.cpp
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> vec = {0, 1, 2}; // 初期状態ではソートされていることを保証すること
  do {
    for(auto x : vec) { std::cout << x << ", ";};
    std::cout << std::endl;
  }while (std::next_permutation(vec.begin(), vec.end())); // (0, 1, 2), (0, 2, 1), ..., (2, 1, 0)
}
```