C++ STLのContainersとAlgorithms

(2020-01-04)

STL(Standard Template Library)はC++の標準ライブラリ。 その名の通りtemplateで実装され、様々な型で使えるようになっている。

// https://github.com/microsoft/STL/blob/1e8b8d4eef4b2dddeb7533c5231c876383bd0ea6/stl/inc/algorithm#L3501
template <class _RanIt, class _Pr>
void sort(const _RanIt _First, const _RanIt _Last, _Pr _Pred) { // order [_First, _Last), using _Pred
    _Adl_verify_range(_First, _Last);
    const auto _UFirst = _Get_unwrapped(_First);
    const auto _ULast  = _Get_unwrapped(_Last);
    _Sort_unchecked(_UFirst, _ULast, _ULast - _UFirst, _Pass_fn(_Pred));
}

以下の例はC++14で、

$ g++-8 -dM -E -x c++  /dev/null | grep -F __cplusplus
#define __cplusplus 201402L

全部入りHeader bits/stdc++.h をincludeし、std:: を省略している。

#include <bits/stdc++.h>
using namespace std;

Containers

データを保存するオブジェクト。

vector

可変長配列。ランダムアクセスが可能。末尾の挿入/削除はO(1)で、それ以外はO(n)。

vector<int> vec = {3, 1, 2, 4};
vec.erase(vec.begin() + 2);
sort(vec.rbegin(), vec.rend());
vec.insert(vec.begin(), 5);
vec.push_back(6);
for (int i = 0; i < vec.size(); i++)
{
    cout << vec[i] << endl; // => 5 4 3 1 6
}

list

双方向連結リスト。メモリ領域が連続しておらず、アクセスはO(n)かかるが、挿入/削除がO(1)でできる。

list<int> ls = {3, 1, 2, 4};
ls.erase(ls.begin());
ls.sort();
ls.insert(ls.begin(), 5);
ls.push_back(6);
for (list<int>::iterator it = ls.begin(); it != ls.end(); it++)
{
    cout << *it << endl; // => 5 1 2 4 6
}

set

集合。通常二分木で実装され、アクセスや挿入/削除するのにO(log n)かかる。

set<int> st = {3, 1, 2, 4};
st.erase(3);
st.insert(4);
st.insert(5);
if (st.find(5) != st.end())
{
    cout << "5 is found" << endl; // => 5 is found
}
if (st.find(6) != st.end())
{
    cout << "6 is found" << endl;
}
for (int x : st)
{
    cout << x << endl; // => 1 2 4 5
}

map

連想配列。通常二分木で実装され、オーダーははsetと同じ。

map<string, int> mp = {{"a", 3}, {"b", 4}, {"c", 5}};
mp.erase("b");
mp["d"] = 6;
if (mp.count("d") != 0)
{
    cout << "d is found" << endl; // => d is found
}
if (mp.count("e") != 0)
{
    cout << "e is found" << endl;
}
for (auto it = mp.begin(); it != mp.end(); it++)
{
    cout << it->first << ":" << it->second << endl; // a:3 c:5 d:6
}

unordered_map (hash map)

hash tableで実装されたmap。O(1)でアクセス/挿入/削除できる。

unordered_map<string, int> mp = {{"a", 3}, {"b", 4}, {"c", 5}};
mp.erase("b");
mp["d"] = 6;
if (mp.count("d") != 0)
{
    cout << "d is found" << endl; // => d is found
}
if (mp.count("e") != 0)
{
    cout << "e is found" << endl;
}
for (auto it = mp.begin(); it != mp.end(); it++)
{
    cout << it->first << ":" << it->second << endl; // d:6 c:5 a:3
}

deque (double-ended queue)

O(1)で両端に挿入/削除できるキュー。listとは異なり途中への挿入/削除はO(n)で、メモリ領域は連続していないがランダムアクセスできる。deckと発音するらしい。

deque<int> mp = {1, 2, 3};
cout << mp.back() << endl;  // => 3
cout << mp.front() << endl; // => 1
mp.pop_back();
mp.pop_front();
mp.push_back(4);
mp.push_front(5);
for (int i = 0; i < mp.size(); i++)
{
    cout << mp[i] << endl; // 5 2 4
}

