On Wed, Mar 16, 2022 at 5:40 PM Ville Voutilainen <
ville.voutilainen_at_[hidden]> wrote:

> 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.
>

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.
>

I don't think it is the nature of the concept of the container, but it is
an outcome of how it would need to be implemented.
We get to the same answer though - let's not have an == (nor <=>) on the
container.

-- 
Be seeing you,
Tony