MENU
  1. ホーム
  2. C++
  3. STL
  4. deque
  5. [C++] std::dequeの使い方について詳しく解説

[C++] std::dequeの使い方について詳しく解説

std::dequeはC++標準ライブラリに含まれるコンテナで、両端からの高速な挿入と削除が可能です。

このコンテナは、動的配列のようにランダムアクセスが可能であり、std::vectorと似たインターフェースを持っていますが、メモリの再配置が少ないため、特定のシナリオで効率的です。

メソッドにはpush_back、push_front、pop_back、pop_frontなどがあり、これらを使って要素を簡単に操作できます。

また、atやoperator[]を用いて要素にアクセスすることも可能です。

この記事でわかること
  • std::dequeの基本的な特性と利点
  • 要素の追加、削除、アクセス方法
  • std::dequeの主要なメソッドの使い方
  • キュー、スタック、双方向リストとしての利用方法
  • スレッドセーフ性やメモリ効率、パフォーマンスに関する情報

目次から探す

std::dequeとは

std::deque(ダブルエンドキュー)は、C++の標準ライブラリに含まれるコンテナの一つで、両端からの要素の追加や削除が効率的に行えるデータ構造です。

dequeは、動的配列のように要素を格納しますが、両端からの操作が可能なため、特にキューやスタックの実装に適しています。

std::dequeの基本概念

  • 両端操作: std::dequeは、先頭と末尾の両方から要素を追加・削除できます。
  • 動的サイズ: 要素数に応じて自動的にサイズが調整されます。
  • ランダムアクセス: インデックスを使用して任意の位置の要素にアクセスできます。

std::dequeとstd::vectorの違い

スクロールできます
特徴std::dequestd::vector
要素の追加・削除両端から可能末尾のみ
メモリ管理非連続的にメモリを使用連続的にメモリを使用
アクセス速度一般的に遅い高速
サイズ変更のコスト高い(再配置が必要な場合あり)低い(末尾の追加は効率的)

std::dequeの利点と欠点

  • 利点:
  • 両端からの要素操作が可能で、キューやスタックの実装に便利。
  • サイズが動的に変化し、必要に応じてメモリを確保。
  • 欠点:
  • メモリの使用効率がstd::vectorに比べて劣る場合がある。
  • ランダムアクセスの速度が遅くなることがある。

std::dequeの基本操作

std::dequeは、要素の追加、削除、アクセス、サイズの取得や変更が簡単に行える便利なコンテナです。

以下では、これらの基本操作について詳しく解説します。

要素の追加と削除

std::dequeでは、要素を両端から追加・削除するためのメソッドが用意されています。

以下は、主なメソッドの一覧です。

スクロールできます
操作メソッド名説明
末尾に追加push_back要素を末尾に追加
先頭に追加push_front要素を先頭に追加
末尾から削除pop_back末尾の要素を削除
先頭から削除pop_front先頭の要素を削除

以下は、要素の追加と削除のサンプルコードです。

#include <iostream>
#include <deque>
int main() {
    std::deque<std::string> dq;
    dq.push_back("要素1");
    dq.push_front("要素0");
    dq.push_back("要素2");
    std::cout << "先頭の要素: " << dq.front() << std::endl; // 要素0
    std::cout << "末尾の要素: " << dq.back() << std::endl;  // 要素2
    dq.pop_front(); // 要素0を削除
    dq.pop_back();  // 要素2を削除
    std::cout << "残っている要素: " << dq.front() << std::endl; // 要素1
    return 0;
}
先頭の要素: 要素0
末尾の要素: 要素2
残っている要素: 要素1

要素へのアクセス

std::dequeでは、要素へのアクセスも簡単に行えます。

以下のメソッドを使用します。

スクロールできます
操作メソッド名説明
インデックスアクセスoperator[]指定したインデックスの要素にアクセス
範囲チェック付きアクセスat指定したインデックスの要素にアクセス(範囲チェックあり)
先頭の要素front先頭の要素を取得
末尾の要素back末尾の要素を取得

