Skip to content

Miscellaneous utilities

Jump to bottom
Morwenn edited this page May 31, 2017 · 45 revisions

The following utilities are available in the directory cpp-sort/utility and live in the namespace cppsort::utility. While not directly related to sorting, they might be useful.

The detection toolkit

#include <cpp-sort/utility/detection.h>

cpp-sort implements the detection toolkit proposed by N4502 which should be available in the Library Fundamentals TS v2.

Since the documentation is already available online, it won't be repeated here. Note that this header also provides the types void_t and nonesuch which are used to implement the detection toolkit.

Warning: utility::void_t does not exist anymore in the C++17 branch; use std::void_t instead.

any and all 

#include <cpp-sort/utility/any_all.h>

The constexpr functions any and all take several boolean parameters and respectively return whether any of them is true or whether all of them are true.

template<typename... Bools>
constexpr bool any(bool head, Bools... tail);

template<typename... Bools>
constexpr bool all(bool head, Bools... tail);

Warning: this header does not exist anymore in the C++17 branch; use fold expressions instead.

as_comparison and as_projection 

#include <cpp-sort/utility/functional.h>

When given a function that satisfies both the comparison and projection concepts, every sorter in cpp-sort considers that it is a comparison function (unless it is a projection-only sorter, in which case the function is considered to be a projection). To make such ambiguous functions usable as projections, the utility function as_projection is provided, which wraps a function and exposes only its unary overload. A similar as_comparison function is also provided in case one needs to explicitly expose the binary overload of a function.

template<typename Function>
auto as_projection(Function&& func)
    -> /* implementation-defined */;

template<typename Function>
auto as_comparison(Function&& func)
    -> /* implementation-defined */;

as_function

#include <cpp-sort/utility/as_function.h>

as_function is an utility function borrowed from Eric Niebler's Ranges v3 library. This function takes a parameter and does what it can to return an object callable with the usual function call syntax. It is notably useful to transform a pointer to member data into a function taking an instance of the class and returning the member.

To be more specific, as_function returns the passed object as is if it is already callalble with the usual function call syntax, and uses std::mem_fn to wrap the passed object otherwise.

struct wrapper { int foo; };
// func is a function taking an instance of wrapper
// and returning the value of its member foo
auto&& func = utility::as_function(&wrapper::foo);

begin and end 

#include <cpp-sort/utility/begin_end.h>

This header contains a set of functions similar to std::begin and std::end, except that they are enhanced to properly handle rvalues too: when given a temporary collection, they can return a mutable iterator, which might sometimes be needed. They are equivalent to the ones described in the Ranges TS and implemented in Eric Niebler's Ranges v3.

Bit operations

#include <cpp-sort/utility/bitops.h>

Sometimes, algorithms need to perform some fast math operations and play with bits a bit, generally for sorting heuristics. This header exposes the bit operations used in the library, and some more for consistency.

template<typename Integer>
constexpr Integer log2(Integer n);

This function computes the binary logarithm of the given integer. The binary logarithm of the size of a collection to sort is typically used as a heuristic by sorting algorithms to perform tasks a limited number of times before switching to another algorithm to allow optimizations but still guarantee that the algorithm will run in logarithmic time.

template<typename Unsigned>
constexpr Unsigned hyperceil(Unsigned n);

template<typename Unsigned>
constexpr Unsigned hyperfloor(Unsigned n);

These functions compute the hyperfloor and the hyperceiling of a given integer, basically 2^floor(log2(n)) and 2^ceil(log2(n)).

Branchless traits

#include <cpp-sort/utility/branchless_traits.h>

Some of the library's algorithms (pdq_sorter and everything that relies on it, which means many things since it's the most common fallback for other algorithms) may use a different logic depending on whether the use comparison and projection functions are branchful and branchless. Unfortunately, it isn't something that can be deterministically determined; in order to provide the information, the following traits are available (they always inherit from either std::true_type or std::false_type):

template<typename Compare, typename T>
struct is_probably_branchless_comparison;

This trait tells whether the comparison function Compare is likely to generate branchless code when comparing two instances of T. By default it considers that the following comparison functions are likely to be branchless:

template<typename Projection, typename T>
struct is_probably_branchless_projection;

This trait tells whether the projection function Projection is likely to generate branchless code when called with an instance of T. By default it considers that the following projection functions are likely to be branchless:

  • cppsort::utility::identity for any type
  • Any type that satisfies std::is_member_function_pointer provided it is called with an instance of the appropriate class

These traits can be specialized for user-defined types. If one of the traits is specialized to consider that a user-defined type is likely to be branchless with a comparison/projection function, cv-qualified and reference-qualified versions of the same user-defined type will also be considered to produce branchless code when compared/projected with the same function.

Buffer providers

#include <cpp-sort/utility/buffer.h>

Buffer providers are classes designed to be passed to dedicated sorters; they describe how a the sorter should allocate a temporary buffer. Every buffer provider shall have a buffer inner class constructible with an std::size_t, and providing the methods begin, end, cbegin, cend and size.

template<std::size_t N>
struct fixed_buffer;

