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

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

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

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

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

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

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

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)
}