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

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