Date: Wed, 16 Mar 2022 13:23:14 -0400

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

>

- 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

>

Received on 2022-03-16 17:23:27