template<class UnaryPred>

iterator partition_point(UnaryPred p);

template<class UnaryPred>

const_iterator partition_point(UnaryPred p) const;

It examines the keys in the container, which must be partitioned by bool(p(key)), and returns the end iterator to the first partition (i.e. the first key which bool(p(key)) is false, end() if no such key).

If the keys are not partitioned with respect to bool(p(key)), the behavior is undefined.

It calls p(key) at most O(log(size() + 1)) times.

Following is one of the use cases I've encountered a lot in competitive programming.

We need to process three kinds of queries, starting from an empty set S. (assume everything fits in int)

Q1. Add a point (x, y) to S, assuming that all x coordinates are non-negative and unique for the sake of simplicity. Same for y coordinates.

Q2. Given A, find the point (x, y) with maximum y such that x >= A, or report that there are none

Q3. Given B, find the point (x, y) with maximum x such that y >= B, or report that there are none

We want to do this online. i.e. if the current query is Q2 or Q3, we only get to know queries after answering it.

With this proposal, there's a simple way to solve this in amortized O(log(n)) time for each queries.

// T contains all points (x, y) such that there is no point (z, w) with x < z and y < w
// Clearly, (x, y) not in T cannot be an answer to Q2 or Q3
// The points are maintained in increasing order of x
// By the definition of T, y coordinates are in decreasing order

std::set<std::pair<int, int>> T;

auto Q1 = [&](int x, int y)->void{

    auto it = T.lower_bound(std::pair{x, y});
    // erase all point (z, w) with z < x and w < y from T
    while(it != T.begin() && std::prev(it)->second < y) T.erase(std::prev(it));
    // insert (x, y) if no point (z, w) satisfy x < z and y < w
    if(it == T.end() || y > it->second) T.insert(it, std::pair{x, y});
};

// Returns (-1, -1) if no answer
auto Q2 = [&](int A)->std::pair<int, int>{
    // use the fact that x coordinate is in increasing order
    auto it = T.partition_point([&](auto key){ return key.first < A; });
    return it == T.end() ? std::pair{-1, -1} : *it;
};

// Returns (-1, -1) if no answer
auto Q3 = [&](int B)->std::pair<int, int>{
    // use the fact that y coordinate is in decreasing order
    auto it = T.partition_point([&](auto key){ return key.second >= B; });
    return it == T.begin() ? std::pair{-1, -1} : *std::prev(it);
};

On Wed, Jun 12, 2024 at 4:29 AM Jonathan Wakely <cxx@kayari.org> wrote:

On Tue, 11 Jun 2024, 20:02 Aeren via Std-Proposals, <std-proposals@lists.isocpp.org> wrote:

Hi, this is my first proposal to C++ STL and I'm looking forward to getting some feedback :)

std::lower_bound / std::upper_bound lets you binary search on a range defined by a pair of legacy random access iterators, and we have a BBST counterpart for this: std::(set / map / multiset / multimap)::(lower_bound / upper_bound)

I would like to propose to add the BBST counterpart of std::partition_point, which generalizes both std::lower_bound and std::upper_bound.

This addition would let us binary search on dynamically changing points with an arbitrary binary predicate on which the points are "partitioned".

What would be your proposed API, what would the precise semantics be, and what are the motivating use cases? 

Currently, there's a workaround for this using the signature (3) and (4) on cppreference lower_bound doc. However, it is very ugly to do this because it forces K and x to be meaningless and forces me to define a weird comparator with K.

Thank you for taking your time to read this proposal :)

Aeren

--
Std-Proposals mailing list
Std-Proposals@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals

--
Std-Proposals mailing list
Std-Proposals@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals