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