As per the document about std::lower_bound, which says that:
The range [first, last) must be partitioned with respect to the expression
element < valueorcomp(element, value), i.e., all elements for which the expression istruemust precede all elements for which the expression isfalse. 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.
CodePudding user response：
What's element < value
value is the parameter to lower_bound, see at the beginning of that page:
template< class ForwardIt, class T > ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
The value in question is mentioned right here, the last parameter to the template. And element, references to some element and every element in the sequence.
This is rather a terse way to define the following: take every element in the sequence, one element at a time. When you do that, all elements for which the expression element < value returns true must appear in the sequence before all other elements, for which the same expression is false. It is explicitly intentional for the requirements to be defined in this manner, here's the explanation:
For example, if value is 4, and we're talking about natural integers, here's one such sequence:
1, 2, 3, 4, 5, 6
Here, all the elements for which this expression is true (1, 2, and 3), appear before all the elements for which this expression is false (4, 5, and 6).
The following sequence is also a valid sequence, in this case:
3, 2, 1, 6, 5, 4
Here, same thing: 3, 2, and 1, for which the expression element < 4 is true, appears before value 4, 5 and 6 for which the expression element < 4 would be false. So, yes, this would also be a valid sequence for a call to lower_bound for the value of 4.
The following sequence will NOT be a valid sequence for this specific case of using std::lower_bound:
1, 2, 4, 3, 5, 6
And as far as why is this lower_bound requirement specified in such an strange manner, well, that would be a different question. But this is what it means.
CodePudding user response：
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.)
CodePudding user response：
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.