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




binary-search