コンテンツにスキップ

C++/標準ライブラリ/deque

出典: フリー教科書『ウィキブックス(Wikibooks)』

標準ライブラリ:deque ヘッダー

[編集]

はじめに

[編集]

deque ヘッダーは、双方向キューを実装するためのテンプレートクラスを提供します。このヘッダーは、要素の追加と削除を効率的に行う必要がある場合に役立ちます。

deque の利点

[編集]
  • 要素の追加と削除を効率的に行える
  • ランダムアクセスが可能
  • メモリ割り当てのオーバーヘッドが少ない

deque の欠点

[編集]
  • リスト構造に比べて要素へのアクセス速度が遅い
  • スタックやキューに比べて機能が少ない

deque の使用例

[編集]
  • 履歴データの保存
  • ネットワークパケットのキューイング
  • アルゴリズムの実装

deque の基本操作

[編集]

deque のコンストラクタとデストラクタ

[編集]
template <typename T> 
class deque {
  public:
    // コンストラクタ
    deque();
    deque(const deque &other);
    deque(size_t size);
    deque(size_t size, const T &value);
    template <typename InputIterator>
    deque(InputIterator first, InputIterator last);

    // デストラクタ
    ~deque();
};
  • deque():空の deque を作成します。
  • deque(const deque& other):他の deque をコピーして新しい deque を作成します。
  • deque(size_t size):size 個の要素を持つ deque を作成します。
  • deque(size_t size, const T& value):size 個の value で初期化された要素を持つ deque を作成します。
  • template <typename InputIterator> deque(InputIterator first, InputIterator last):first から last までの範囲の要素を持つ deque を作成します。

deque の要素へのアクセス

[編集]
template <typename T>
class deque {
  public:
    T &front();
    const T &front() const;
    T &back();
    const T &back() const;

    T &operator[](size_t pos);
    const T &operator[](size_t pos) const;
};
  • front():deque の先頭の要素を取得します。
  • front() const:deque の先頭の要素を const として取得します。
  • back():deque の末尾の要素を取得します。
  • back() const:deque の末尾の要素を const として取得します。
  • operator[](size_t pos):pos 番目の要素を取得します。
  • operator[](size_t pos) const:pos 番目の要素を const として取得します。

deque の要素の追加と削除

[編集]
template <typename T>
class deque {
  public:
    void push_front(const T &value);
    void push_back(const T &value);
    void pop_front();
    void pop_back();
};
  • push_front(const T& value):value を deque の先頭に挿入します。
  • push_back(const T& value):value を deque の末尾に挿入します。
  • pop_front():deque の先頭の要素を削除します。
  • pop_back():deque の末尾の要素を削除します。

deque の容量とサイズ

[編集]
template <typename T>
class deque {
  public:
   size_t size() const;
   size_t max_size() const;
   bool empty() const;
 };
  • size():deque の要素数を取得します。
  • max_size():deque の最大容量を取得します。
  • empty():deque が空かどうかを確認します。

deque のアルゴリズム

[編集]

deque ヘッダーは、deque に対する標準アルゴリズムをいくつか提供しています。

  • std::copy:deque の要素を別の deque にコピーします。
  • std::find:deque 内の特定の要素を検索します。
  • std::count:deque 内の特定の要素の個数をカウントします。
  • std::sort:deque の要素をソートします。

deque ヘッダーは、deque に対する独自のアルゴリズムもいくつか提供しています。

  • std::push_heap:deque をヒープ構造に変換します。
  • std::pop_heap:ヒープ構造から要素を削除します。
  • std::make_heap:deque をヒープ構造に変換し、要素をソートします。

deque の特殊な機能

[編集]

deque のスワップ

[編集]
template <typename T>
class deque {
  public:
    void swap(deque& other);
};

swap() メンバー関数を使用して、2 つの deque の要素をスワップできます。

auto d1 = deque{1, 2, 3};
auto d2 = deque{4, 5, 6};

d1.swap(d2);

// d1 は {4, 5, 6} になります。
// d2 は {1, 2, 3} になります。

deque の割り当て

[編集]
template <typename T>
class deque {
  public:
    deque& operator=(const deque& other);
};

operator= メンバー関数を使用して、別の deque の要素をこの deque に割り当てることができます。

auto d1 = deque{1, 2, 3};
auto d2 = deque{4, 5, 6};
 
d2 = d1;
 
// d2 は {1, 2, 3} になります。

deque のシリアライズ

[編集]
template <typename T>
class deque {
  public:
    template <typename Archive>
    void serialize(Archive& ar) const;
 
    template <typename Archive>
    void deserialize(Archive& ar);
};

serialize()deserialize() メンバー関数を使用して、deque の状態をシリアライズまたはデシリアライズできます。

auto d = deque{1, 2, 3};
 
std::ofstream ofs("data.bin");
std::ostream_archive oa(ofs);
d.serialize(oa);
 
std::ifstream ifs("data.bin");
std::istream_archive ia(ifs);
deque<int> d2;
d2.deserialize(ia);
 
// d2 は {1, 2, 3} になります。

deque のエラー処理

[編集]

deque ヘッダーは、以下の例外をスローします。

  • std::out_of_range:範囲外アクセスが発生した場合
  • std::bad_alloc:メモリ割り当てに失敗した場合

deque の詳細

[編集]

deque の内部表現

[編集]

deque は、通常、動的配列を使用して実装されます。動的配列は、要素の追加と削除を効率的に行うことができるデータ構造です。

deque のパフォーマンス

[編集]

deque は、要素の追加と削除を効率的に行うことができます。ただし、リスト構造に比べて要素へのアクセス速度が遅くなります。

deque の互換性

[編集]

deque は、C++ 標準ライブラリの一部であり、すべての C++ コンパイラでサポートされています。

deque の応用例

[編集]

deque は、さまざまなアプリケーションで使用することができます。

  • 履歴データの保存
  • ネットワークパケットのキューイング
  • アルゴリズムの実装

まとめ

[編集]

deque ヘッダーは、双方向キューを実装するためのテンプレートクラスを提供します。deque は、要素の追加と削除を効率的に行う必要がある場合に役立ちます。

この章では、deque ヘッダーの主な機能について説明しました。deque ヘッダーの詳細については、C++ 標準ライブラリのドキュメントを参照してください。