Closed Morwenn closed 1 year ago
Not among the features proposed in the original description, but definitely in the same perimeter: sorted_iterators
takes a sorter, returns a function object that accepts a collection/compare/projection and returns an std::vector
of iterators to the elements of the passed collection in sorted order.
Interestingly the use cases are different from that of sorted_indices
: indices can be used several times to apply the same permutation to several collections while iterators only point to the original collection so can't be used on different collections. However sorted_iterators
can work on forward and bidirectional collections and is a more natural way to get a "sorted view" of a collection without destroying the original order (though a view
according to the standard concept has space and time guarantees that can't be achieved while sorting). sorted_iterators
covers part of the concerns described in #42.
To easily work on a collection of iterators, I should probably move indirect_t
and indirect
from cppsort::detail
to cppsort::utility
- putting in it <cpp-sort/utility/functional.h>
would be the logical thing to do.
indirect
is now a simple projection and relies on operator|
when it needs to adapt another projection, making its design simpler and more consistent with the rest of the library. This and the addition of utility::apply_permutation
pretty much complete the normal and extended feature set for this issue.
A couple of useful functions would be nice to have:
sorted_indices
to get a collection of indices corresponding to a sorted permutation of the passed collection. Basically an equivalent tonumpy.argsort
.apply_permutation
to shuffle a collection according to a vector of indices, which would notably allow to apply back the result ofsorted_indices
to any collection. Basically an equivalent to Boost.Algorithmapply_permutation
.Both of these algorithms somewhat intervene in the implementation of
indirect_adapter
, so there shouldn't be any big technical difficulty from an implementation point of view.However
sorted_indices
would probably better be implemented as a sorter adapter, so that it could work with any sorter and with the flexibility ofsorter_facade
. The biggest challenge is to modify most of the documentation to relax sorter adapter restrictions so that they don't have to produce sorters. Alternatively I can just give it the interface of a sorter adapter without mentioning it explicitly and shove it in<cpp-sort/utility>
without having to make a bigger change today.apply_permutation
can surely use the Boost.Algorithm interface and live in<cpp-sort/utility>
without trying to be more than that.