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