On Wed, 16 Mar 2022 at 23:05, Tony V E via SG14 <sg14_at_[hidden]> wrote:
>
>
>
> 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?

I fail to see why you and Nevin think hive should have an equality.
The lack of such an equality wouldn't make hive a "special snowflake",
it already is one. The worst-case scenario is hit for an unordered
containers in hopefully rare occasions, but for hive, it's hit for
every 'unfortunate' case where two hives compare equal. Unless, of
course, you're willing to allocate eight megabytes of memory
to compare two 1-million-element hives, which certainly sounds to me
like something I'd rather seriously want to opt in to, as opposed
to having it be available as a 'regular' operation, if at all, in the
standardized API of hive. And to add insult to injury, we'd then pay
the full allocation cost for most if not all comparisons of hives,
even ones that don't even need it. None of that suggests to me that
we should perform hitherto untested heroics to get the equality,
especially when there's barely any use cases for it. The lack of
such an equality is just the nature of the beast of how hive works, if
you ask me.