「プログラミング言語C++第四版」について気が付いたことなど (15)

間違ってるわけではないのだけど、あらぬ誤解を招きそうな …


32.6.1   2分探索

…(略、(14)の続き)…

不思議に感じられるかもしれないが、2分探索アルゴリズムでは、ランダムアクセス反復子は不要であり、前進反復子で十分である。


原文:

Curiously enough, the binary search algorithms do not require random-access iterators: a forward iterator suffices.


考察:

forward iterator で実装できるのは確かなのだけれども、binary_search()は random-access iteratorが与えられた時はそれを使って探索を効率化することになっている。なので、「不要」と言い切っちゃうのは抵抗があるし、「前進反復子で十分」というのはあらぬ誤解を招くんじゃないだろうか。というわけで。


試訳:

奇妙に思えるかもしれないが、二分探索アルゴリズムにはランダムアクセス反復子は必須ではない。前進反復子でも用は足りる。

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です