LoginSignup
8
8

More than 5 years have passed since last update.

@ktsujino(Kosuke Tsujino)

My STL cheatsheet

Last updated at Posted at 2015-04-30

一覧、逆引き向け。
サンプルは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)
}
8
8
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
8
8