>
> 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.
>

If we also require that the element found in Q2 and Q3 must be deleted,
this approach doesn't work anymore.

 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.


This is my first time proposing and I don't know how things get decided on
WG21 so please correct me if I'm missing something, but this statement
sounds weird to me for the following reasons

1. In my initial proposal, I stated that my motivation is adding a
counterpart to std::partition_point to BBST structures, just like
std::lower_bound and std::upper_bound, and this doesn't really sound
"competitive-programming-motivated" to me. This is motivated by the
"completeness" of the standard library more than anything.
2. The example I gave applies to any setting that can be abstracted into
that form, and it looked general enough that whenever you're dealing with
optimization over multivariate functions, I thought that this proposal can
be very useful. I'm not sure how adding "competitive programming" changes
anything. Would it be better if I instead wrote "I found this
abstractization in my production code"?

On Wed, Jun 12, 2024 at 6:38 AM Brian Bi <bbi5291_at_[hidden]> wrote:

>
>
> 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*
>