priority_queue

入れた順ではなく優先度の高い順で取り出されるqueue。通常二分ヒープで実装される。 二分ヒープは子のノードが親以上(あるいは以下)の値を持つ二分木で、先頭の取り出しはO(1)だが他は基本setと同じ。 単にヒープと呼ぶこともあってメモリのヒープ領域と関係があるのかと思って調べてみたが、少なくとも今はないらしい。

デフォルトの比較関数はless(降順)。

vector<int> vec = {3, 1, 2, 4};
priority_queue<int> Q(vec.begin(), vec.end());
Q.push(2);
while (!Q.empty())
{
    cout << Q.top() << endl; // 4 3 2 2 1
    Q.pop();
}

テンプレートパラメータでgreater(昇順)や自作の比較関数を指定することができる。 lambdaを使う場合、テンプレートパラメータにdecltype()で取った型を渡した上で、コンストラクタ引数に渡す必要がある。

priority_queue<int, vector<int>, greater<int>> Q2(vec.begin(), vec.end());
Q2.push(2);
while (!Q2.empty())
{
    cout << Q2.top() << endl; // 1 2 2 3 4
    Q2.pop();
}

auto compare = [](string a, string b) { return a.size() < b.size(); };
priority_queue<string, vector<string>, decltype(compare)> Q3(compare);
Q3.push("AAAA");
Q3.push("AAA");
Q3.push("A");
while (!Q3.empty())
{
    cout << Q3.top() << endl; // AAAA AAA A
    Q3.pop();
}

tuple

異なる型の値を格納できる。

tuple<int, string> x = make_tuple(1, "aaa");
printf("%d %s\n", get<0>(x), get<1>(x).c_str());

// C++17-
// x = {2, "bbb"};
// auto [ num, str ] = x; 
// printf("%d %s\n", num, str.c_str()); 

Algorithm

for_each

値を書き換えることもできる。

vector<int> vec = {3, 1, 2, 4};
for_each(vec.begin(), vec.end(), [](int &x) { x *= 2; });
for_each(vec.begin(), vec.end(), [](int x) { cout << x << endl; }); // => 6 2 4 8

sort

priority_queueと同様デフォルトの比較関数はless

vector<string> vec = {"AAAA", "BBB", "CC", "D"};
sort(vec.begin(), vec.end(), [](string a, string b) { return a.size() < b.size(); });
for_each(vec.begin(), vec.end(), [](string &x) { cout << x << endl; }); // D CC BBB AAAA

binary_search, lower_bound, upper_bound

二分探索する。事前にソートしておく。binary_search()は存在するかどうかを返し、 lower_bound()はそれ以上の値が最初に登場する位置のiteratorを、upper_bound()はそれより大きい値が最初に登場する位置のiteratorを返す。

vector<int> vec = {5, 6, 9, 3, 8, 7};
sort(vec.begin(), vec.end());
if (binary_search(vec.begin(), vec.end(), 6)) {
    cout << "found" << endl; // found
} else {
    cout << "not found" << endl;
}
auto iter = lower_bound(vec.begin(), vec.end(), 6);
cout << *iter << endl; // 6
iter = upper_bound(vec.begin(), vec.end(), 6);
cout << *iter << endl; // 7
iter = upper_bound(vec.begin(), vec.end(), 4);
cout << *iter << endl; // 5

copy

指定した範囲の値を順に代入していく。 inserter()back_inserter() は代入する代わりに引数の .insert().push_back() を呼ぶoutput iteratorを生成する。

vector<int> vec = {3, 1, 2, 4};
copy(vec.begin(), vec.end(), back_inserter(vec));
set<int> st;
copy(vec.begin(), vec.end(), inserter(st, st.end()));
for_each(vec.begin(), vec.end(), [](int x) { cout << x << endl; }); // => 3 1 2 4 3 1 2 4
for_each(st.begin(), st.end(), [](int x) { cout << x << endl; });   // => 1 2 3 4

参考

Standard Template Library - Wikipedia

C++ STL | ++C++; // 未確認飛行 C

[C++] STLの型の使い分け - Qiita

cpprefjp - C++日本語リファレンス

そろそろstd::dequeについて語ろうか - kikairoya’s diary