How to understand the requirement of `std::lower_bound`?

Question

As per the document about std::lower_bound, which says that:

The range [first, last) must be partitioned with respect to the expression element < value or comp(element, value), i.e., all elements for which the expression is true must precede all elements for which the expression is false. A fully-sorted range meets this criterion.

I have a little difficulty to fully understand it.

1.What's element < value? It seems that element (or value) is never mentioned before this paragraph in the aforementioned document. Does the said element mean the elements before the current element, and the said value means the value of the current element?

UPDATED:

2.Since whether a specific sequence is valid(i.e. suits the requirement) or not depends the value, the requirement for a specific sequence could not be always be guaranteed when the value is different. I think it's meaningless to define such a requirement. It's seems that a fully sorted seuqence is more reliable and practical.

Answer 1

From cppreference

Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found.

The range [first, last) must be partitioned with respect to the expression element < value or comp(element, value), i.e., all elements for which the expression is true must precede all elements for which the expression is false. A fully-sorted range meets this criterion.

From your question:

What's element < value? It seems that element (or value) is never mentioned before this paragraph in the aforementioned document. Does the said element mean the elements before the current element, and the said value means the value of the current element?

value and comp are mentioned in the function signatures at the beginning of the page. value is the argument with which you call std::lower_bound, and comp an optional comparison function; shouldn't a comparison function be provided, < would be used instead.

element refers to each element in the range [first, last).

So, what std::lower_bound does is to compare value to the elements in the range until it finds the first one that is not "less than" (through < or comp) value.

The requirement for std::lower_bound to work is that the input range is partitioned in such a way that all the elements that are "less than" value are placed before the rest; that requirement is met, for example, if the range is fully sorted.

(As @Passerby mentions in the comments below, std::lower_bound won't need to compare against all the elements that are "less than" value, due to the partitioned range requirement, but that is an implementation detail.)

Answer 2

Partitions

A list of values may be partitioned, or grouped according to some criterion. For example:

?????????????????????????????????????????
|  2 |  7 |  3 | -5 | 11 | 94 | 15 | 12 |
?????????????????????????????????????????
        x < 10      |       x ? 10

In this list we have two partitions:

• elements where x < 10
• elements where x is not < 10

Further, the criterion implies an order:

• all xs such that (x < 10) come —before— all xs such that !(x < 10)

(In C++ we tend to use a “comparator” or “comparison function” to specify the criterion.)

Notice that it does not matter what order the elements are relative to each other in each partition! That said, it is also noteworthy that if the list were sorted, it would still have the exact same two partitions:

?????????????????????????????????????????
| -5 |  2 |  3 |  7 | 11 | 12 | 15 | 94 |
?????????????????????????????????????????
        x < 10      |       x ? 10

(My example here has two equal-sized partitions. That is not necessarily the case. A partition may have zero or more elements, and each partition may have a different size than the others.)

Lower bound ? index of start of partition

What the lower_bound algorithm does is find the first element of an existing partition.

The only caveat that the algorithm requires is that the sequence must already be partitioned in a way that the sort criterion makes sense. (Because the algorithm only finds partitions, it does not sort stuff!)

For example, our original sequence does not support a criterion that separates elements into (x < 7) and (x ? 7), because the elements are not partitioned in that way — it would not make sense to try to find the “first” element of a partition that doesn’t exist.

This is the meaning of the language used by cppreference.com.