C++11 includes the algorithm std::partition_point()
. However for all the cases I have tried it gives the same answer as std::lower_bound()
. The only difference being the convenient T& value
parameter.
Did I miss something or are these two functions doing more or less the same thing?
The lower_bound() method in C++ is used to return an iterator pointing to the first element in the range [first, last) which has a value not less than val. This means that the function returns an iterator pointing to the next smallest number just greater than or equal to that number.
Upper bound and Lower bound for non increasing vector in C++ In a Vector, lower bound returns an iterator pointing to the first element in the range that does not compare the given value. Upper Bound returns an iterator pointing element in the range that smaller than given value.
lower_bound in c++ stl returns an iterator even when the element is not present.
They are basically equivalent. This would be a valid implementation of lower_bound
:
template <typename ForwardIterator, typename T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
T const& value)
{
return partition_point(first, last, [&](auto&& elem) {
return elem < value;
});
}
template <typename ForwardIterator, typename T, typename Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
T const& value, Compare comp)
{
return partition_point(first, last, [&](auto&& elem) {
return comp(elem, value);
});
}
The two algorithms rely upon finding the partition point of a partitioned range, they just take different arguments with which to search (a unary predicate for partition_point
, vs a value or value and binary predicate for lower_bound
).
We just typically think of lower_bound
in the context of sorted range with a binary predicate - even though a fully sorted range with respect to such a predicate is not a requirement for that algorithm.
While we're at it, upper_bound
can also be implemented in terms of partition_point
, just with the operands flipped and the predicate negated:
template <typename ForwardIterator, typename T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
T const& value)
{
return partition_point(first, last, [&](auto&& elem) {
return !(value < elem);
});
}
template <typename ForwardIterator, typename T, typename Compare>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
T const& value, Compare comp)
{
return partition_point(first, last, [&](auto&& elem) {
return !comp(value, elem);
});
}
It's weird how differently the two are worded.
lower_bound
returns (the upper_bound
wording is similar):
The furthermost iterator
i
in the range[first, last]
such that for every iteratorj
in the range[first, i)
the following corresponding conditions hold:*j < value
orcomp(*j, value) != false
.
while partition_point
returns
An iterator
mid
such thatall_of(first, mid, pred)
andnone_of(mid, last, pred)
are bothtrue
.
Those phrases are equivalent since the requirement is that the range is partitioned. But it sure doesn't seem that way at first glance.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With