以下は、要素へのアクセスのサンプルコードです。

#include <iostream>
#include <deque>
int main() {
    std::deque<int> dq = {10, 20, 30, 40, 50};
    std::cout << "インデックス1の要素: " << dq[1] << std::endl; // 20
    std::cout << "インデックス2の要素: " << dq.at(2) << std::endl; // 30
    std::cout << "先頭の要素: " << dq.front() << std::endl; // 10
    std::cout << "末尾の要素: " << dq.back() << std::endl; // 50
    return 0;
}
インデックス1の要素: 20
インデックス2の要素: 30
先頭の要素: 10
末尾の要素: 50

サイズの取得と変更

std::dequeのサイズを取得したり、サイズを変更したりするためのメソッドも用意されています。

スクロールできます
操作メソッド名説明
サイズの取得size現在の要素数を取得
サイズの変更resize要素数を指定したサイズに変更
全要素の削除clear全ての要素を削除

以下は、サイズの取得と変更のサンプルコードです。

#include <iostream>
#include <deque>
int main() {
    std::deque<int> dq = {1, 2, 3, 4, 5};
    std::cout << "初期サイズ: " << dq.size() << std::endl; // 5
    dq.resize(3); // サイズを3に変更
    std::cout << "サイズ変更後: " << dq.size() << std::endl; // 3
    dq.clear(); // 全要素を削除
    std::cout << "クリア後のサイズ: " << dq.size() << std::endl; // 0
    return 0;
}
初期サイズ: 5
サイズ変更後: 3
クリア後のサイズ: 0

std::dequeのメソッド

std::dequeは、さまざまなメソッドを提供しており、要素の追加、削除、アクセス、サイズの管理が容易に行えます。

以下では、主要なメソッドについて詳しく解説します。

push_backとpush_front

  • push_back: 要素を末尾に追加します。
  • push_front: 要素を先頭に追加します。

これらのメソッドは、std::dequeの両端からの操作を可能にします。

#include <iostream>
#include <deque>
int main() {
    std::deque<std::string> dq;
    dq.push_back("要素1");
    dq.push_front("要素0");
    dq.push_back("要素2");
    for (const auto& elem : dq) {
        std::cout << elem << " "; // 要素0 要素1 要素2
    }
    std::cout << std::endl;
    return 0;
}
要素0 要素1 要素2

pop_backとpop_front

  • pop_back: 末尾の要素を削除します。
  • pop_front: 先頭の要素を削除します。

これらのメソッドを使用することで、std::dequeの両端から要素を削除できます。

#include <iostream>
#include <deque>
int main() {
    std::deque<int> dq = {1, 2, 3, 4, 5};
    dq.pop_front(); // 先頭の要素を削除
    dq.pop_back();  // 末尾の要素を削除
    for (const auto& elem : dq) {
        std::cout << elem << " "; // 2 3 4
    }
    std::cout << std::endl;
    return 0;
}
2 3 4

atとoperator[]

  • at: 指定したインデックスの要素にアクセスします。

範囲チェックが行われ、無効なインデックスの場合は例外がスローされます。

  • operator[]: 指定したインデックスの要素にアクセスします。

範囲チェックは行われません。

これにより、要素への安全なアクセスと高速なアクセスが可能です。

#include <iostream>
#include <deque>
int main() {
    std::deque<int> dq = {10, 20, 30, 40, 50};
    std::cout << "at(2): " << dq.at(2) << std::endl; // 30
    std::cout << "operator[](1): " << dq[1] << std::endl; // 20
    return 0;
}
at(2): 30
operator[](1): 20

sizeとresize

  • size: 現在の要素数を取得します。
  • resize: 要素数を指定したサイズに変更します。

新しいサイズが現在のサイズより大きい場合は、追加された要素はデフォルト値で初期化されます。

これにより、std::dequeのサイズを動的に管理できます。

