標準では、データ構造にランダムアクセスがある場合、およびstd::binary_search(...)2つの関連する関数はO（log n）であるとされています。したがって、これらのアルゴリズムのパフォーマンスはO（log n）であると想定します（その内容がユーザーによってソートされていると仮定します）。std::lower_bound(...)std::upper_bound(...)std::deque
ただし、の内部表現std::dequeはトリッキー（チャンクに分割されている）のように思われるので、疑問に思っていました。O（log n）検索の要件は。に当てはまりますかstd::deque。
dequeはい、コンテナは一定時間内に任意の要素へのアクセスを提供する必要があるため（よりわずかに高い定数）、それは依然として有効ですvector。
dequeしかし、それはあなたが分類される義務からあなたを解放しません。
はい。dequeは、インデックスが存在する場合、インデックスに常時アクセスできます。同じサイズのページで構成されています。あなたが持っているのはsmthです。ページへのポインタのベクトルのようなものです。たとえば、100個の要素を持つ2つのページがあり、103/100 = 1でページを決定し、103％100 => 3でページのインデックスを決定するよりも、103番目の要素にアクセスしたい場合は、要素を取得するための2つのベクトル。
ここにhttp://www.cplusplus.com/reference/stl/deque/からのステートメントがあります：
Dequeは、特定のライブラリによってさまざまな方法で実装できますが、すべての場合で、ランダムアクセスイテレータを介して個々の要素にアクセスでき、ストレージは常に自動的に処理されます（必要に応じて拡張および縮小）。
それをテストするプログラムを書くだけで、dequeのbinary_searchの実装はvectorの実装よりも遅くなると思いますが、その複雑さは依然としてO（logn）です。