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

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 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_at_[hidden]>:

> 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>::reduceC++ 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
>