Sets should not impl Ord, and should impl PartialOrd differently (?)

[Gankra]

Currently, sets that have some notion of an ordering over their elements (TreeSet and BitvSet, at least) implement Ord in terms of the lexicographic ordering of their contents. However, as @apoelstra notes in #16559 it may be more natural for sets to be ordered by inclusion. That is, a<=b if a subseteq b.

However, there is no total ordering over set inclusion. It instead forms a diamond-shaped DAG. Thus, Sets would not implement Ord under this scheme. In fact, almost all pairs of sets would have cmp yield None, which makes it a not-very-useful operator for generic comparison. Further, inclusion relationships are already provided by the actual Set api.

[Gankra]

CC @aturon

[apoelstra]

Discuss thread with these points listed:
http://discuss.rust-lang.org/t/stdlib-has-many-ord-implementations-on-things-that-arent-totally-ordered/394

Perhaps as part of the collections restructuring support for multiple orderings will have to be invented somehow.

[thestinger]

I think all containers should implement ordering as a lexicographic comparison. There are separate methods for checking for a subset / superset already, and we would lose the nice O(n) worst-case lexicographic comparisons on TreeSet. I don't understand why lexicographic comparisons are "crazy" semantics, as it's what I expect for all ordered containers. It would be very surprising if Rust's implementation was different than the C++ standard library, and would lead to bugs based on an assumption of a familiar implementation.

[apoelstra]

@thestinger Lexicographic comparisons are crazy for set types because sets are unordered and the only natural ordering used on them is subset inclusion.

For ordered containers, you're right, they make sense (and set inclusion doesn't).

[thestinger]

The sole reason TreeSet exists is to provide an ordered set. It is an ordered container and a lexicographic comparison is both sensible and very useful. It would be surprising to do anything else, because that's what ordered sets in the C++ standard library do.

[apoelstra]

Ok, thanks. I was misunderstanding the implied semantics of -Set types, and also wasn't aware of their STL equivalents.

[Gankra]

Alright, satisfied that this has been addressed: Lexicographic ordering is useful and standard.