C++ Logo


Advanced search

Re: Colony/hive & unordered vs ordered == operator

From: Tony V E <tvaneerd_at_[hidden]>
Date: Wed, 16 Mar 2022 17:05:32 -0400
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

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,

Received on 2022-03-16 21:05:45