Deque

Deque

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

言語: Visual Basic    C#

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

説明

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

 

Dequeの特徴

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

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

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

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

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

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

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

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

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

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

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

 

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

 

IEnumerable(Of T) をサポート

Deque は IEnumerable(Of T) インターフェースを実装しています(ここで、T はコンテナが格納する要素の型です)。そのため、For Each 構文を利用して要素の反復を行うことができます。

IEnumerable<T> をサポート

Deque は IEnumerable<T> インターフェースを実装しています(ここで、T はコンテナが格納する要素の型です)。そのため、foreach 構文を利用して要素の反復を行うことができます。

ページトップへ

 

Dequeの反復子

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

ページトップへ

 

メソッド一覧

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

コンストラクタ

メソッド 説明
New いくつかの方法でコンテナオブジェクトを作成します。
メソッド 説明
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.