Deque

　>>　NGL　>>　リファレンス　>>　Containerカテゴリ　>>　Containerのクラス　>>　Deque

言語： Visual Basic    C#

最終更新日付：2012/06/21 12:06:18

説明

Deque はシーケンスの両端に自由に要素を追加できる、ランダムアクセス可能なコンテナです。

• Dequeの特徴
• Dequeの反復子
• メソッド一覧

　

Dequeの特徴

ここでは、Deque クラスの特徴について説明します。各コンテナの特徴を比較した表は「時間計算量について」をご覧下さい。

任意の要素へのアクセスが定数時間で行える

Deque はランダムアクセスコンテナです。インデックスを指定しての要素の取得・設定を定数時間で実行します。NGL が提供するコンテナの中で、任意要素への定数アクセスを実現しているのは Vector と Deque だけです。

両端への要素の追加・削除が定数時間で行える

Deque は、Vector 同様、シーケンスの末尾への追加・削除を定数時間で実行します。しかし、Vector と異なるのは、先頭への追加・削除も定数時間で実行可能という部分です。このために、Deque は Vector クラスがサポートしない PushFrontと PopFront というメソッドをサポートします。

先頭の要素を追加・削除しても既存反復子が無効にならない

Deque クラスは先頭要素を追加・削除しても既存の反復子を無効にしません。つまり、先頭に要素を追加する前にシーケンス内のある要素を指していた反復子は、先頭要素の追加後も同じ要素を指すことが保証されるということです。このことは、Deque クラスが内部のシーケンスを単なる配列で管理しているわけではないことを意味します。Vector クラスのようなシンプルな実装 （反復子が配列への参照とインデックスを保持する ）では、先頭要素の位置が変わってしまえば、反復子を無効にせざるを得ません。

両端以外での挿入・削除には線形時間を要する

よい話の後は悪い話をしなくてはなりません。Deque クラスは Vector と同じく、シーケンス中央（つまり、両端でない場所)での要素の追加・削除には線形時間の計算量を必要とします。

要素の検索にも線形時間を要する

Deque クラスは、Vector と同じ線形コンテナですから、要素の検索には総当りで臨むしかありません。つまり、検索にも線形時間を要します。

　

ここまででわかるのは、Deque は Vector とほとんど同じ特徴をもち、シーケンスの先頭への追加・削除が定数時間で実行できるようになっている、ということです。しかし、これをもって Deque が Vector よりも優秀ということにはなりません。確かに特徴としては同じかもしれませんが、同じ時間計算量であるということは、同じ時間がかかるということを必ずしも意味しません。Deque クラスはその特徴を実現するために、単なる配列ではないオブジェクト構造を採用しています。そのため、各操作は Vector と比べれば全体的にコスト高となっています。ですから、シーケンス先頭での要素の出し入れが頻繁に発生しないのであれば、Vector を使用することをお勧めします。

　

ページトップへ

　

Dequeの反復子

Deque クラスはランダムアクセス反復子をサポートします。ランダムアクセス反復子に関する詳細は RandomAccessIterator を参照してください。

• DequeIterator ・・・ Begin および End が返す標準の反復子です。
• DequeRIterator ・・・ RBegin および REnd が返す逆方向反復子です。

ページトップへ

　

メソッド一覧

Deque クラスのメソッドの一覧を以下に示します。各コンテナがサポートするメソッドの一覧は「コンテナのメソッド」 をご覧下さい。

コンストラクタ

参照・設定　

メソッド	説明
Front	シーケンスの先頭要素の値を取得／設定します
Back	シーケンスの最後の要素の値を取得／設定します
At	シーケンスの指定した位置の要素の値を取得／設定します

追加・取出

メソッド	説明
PushBack	シーケンスの末尾に要素を追加します
PushFront	シーケンスの先頭に要素を追加します
PopBack	シーケンスの末尾から要素を取り除きます
PopFront	シーケンスの先頭から要素を取り除きます

反復子

メソッド	説明
Begin	シーケンスの先頭を指す反復子を返します
End	シーケンスの終端を指す反復子を返します
RBegin	逆シーケンスの先頭を指す逆方向反復子を返します
REnd	逆シーケンスの末尾を指す逆方向反復子を返します

挿入・削除

メソッド	説明
Insert	シーケンスの指定した位置に要素を挿入します
Erase	シーケンスの指定した位置から要素を取り除きます
Clear	シーケンス内の要素を全て取り除きます

サイズ

メソッド	説明
Empty	空シーケンスかどうかを返します
Size	シーケンスが管理する要素の個数を返します
Resize	シーケンスが管理する要素の個数を設定します
MaxSize	管理可能な要素の最大数を返します

置き換え

メソッド	説明
Assign	シーケンスを指定した別のシーケンスで置き換えます
Swap	別の Deque オブジェクトと管理シーケンスを交換します

比較

メソッド	説明
IsEqual	他の Deque オブジェクトと等しいかどうか調べます。
Compare	他の Deque オブジェクトと辞書順比較をします。

ページトップへ

　

　

---

Copyright(C) 2011-2012 Show MATSUOKA.
Powered by Prefab.