On Thu, Mar 17, 2022 at 2:34 PM Henry Miller via SG14 <sg14_at_[hidden]>
wrote:

> On Thu, Mar 17, 2022, at 13:19, Arthur O'Dwyer wrote:
> >
> > FWIW, I'm sympathetic to Henry's argument. But on the other hand, this
> > again comes down to what properties are salient and what properties are
> not.
> >
> > std::hive<int> a = {1,2,3,4,5};
> > a.sort();
> > assert(std::is_sorted(a.begin(), a.end()));
> > auto b = a;
> > // Copies are substitutable. Every salient property of `a` is now a
> > property of `b`.
> > // Is sortedness salient? Or can it be "lost" simply by copying the
> > object?
> > assert(std::is_sorted(b.begin(), b.end())); // ???
>
> That is a good point, though it may better make the argument that hive
> [should not be] sortable. While the implementation allows sort, that seems
> like an accident of implementation, the intended use cases is a set of
> items that you need to iterate quickly without concern for order.
> std::unordered_set is not sortable.
>

A std::unordered_set cannot be sorted *in its entirety* without breaking
its hash invariant; although I suppose one could imagine sorting each
bucket individually, and the STL's unordered_set doesn't actually permit
that. (It does expose the buckets via `.begin(x)` and the local_iterator
API, but it doesn't let you manipulate the buckets themselves in the same
way you can manipulate, say, a std::list.)

The better analogy here would be sg14::slot_map. Philippe Groarke has
thought a lot about the "special skills" of slot_map, although it was years
ago now:
https://github.com/WG21-SG14/SG14/issues/147
https://github.com/WG21-SG14/SG14/issues/131
https://github.com/WG21-SG14/SG14/pull/133
Order-of-elements in general *is* a salient property for sg14::slot_map:
it's preserved by copying. This includes sortedness, partitionedness, even
heapness. However, sg14::slot_map doesn't actually support those "special
skills" today; there's an old unmerged pull request (from me) for
.partition() but I never thought about .sort() or .reverse() or
.make_heap() or .next_permutation() or .rotate() or any other ordering verb
in particular.

Note that immediately after x.sort(), the container *is sorted*; but since
the elements' values are mutable, you can't assume that it'll *stay* sorted
for long. So we can't play any too-clever tricks such as keeping track of
an "is_sorted" flag and having copy do different things depending on
whether the container is_sorted or not. Either order-of-elements in general
is salient, or it's not.
https://godbolt.org/z/r9fx1s411

–Arthur