[[[[[My comments in bold]]]]]

вт, 11 февр. 2025 г. в 20:12, Sebastian Wittmeier via Std-Proposals <
std-proposals_at_[hidden]>:

> One would probably use a multiset to store distinct objects per key
> (otherwise one would probably map the key to an int).
>
>
>
> Common operations are to get all objects with a key or to remove all
> objects with a key.
>
>
>
> When would one want to delete some objects with a key, but not all,
> without specifying which objects?
>
>
>
> Is there any practical use case?
>

[[[[Aleksandr]]]]] I believe it might be the case when a priority queue is
needed while order of elements is also preserved (so, it is a
priority_queue + the order of inserts being preserved).


>
>
> -----Ursprüngliche Nachricht-----
> *Von:* Александр Поваляев via Std-Proposals <
> std-proposals_at_[hidden]>
> *Gesendet:* Di 11.02.2025 17:20
> *Betreff:* Re: [std-proposals] A Proposal to Add a New Multiset container
> Method to the Standard Library Technical Report
> *An:* Jonathan Wakely <cxx_at_[hidden]>; std-proposals_at_[hidden];
> *CC:* Александр Поваляев <apovalyaev_at_[hidden]>;
> Hmm
>
> I think that what a 'reduce' method is supposed to do is a very common
> case. 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.
>
> вт, 11 февр. 2025 г. в 17:12, Jonathan Wakely <cxx_at_[hidden]>:
>
>
>
> On Tue, 11 Feb 2025 at 11:27, Александр Поваляев <apovalyaev_at_[hidden]>
> wrote:
>
> Hi there,
>
> *[My comments below in bold] *
>
> вт, 11 февр. 2025 г. в 13:04, Jonathan Wakely <cxx_at_[hidden]>:
>
>
>
> On Tue, 11 Feb 2025 at 08:30, Александр Поваляев via Std-Proposals <
> std-proposals_at_[hidden]> 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;
> }
>
> [Aleksandr] It looks a little bit tricky to implement such an easy
> operation (just to remove a particular number of elements with the same key
> value).
> There is a well-known "common rule" that it is good to
> hold any class method in bounds of 1 - 15 lines.
> Without such kind of universality (a single "reduce"
> method), it will be much harder to follow the rule.
>
>
> Sorry, I don't understand this. You add the function above to your code,
> now you can call it in one line. The same as if it was a new member
> function of multiset.
>
>
>
> Erasing elements is not about STL iterators, but more
> about STL containers functionality.
> So, introducing such a std::multiset interface
> extension can be considered as one more step towards STL containers
> universality.
>
>
>
> 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_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
>
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>