#include <iostream>
#include <deque>
int main() {
    std::deque<int> dq = {1, 2, 3};
    std::cout << "初期サイズ: " << dq.size() << std::endl; // 3
    dq.resize(5); // サイズを5に変更
    std::cout << "サイズ変更後: " << dq.size() << std::endl; // 5
    for (const auto& elem : dq) {
        std::cout << elem << " "; // 1 2 3 0 0
    }
    std::cout << std::endl;
    return 0;
}
初期サイズ: 3
サイズ変更後: 5
1 2 3 0 0

clearとerase

  • clear: 全ての要素を削除します。

サイズは0になります。

  • erase: 指定した位置または範囲の要素を削除します。

これにより、std::dequeの要素を柔軟に管理できます。

#include <iostream>
#include <deque>
int main() {
    std::deque<int> dq = {1, 2, 3, 4, 5};
    dq.erase(dq.begin() + 1); // インデックス1の要素を削除
    std::cout << "erase後: ";
    for (const auto& elem : dq) {
        std::cout << elem << " "; // 1 3 4 5
    }
    std::cout << std::endl;
    dq.clear(); // 全要素を削除
    std::cout << "クリア後のサイズ: " << dq.size() << std::endl; // 0
    return 0;
}
erase後: 1 3 4 5
クリア後のサイズ: 0

std::dequeのイテレータ

std::dequeは、イテレータを使用して要素にアクセスすることができます。

イテレータを使うことで、コンテナ内の要素を簡単に操作したり、ループ処理を行ったりすることが可能です。

以下では、std::dequeのイテレータについて詳しく解説します。

イテレータの基本

イテレータは、コンテナ内の要素を指し示すオブジェクトで、ポインタのように振る舞います。

std::dequeのイテレータは、以下の特徴を持っています。

  • ランダムアクセス: イテレータを使って、任意の位置の要素にアクセスできます。
  • イテレータの種類: std::dequeは、通常のイテレータと逆イテレータの両方を提供します。

beginとend

  • begin: コンテナの最初の要素を指すイテレータを返します。
  • end: コンテナの最後の要素の次を指すイテレータを返します。

このため、endは実際の要素を指し示すわけではありません。

これらのメソッドを使用することで、std::dequeの全要素に対してループ処理を行うことができます。

#include <iostream>
#include <deque>
int main() {
    std::deque<int> dq = {10, 20, 30, 40, 50};
    std::cout << "要素: ";
    for (auto it = dq.begin(); it != dq.end(); ++it) {
        std::cout << *it << " "; // 10 20 30 40 50
    }
    std::cout << std::endl;
    return 0;
}
要素: 10 20 30 40 50

rbeginとrend

  • rbegin: コンテナの最後の要素を指す逆イテレータを返します。
  • rend: コンテナの最初の要素の前を指す逆イテレータを返します。

このため、rendも実際の要素を指し示すわけではありません。

逆イテレータを使用することで、std::dequeの要素を逆順に処理することができます。

#include <iostream>
#include <deque>
int main() {
    std::deque<int> dq = {10, 20, 30, 40, 50};
    std::cout << "逆順の要素: ";
    for (auto it = dq.rbegin(); it != dq.rend(); ++it) {
        std::cout << *it << " "; // 50 40 30 20 10
    }
    std::cout << std::endl;
    return 0;
}
逆順の要素: 50 40 30 20 10

std::dequeの応用例

std::dequeは、その特性を活かしてさまざまなデータ構造として利用できます。

以下では、std::dequeをキュー、スタック、双方向リストとして使用する方法について解説します。

キューとしての使用

std::dequeは、両端からの要素の追加と削除が可能なため、キュー(FIFO：先入れ先出し)として非常に適しています。

push_backで要素を追加し、pop_frontで要素を削除することで、キューの動作を実現できます。

