C++ は、std::set、std::map などの begin/end/rbegin/rend を一定時間で実行しますか?

StackOverflow https://stackoverflow.com/questions/83640

  •  01-07-2019
  •  | 
  •  

質問

検索が対数時間で行われる std::set や std::map などのデータ型の場合、実装では開始イテレータと終了イテレータを維持する必要がありますか?アクセスの開始と終了は、対数時間で発生する可能性のある検索を意味しますか?

私は常に、開始と終了は常に一定の時間で起こると考えてきましたが、Josuttis ではこれの確証が見つかりません。現在、パフォーマンスに関して徹底的に取り組む必要があることに取り組んでいるので、基礎を確実にカバーしたいと考えています。

ありがとう

役に立ちましたか？

解決

それらは一定の時間内に発生します。ISO/IEC 14882:2003 規格の 466 ページを見ています。

表 65 - コンテナの要件

a.begin(); (一定の複雑さ)

a.end(); (一定の複雑さ)

表 66 - リバーシブルコンテナの要件

a.rbegin(); (一定の複雑さ)

a.rend(); (一定の複雑さ)

他のヒント

はい、によると http://www.cplusplus.com/reference/stl/, 、begin()、end() などはすべて O(1) です。

C++ 標準では、23.1 (コンテナ要件) の表 65 に、begin() と end() が定数時間を必要とするものとしてリストされています。実装がこれに違反している場合は、準拠していません。

コードを見てください。ここでは、GNU libstdc++ の std::map 内の反復子を確認できます。

std::map

すべての終わりがつながっていることがわかります...すべて一定時間で実装されます。

ただし、hash_map には注意してください。begin() は定数ではありません。

std::set の場合

始める：定数、終了:定数、rbegin：一定、レンド：絶え間ない、

std::map の場合

それらも定数です（すべて）

疑問がある場合は、確認してください www.cplusplus.com

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top