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
>

-- 
*Brian Bi*