#include <iostream>
#include <deque>
int main() {
    std::deque<int> queue;
    // キューに要素を追加
    queue.push_back(1);
    queue.push_back(2);
    queue.push_back(3);
    // キューから要素を削除
    while (!queue.empty()) {
        std::cout << "キューから取り出した要素: " << queue.front() << std::endl; // 1, 2, 3
        queue.pop_front();
    }
    return 0;
}
キューから取り出した要素: 1
キューから取り出した要素: 2
キューから取り出した要素: 3

スタックとしての使用

std::dequeは、スタック(LIFO：後入れ先出し)としても使用できます。

push_backで要素を追加し、pop_backで要素を削除することで、スタックの動作を実現できます。

#include <iostream>
#include <deque>
int main() {
    std::deque<int> stack;
    // スタックに要素を追加
    stack.push_back(1);
    stack.push_back(2);
    stack.push_back(3);
    // スタックから要素を削除
    while (!stack.empty()) {
        std::cout << "スタックから取り出した要素: " << stack.back() << std::endl; // 3, 2, 1
        stack.pop_back();
    }
    return 0;
}
スタックから取り出した要素: 3
スタックから取り出した要素: 2
スタックから取り出した要素: 1

双方向リストとしての使用

std::dequeは、双方向リストのように要素を前後に追加・削除できるため、双方向リストとしても利用できます。

push_frontやpush_backを使って要素を追加し、pop_frontやpop_backで要素を削除することで、双方向リストの機能を実現できます。

#include <iostream>
#include <deque>
int main() {
    std::deque<std::string> list;
    // 双方向リストに要素を追加
    list.push_back("要素1");
    list.push_front("要素0");
    list.push_back("要素2");
    std::cout << "双方向リストの要素: ";
    for (const auto& elem : list) {
        std::cout << elem << " "; // 要素0 要素1 要素2
    }
    std::cout << std::endl;
    // 要素を削除
    list.pop_front(); // 要素0を削除
    list.pop_back();  // 要素2を削除
    std::cout << "削除後の要素: ";
    for (const auto& elem : list) {
        std::cout << elem << " "; // 要素1
    }
    std::cout << std::endl;
    return 0;
}
双方向リストの要素: 要素0 要素1 要素2
削除後の要素: 要素1

よくある質問

std::dequeはスレッドセーフですか？

std::deque自体はスレッドセーフではありません。

複数のスレッドが同時に同じstd::dequeインスタンスに対して読み書きを行う場合、データ競合が発生する可能性があります。

そのため、スレッド間での安全な操作を行うためには、ミューテックスやロックを使用して適切に同期を取る必要があります。

std::dequeのメモリ効率はどうですか？

std::dequeは、内部的に複数のメモリブロックを使用して要素を格納します。

このため、メモリの使用効率はstd::vectorに比べて劣る場合がありますが、両端からの要素の追加・削除が効率的に行えるため、特定の用途においては非常に便利です。

メモリの断片化が発生する可能性もあるため、使用する際には注意が必要です。

std::dequeのパフォーマンスはどうですか？

std::dequeは、両端からの要素の追加・削除がO(1)の時間で行えるため、これらの操作においては非常に高いパフォーマンスを発揮します。

しかし、ランダムアクセスの速度はstd::vectorに比べて遅くなることがあります。

したがって、使用する場面によっては、他のコンテナと比較してパフォーマンスが異なることを理解しておく必要があります。

まとめ

この記事では、std::dequeの基本概念から、基本操作、メソッド、応用例、よくある質問まで幅広く解説しました。

std::dequeは、両端からの操作が可能な柔軟なコンテナであり、キューやスタック、双方向リストとしての利用が可能です。

ぜひ、実際のプログラムでstd::dequeを活用し、その特性を体験してみてください。

目次に戻る

当サイトはリンクフリーです。出典元を明記していただければ、ご自由に引用していただいて構いません。

C言語
C++
Python
HTML
Java
HTTP

関連カテゴリーから探す

deque
  • URLをコピーしました！

関連記事

目次から探す