C++ Logo


Advanced search

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

From: Matthew Bentley <mattreecebentley_at_[hidden]>
Date: Wed, 16 Mar 2022 20:01:42 +1300
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.

Received on 2022-03-16 07:02:45