C++ で Deque コンテナを使用する

胡金庫 2023年10月12日
  1. 高速なキューの挿入/削除操作を処理するために std::deque コンテナを使用する
  2. std::deque に要素を挿入するには std::push_back/std::push_front メソッドを利用する
  3. ラッパー関数を用いた push_front メソッドで固定サイズのキューを実装する
C++ で Deque コンテナを使用する

この記事では、C++ で std::deque コンテナを利用する方法について複数の方法を示します。

高速なキューの挿入/削除操作を処理するために std::deque コンテナを使用する

std::deque はダブルエンドキューを実装しており、その両端で一定時間の挿入・削除操作を行うことができます。したがって、このデータ構造は、このような操作がトランザクションの大部分を占めるようなシナリオで利用されるべきです。デメリットとしては、std::deque の要素が連続したメモリ上に格納されないことと、操作を処理するために余分な操作を必要とし、結果として std::vector コンテナよりも多くのオブジェクトサイズが必要となることが挙げられます。次の例は、vector オブジェクトから構築された文字列の deque を示しています。文字列の入力から新しい要素を追加するには emplace_back メソッドを使用することが推奨されています。

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

using std::cout;
using std::deque;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printElements(deque<T> &d) {
  cout << "[ ";
  for (const auto &item : d) {
    cout << item << ", ";
  }
  cout << "\b\b ]" << endl;
}

int main() {
  vector<string> vec = {"plie", "flie", "blie", "clie"};
  ;

  deque<string> deque2(vec.begin(), vec.end());
  deque2.emplace_back("hlie");
  printElements(deque2);

  exit(EXIT_SUCCESS);
}

出力:

[ plie, flie, blie, clie, hlie ]

std::deque に要素を挿入するには std::push_back/std::push_front メソッドを利用する

std::deque には、要素操作のための豊富な機能を提供するための複数の関数が組み込まれています。最も一般的なものは push_backpush_front メソッドで、与えられたオブジェクトを deque の対応する面に要素として追加します。これらの関数には、要素を削除するための逆のメソッド pop_backpop_front があることに注意してください。以下の例は、上記のメソッドの基本的な使い方を示しています。

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

using std::cout;
using std::deque;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printElements(deque<T> &d) {
  cout << "[ ";
  for (const auto &item : d) {
    cout << item << ", ";
  }
  cout << "\b\b ]" << endl;
}

int main() {
  vector<string> vec = {"plie", "flie", "blie", "clie"};
  ;

  deque<string> deque2(vec.begin(), vec.end());

  string str1("alie");
  deque2.push_back(str1);
  printElements(deque2);
  deque2.push_front(str1);
  printElements(deque2);

  deque2.pop_back();
  deque2.pop_front();
  printElements(deque2);

  exit(EXIT_SUCCESS);
}

出力:

[ plie, flie, blie, clie, alie ]
[ alie, plie, flie, blie, clie, alie ]
[ plie, flie, blie, clie ]

ラッパー関数を用いた push_front メソッドで固定サイズのキューを実装する

また、std::deque コンテナを利用して、n 個の要素を格納する固定サイズのスタックとして操作し、いっぱいになると、新しい挿入のたびに自動的に後ろから要素を削除する方法もあります。今回は、push_front メソッドと pop_back メソッドを別の関数でラップすることでこの機能を実装しました。同様の機能は、コンテナアダプタ std::stack を用いても実現できます。

#include <deque>
#include <iostream>

using std::cout;
using std::deque;
using std::endl;
using std::string;

template <typename T>
void printElements(deque<T> &d) {
  cout << "[ ";
  for (const auto &item : d) {
    cout << item << ", ";
  }
  cout << "\b\b ]" << endl;
}

template <typename T>
void pushElement(T &elem, deque<T> &d) {
  d.push_front(elem);
  d.pop_back();
}

int main() {
  deque<int> deque1 = {3, 5, 7, 9};
  int i1 = 11;

  printElements(deque1);
  pushElement(i1, deque1);
  printElements(deque1);

  exit(EXIT_SUCCESS);
}

出力:

[ 3, 5, 7, 9 ]
[ 11, 3, 5, 7 ]
著者: 胡金庫
胡金庫 avatar 胡金庫 avatar

DelftStack.comの創設者です。Jinku はロボティクスと自動車産業で8年以上働いています。自動テスト、リモートサーバーからのデータ収集、耐久テストからのレポート作成が必要となったとき、彼はコーディングスキルを磨きました。彼は電気/電子工学のバックグラウンドを持っていますが、組み込みエレクトロニクス、組み込みプログラミング、フロントエンド/バックエンドプログラミングへの関心を広げています。

LinkedIn Facebook