On Wed, 12 Feb 2025 at 12:12, Александр Поваляев <apovalyaev_at_[hidden]>
wrote:

> 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.
>

I don't agree.

For example, std::multiset count is 2^20, 'equal_range' will require 2*20
> compare operations.
>

For 2^20 equivalent elements, I get 57 comparisons for equal_range. If you
want to remove 1% of those 2^20 equivalent elements, your preferred
approach would require 10k comparisons. But using equal_range would require
57 comparisons.

https://godbolt.org/z/E1E5T6daM

57 is not double 10k.



> 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."
>>
>>
>>
>>