>
> 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.
>>
>
> Why not? If you find (x, y) in Q2, you just delete it and then delete (y,
> x) from Q3 immediately thereafter, and vice versa.
>

Ah yes you're right. I was mistaken.


> Writing and presenting papers is a lot of work, so my advice is to think
> about how you would write the "motivation" section of the paper before you
> actually start writing it. A code example that could plausibly be in a
> non-competitive-programming application would help.


Thanks. I will keep those in mind.

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

>
>
> On Tue, Jun 11, 2024 at 6:15 PM Aeren <tiltingwindmill1564_at_[hidden]>
> wrote:
>
>> 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.
>>
>
> Why not? If you find (x, y) in Q2, you just delete it and then delete (y,
> x) from Q3 immediately thereafter, and vice versa.
>
>
>>
>> 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"?
>>
>
> From a theoretical point of view, I agree that `partition_point` seems
> like a natural generalization of `lower_bound` and `upper_bound`. The
> internal balanced binary search tree repeatedly descends into one subtree
> or another based on some predicate, so why not just let the user specify
> that predicate directly?
>
> And you can certainly write a paper and submit it in a mailing and get a
> slot allocated in LEWG to discuss the proposal. If that happens, then there
> will be a bunch of people in the room, some of them will say "oh yeah, I've
> also had to do X, Y, and Z where this proposed method would have helped"
> and there will also be other people who could be persuaded to encourage
> further work on your paper even if they haven't personally encountered the
> use cases, if you can convince them that the use cases are common enough to
> make it worthwhile. If they think that the use cases are rare, they'll
> probably vote against it.
>
> Writing and presenting papers is a lot of work, so my advice is to think
> about how you would write the "motivation" section of the paper before you
> actually start writing it. A code example that could plausibly be in a
> non-competitive-programming application would help.
>
>
>>
>> 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*
>>>
>>
>
> --
> *Brian Bi*
>