Sorter traits

#include <cpp-sort/sorter_traits.h>

is_projection and is_projection_iterator

The goal is these variable templates is to check whether a projection function can be vallued on the value_type of an iterable or an iterator. The additional template parameter Compare may be passed and the traits will also check whether the given binary comparison function can be called with two projected values.

template<
    typename Projection,
    typename Iterable,
    typename Compare = std::less<>
>
constexpr bool is_projection = /* implementation-defined */;

template<
    typename Projection,
    typename Iterator,
    typename Compare = std::less<>
>
constexpr bool is_projection_iterator = /* implementation-defined */;

is_sorter and friends

The is_sorter family of variable templates is to check whether a given sorter satisfies some properties: being able to be called with of variety of parameters and checking whether the parameters play nice together. For example, is_comparison_sorter returns true if Sorter is a type that can be called with an collection Iterable& and a comparison function Compare and returns false otherwise. These traits mainly exist for SFINAE purpose and concept checking.

template<typename Sorter, typename Iterable>
constexpr bool is_sorter = /* implementation-defined */;

template<typename Sorter, typename Iterable, typename Compare>
constexpr bool is_comparison_sorter = /* implementation-defined */;

template<typename Sorter, typename Iterable, typename Projection>
constexpr bool is_projection_sorter = /* implementation-defined */;

template<typename Sorter, typename Iterable, typename Compare, typename Projection>
constexpr bool is_comparison_projection_sorter = /* implementation-defined */;

There are also variants of these variable templates which take a potential sorter type and an iterator type. They exist to check whether the sorter can be called with a pair of iterators.

template<typename Sorter, typename Iterator>
constexpr bool is_sorter_iterator = /* implementation-defined */;

template<typename Sorter, typename Iterator, typename Compare>
constexpr bool is_comparison_sorter_iterator = /* implementation-defined */;

template<typename Sorter, typename Iterator, typename Projection>
constexpr bool is_projection_sorter_iterator = /* implementation-defined */;

template<typename Sorter, typename Iterator, typename Compare, typename Projection>
constexpr bool is_comparison_projection_sorter_iterator = /* implementation-defined */;

sorter_traits

The class template sorter_traits<Sorter> contains information about sorters and sorter adapters such as the kind of iterators accepted by a sorter and whether it implements or not a stable sorting algorithm.

template<typename Sorter>
struct sorter_traits;

This class template peeks into Sorter to extract the following types:

• using iterator_category = typename Sorter::iterator_category;
• using is_stable = typename Sorter::is_stable;

This class is a bit different than the trait classes in the standard library: if one of the types above doesn't exist in the passed sorter, it won't exist in sorter_traits either. That means that the traits are not tightly coupled: if a sorter doesn't define is_stable but defines iterator_category, it can still be used in hybrid_adapter; instantiating the corresponding sorter_traits won't cause a compile-time error because of the missing is_stable.

iterator_category

template<typename Sorter>
using iterator_category = typename sorter_traits<Sorter>::iterator_category;

Some tools need to know which category of iterators a sorting algorithm can work with. Therefore, a well-defined sorter shall provide one of the standard library iterator tags in order to document that.

When a sorter is adapted so that it may be used with several categories of iterators, the resulting sorter's iterator category will correspond to the most permissive among the original sorters. For example, if an hybrid_adapter merges sorting algorithms with std::forward_iterator_tag and std::random_access_iterator_tag, the resulting sorter's category will be std::forward_iterator_tag since it is guaranteed to work with any iterable type which has at least forward iterators.

is_stable

template<typename Sorter>
using is_stable = typename sorter_traits<Sorter>::is_stable;

This type trait is always either std::true_type or std::false_type and tells whether a sorting algorithm is stable or not. This information may be useful in some contexts, even though it is currently unused by the library.

When a sorter adapter is used, the resulting sorter is stable if and only if its stability can be guaranteed and unstable otherwise, even when the adapted sorter may be stable (for example, self_sort_adapter is always considered unstable since it is impossible to guarantee the stability of any sort method).

rebind_iterator_category

template<typename Sorter, typename Category>
struct rebind_iterator_category;

This class allows to get a sorter similar to the one passed but with a stricter iterator category. For example, it can generate a sorter whose iterator category is std::bidirectional_iterator_tag from another sorter whose iterator category is std::forward_iterator_tag. It is mostly useful to make several sorters with the same iterator category work for different iterator categories in an hybrid_adapter. Let's say we have two sorters, foo_sorter and bar_sorter; both have the iterator category std::forward_iterator_tag, but foo_sorter is the best to sort forward iterators while bar_sorter benefits from some optimizations for bidirectional and random-access iterators. It is possible to use the best of both with the following sorter:

using sorter = cppsort::hybrid_adapter<
    foo_sorter,
    cppsort::rebind_iterator_category<
        bar_sorter,
        std::bidirectional_iterator_tag
    >
>;

The sorter above will pick foo_sorter for forward iterators, but will pick bar_sorter for bidirectional and random-access iterators. A compile-time error will occur if one tries to rebind to an iterator category that is not derived from the sorter's original iterator category.