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

標準ライブラリ：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++ 標準ライブラリのドキュメントを参照してください。