はじめに
競技プログラミングで必須となるC++標準ライブラリのデータ構造（+α）について概要と使い方をシンプル（サンプルコード多め、文章の解説少なめ）にまとめています。
C++でコンテストに参加する際のメモ代わりになれば幸いです。
C++14 (GCC 5.4.1) を前提としていますので、その点ご了承お願いします。
C++でよく使うデータ構造
この記事では以下のデータ構造について紹介します。
- int, long long
- string
- pair
- tuple
- vector
- set
- multiset
- stack
- queue
- priority_queue
- deque
- map
- unordered_map
これらはbits/stdc++.hをインクルードしておけば使えます。
また、以下では簡単のため、using namespace std;をプログラム冒頭に記載しているものとして下記プログラム例ではstd::は省略します。
int, long long
int, long long で扱うことができる数字の範囲を記載しておきます。
intは2*10^9, long long は9*10^18程度が最大値となります。
| 型 | 値の範囲 |
|---|---|
| int | -2,147,483,648 ~ 2,147,483,647 |
| long long | -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 |
bit全探索やbitDPなどで必要なbit演算についてもまとめておきます。
bit演算については下記の記事に非常に丁寧にまとめられています。
ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜
クイックリファレンスのために記載した下の表はこちらの記事から引用させていただきました。
| やりたいこと | 実装 |
|---|---|
| ビット bit に i 番目のフラグが立っているかどうか | if (bit & (1<<i)) |
| ビット bit に i 番目のフラグが消えているかどうか | if (!(bit & (1<<i))) |
| ビット bit に i 番目のフラグを立てる | bit｜= (1<<i) |
| ビット bit に i 番目のフラグを消す | bit &= ~(1<<i) |
| ビット bit に何個のフラグが立っているか | __builtin_popcount(bit) |
| ビット bit に i 番目のフラグを立てたもの | bit｜(1<<i) |
| ビット bit に i 番目のフラグを消したもの | bit & ~(1<<i) |
| mask で表された部分のフラグをまとめて立てる | bit ｜= mask |
| mask で表された部分のフラグをまとめて消す | bit &= ~mask |
| mask で表された部分の情報のみを取り出したもの | bit & mask |
| mask で表された部分のどれかのフラグが立っているかどうか | if (bit & mask) |
| mask で表された部分のすべてのフラグが立っているかどうか | if ((bit & mask) == mask) |
string
//変数宣言（空）
string s;
//文字数を確認
cout << s.size() << endl; //0
s = "plan";
cout << s.size() << endl; //4
//先頭・末尾の文字を参照
cout << s.front() << " " << s.back() << endl; //p n
//文字列の結合
s += "et";
cout << s << endl; //planet
//末尾の文字を削除
s.pop_back();
cout << s << endl; //plane
s = "plan1plan";
//文字列を前方から検索
auto itr = s.find("lan");
if(itr != string::npos)cout << itr << endl;//1
else cout << "Nout Found" << endl;
//文字列を後方から検索
itr = s.rfind("lan");
if(itr != string::npos)cout << itr << endl;// 6
else cout << "Nout Found" << endl;
pair
概要・使いどころ
pairは異なる二つの値をペアで保持するデータ構造です。
ペアとなる二つの値は異なる型でも構いません。
pair単体では二つの要素を単にまとめたものであるため、mapなどのデータ型の要素として用いられる場合が多いです。
使い方
pair
//変数宣言
pair<int,int> p = make_pair(1,2);
//要素へのアクセス
cout << p.first << endl;//1
cout << p.second << endl;//2
//変数宣言
pair<int,string> p2 = make_pair(1,"No.1");
//要素へのアクセス
cout << p2.first << endl;//1
cout << p2.second << endl;//"No1"
tuple
概要・使いどころ
pairは2つの型の値を保持することができましたが、tupleを使うと2つ以上の型の値を保持することができます。
使い方
tuple
//3要素のtupleを作る
tuple<int, int, string> t1 = make_tuple(1,3,"first");
tuple<int, int, string> t2 = make_tuple(2,3,"second");
tuple<int, int, string> t3 = make_tuple(2,4,"third");
//0番目の要素を取得する
int& i = get<0>(t1);
cout << i << endl; //1
//大小比較は0番目の要素⇒1番目の要素⇒2番目の要素・・・の順番に行われる
//第0要素についてt1 < t2であるためtrue
if(t1 < t2)cout << "t1 < t2" << endl; //true
//第0要素は等しいが第1要素についてt2 < t3であるためtrue
if(t2 < t3)cout << "t2 < t3" << endl; //true
vector
概要・使いどころ
C++における動的配列です。
vector単体で使うと普通の配列ですが、vectorを重ねて多次元配列にしたり、
静的配列と組み合わせることもできます。
以下のコードではswapや全要素への走査(for(auto a : v))など、ほかのデータ構造に対しても使える関数も記載しています。
計算量
| 処理 | 計算量 |
|---|---|
| ソート | O(NlogN) |
| 各要素へのアクセス | O(1) |
| 全要素への走査 | O(N) |
| 要素の追加・削除 | 償却定数時間 |
使い方
vector
int n = 4;
//変数宣言（要素数0）
vector<int> v1;
cout << v1.empty() << endl;//1(TRUE)
//変数宣言&初期化（要素数n, 0で初期化）
vector<int> v2(n,0);
//値の代入
v2[0] = 1;v2[1] = 3;v2[2] = 2;v2[3] = 4;
cout << v2.size() << endl;//4
//末尾に要素を追加
v2.push_back(-1);
cout << v2.size() << endl;//5
//2次元配列の場合
vector<vector<int>> vv;
vv.push_back({1,2,3,4});
cout << vv[0][0] << " " << vv[0][1] << " " << vv[0][2] << endl;//1 2 3
//v1に含まれるすべての要素を走査
//mapやsetでも同じことができるので便利
for(auto v : v2)cout << v << " ";cout << endl;//1 3 2 4 -1
//末尾の要素を確認
cout << v2.back() << endl; //-1
//末尾の要素に代入
v2.back() = 0;
cout << v2.back() << endl; //0
//末尾の要素を削除
v2.pop_back();
cout << v2.size() << endl;//4
//昇順でソート
sort(v2.begin(),v2.end());
for(auto v : v2)cout << v << " ";cout << endl;//1 2 3 4
//要素の順番を逆にする
reverse(v2.begin(),v2.end());
for(auto v : v2)cout << v << " ";cout << endl;//4 3 2 1
reverse(v2.begin(),v2.end());
//b → 1, 2, 3, 4
//指定された要素以上が現れる最初の位置のイテレータを取得
//事前にソートしておく必要あり
//見つからない場合、itr == v2.end()がTRUE
auto itr = lower_bound(v2.begin(),v2.end(),3);
int index = itr - v2.begin();
cout << index << endl;//2
//指定された要素より大きい値が現れる最初の位置のイテレータを取得
itr = upper_bound(v2.begin(),v2.end(),3);
index = itr - v2.begin();
cout << index << endl;//3
//降順にソートされている場合のlower_bound, upper_bound
//降順にソート
sort(v2.begin(),v2.end(),greater<int>());
for(auto v : v2)cout << v << " ";cout << endl; //4 3 2 1
//指定された要素以下が現れる最初の位置のイテレータを取得
itr = lower_bound(v2.begin(),v2.end(),3,greater<int>());
index = itr - v2.begin();
cout << index << endl;//1
//指定された要素より小さい値が現れる最初の位置のイテレータを取得
itr = upper_bound(v2.begin(),v2.end(),3,greater<int>());
index = itr - v2.begin();
cout << index << endl;//2
v1.push_back(11);v1.push_back(12);v1.push_back(13);
//v1とv2を入れ替える
swap(v1,v2);
//vector同士の結合
v1.insert(v1.end(),v2.begin(),v2.end());
//以下は低速のためあまり使わないほうが良い
v2.insert(v2.begin()+2,99);//v[2]の位置に99を挿入（代入ではない）
v2.erase(v2.begin()+2);//v[2]の位置の要素を削除
二つの配列を対にしてソート
二つの異なる配列a, bについて、片方をソートしてもう一方をそれに合わせて並び替えるコードは以下のように書けます。
（こちらの記事を参考にさせていただきました。）
二つの配列を対にしてソート
#include<bits/stdc++.h>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define vecprint(v) rep(i,0,v.size()-1)cout << v[i] << " ";cout << endl;
using namespace std;
void sort2vectors(vector<int> &av, vector<int> &bv){
int n = av.size();
vector<int> p(n), av2(n), bv2(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int a, int b) { return av[a] < av[b]; });
for (int i = 0; i < n; i++) {
av2[i] = av[p[i]];
bv2[i] = bv[p[i]];
}
av = av2;
bv = bv2;
}
int main(){
vector<int> a = {1,3,2,4,5};
vector<int> b = {10,4,7,6,5};
//aを基準にa,bを昇順ソート
sort2vectors(a,b);
vecprint(a);//1 2 3 4 5
vecprint(b);//10 7 4 6 5
//bを基準にa,bを昇順ソート
sort2vectors(b,a);
vecprint(a);//3 5 4 2 1
vecprint(b);//4 5 6 7 10
return 0;
}
set
概要・使いどころ
setは集合を保持するデータ構造であり、要素の重複はなく、キーそのものが値となります。
競技プログラミングではフラグ的な使い方をされることもあります。
計算量
| 処理 | 計算量 |
|---|---|
| 値の検索 | O(log(N)) |
| 要素の追加・削除 | O(log(N)) |
使い方
set
//変数宣言（空集合）
set<int> s;
cout << s.empty() << endl;//1:TRUE
//変数宣言と同時に初期化
set<int> ss{3,1,4,5};
cout << ss.size() << endl;//4
//要素を追加
s.insert(3);s.insert(1);s.insert(5);
cout << s.size() << endl;//3
s.insert(1);
cout << s.size() << endl;//3（要素は重複しない）
//各要素へのアクセス
for(auto i=s.begin();i!=s.end();i++)cout << *i << endl;//1 3 5
//各要素へのアクセス（逆順）
for(auto i=s.rbegin();i!=s.rend();i++)cout << *i << endl;//5 3 1
//要素の削除
s.erase(3);
cout << s.size() << endl;//2
s.erase(100);//元から無い要素をeraseしても変化はない（エラーも吐かない）
cout << s.size() << endl;//2
s.insert(3);
//要素の検索
auto itr = s.find(3);
cout << *itr << endl;//3
//要素が見つからない場合はitr == s.end()
itr = s.find(99);
int a;
a = itr == s.end() ? 1 : 0;
cout << a << endl;//1
//2分探索
itr = s.lower_bound(3);
cout << *itr << endl; //3
itr = s.upper_bound(3);
cout << *itr << endl; //5
//集合の要素をすべて削除
s.clear();
multiset
概要・使いどころ
setは重複を許さない集合でしたが、multisetは重複を許す集合です。
おおよその使い方はsetと同じですが、要素の検索、削除等で若干使い勝手が異なります。
計算量
| 処理 | 計算量 |
|---|---|
| 値の検索 | O(log(N)) |
| 値の個数(count) | O(m+log(N))※mは要素の個数 |
| 要素の追加・削除 | O(log(N)) |
使い方
setと異なる点のみ記載します。
multiset
//変数宣言（空集合）
multiset<int> s;
//要素の挿入
s.insert(1),s.insert(3),s.insert(3),s.insert(4),s.insert(4),s.insert(5);
//各要素へのアクセス
for(auto i=s.begin();i!=s.end();i++)cout << *i << endl;//1 3 3 4 4 5
//要素数の確認
auto c = s.count(3);
cout << c << endl; //2
//要素の削除（重複している場合はすべて消す）
c = s.erase(3);
cout << c << endl; //2
for(auto i=s.begin();i!=s.end();i++)cout << *i << endl;//1 4 4 5
//要素の削除（重複している場合は1つだけ消す）
//集合にない要素を削除しようとするとエラーとなるため、eraseの前にfindしておく。
auto it = s.find(4);
if (it != s.end()) s.erase(it);
for(auto i=s.begin();i!=s.end();i++)cout << *i << endl;//1 4 5
stack
概要・使いどころ
LIFO (Last In, First Out) のデータ構造です。
一番最後に挿入された要素から取り出します。
山積みされた本を取り出すような動きをイメージすると良いでしょう。
スタック内の要素はソートされません。
要素はbackから挿入され、backから取り出します。
計算量
| 処理 | 計算量 |
|---|---|
| 先頭要素の参照 | O(1) |
| 先頭要素の追加・削除 | O(1) |
使い方
stack
//変数宣言
stack<int> st;
//stackに1→2→-1の順に要素を挿入
st.push(1);st.push(2);st.push(-1);
//現在スタックに入っている要素の数
cout << st.size() << endl;//3
//先頭の要素を参照する
cout << st.top() << endl;//-1
//先頭の要素を取り出す
st.pop();
//要素数が1減り、topが参照する要素も変わる
cout << st.size() << endl;//2
cout << st.top() << endl;//2
queue
概要・使いどころ
FIFO (First In, First Out) のデータ構造です。
入れた順に取り出す、一般的なキューです。
キュー内の要素はソートされません。
要素はbackから挿入され、frontから取り出します。
stackとの違いを理解しましょう。
計算量
| 処理 | 計算量 |
|---|---|
| 先頭・末尾要素の参照 | O(1) |
| 末尾要素の追加・削除 | O(1) |
使い方
queue
//変数宣言
queue<int> q;
//queueに1→2→-1の順に要素を挿入
q.push(1);q.push(2);q.push(-1);
//現在スタックに入っている要素の数
cout << q.size() << endl;//3
//先頭の要素を参照する
cout << q.front() << endl;//1
//末尾の要素を参照する
cout << q.back() << endl;//-1
//先頭の要素を取り出す
q.pop();
//要素数が1減り、topが参照する要素も変わる
cout << q.size() << endl;//2
cout << q.front() << endl;//2
priority_queue
概要・使いどころ
優先度付きキューと呼ばれるデータ構造です。
上述のqueueとは異なり、優先度付きキューは常にソートした状態でデータを保持します。
最大値・最小値を早く計算するのに優れているため、計算量を気にして最大・最小を計算するときによく使われるデータ型です。
計算量
| 処理 | 計算量 |
|---|---|
| 最大要素の参照 | O(1) |
| 要素の追加・削除 | O(log(N)) |
使い方
priority_queue
//変数宣言
priority_queue<int> q;//降順（デフォルト）
priority_queue<int,vector<int>,greater<int>> qq;//昇順
//queueに1→2→-1の順に要素を挿入
q.push(1);q.push(2);q.push(-1);
qq.push(1);qq.push(2);qq.push(-1);
//現在スタックに入っている要素の数
cout << q.size() << endl;//3
//先頭の要素を参照する
cout << q.top() << endl;//2
cout << qq.top() << endl;//-1
//先頭の要素を取り出す
q.pop();
//要素数が1減り、topが参照する要素も変わる
cout << q.size() << endl;//2
cout << q.top() << endl;//1
pairとpriority_queueを組み合わせる
以下のようにpriority_queueの要素にpairを使うこともできます。
その際には比較関数を自作しておくと、一つ目の要素(first)で比較したり二つ目の要素(second)を比較することができます。
をgreater>とすると、first同士の比較になります。
pairとpriority_queueを組み合わせる
#include <bits/stdc++.h>
using namespace std;
//あらかじめ比較関数を定義しておく
//下記はgreater<pair<int,int>>と同義
class CompareFirst
{
public:
bool operator()(pair<int,int> n1,pair<int,int> n2) {
return n1.first>n2.first; //>:降順 pairのfirst同士を比較する
}
};
int main(){
//変数宣言
priority_queue<pair<int,int>,//pairを要素にしてpriority_queueを宣言
vector<pair<int,int>>,//vectorの要素もpairにする
CompareFirst> q;//上記で定義した比較関数
//要素の追加
q.emplace(1,3);
//emplaceは下記と同義
q.push(make_pair(3,-1));q.push(make_pair(2,10));
//上記で定義した通り、pair.firstの昇順でソートされる
//先頭の要素(pair)を取り出す
auto p = q.top();
cout << p.first << " " << p.second << endl;//1 3
//先頭の要素を取り出す
q.pop();
p = q.top();
cout << p.first << " " << p.second << endl;//2 10
return 0;
}
deque
概要・使いどころ
queueでは末尾からの要素の追加と先頭からの要素の削除しかできませんが、
dequeでは先頭・末尾両方ともに要素の追加・削除をすることができます。
基本的な使い方はqueueと同じです。
vectorなどと同様にイテレータを使った走査も可能です。
計算量
| 処理 | 計算量 |
|---|---|
| 先頭・末尾要素の参照 | O(1) |
| 先頭・末尾要素の追加・削除 | O(1) |
使い方
deque
//初期宣言
deque<int> dq{1,4,3,6,2,8,2,5};
//先頭・末尾要素の表示
cout << dq.front() << endl;//1
cout << dq.back() << endl;//5
//先頭要素の書き換え（末尾も同様）
dq.front() = 100;
cout << dq.front() << endl;//100
//vectorと同様に任意位置の要素を参照可能
cout << dq[2] << endl; //3
//全要素の走査
for(auto q : dq){
cout << q << endl;
}
//イテレータも使える
for(auto itr = dq.begin(); itr != dq.end(); ++itr) {
cout << *itr << endl;
}
//要素の追加
dq.push_front(0);dq.push_back(-99);
//要素の削除
dq.pop_front();dq.pop_back();
map
概要・使いどころ
mapは、キーとそれに対応する値を格納することができるデータ型です。
キーを指定して対応する値を取り出す処理が高速です。
キーを重複して登録することはできません。
また、mapは内部で要素がソートされています。
単に要素へ高速にアクセスしたい場合は、後述のunordered_mapを使うほうがいいです。
計算量
| 処理 | 計算量 |
|---|---|
| キーの検索 | O(log(N)) |
| 要素の追加・削除 | O(log(N)) |
使い方
map
//変数宣言
map<string, int> m;
//キー (Jan) と対応する値 (1) を登録
m["Jan"] = 1;
//mapに登録されている要素数を確認する
cout << m.size() << endl;//1
//未登録のキーを参照すると0が返ってくる
cout << m["Feb"] << endl;//0
//未登録のキーを参照した場合も、要素数が1増える
//m["Feb"] = 0;と登録した場合と同じ状態になる
cout << m.size() << endl;//2
//キーを検索しイテレータを返す
auto itr1 = m.find("Jan");//見つかる
auto itr2 = m.find("Dec");//見つからない
if(itr1 != m.end())cout << "Find Jan" << endl;
if(itr2 == m.end())cout << "Not Find Dec" << endl;
//countでキーが登録されているかどうかを判定
if(m.count("Jan") > 0)cout << "Find Jan" << endl;
//at()でも要素を検索できるが、未登録の場合はエラーとなる
cout << m.at("Jan") << endl;//1
// cout << m.at("Mar") << endl;//1
//要素の全走査
for(auto itr = m.begin(); itr != m.end(); ++itr) {
//first:key, second:value
cout << itr->first << " " << itr->second << endl;
}
//mapはソートされているのでlower_boundが使える
map<int,string> m2;
m2[1] = "One";m2[2] = "Two";m2[3] = "Three";
auto itr = m2.lower_bound(2);
cout << itr->first << "." << itr->second << endl;//2.Two
//要素を全削除
m.clear();
cout << m.size() << endl;//0
unordered_map
概要・使いどころ
mapの要素がソートされていないバージョンです。
キーのハッシュ値に基づき各要素が保存されるため、各要素へのアクセスが高速です。
特にソートする必要がない場合はmapではなくunordered_mapを使いましょう。
基本的な使い方はmapと同じです。
計算量
| 処理 | 計算量 |
|---|---|
| キーの検索 | O(1) |
| 要素の追加・削除 | O(1) |
使い方
unordered_map
//変数宣言
unordered_map<string, int> m;
//キー (Jan) と対応する値 (1) を登録
m["Jan"] = 1;
//mapに登録されている要素数を確認する
cout << m.size() << endl;//1
//未登録のキーを参照すると0が返ってくる
cout << m["Feb"] << endl;//0
//未登録のキーを参照した場合も、要素数が1増える
//m["Feb"] = 0;と登録した場合と同じ状態になる
cout << m.size() << endl;//2
//キーを検索しイテレータを返す
auto itr1 = m.find("Jan");//見つかる
auto itr2 = m.find("Dec");//見つからない
if(itr1 != m.end())cout << "Find Jan" << endl;
if(itr2 == m.end())cout << "Not Find Dec" << endl;
//countでキーが登録されているかどうかを判定
if(m.count("Jan") > 0)cout << "Find Jan" << endl;
//at()でも要素を検索できるが、未登録の場合はエラーとなる
cout << m.at("Jan") << endl;//1
// cout << m.at("Mar") << endl;//1
//要素を全削除
m.clear();
cout << m.size() << endl;//0
おわりに
やや長くなってしまいましたが、この記事ではC++で使える基本的なデータ構造について紹介しました。
お読みいただいた方々のご参考になれば幸いです。