バイナリ検索ではdeque C++データ構造の対数パフォーマンスはありますか？

Question

標準では、データ構造にランダムアクセスがある場合、std::binary_search(...)と2つの関連関数std::lower_bound(...)とstd::upper_bound(...)はO（log n）となります。だから、私はこれらのアルゴリズムがstd::dequeにO（ログn）の性能を持っていると推測します（その内容はユーザーによってソートされていると仮定します）。

しかし、std::dequeの内部表現は厄介なので、私は疑問を抱いていました.O（ログn）検索の要件はstd::dequeです。

Answer 1

はいコンテナは一定時間内に任意の要素へのアクセスを提供する必要があるため（vectorよりわずかに高い定数）、それでもdequeのために保持されます。

これは、dequeをソートする義務を免れません。

Answer 2

ちょうど私がbinary_searchの両端キューの実装が遅くベクトルのよりになると思うが、それは複雑だ、それをテストするためのプログラムを書くには、まだO（LOGN）

Answer 3

はいです。 dequeは、索引が存在する場合、索引に対して一定の時間アクセスを持ちます。同じサイズのページで構成されています。あなたが持っているものは優しさです。ページへのポインタのベクトルのように。 100要素で2ページと言うと、103番目の要素にアクセスするには103/100 = 1でページを決定し、103％でページのインデックスを決定する100 => 3.ここで、要素を取得する2つのベクトル。

ここhttp://www.cplusplus.com/reference/stl/deque/からの声明：

ストレージは常に自動的に処理して、Dequeとは異なる方法で特定のライブラリで実装されてもよいが、すべてのケースで、彼らはランダムアクセスイテレータを介してアクセスするための個々の要素を可能に（必要に応じて伸縮する）。