Skip to content

Sorter facade

Jump to bottom
Morwenn edited this page Nov 18, 2015 · 21 revisions

To make a decent full-fledged sorter, implementers are required to implement a variety of operator() overloads with a rather high redundancy factor. Therefore, cpp-sort provides a wrapper class which makes creating sorters easier by generating most of the boilerplate for the required operations in the simplest cases. To use it, one needs to create a sorter implementation and to wrap it into sorter_facade:

struct frob_sorter_impl
{
    // Regular sorter code
};

struct frob_sorter:
    cppsort::sorter_facade<frob_sorter_impl>
{};

Conversions to function pointers

sorter_facade provides the following member functions so that a sorter can be turned into a function pointer:

template<typename Iterable, typename... Args>
operator Ret(*)(Iterable&, Args...)() const;

template<typename Iterator, typename... Args>
operator Ret(*)(Iterator, Iterator, Args...)() const;

Note that the function pointer conversion syntax above is made up, but it allows to clearly highlight what it does while hiding the ugly typedefs needed for the syntax to be valid. In these signatures, Ret is an std::result_of_t of the parameters (well, it is what you would expect it to be). The actual implementation is more verbose and redundant, but it allows to transform a sorter into a function pointer corresponding to any valid overload of operator().

operator() for pairs of iterators

sorter_facade provides the following overloads of operator() to handle pairs of iterators:

template<typename Iterator>
auto operator()(Iterator first, Iterator last) const
    -> /* implementation-defined */;

template<typename Iterator, typename Compare>
auto operator()(Iterator first, Iterator last, Compare compare) const
    -> /* implementation-defined */;

template<typename Iterator, typename Projection>
auto operator()(Iterator first, Iterator last, Projection projection) const
    -> /* implementation-defined */;

template<typename Iterator, typename Compare, typename Projection>
auto operator()(Iterator first, Iterator last,
                Compare compare, Projection projection) const
    -> /* implementation-defined */;

These overloads will generally forward the parameters to the corresponding operator() in the wrapped sorter. It does some additional magic to forward compare and projection to the most suitable operator() overload in sorter and to complete the call with instances of std::less<> and/or utility::identity if it needs additional parameters. Basically, it ensures that everything can be done if Sorter has a single operator() taking a pair of iterators, a comparison function and a projection function.

Provided you have a sorting function with a standard iterator interface, creating the corresponding sorter becomes trivial thanks to sorter_facade. For instance, here is a simple sorter wrapping a selection_sort:

struct selection_sorter_impl
{
    template<
        typename RandomAccessIterator,
        typename Compare = std::less<>,
        typename Projection = cppsort::utility::identity
    >
    auto operator()(RandomAccessIterator first, RandomAccessIterator last,
                    Compare compare={}, Projection projection={}) const
        -> void
    {
        selection_sort(first, last, compare, projection);
    }
};

struct selection_sorter:
    cppsort::sorter_facade<selection_sorter_impl>
{};

operator() for ranges

sorter_facade provides the following overloads of operator() to handle ranges:

template<typename Iterable>
auto operator()(Iterable& iterable) const
    -> /* implementation-defined */;

template<typename Iterable, typename Compare>
auto operator()(Iterable& iterable, Compare compare) const
    -> /* implementation-defined */;

template<typename Iterable, typename Projection>
auto operator()(Iterable& iterable, Projection projection) const
    -> /* implementation-defined */;

template<typename Iterable, typename Compare, typename Projection>
auto operator()(Iterable& iterable, Compare compare, Projection projection) const
    -> /* implementation-defined */;

These overloads will generally forward the parameters to the corresponding operator() in the wrapped sorter if they exist, or try to call an equivalent operator() taking a pair of iterators in the wrapped sorter by using std::begin and std::end on the iterable to sort. It also does some additional magic to forward compare and projection to the most suitable operator() overload in sorter and to complete the call with instances of std::less<> and/or utility::identity if it needs additional parameters. Basically, it ensures that everything can be done if Sorter has a single operator() taking a pair of iterators, a comparison function and a projection function.

It will always call the most suitable iterable operator() overload in the wrapped sorter if there is one, and dispatch to an overload taking a pair of iterators when it cannot do otherwise.

Universal support for std::less<> and utility::identity

cpp-sort considers that every collection sorted without a specific comparison function shoud work as if it was sorted with std::less<> and utility::identity. However, some sorters do not implement comparison sorts and therefore do not provide overloads for operator() taking custom comparison or projection functions. sorter_facade provides the following overloads so that every sorter, even non-comparison sorters, can be passed std::less<> and utility::identity:

template<typename Iterable>
auto operator()(Iterable& iterable, std::less<>) const
    -> /* implementation-defined */;

template<typename Iterable>
auto operator()(Iterable& iterable, utility::identity) const
    -> /* implementation-defined */;

template<typename Iterable>
auto operator()(Iterable& iterable, std::less<>, utility::identity) const
    -> /* implementation-defined */;

template<typename Iterator>
auto operator()(Iterator first, Iterator last, std::less<>) const
    -> /* implementation-defined */;

template<typename Iterator>
auto operator()(Iterator first, Iterator last, utility::identity) const
    -> /* implementation-defined */;

template<typename Iterator>
auto operator()(Iterator first, Iterator last,
                std::less<>, utility::identity) const
    -> /* implementation-defined */;

While it does not appear in this documentation, sorter_facade actually relies on an extensive amount of SFINAE tricks to ensure that only the operator() overloads that are needed and viable are generated. For example, the magic std::less<> overloads won't be generated if the wrapped sorter already accepts a comparison function.

Clone this wiki locally