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.

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.