c++ - lower_bound pred
partition_point와 lower_bound의 차이점은 무엇입니까? (2)
그것들은 기본적으로 동일합니다. 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);
});
}
두 알고리즘은 파티션 된 범위의 파티션 포인트를 찾는 데 의존하며, 검색 할 다른 인수를 사용합니다 ( partition_point 에 대한 단항 술어, 값 또는 값 및 lower_bound 대한 2 진 조건).
우리는 일반적으로 이진 술어를 사용하여 정렬 된 범위의 컨텍스트에서 lower_bound 를 생각합니다. 단, 이러한 술어와 관련하여 완전히 정렬 된 범위 는 해당 알고리즘에 대한 요구 사항 이 아니 어도됩니다.
우리 upper_bound 하는 동안 upper_bound 는 피연산자가 반전되고 술어가 부정 된 경우 partition_point 와 관련하여 구현 될 수 있습니다.
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);
});
}
이 두 단어가 다르게 표현되는 것은 이상합니다.
lower_bound 반환 ( upper_bound 문언은 similar ) :
범위
[first, last]i[first, last]모든 반복자j에 대해 다음과 같은 해당 조건이 유지되도록[first, last]범위에있는 가장 가까운 반복자i.*j < value또는comp(*j, value) != false.
partition_point 반환 하는 동안
none_of(mid, last, pred)all_of(first, mid, pred)와none_of(mid, last, pred)가 모두true인 반복자.
그 구는 범위가 분할되어 있기 때문에 동등합니다. 그러나 언뜻보기에는 그런 식으로 보이지 않습니다.
C ++ 11에는 알고리즘 std::partition_point() 있습니다. 그러나 모든 경우에 나는 그것을 시도했다 std::lower_bound() 같은 대답을 제공합니다. 유일한 차이점은 편리한 T& value 매개 변수입니다.
내가 놓친 것이 있습니까? 아니면이 두 가지 기능이 어느 정도 동일한 일을하고 있습니까?
둘 다 이진 검색 알고리즘을 사용합니다 (임의 액세스 반복 자용).
-
std::lower_bound는 표현element < value또는comp(element, value)대해 분할 된(2 진) 술어에 따라 범위를 정렬해야합니다 (범위가 2 진 술어에 따라 정렬되는 경우). -
std::partition_point는 범위가 (단항) 술어에 따라 분할되어야합니다.
실제로 다른 알고리즘을 사용할 수있는 술어를 작성할 수 있습니다.
와:
const std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8};
lower_bound 할 수 있습니다 :
assert(std::is_sorted(v.begin, v.end(), std::less<>));
auto it1 = std::lower_bound(v.begin, v.end(), 5, std::less<>);
또는 partition_point 와 함께 :
auto pred = [](int e){ return e < 5; }
assert(std::is_partition(v.begin, v.end(), pred));
auto it2 = std::partition_point(v.begin, v.end(), pred);
assert(it1 == it2); // *it1 = 5
또는 다른 쪽에서
const std::vector<int> v{1, 3, 4, 2, 7, 5, 8, 6};
partition_point 할 수 있습니다 :
auto pred = [](int e){ return e < 5; }
assert(std::is_partition(v.begin, v.end(), pred));
auto it1 = std::partition_point(v.begin, v.end(), pred);
또는 lower_bound :
auto pred2 = [](int lhs, int rhs){ return (lhs < 5) > (rhs < 5); }
assert(std::is_sorted(v.begin, v.end(), pred2));
auto it2 = std::lower_bound(v.begin, v.end(), 5, pred2);
assert(it1 == it2); // *it1 == 7
