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

lower_boundとupper_bound、ややこしい仕様ではあるのだけれども …


32.6.1    2分探索

…(略)…

lower_bound(first,last,k)は、kを探索するのではなく、kより大きなキーをもつ先頭の要素を指す反復子を返す。ただし、kより大きなキーをもつ要素が存在しなければlastを返す。同様のエラー通知方法は、upper_bound()やequal_range()でも行われている。


原文:

If lower_bound(first,last,k) doesn’t find k, it returns an iterator to the first element with a key greater than k, or last if no such greater element exists. This way of reporting failure is also used by upper_bound() and equal_range().


試訳:

lower_bound(first,last,k)がkと一致するキーを見つけられない場合はkより大きなキーを持つ最初の要素を指す反復子を、その様な要素が存在しない場合はlastを返す。同様のエラー通知方法は、upper_bound() と equal_range() でも用いられている。


考察:

ややこしいが、(探索に成功した場合)lower_boundはkと一致する最初の要素を返し、upper_boundはkより大きなキーを持つ最初の要素を返す。なので「kを探索するのではなく」だとupper_boundの仕様になってしまう。たぶん、一覧表の方に出ているlower_bound関数の仕様(p=lower_bound(b,e,v)  pは、[b:e)内で最初に出現するvを指すようになる)を忘れていて、かつ文頭の”If”を見落としている。

 

コメントを残す

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