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

Question

ルックアップが対数時間で行われる std::set や std::map などのデータ型の場合、開始イテレータと終了イテレータを維持するために実装が必要ですか? begin と end へのアクセスは、対数時間で発生するルックアップを意味しますか?

開始と終了は常に一定の時間内に発生すると常に想定してきましたが、Josuttis でこれを確認することはできません。今は、パフォーマンスについて分析する必要があるものに取り組んでいるので、自分のベースを確実にカバーしたいと考えています。

ありがとう

score 9 · Accepted Answer

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

表 65 - コンテナの要件

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

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

表 66 - 可逆コンテナの要件

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

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

score 5 · Accepted Answer

はい、http： //www.cplusplus.com/reference/stl/によると、begin（）、end（）などはすべてO（1）です。

score 4 · Accepted Answer

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

score 2 · Accepted Answer

コードを見るだけで、GNUlibstdc++のstd::mapにイテレータが表示されます。

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

score 1 · Accepted Answer

1

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

于 2008-09-17T14:58:55.530 に答える

score 0 · Accepted Answer

std::setの場合

begin：定数、end：定数、rbegin：定数、rend：定数、

std::mapの場合

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

6 に答える 6