配列の先頭と末尾を管理できる deque 型

　AtCoderの過去問より、この問題を解いていた。

atcoder.jp

やりたいこと

　任意の数列を、空の配列の先頭と末尾に交互に追加していきたい。Ruby であれば、これは Array#unshift と Array#push を使って簡単に書ける。例えばこう。

n = 10
ans = []

1.upto(n) do |i|
  i % 2 == 1 ? ans.push(i) : ans.unshift(i)
end

ans
# => => [10, 8, 6, 4, 2, 1, 3, 5, 7, 9]

　これを C++ で実装してみたい。

vector と deque

　長さを意識せずに扱うことのできる配列として vector があるが、 vector には unshift のような便利な関数はない。あるのは vector::push_back() だけである。つまり vecotr は末尾に向かって伸びるだけで、先頭は固定されている。

　deque というデータ構造がある。正式には Double Ended QUEue 、略して deque という。双方向キューとでも訳しておく。

　こちらには deque::push_front() と deque::push_back() が実装されていて、先頭と末尾の要素をどちらも管理することができる。

#include <iostream>
#include <deque>

using namespace std;

int main()
{
  int n = 10;
  deque<int> q;

  for (int i = 1; i <= n; ++i)
  {
    i % 2 == 1 ? q.push_back(i) : q.push_front(i);
  }

  for (int i = 0; i < n; ++i)
  {
    if (i != 0) cout << ", ";
    cout << q[i];
  }

  cout << endl;
  return 0;
}

　肝心なのは計算量である。 deque の方が高次の機能を持つデータ構造なのだから、当然いくらか遅くなるという認識でいた。結論から言ってこれは誤謬であった。

　deque::push_front() および deque::push_back() の実行時間はいずれも O(1) である。これに対して vector::push_back() は最悪で O(N) となってしまう。

　 vector は可変長の配列である。配列の長さをあらかじめ宣言せずとも、 vector 自身がよしなにメモリを確保してくれる。あらかじめ確保したメモリの大きさを超えて要素が追加されるような時は、自動的にサイズを拡張してくれる。しかしメモリを動的に管理するこの処理が、ボトルネックとなる。

　つまり要素数が少なければ vector::push_back() の実行時間は O(1) だが、要素数が多くなるに連れて、まれに O(N) となる。しかもこれは当然、要素数 N が増えれば増えるほど、線形に悪化する。

　それに比べて、 deque は先頭/末尾の要素の追加/削除を、いずれも O(1) で実行できる。要素数がどれだけ増えても定数時間で実行できるから、長いリストを扱う場合には vector よりもこちらに軍配があがる。

　もっとも、 vector でも [] オペレータを使えば、こちらも定数倍で実行可能である。 　以下にふたつのパターンを示すが、後者の書き方をよく見かけるのは、単に記述量が少ないというだけでなく、実行時間として明らかに優れているからである。そういうことを今日は学んだ。

int main()
{
  int n;
  cin >> n;

  // push_back() の実行時間は O(n)
  vector<int> a;
  for (int i = 0; i < n; ++i)
  {
    int p;
    cin >> p;
    a.push_back(p);
  }

  // [] の実行時間は O(1)
  vector<int> b(n);
  for (int i = 0; i < n; ++i)
  {
    cin >> b[i];
  }

  // ...

  return 0;
}