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

【競プロで使える】C++の標準データ構造まとめ

はじめに

競技プログラミングで必須となるデータ構造について概要と使い方をシンプル(サンプルコード多め、文章の解説少なめ)にまとめています。
C++でコンテストに参加する際のメモ代わりになれば幸いです。
C++14 (GCC 5.4.1) を前提としていますので、その点ご了承お願いします。

C++でよく使うデータ構造

この記事では以下のデータ構造について紹介します。

これらはbits/stdc++.hをインクルードしておけば使えます。
また、以下では簡単のため、

using namespace std;

をプログラム冒頭に記載しているものとして下記プログラム例ではstd::は省略します。

vector

概要・使いどころ

C++における動的配列です。
vector単体で使うと普通の配列ですが、vectorを重ねて多次元配列にしたり、
静的配列と組み合わせてちょっと高度なこともできたりします。
C++でstd::vectorと静的配列[]を組み合わせて深さ優先探索(DFS)
以下のコードではswapや全要素への走査(for(auto a : v))など、ほかのデータ構造に対しても使える関数も記載しています。

計算量

処理 計算量
ソート O(NlogN)
各要素へのアクセス O(1)
全要素への走査 O(N)
要素の追加・削除 償却定数時間

使い方

  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 << endl;//1 3 2 4 -1

  //末尾の要素を削除
  v2.pop_back();
  cout << v2.size() << endl;//4

  //昇順でソート
  sort(v2.begin(),v2.end());
  cout << v2[0] << endl;//1

  //要素の順番を逆にする
  reverse(v2.begin(),v2.end());
  cout << v2[0] << endl;//4

  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 == v2.end()がTRUE
  itr = upper_bound(v2.begin(),v2.end(),3);
  index = itr - v2.begin();
  cout << index << endl;//3

  v1.push_back(11);v1.push_back(12);v1.push_back(13);
  //v1とv2を入れ替える
  swap(v1,v2);

  //以下は低速のためあまり使わないほうが良い
  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;
}

Topに戻る

set

概要・使いどころ

setは集合を保持するデータ構造であり、要素の重複はなく、キーそのものが値となります。
競技プログラミングではフラグ的な使い方をされることもあります。

計算量

処理 計算量
各要素へのアクセス O(log(N))
要素の追加・削除 O(log(N))

使い方

  //変数宣言(空集合)
  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

  //要素の削除
  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

Topに戻る

pair

概要・使いどころ

pairは異なる二つの値をペアで保持するデータ構造です。
ペアとなる二つの値は異なる型でも構いません。
pair単体では二つの要素を単にまとめたものであるため、mapなどのデータ型の要素として用いられる場合が多いです。

使い方

  //変数宣言
  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"

Topに戻る

stack

概要・使いどころ

LIFO (Last In, First Out) のデータ構造です。
一番最後に挿入された要素から取り出します。
山積みされた本を取り出すような動きをイメージすると良いでしょう。
スタック内の要素はソートされません。
要素はbackから挿入され、backから取り出します。

計算量

処理 計算量
先頭要素の参照 O(1)
先頭要素の追加・削除 O(1)

使い方

  //変数宣言
  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

Topに戻る

queue

概要・使いどころ

FIFO (First In, First Out) のデータ構造です。
入れた順に取り出す、一般的なキューです。
キュー内の要素はソートされません。
要素はbackから挿入され、frontから取り出します。
stackとの違いを理解しましょう。

計算量

処理 計算量
先頭・末尾要素の参照 O(1)
末尾要素の追加・削除 O(1)

使い方

  //変数宣言
  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

Topに戻る

priority_queue

概要・使いどころ

優先度付きキューと呼ばれるデータ構造です。
上述のqueueとは異なり、優先度付きキューは常にソートした状態でデータを保持します。
最大値・最小値を早く計算するのに優れているため、計算量を気にして最大・最小を計算するときによく使われるデータ型です。

計算量

処理 計算量
最大要素の参照 O(1)
要素の追加・削除 O(log(N))

使い方

  //変数宣言
  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  

Topに戻る

pairとpriority_queueを組み合わせる

以下のようにpriority_queueの要素にpairを使うこともできます。
その際には比較関数を自作しておくと、一つ目の要素(first)で比較したり二つ目の要素(second)を比較することができます。
をgreater>とすると、first同士の比較になります。

#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;
}

Topに戻る

deque

概要・使いどころ

queueでは末尾からの要素の追加と先頭からの要素の削除しかできませんが、
dequeでは先頭・末尾両方ともに要素の追加・削除をすることができます。
基本的な使い方はqueueと同じです。
vectorなどと同様にイテレータを使った走査も可能です。

計算量

処理 計算量
先頭・末尾要素の参照 O(1)
先頭・末尾要素の追加・削除 O(1)

使い方

  //初期宣言
  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

  //全要素の走査
  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();

Topに戻る

map

概要・使いどころ

mapは、キーとそれに対応する値を格納することができるデータ型です。
キーを指定して対応する値を取り出す処理が高速です。
キーを重複して登録することはできません。
また、mapは内部で要素がソートされています。
単に要素へ高速にアクセスしたい場合は、後述のunordered_mapを使うほうがいいです。

計算量

処理 計算量
キーの検索 O(log(N))
要素の追加・削除 O(log(N))

使い方

  //変数宣言
  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

  //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

Topに戻る

unordered_map

概要・使いどころ

mapの要素がソートされていないバージョンです。
キーのハッシュ値に基づき各要素が保存されるため、各要素へのアクセスが高速です。
特にソートする必要がない場合はmapではなくunordered_mapを使いましょう。
基本的な使い方はmapと同じです。

計算量

処理 計算量
キーの検索 O(1)
要素の追加・削除 O(1)

使い方

  //変数宣言
  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

Topに戻る

おわりに

やや長くなってしまいましたが、この記事ではC++で使える基本的なデータ構造について紹介しました。
お読みいただいた方々のご参考になれば幸いです。

Why do not you register as a user and use Qiita more conveniently?
  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
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