This buffer provider allocates N elements on the stack. It uses std::array behind the scenes, so it also allows buffers of size 0. The runtime size passed to the buffer at construction is discarded.

template<typename SizePolicy>
struct dynamic_buffer;

This buffer provider allocates on the heap a number of elements depending on a given size policy (a class whose operator() takes the size of the collection and returns another size). You can use the function objects from utility/functional.h as basic size policies. The buffer construction may throw an instance of std::bad_alloc if it fails to allocate the required memory.

Miscellaneous function objects

#include <cpp-sort/utility/functional.h>

The struct identity is a function object that can type any value of any movable type and return it as is. It is used as a default for every projection parameter in the library so that sorters view the values as they are by default, without a modification.

struct identity
{
    template<typename T>
    constexpr auto operator()(T&& t) const noexcept
        -> T&&;

    using is_transparent = /* implementation-defined */;
};

It is equivalent to the proposed std::identity from the Ranges TS and will probably be replaced by the standard function object the day it makes its way into the standard.

This header also provides additional function objects implementing basic unary operations. These functions objects are designed to be used as size policies with dynamic_buffer and similar classes. The following function objects are available:

  • half: returns the passed value divided by 2.
  • log: returns the base 10 logarithm of the passed value.
  • sqrt: returns the square root of the passed value.

inplace_merge

#include <cpp-sort/utility/inplace_merge.h>

This function is similar to std::inplace_merge except that it is aso allowed to work with forward iterators while the standard version only works with bidirectional iterators. Moreover, it has also been enhanced to accept a projection parameter. This function will try to allocate additional memory to merge the ranges, and will perform between n and n log n comparisons depending on the amount of memory it managed to allocate.

template<
    typename ForwardIterator,
    typename Compare = std::less<>,
    typename Projection = utility::identity
>
void inplace_merge(ForwardIterator first, ForwardIterator middle, ForwardIterator last,
                   Compare compare={}, Projection projection={});

is_callable

#include <cpp-sort/utility/is_callable.h>

Provides the type trait is_callable which is equivalent to the one accepted into C++17. This file does not contain is_nothrow_callable, nor the variable templates that generally come with type traits.

is_in_pack

#include <cpp-sort/utility/is_in_pack.h>

The variable template is_in_pack<std::size_t Value, std::size_t... Values> equals true if Value exists into the non-type template parameter pack Values and equals false otherwise.

template<std::size_t Value, std::size_t... Values>
constexpr bool is_in_pack = /* implementation-defined */;

iter_move and iter_swap 

#include <cpp-sort/utility/iter_move.h>

The functions iter_move and iter_swap are equivalent to the same functions as proposed by P0022: utility functions intended to be used with ADL to handle proxy iterators among other things. An algorithm can use them instead of std::move and possibly ADL-found swap to handle tricky classes such as std::vector<bool>.

The default implementation of iter_move simply move-returns the dereferenced iterator. iter_swap is a bit more tricky: if the iterators to be swapped have a custom iter_move, then iter_swap will use it, otherwise it will call an ADL-found swap or std::swap on the dereferenced iterators.

template<typename Iterator>
auto iter_move(Iterator it)
    -> decltype(std::move(*it));

template<typename Iterator>
auto iter_swap(Iterator lhs, Iterator rhs)
    -> void;

Logical type traits

#include <cpp-sort/utility/logical_traits.h>

This header contains reimplementations of the C++17 (and Library Fundamentals TS V2) logical type traits std::conjunction, std::disjunction and std::negation as proposed by P0013R1. The linked documentation already is pretty good, so it won't be repeated here.

Warning: this header does not exist anymore in the C++17 branch; use the corresponding standard traits instead.

make_integer_range

#include <cpp-sort/utility/make_integer_range.h>

The class template make_integer_range can be used wherever an std::integer_sequence can be used. An integer_range takes a type template parameter that shall be an integer type, then three integer template parameters which correspond to the beginning of the range, the end of the range and the « step ».

template<
    typename Integer,
    Integer Begin,
    Integer End,
    Integer Step = 1
>
using make_integer_range = /* implementation-defined */;

make_index_range is a specialization of integer_range for std::size_t.

template<
    std::size_t Begin,
    std::size_t End,
    std::size_t Step = 1u
>
using make_index_range = make_integer_range<std::size_t, Begin, End, Step>;

size

#include <cpp-sort/utility/size.h>

size is a function that can be used to get the size of an iterable. It is equivalent to the C++17 function std::size but has an additional tweak so that, if the iterable is not a fixed-size C array and doesn't have a size method, it calls std::distance(std::begin(iter), std::end(iter)) on the iterable. Therefore, this function can also be used for std::forward_list as well as some implementations of ranges.

static_const

#include <cpp-sort/utility/static_const.h>

static_const is a tiny utility used to instantiate function objects (for example sorters) and expose a single global instance to users of the library while avoiding ODR problems. It is taken straight from Ranges v3. The general pattern to instantiate function objects is as follows:

namespace
{
    constexpr auto&& awesome_sort
        = cppsort::utility::static_const<awesome_sorter>::value;
}

You can read more about this instantiation pattern in an article by Eric Niebler.

Clone this wiki locally