On Tue, 11 Feb 2025, 17:46 Александр Поваляев, <apovalyaev_at_[hidden]> wrote:

> [[*My comments below in bold*]]
>
> вт, 11 февр. 2025 г. в 19:50, Jonathan Wakely <cxx_at_[hidden]>:
>
>>
>>
>> On Tue, 11 Feb 2025 at 16:20, Александр Поваляев <apovalyaev_at_[hidden]>
>> wrote:
>>
>>> Hmm
>>>
>>> I think that what a 'reduce' method is supposed to do is a very common
>>> case.
>>>
>>
>> I don't think I've ever needed it.
>>
>>
>>> std:;multiset can handle several elements with the same key value, so it
>>> is quite straightforward to have a method in-place which will take care of
>>> this. Implementing this behaviour each time in your code is anyway a
>>> possibility to make a mistake.
>>> Moreover, when 'reduce' is a method, there is a possibility to make its
>>> realization more efficient within the lapse of time (for example, when an
>>> internal structure is changed somehow).
>>> Cause equal_range requires a lot of excessive comparison operations
>>> which might be quite inefficient.
>>> For example, if std::multiset consists of N elements within the same key
>>> value (and N is quite big: 1000, 10000, e.t.c.), your code will require
>>> 1000 comparison operations to just delete a couple.
>>>
>>
>> No it won't, it's a binary tree so it's logarithmic.
>>
> *[[Aleksandr]] I don't say it is linear. According to
> https://en.cppreference.com/w/cpp/container/multiset/equal_range
> <https://en.cppreference.com/w/cpp/container/multiset/equal_range>, it is
> logarithmic, but in the SIZE OF CONTAINER not the NUMBER OF ELEMENTS we're
> going to operate to. So, excessive comparison operations will be inplace.*
>
>


I don't know what you mean by "inplace" but finding both bounds has to be
done efficiently, using the RB tree structure.





> But here's an (untested) alternative that doesn't use equal_range:
>>
>> template<typename T, typename Cmp, typename Alloc>
>> std::size_t
>> reduce(std::multiset<T, Cmp, Alloc>& s, const T& key, std::size_t count =
>> -1zu)
>> {
>> std::size_t n = 0;
>> auto it = s.find(key);
>> if (it == s.end())
>> return 0;
>> while (n < count)
>> {
>> it = s.erase(it);
>> ++n;
>> if (it == s.end() || s.key_comp()(key, *it))
>> break;
>> }
>> return n;
>> }
>>
>> This will do n comparisons instead of O(log2(N)) comparisons, where N is
>> s.count(key). You could make it adaptive so it uses a linear search for
>> small count arguments and equal_range otherwise.
>>
>> It still doesn't need to be a member function though.
>>
>
> *[[Aleksandr]] My logic and the original proposal is not about the
> particular implementation. It is more about a general approach to STL
> container structures. Once we can add one by one new container elements
> (with the same key value), we should have an opportunity to delete them
> also one by one.*
>