C++ STLメモ2

vector と dequeの違いは・・・。

どちらも可変長配列です。ほとんど用途が同じです。
違いを簡単に言うとvectorのメモリ管理機能を高性能にしたものがdequeです。

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main( )
{
  vector<int> v; // int型の可変長配列vectorタイプ
  deque<int> d; // int型の可変長配列dequeタイプ

  v.reserve(20); // vectorはデータの確保の予約が出来ます。ここでは20要素分で予約しています。
  v.resize(10); // 要素数は10です
  d.resize(10); // 要素数は10です。予約などは自動です。

// 要素数の確認をして見ます。
  cout << "vの要素数は" << v.size() << endl;
  cout << "dの要素数は" << d.size() << endl;

// for文で使う例。要素数はsizeで取れるため,以下のコードが使えます。
  int i;
  for(i = 0; i < v.size(); i++) {
    v[i] = 10;
  }

  for(i = 0; i < d.size(); i++) {
    d[i] = 10;
  }

  v.push_back(5); // 最後の要素の後ろに値が5で追加します。
  d.push_back(3); // 最後の要素の後ろに値が3で追加します。

// 要素数の確認をして見ます。 それぞれ11になっているはずです。
  cout << "vの要素数は" << v.size() << endl;
  cout << "dの要素数は" << d.size() << endl;

  return 0;
}

vectorは,メモリ管理機能は必要最小限しかなく,
一応サイズの増加は出来ますが,メモリ確保の効率は
使う側が制御しなければなりません。逆に言えば,
使いこなせばdequeよりも高効率なメモリ管理が可能です。
また,vectorの方が機能が単純な分コードサイズが小さくなります。

dequeはメモリ管理機能がある程度効率よくやってくれます。

どちらもpush_back( )などで,後ろに要素追加出来るのですが,
vectorの方では,reserve()で要素が使うメモリ領域の予約が出来ます。

なぜ,メモリ領域の予約が必要なのでしょうか?

これは使わなくてもよいですが,これを使わないとサイズが
変更される度に毎回全ての要素のメモリのコピーと再度確保とメモリ開放が
行われてしまう危険性があります。要素数が増えると,無視できない負荷です。

メモリというのは基本的には確保した後はサイズを増やすことが出来ない場合が
多いため,領域サイズを大きくするには,再度別のメモリ領域を大きめに確保し,
今まで確保していた内容のすぺての要素をコピーしてやる必要があります。
こうなると,必要なメモリ領域がコピーするときまで使用する領域の
2倍以上必要となります。

dequeにはreserve()がありません。というか,dequeはこれが自動です。
基本的に使うときは気にする必要がありません。

何も考えていないときは,dequeを使うほうが良い場合多いと思います。
追加削除などをよく使う場合も,dequeの方がよいでしょう(多分)。

なので,vectorの方は,要素の追加・削除などは行わないが,
実行時まで要素数が決まらないが,一度決まればサイズが変更されない場合や
dequeの自動メモリ管理機能ではパフォーマンスが明らかに悪く,
自分で管理したほうがよい場合に使います。

たとえば,極端な例ですが,データの追加の件数や追加するタイミングが
分かっていて,1万件程度のデータを追加し,追加しないときは全然追加しない,
といったときはdequeよりvectorを使うほうがパフォーマンスがよくなる
可能性があります。

※実際には動作テスト等をして実行時間や使用メモリ量を比較して
どちらがよいのか比較検討をしたほうがよいでしょう。

この記事へのコメント

この記事へのトラックバック