On Tue, 11 Feb 2025 at 08:30, Александр Поваляев via Std-Proposals <std-proposals@lists.isocpp.org> wrote:

A Proposal to Add a New Multiset container Method to the Standard Library Technical Report

I. Motivation

The idea of a new method is quite straightforward. While std::multiset is a constant member of Standard Library Containers
list, it is quite specific. While being a kind of "extension" to std::set, std::multiset exports the same list of methods
as std::set does.

However, there is an internal structure which makes these two containers behave differently. std::multiset provides a tool
to add a countable number of the elements within the same key value. So, 'count' method returns the number of elements
matching a specific key. For std::set 'count' method can return 0 and 1 only. Whereas std::multiset 'count' method can
return 0, 1, ... N corresponding the number of the elements within the same key value.

Each time 'insert' method is called:
* it sets an internal counter to 1 in case of std::set
* it INCREASES an internal counter in case of std::multiset

There is no such internal counter in reality. The container doesn't need to keep such a count for each key value (it would just waste memory).

When you call count, it doesn't return an internal counter, it counts how many elements match the key.

 

So, here is the case when these two containers behave differently while providing right the same interface method.
It is because of the different in internal containers structure.

They don't have any different structure.

 

The same is true while an element is being erased by means of 'erase' method:
* it sets an internal counter to 0 in case of std::set
* it DOES NOT DECREASE an internal counter in case of std::multiset - it just erased all the elements within the same
  key value and sets and internal counter to 0

Here we go. Compared to the existing standard container std::set, std::multiset can offer an advantage making its interface
more universal:

* a method which acts right the opposite way as 'insert' does
* a method which can be used to decrease the number of elements with the same key value in more discrete. robust and more fine-grained.

You can use std::erase_if to do this, or something like:

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 [lo,hi] = s.equal_range(key);

  auto last = lo;

  while (last != hi &&  std::cmp_less(n, count))

  {

    ++last;

    ++n;

  }

  s.erase(lo, last);

  return n;

}

It doesn't need to be a member function.

 

II. Impact On the Standard

This proposal is a pure std::multiset container interface extension. While it does not require any change in the core language, it might
benefit from providing more universal way to do the simple things. It allows to express the same logic in less value of C++ code.

III. Design Decisions

This proposal is about adding new method 'reduce' to std::multiset container interface.

std::multiset<Key,Compare,Allocator>::reduce

C++ Containers library std::multiset

(1) size_type reduce( const Key& key );

(2)
template< class K >
size_type reduce( K&& x );

(3) size_type reduce( const Key& key, size_type count );

(4)
template< class K >
size_type reduce( K&& x, size_type count );

This method acts in right the opposite way to how method 'insert' does. Method 'reduce' decreases the number of std::multiset elements with
the same key value. And while being supplied within the second argument 'size_type count', method 'reduce' decreases the number of std::multiset
elements with the same key value but several times.
 
So, this innovation implies several changes to standard template library header file <set>.

VI References

[1] Bjarne Stroustrup, The C++ Programming Language 3rd edition, 1997, Addison Wesley ISBN 0-201-88954-4 p496
[2] Matthew H. Austern, Generic Programming and the STL, 1998, Addison Wesley ISBN 0-201-30956-4 pp59-67
[3] Nicolai M. Josuttis, The C++ Standard Library - A Tutorial and Reference, 1999, Addison Wesley ISBN 0-201-37926-0 pp218-221

вт, 11 февр. 2025 г. в 11:25, Александр Поваляев <apovalyaev@gmail.com>:

I. Motivation

The idea of a new method is quite straightforward. While std::multiset is a constant member of Standard Library Containers
list, it is quite specific. While being a kind of "extension" to std::set, std::multiset exports the same list of methods
as std::set does.

However, there is an internal structure which makes these two containers behave differently. std::multiset provides a tool
to add a countable number of the elements within the same key value. So, 'count' method returns the number of elements
matching a specific key. For std::set 'count' method can return 0 and 1 only. Whereas std::multiset 'count' method can
return 0, 1, ... N corresponding the number of the elements within the same key value.

Each time 'insert' method is called:
* it sets an internal counter to 1 in case of std::set
* it INCREASES an internal counter in case of std::multiset

So, here is the case when these two containers behave differently while providing right the same interface method.
It is because of the different in internal containers structure.

The same is true while an element is being erased by means of 'erase' method:
* it sets an internal counter to 0 in case of std::set
* it DOES NOT DECREASE an internal counter in case of std::multiset - it just erased all the elements within the same
  key value and sets and internal counter to 0

Here we go. Compared to the existing standard container std::set, std::multiset can offer an advantage making its interface
more universal:

* a method which acts right the opposite way as 'insert' does
* a method which can be used to decrease the number of elements with the same key value in more discrete. robust and more fine-grained.

II. Impact On the Standard

This proposal is a pure std::multiset container interface extension. While it does not require any change in the core language, it might
benefit from providing more universal way to do the simple things. It allows to express the same logic in less value of C++ code.

III. Design Decisions

This proposal is about adding new method 'reduce' to std::multiset container interface.

std::multiset<Key,Compare,Allocator>::reduce

C++ Containers library std::multiset

(1) size_type reduce( const Key& key );

(2)
template< class K >
size_type reduce( K&& x );

(3) size_type reduce( const Key& key, size_type count );

(4)
template< class K >
size_type reduce( K&& x, size_type count );

This method acts in right the opposite way to how method 'insert' does. Method 'reduce' decreases the number of std::multiset elements with
the same key value. And while being supplied within the second argument 'size_type count', method 'reduce' decreases the number of std::multiset
elements with the same key value but several times.
 
So, this innovation implies several changes to the standard template library header file <set>.

VI References

[1] Bjarne Stroustrup, The C++ Programming Language 3rd edition, 1997, Addison Wesley ISBN 0-201-88954-4 p496
[2] Matthew H. Austern, Generic Programming and the STL, 1998, Addison Wesley ISBN 0-201-30956-4 pp59-67
[3] Nicolai M. Josuttis, The C++ Standard Library - A Tutorial and Reference, 1999, Addison Wesley ISBN 0-201-37926-0 pp218-221

--
Std-Proposals mailing list
Std-Proposals@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals