Well, to make things more clear.
The process of inserting a new element with the same key value might lead
to a different result (different position of a newly inserted element).
And the result depends upon whether a hint is being used within 'insert'
method of std::multiset or not.
But once the new element has been inserted, the order is preserved starting
from that moment.

Let's call an 'oldest' element that one which is closest to the beginning
among all the elements within the same key value.
To the moment when the 'reduce' method is called.

'reduce' method is not supposed to use 'equal_range' as we have already
discovered. Since it would double the number of compare operations required.
For example, std::multiset count is 2^20, 'equal_range' will require 2*20
compare operations.
So, we will use the implementation of 'reduce' method which is closer to
the second variant you proposed (when we find the first element over the
sequence of the element with the same key value) and then use iterator to
delete every next element one by one until we reach the end of
'std::multiset' or the end of the sequence of the elements with the same
key value.
Then the 'reduce' method returns the number of elements which have been
deleted.






ср, 12 февр. 2025 г. в 12:53, Jonathan Wakely <cxx_at_[hidden]>:

>
>
> On Wed, 12 Feb 2025 at 09:04, Александр Поваляев <apovalyaev_at_[hidden]>
> wrote:
>
>> Do you mean that "The order of the elements that compare equivalent is
>> the order of insertion and does not change." (
>> https://en.cppreference.com/w/cpp/container/multiset") statement is
>> wrong?
>>
>
> It's incomplete or ambiguous at best. It could be read to mean that the
> order is determined at the time of insertion and doesn't change after that,
> which would be correct. You are reading it to mean that the spatial order
> in the container is the same as the temporal order that they are inserted,
> which is wrong.
>
> cppreference is not the standard, and not every statement on every page is
> authoritative. You find a more correct statement at the link you gave
> earlier:
>
> https://en.cppreference.com/w/cpp/container/multiset/equal_range#Return_value
> "Since `emplace` and unhinted `insert` always insert at the upper bound,
> the order of equivalent elements in the equal range is the order of
> insertion unless hinted `insert` or `emplace_hint` was used to insert an
> element at a different position."
>
>
>
>
>> And a hint while being used with 'insert' method of 'std::multiset' is
>> considered as "A MUST", not as "A RECOMMENDATION"?
>>
>
> Yes. The standard says for a.insert(p, t) that "t is inserted as close as
> possible to the position just prior to p."
>
>
>
>