標準ライブラリ コレクション (std::map など) のイテレータをインクリメント/デクリメントするのにかかる時間に上限はありますか? (コンテナ自体は変更されていないと仮定します。)
質問する
555 次
2 に答える
3
std::mapイテレータのインクリメント操作は、償却された定数コストを持つことが保証されています。つまり、n 個の要素の完全な走査は O( n ) です。実際、これはすべての反復子に当てはまります (24.2.1/8 を参照)。
イテレータのすべてのカテゴリは、特定のカテゴリに対して一定時間 (償却) で実現可能な関数のみを必要とします。
于 2012-11-14T16:22:40.147 に答える
1
いいえ、イテレータのインクリメント/デクリメントにかかる時間に上限はありません。標準は、プログラムの実行にかかる時間について沈黙しています。私の知る限り、一般的なコンパイラはすべてこの件について沈黙しています。
ただし、一般的な実装では、かなりの時間がかかることは何もしません。メモリ割り当てやファイル IO はありません (VM のページインを除く)。
于 2012-11-14T16:18:14.040 に答える