Sorter adapters
Sorter adapters are the main reason for using sorter function objects instead of regular functions. A sorter adapter is a class template that takes another Sorter template parameter and alters its behavior. The resulting class can be used as a regular sorter, and be adapted in turn. Note that some of the adapters are actually fixed-size sorter adapters instead of regular sorter adapters. It is possible to include all of the available adapters at once with the following directive:
#include <cpp-sort/adapters.h>In this documentation, we will call adapted sorters the sorters passed to the adapters and resulting sorter the sorter class that results from the adaption of a sorter by an adapter. If not specified, the stability and the iterator category of the resulting sorter is that of the adapted sorter provided there is a single adapted sorter.
The following sorter adapters and fixed-size sorter adapters are available in the library:
#include <cpp-sort/adapters/container_aware_adapter.h>Sorters in cpp-sort are typically container-agnostic: they only care about iterators, which is a strength since it means that they can work with any container satisfying a few simple iterator requirements. However, abstracting away containers also means that the sorting algorithms can't take some interesting container structure into account. For example, a selection sort is generally unstable because it swaps non-adjacent elements, but it can be made stable by rotating the element in its final place instead; rotating is a O(n) operation given a mere iterator abstraction, but we know that it is possible to rotate an element into its final in O(1) time with lists, and it's somewhat of a shame to throw away that ability.
container_aware_adapter is a tool that allows to make the wrapped sorter container-aware and to use dedicated algorithms when sorting known containers. For example, when give an std::list, container_aware_adapter<selection_sorter> will use a dedicated algorithm that stably sorts the list with O(1) rotate operations.
template<typename Sorter>
struct container_aware_adapter;Some sorters in the library already have dedicated algorithms for std::list and std::forward_list. Wrapping those sorters with container_aware_adapter will make the operator() call the dedicated algorithms instead of the default ones. The dedicated algorithms are only called when the resulting sorter is called with a full collection since iterators don't hold enough information. When called with a pair of iterators, the resulting sorter uses the raw adapted sorter.
#include <cpp-sort/adapters/counting_adapter.h>Unlike usual sorters, counting_adapter::operator() does not return void but the number of comparisons that have been needed to sort the iterable. It will adapt the comparison function so that it can count the number of comparisons made by any other sorter with a reasonable implementation. The actual number of comparisons needed to sort an iterable can be used as a heuristic in hybrid sorts and may constitute interesting information nevertheless.
The actual counter type can be configured with the template parameter CountType, which defaults to std::size_t if not specified. While this doesn't matter most of the times, this parameter may be changed to std::atomic<std::size_t> to count the number of comparisons performed by parallel sorting algorithms (or to a reducer, which would probably be a better idea).
template<
typename ComparisonSorter,
typename CountType = std::size_t
>
struct counting_adapter;Note that this adapter only works with sorters that satisfy the ComparisonSorter concept since it needs to adapt a comparison function.
#include <cpp-sort/adapters/hybrid_adapter.h>The goal of this sorter adapter is to aggregate several sorters into one unique sorter. The new sorter will call the appropriate sorting algorithm based on the iterator category of the collection to sort. If several of the aggregated sorters have the same iterator category, the first to appear in the template parameter list will be chosen, unless some SFINAE condition prevents it from being used. As long as the iterator categories are different, the order of the sorters in the parameter pack does not matter.
For example, the following sorter should call a pattern-defeating quicksort to sort a random-access collection, a vergesort to sort a bidirectional collection and a bubble sort to sort a forward collection:
using general_purpose_sorter = hybrid_adapter<
bubble_sorter,
verge_sorter,
pdq_sorter
>;This adapter uses cppsort::iterator_category to check the iterator category of the sorters to aggregate. Therefore, if you write a sorter and want it to be usable with hybrid_adapter, you will need your sorter to provide an iterator_category type alias corresponding to one of the standard iterator tags. If you write specific sorters that only work with some specific types, you might want to SFINAE out the overloads of operator() when they are not valid instead of triggering a hard error. Doing so will allow to use them with fallback sorters in hybrid_adapter to handle the cases where the type to sort cannot be handled by your sorter.
The resulting sorter's is_always_stable is std::true_type if and only if every adapted sorter's is_always_stable is std::true_type. is_stable is specialized so that it will return the stability of the called adapted sorter with the given parameters. The iterator category of the resulting sorter is the most permissive iterator category among the adapted sorters.
#include <cpp-sort/adapters/indirect_adapter.h>This adapter implements an indirect sort: a sorting algorithm that actually sorts the iterators rather than the values themselves, then uses the sorted iterators to move the actual values to their final position in the original collection. The actual algorithm used is a mountain sort, whose goal is to sort a collection while performing a minimal number of move operations on the elements of the collection. This indirect adapter copies the iterators and sorts them with the given sorter before performing cycles in a way close to a cycle sort to actually move the elements. There are a few differences though: while the cycle sort always has a O(n²) complexity, the resulting sorter of indirect_adapter has the complexity of the adapted sorter. However, it stores n additional iterators as well as n additional booleans and performs up to (3/2)n move operations once the iterators have been sorted; these operations are not significant enough to change the complexity of the adapted sorter, but they do represent a rather big additional constant factor.
Note that indirect_adapter provides a rather good exception guarantee: as long as the collection of iterators is being sorted, if an exception is thrown, the collection to sort will remain in its original state. However, it doesn't provide the strong exception guarantee since exceptions could still be thrown when the elements are moved to their sorted position.
template<typename Sorter>
class indirect_adapter;The resulting sorter only accepts random-access iterators, but the iterator category of the adapted sorter does not matter. Note that this algorithm performs even fewer move operations than low_moves_sorter, but at the cost of a higher constant factor that may not always be worth it for small collections.
#include <cpp-sort/adapters/schwartz_adapter.h>This adapter implements a Schwartzian transform that helps to reduce the runtime cost when projections are expensive. A regular sorting algorithm generally projects elements on-the-fly during a comparison, that is, every time a sorting algorithm performs a comparison, it projects both operands before comparing the results, which is ok when the projection operation is cheap, but which might become a problem when the projection is more expensive. A sorter wrapped into schwartz_adapter will instead precompute the projection for every element in the collection to sort, then sort the original collection according to the projected elements. Compared to a raw sorter, it requires O(n) additional space to store the projected elements.
template<typename Sorter>
struct schwartz_adapter;The mechanism used to synchronize the collection of projected objects with the original collection during the sort might be too expensive when the projection is cheap. When in doubt, time things before drawing conclusions.
Warning: a sorter wrapped into schwartz_adapter is only guaranteed to work if it properly handles proxy iterators.
#include <cpp-sort/adapters/self_sort_adapter.h>This adapter takes a sorter and, if the collection to sort has a suitable sort method, it is used to sort the collection. Otherwise, if the collection to sort has a suitable stable_sort method, it is used to sort the collection. Otherwise, the adapted sorter is used instead to sort the collection. If self_sort_adapter is wrapped into stable_adapter, if the collection to sort has a suitable stable_sort method, it is used to sort the collection. Otherwise, the adapted sorter wrapped into stable_adapter is used instead to sort the collection.
This sorter adapter allows to support out-of-the-box sorting for std::list and std::forward_list as well as other user-defined classes that implement a sort method with a compatible interface.
template<typename Sorter>
struct self_sort_adapter;Since it is impossible to guarantee the stability of the sort method of a given iterable, the resulting sorter's is_always_stable is std::false_type. However, is_stable will be std::true_type if a container's stable_sort is called or if a call to the adapted sorter is stable. A special case considers valid calls to std::list::sort and std::forward_list::sort to be stable.
#include <cpp-sort/adapters/small_array_adapter.h>This adapter is not a regular sorter adapter, but a fixed-size sorter adapter. It wraps a fixed-size sorter and calls it whenever it is passed a fixed-size C array or an std::array with an appropriate size.
template<
template<std::size_t> class FixedSizeSorter,
typename Indices = /* implementation-defined */
>
struct small_array_adapter;The Indices parameter may be either void or a specialization of the standard class template std::index_sequence. When it is void, small_array_adapter will try to call the underlying fixed-size sorter for C arrays or std::array instances of any size. If an std::index_sequence specialization is given instead, the adapter will try to call the underlying fixed-size sorter only if the size of the array to be sorted appears in the index sequence. If the template parameter Indices is omitted, this class will check whether the fixed_sorter_traits specialization for the given fixed-size sorter contains a type named domain and use it as indices; if such a type does not exist, void will be used as Indices.
The operator() overloads are SFINAEd out if a collection not handled by the fixed-size sorter is passed (e.g. wrong type or array too big). These soft errors allow small_array_adapter to play nice with hybrid_adapter. For example, if one wants to call low_moves_sorter when a sorter is given an array of size 0 to 8 and pdq_sorter otherwise, they could easily create an appropriate sorter the following way:
using sorter = cppsort::hybrid_adapter<
cppsort::small_array_adapter<
cppsort::low_moves_sorter,
std::make_index_sequence<9>
>,
cppsort::pdq_sorter
>;#include <cpp-sort/adapters/stable_adapter.h>This adapter takes a sorter and alters its behavior (if needed) to produce a stable sorter. It does so by associating every element of the collection to sort to its starting position and, whenever two elements compare equivalent, the algorithm uses the starting position of the compared elements to make sure that their relative starting positions are preserved. Compared to a raw sorter, it requires O(n) additional space to store the starting positions.
template<typename Sorter>
struct stable_adapter;However, if the adapted sorter already implements a stable sorting algorithm when called with a specific set of parameters (if is_stable is std::true_type for the parameters), then the resulting sorter will call the adapted sorter directly. The resulting sorter is always stable.
One can provide a dedicated stable algorithm by explicitly specializing stable_adapter to bypass the automatic transformation and allow optimizations (this isn't clean per se, but...), which can be useful when a pair of stable and unstable sorting algorithms are closely related. For example, while std_sorter calls std::sort, the explicit specialization stable_adapter<std_sorter> actually calls std::stable_sort instead. In cpp-sort, stable_adapter has specializations for the following sorters and adapters:
While stable_adapter is the "high-level" adapter whenever one wants a stable sorting algorithm, the header also provides make_stable, which directly exposes the raw mechanism used to transform an unstable sorter into a stable one without applying any of the short-circuits described above:
template<typename Sorter>
struct make_stable;Contrary to stable_adapter, make_stable isn't meant to be specialized by end users.
- Home
- Quickstart
- Sorting library
- Comparators and projections
- Miscellaneous utilities
- Tutorials
- Tooling
- Benchmarks
- Changelog
- Original research