Help us understand the problem. What is going on with this article?

My STL cheatsheet

More than 3 years have passed since last update.

一覧、逆引き向け。
サンプルは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)
}
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした