Robert Fendt wrote:
Hi,
does anyone know if std::lower_bound and upper_bound are
guaranteed to be reasonably well-behaved even if the input list
is not completely sorted?
E.g., if I get input like this:
int myvals[] = {1, 4, 5, 7, 2, 3, 8, 9};
is it still 'legal' to use std::lower_bound(4) on it (granted it
is not guaranteed whether the result will be 1 or 6)? It would
not matter which value were returned, as long as it is a legal
array index.
Formally, that's allowed by the C++03 standard. But that's a bug, and
it's expressly disallowed in C++0x. When calling lower_bound(first,
last), "[t]h elements e of [first, last) shall be partitioned with
respect to the expression e < value or comp(e, value)." And "partitioned
with respect to an expression f(e)" means that "there exists an integer
n such that for all 0 <= i < distance(start, finish), f(*(start + i)) is
true if and only if i < n."