A few notes:
- Some people in this thread have used the adjectives "ordered" and
"unordered" to talk about operator=='s behavior. I believe those terms are
ambiguous. I used "order-sensitive" and "order-insensitive" to try to deal
with that ambiguity.
- Every STL container has a (possibly non-deterministic) *iteration order*,
i.e., the order in which the elements are traversed from .begin() to
.end(). Your only job is to decide whether that iteration order is salient
or not. (For a vector or list, the iteration order is obviously salient.
For a std::unordered_set, the iteration order is obviously non-salient. For
a std::set, the iteration order is fixed so conceptually it doesn't matter
whether it's salient or not, at least for non-pathological element types.)
- "Order-sensitive equality comparison" is always implementable as
    bool operator==(const C& a, const C& b) { return std::equal(a.begin(),
a.end(), b.begin(), b.end()); }
Sequence and associative containers mandate exactly this implementation:
https://eel.is/c++draft/container.reqmts#lib:operator==,containers
- "Order-insensitive equality comparison" is always implementable as
    bool operator==(const C& a, const C& b) { return
std::is_permutation(a.begin(), a.end(), b.begin(), b.end()); }
Unordered containers mandate a slight performance optimization of this
implementation: https://eel.is/c++draft/unord.req#general-237
- If copying a container can change the iteration order, then iteration
order must not be salient, by definition (because, by definition, a copy
copies all the salient properties of the original). In other words, if
`auto b = a; assert(std::equal(a.begin(), a.end(), b.begin(), b.end()));`
can fail in practice, then iteration order must not be salient, by
definition.


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.
>
> _______________________________________________
> SG14 mailing list
> SG14_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/sg14
>