Talk:cpp/algorithm/binary search


I believe the definition for comp is incorrect. The standard says:

Requires: The elements e of [first,last) are partitioned with respect to the expressions e < value and !(value < e) or comp(e, value) and !comp(value, e). Also, for all elements e of [first, last), e < value implies !(value < e) or comp(e, value) implies !comp(value, e).

(I'm not sure where, I'm quoting what I was told by Howard Hinnant on the Apple developer forums.)

It states that value < e and e < value will both be used, which means that both T and *ForwardIt must implicitly convert to both Type1 and Type2.

Also, I believe the potential implementation section is wrong for both versions as well, as the standard doesn't require operator != .

Joseph Galbraith 17:12, 6 May 2013 (PDT)

Note that a similar change was made to the equal_range page on 29-oct-2012.

Joseph Galbraith 18:19, 6 May 2013 (PDT)

you're right (you don't even need to name drop), the comparison function is indeed called both ways, and equality/non-equality operator is indeed wrong to show in the "possible implementation". We should probably change 'equal' to 'equivalent' in the description (both here and equal_range) too. I'll make the changes when I find the time, but you can certainly make them yourself: it is a wiki. --Cubbi 07:15, 7 May 2013 (PDT)
actually, nevermind the "possible implementation", it was correct, and matched Howard Hinnant's own. I didn't read it carefully. It was only missing one "comp" --Cubbi 11:46, 7 May 2013 (PDT)