Date: Tue, 11 Jun 2024 17:38:02 -0400

On Tue, Jun 11, 2024 at 5:05 PM Aeren via Std-Proposals <

std-proposals_at_[hidden]> wrote:

> 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_at_[hidden]> wrote:

>

>>

>>

>> On Tue, 11 Jun 2024, 20:02 Aeren via Std-Proposals, <

>> std-proposals_at_[hidden]> 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

>>> <https://en.cppreference.com/w/cpp/container/set/lower_bound>. 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.

>>>

>>

Yes, this is one of the possible approaches. The other, which is probably

what most competitive programmers would do, is just use twice as much

memory by maintaining a parallel second `std::set` that's sorted on y

instead of x. That way, you can just do lower_bound on the first set to

answer queries of type Q2, and lower_bound on the second set to answer

queries of type Q3.

I think we need motivation outside of competitive programming in order to

generate interest in standardization. I don't even mention competitive

programming to WG21 because I know they'll just laugh at me.

>

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

>>> Aeren

>>> --

>>> Std-Proposals mailing list

>>> Std-Proposals_at_[hidden]

>>> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals

>>>

>> --

> Std-Proposals mailing list

> Std-Proposals_at_[hidden]

> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals

>

std-proposals_at_[hidden]> wrote:

> 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_at_[hidden]> wrote:

>

>>

>>

>> On Tue, 11 Jun 2024, 20:02 Aeren via Std-Proposals, <

>> std-proposals_at_[hidden]> 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

>>> <https://en.cppreference.com/w/cpp/container/set/lower_bound>. 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.

>>>

>>

Yes, this is one of the possible approaches. The other, which is probably

what most competitive programmers would do, is just use twice as much

memory by maintaining a parallel second `std::set` that's sorted on y

instead of x. That way, you can just do lower_bound on the first set to

answer queries of type Q2, and lower_bound on the second set to answer

queries of type Q3.

I think we need motivation outside of competitive programming in order to

generate interest in standardization. I don't even mention competitive

programming to WG21 because I know they'll just laugh at me.

>

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

>>> Aeren

>>> --

>>> Std-Proposals mailing list

>>> Std-Proposals_at_[hidden]

>>> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals

>>>

>> --

> Std-Proposals mailing list

> Std-Proposals_at_[hidden]

> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals

>

-- *Brian Bi*

Received on 2024-06-11 21:38:17