On Thu, Mar 17, 2022 at 2:34 PM Henry Miller via SG14 <sg14@lists.isocpp.org> 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