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.
Here we are talking about possible implementations.
Let me explain to you, how do I count comparison operations needed:
* Given a std::multiset of 2^20 elements in total (some of them do have equal keys and some of them don't), 'count' will return 2^20
* Let it be a pair of two elements with the same key K (A and B), so both A and B has the same key K and no any other element amongst 2^20 has key K
* The order in which these elements are placed inside std::multiset is A then B, so A element is "oldest" and is placed closed to the beginning
* So, we're going to delete only one element of these two
* We call 'reduce' method of std::multiset container with the following parameters reduce(K, 1)
* Here we comes to the place where we can compare two possible implementations you proposed earlier:
Implementation 1: 'equal_range' is used and so about 20 * 2 comparisons are needed. I get 57 comparisons because a red-black tree is used, not a pure binary.
Implementation 2: 'find' method is being used and so, it is required about 20 comparisons (or so, may be 28)
* Implementation 2 requires twice as much comparisons as Implementation 1. It is bad, because if a class of elements A and B defines custom comparator, it will work significantly slower.
We're talking about STL library implementation (it is a gold standard for industry), so we can't just afford just unnecessary doubling of any operations;
* Don't take about O(lnN) or O(N), cause our N is not going to infinity :D, but we know for sure that Implementation 1 works at least twice slower than Implementation 2
* I think we will need a third implementation, cause there is a lot of cases which needed to be considered
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.
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:
"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."