icon

sambaiz-net
github
goodreads
google maps
board game arena
aws golang machinelearning etl python kubernetes web fluentd gcp ios ...

C++ STLのContainersとAlgorithms

c++

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

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

各Containerにアクセス/挿入/削除する際の計算量

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
}

素の配列は初期化やコピーのためにmemsetやmemcpyといったバイトレベルの関数を用いるが、 STLのContainerは次のようなインタフェースのコンストラクタを提供している。

// initialize
int arr[10][10];
memset(arr, 0, sizeof(arr)); // Fill bytes by 0 (as a result 0 are assigned)
cout << arr[9][9] << endl; // => 0

vector<vector<int>> vec(10, vector<int>(10, 0)); // 10x10
cout << vec[9][9] << endl; // => 0

// copy
arr[9][9] = 100;
int arr2[10][10];
memcpy(arr2, arr, sizeof(arr));
cout << arr2[9][9] << endl; // => 100

vec[9][9] = 100;
vector<vector<int>> vec2(10);
for (int i = 0; i < 10; i++) vec2[i] = vector<int>(vec[i].begin(), vec[i].end());
cout << vec2[9][9] << endl; // => 100

list

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

list<int> ls = {3, 1, 2, 4};
ls.erase(ls.begin());
ls.sort(); // cannot call sort(list.begin(), list.end()) because list is not available to be random-accessed
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
}

C++ STLのmapやunordered_mapのkeyにstructを使えるようにする - sambaiz-net

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。 ランダムアクセスできる必要があるため非対応のlistは代わりにlist.sort()を呼ぶ。

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を返す。 つまり upper_bound() - lower_bound() すると同じ値の個数が分かる。それ以上の値が存在しない場合iteratorはend()を指す。

vector<int> vec = {1, 2, 3, 3, 3, 3, 3, 3, 4, 5};
cout << "binary search 3: " << binary_search(vec.begin(), vec.end(), 3) << endl; // 1 (TRUE)
auto upper = upper_bound(vec.begin(), vec.end(), 3);
auto lower = lower_bound(vec.begin(), vec.end(), 3);
cout << "upper 3 value: " << *upper << endl;      // 4
cout << "lower 3 value: " << *lower << endl;      // 3
cout << "found 3 num: " << upper - lower << endl; // 6
auto lower100EqEnd = lower_bound(vec.begin(), vec.end(), 100) == vec.end();
cout << "lower 100 == vec.end(): " << lower100EqEnd << endl; // 1 (TRUE)

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