On Wed, 16 Mar 2022 at 23:05, Tony V E via SG14 <firstname.lastname@example.org> wrote:
> On Wed, Mar 16, 2022 at 3:02 AM Matthew Bentley via SG14 <email@example.com> wrote:
>> On Wed, 16 Mar 2022 at 12:24, Nevin Liber <firstname.lastname@example.org> 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.
Because conceptually, practically, and uh "patterningly" (ie pattern of other containers) it makes sense.
But by "practically" I mean, it is a normal thing to do with a container, and it can be useful.
However, it turns out it is not practical, because it is too costly.
So, if I wasn't being clear, I agree with you - the cost is too high to have ==. Or at least to call it ==.
But I wouldn't be against a function for it. Otherwise someone will try to use std::equal and get it wrong. Or try some other way to do it and get it wrong.
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.
I'm not sure if I understand, but to be pedantic: you can do linear equality until you find entries that don't match, then you allocate (or N^2) to figure out the rest.
If the linear path gets to the end of the container without a mismatch, you never allocate.
None of that suggests to me that
we should perform hitherto untested heroics to get the equality,
Well, it isn't really heroics, and wouldn't be untested.
especially when there's barely any use cases for it.
I mostly agree. But if you never call it, then it is no big deal! :-)
The lack of
such an equality is just the nature of the beast of how hive works, if
you ask me.