On Wed, Mar 16, 2022 at 3:02 AM Matthew Bentley via SG14 <
sg14_at_[hidden]> wrote:

>
>
> On Wed, 16 Mar 2022 at 12:24, Nevin Liber <nevin_at_[hidden]> wrote:
>
>>
>> My opinion is that it should have one, and if it does, the expectation is
>> that it is unordered.
>>
>> For most containers (other than string), I rarely use its comparison
>> operators, but when I need them, they are very handy.
>>
>> We are supposed to be designing a coherent standard library, and all the
>> containers in the standard library are equality comparable. This should
>> not be a snowflake.
>>
>> How does the complexity compare with the complexity of
>> unordered_multiset::operator==?
>>
>
> My apologies to Henry Miller from earlier, time complexity would be approx
> O(n log n), as he states - I forgot the time complexity of the sort
> function itself. At any rate, 1 x O(n) (gather pointers), 1 x O(n log n)
> (sort pointers), 1 x O(n) (compare elements via pointers).
> There may be better ways of doing what I'm talking about, this is only
> what I've managed to come up with thus far.
> Whereas unordered_multiset::operator==is O(n pow 2) in worst case.
>
>
I don't think you can ignore the allocation. It is O(n log n) with an
allocation of an array of n pointers. (IIUC)
So it can throw. And maybe someone wants to use a custom allocator. As
Ville mentioned.

Or would it try to allocate, and then fall back on O(n^2) if it can't
allocate?

Other than the high costs, I agree with what Nevin is saying - it should
have == and it should be equal even when the order is unequal.
But the cost is quite high. Possibly too high to be called "==" and it
needs a named function?

-- 
Be seeing you,
Tony