名前空間
変種
操作

std::deque

提供: cppreference.com
< cpp‎ | container
ヘッダ <deque> で定義
template<

    class T,
    class Allocator = std::allocator<T>

> class deque;
(1)
namespace pmr {

    template <class T>
    using deque = std::deque<T, std::pmr::polymorphic_allocator<T>>;

}
(2) (C++17およびそれ以降)

std::deque (double-ended queue) は先頭と末尾の両方に高速な挿入と削除が行えるインデックス付きのシーケンスコンテナです。 さらに、 deque の先頭または末尾への挿入および削除は残りの要素に対するポインタや参照を決して無効化しません。

std::vector と異なり、 deque の要素は隣接して格納されません。 一般的な実装では、個別に確保された一連の固定サイズの配列を用い、 deque へのインデックスアクセスが2回のポインタ逆参照で行えるように追加の維持管理を行います。 それに対して vector のインデックスアクセスはポインタを1回逆参照するだけです。

deque の記憶域は必要に応じて自動的に拡張されたり縮小されたりします。 deque の拡張は、既存の要素を新しいメモリ位置にコピーする必要がないため、 std::vector の拡張よりも安く行えます。 一方で、 deque は一般的には大きな最小メモリコストを持ちます。 deque にたった1個の要素を格納するだけでも、完全な内部配列を確保する必要があります (例えば、64ビットのlibstdc++ではオブジェクトサイズの8倍、64ビットのlibc++ではオブジェクトサイズの16倍か4096バイトの大きい方が確保されます)。

deque の一般的な操作の計算量 (効率性) は以下の通りです。

  • ランダムアクセス - 定数時間 O(1)
  • 末尾または先頭への要素の挿入または削除 - 定数時間 O(1)
  • 要素の挿入または削除 - 線形時間 O(n)

std::dequeContainer, AllocatorAwareContainer, SequenceContainer, ReversibleContainer の要件を満たします。

目次

[編集] テンプレート引数

T - 要素の型。
TCopyAssignable および CopyConstructible の要件を満たさなければなりません。 (C++11以前)
要素に課される要件はコンテナに対して実際に行われる操作によります。 一般的には、要素型は完全型であることが要求され、 Erasable の要件を満たさなければなりませんが、使用するメンバ関数によってはさらに厳しい要件が課されます。 (C++11およびそれ以降)

[edit]

Allocator - メモリを確保/解放したり、そのメモリに要素を構築/破棄したりするために使用されるアロケータ。 この型は Allocator の要件を満たさなければなりません。 Allocator::value_typeT が同じでない場合、動作は未定義です。 [edit]

[編集] イテレータの無効化

この節にはまだいくつか不正確な点があります。 詳細は個別のメンバ関数のページを参照してください。

操作 無効化
すべての読み取り操作 決して無効化されません。
swap, std::swap end() は無効化される場合があります (処理系依存)。
shrink_to_fit, clear, insert, emplace, push_front, push_back, emplace_front, emplace_back 常に無効化されます。
erase 先頭の削除 - 削除された要素のみ無効化されます。

末尾の削除 - 削除された要素および end() のみ無効化されます。
その他 - すべてのイテレータが無効化されます (end() も含みます)。

resize 新しいサイズが古いサイズより小さい場合: 削除された要素と end() のみ無効化されます。

新しいサイズが古いサイズより大きい場合: すべてのイテレータが無効化されます。
その他 - 無効化されるイテレータはありません。

pop_front 削除された要素のみ無効化されます。
pop_back 削除された要素と end() のみ無効化されます。

[編集] 無効化ノート

  • deque の先頭または末尾に挿入する場合、参照は insert および emplace によって無効化されません。
  • push_front, push_back, emplace_front, emplace_back は deque の要素への参照を無効化しません。
  • deque の先頭または末尾を削除する場合、削除されない要素への参照は erase, pop_front, pop_back によって無効化されません。
  • 小さくなるサイズで resize を呼んだ場合、削除されない要素へのいかなる参照も無効化されません。
  • 大きくなるサイズで resize を呼んだ場合、 deque の要素へのいかなる参照も無効化されません。

