C++ Logo

sg14

Advanced search

Re: Colony/hive & unordered vs ordered == operator

From: Matt Bentley <mattreecebentley_at_[hidden]>
Date: Mon, 21 Mar 2022 09:32:05 +1300
Basically, hive/colony is sorted until emplace/insert/splice are called.
No other functions with the exception of swap/operator = (for the
destination)/~hive affect this.
In practice, operator = will always preserve order - I doubt that an
implementation would spawn threads to process operator =, or that there
would be a significant performance advantage to doing so outside of
non-trivially-copyable types, though I suppose it's possible.
However, the 'just in case' argument is worth pursuing.
There is probably less potential harm in not specifying it than in
specifying it.


On 18/03/2022 8:08 am, Arthur O'Dwyer via SG14 wrote:
> On Thu, Mar 17, 2022 at 2:34 PM Henry Miller via SG14
> <sg14_at_[hidden] <mailto: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/147>
> https://github.com/WG21-SG14/SG14/issues/131
> <https://github.com/WG21-SG14/SG14/issues/131>
> https://github.com/WG21-SG14/SG14/pull/133
> <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 <https://godbolt.org/z/r9fx1s411>
>
> –Arthur
>
> _______________________________________________
> SG14 mailing list
> SG14_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/sg14

Received on 2022-03-20 20:35:22