On Tue, 11 Feb 2025 at 16:20, Александр Поваляев <apovalyaev@gmail.com> 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.