[編集] メンバ型

メンバ型 定義
value_type T [edit]
allocator_type Allocator [edit]
size_type 符号なし整数型 (通常 std::size_t) [edit]
difference_type 符号付き整数型 (通常 std::ptrdiff_t) [edit]
reference
Allocator::reference (C++11以前)
value_type& (C++11およびそれ以降)
[edit]
const_reference
Allocator::const_reference (C++11以前)
const value_type& (C++11およびそれ以降)
[edit]
pointer
Allocator::pointer (C++11以前)
std::allocator_traits<Allocator>::pointer (C++11およびそれ以降)
[edit]
const_pointer
Allocator::const_pointer (C++11以前)
std::allocator_traits<Allocator>::const_pointer (C++11およびそれ以降)
[edit]
iterator RandomAccessIterator [edit]
const_iterator const RandomAccessIterator [edit]
reverse_iterator std::reverse_iterator<iterator> [edit]
const_reverse_iterator std::reverse_iterator<const_iterator> [edit]

[編集] メンバ関数

deque を構築します
(パブリックメンバ関数) [edit]
deque を破棄します
(パブリックメンバ関数) [edit]
コンテナに値を代入します
(パブリックメンバ関数) [edit]
コンテナに値を代入します
(パブリックメンバ関数) [edit]
関連付けられているアロケータを返します
(パブリックメンバ関数) [edit]
要素アクセス
境界チェック付きで指定された要素にアクセスします
(パブリックメンバ関数) [edit]
指定された要素にアクセスします
(パブリックメンバ関数) [edit]
最初の要素にアクセスします
(パブリックメンバ関数) [edit]
最後の要素にアクセスします
(パブリックメンバ関数) [edit]
イテレータ
先頭を指すイテレータを返します
(パブリックメンバ関数) [edit]
終端を指すイテレータを返します
(パブリックメンバ関数) [edit]
先頭を指す逆イテレータを返します
(パブリックメンバ関数) [edit]
終端を指す逆イテレータを返します
(パブリックメンバ関数) [edit]
容量
コンテナが空かどうか調べます
(パブリックメンバ関数) [edit]
要素数を返します
(パブリックメンバ関数) [edit]
可能な最大の要素数を返します
(パブリックメンバ関数) [edit]
未使用のメモリを解放してメモリ使用量を減らします
(パブリックメンバ関数) [edit]
変更
すべての要素を削除します
(パブリックメンバ関数) [edit]
要素を挿入します
(パブリックメンバ関数) [edit]
(C++11)
要素をその場で構築します
(パブリックメンバ関数) [edit]
要素を削除します
(パブリックメンバ関数) [edit]
要素を末尾に追加します
(パブリックメンバ関数) [edit]
要素を末尾にその場で構築します
(パブリックメンバ関数) [edit]
最後の要素を削除します
(パブリックメンバ関数) [edit]
要素を先頭に挿入します
(パブリックメンバ関数) [edit]
要素を先頭にその場で構築します
(パブリックメンバ関数) [edit]
最初の要素を削除します
(パブリックメンバ関数) [edit]
格納されている要素の数を変更します
(パブリックメンバ関数) [edit]
内容を入れ替えます
(パブリックメンバ関数) [edit]

[編集] 非メンバ関数

deque 内の値を辞書的に比較します
(関数テンプレート) [edit]
std::swap アルゴリズムの特殊化
(関数テンプレート) [edit]

[編集] 推定ガイド(C++17およびそれ以降)

[編集]

#include <iostream>
#include <deque>
 
int main()
{
    // Create a deque containing integers
    std::deque<int> d = {7, 5, 16, 8};
 
    // Add an integer to the beginning and end of the deque
    d.push_front(13);
    d.push_back(25);
 
    // Iterate and print values of deque
    for(int n : d) {
        std::cout << n << '\n';
    }
}

出力:

13
7
5
16
8
25