Skip to content

Miscellaneous utilities

Jump to bottom
Morwenn edited this page Apr 10, 2016 · 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.

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);

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 a corresponding function. It is mostly useful to transform a pointer to member data into a function taking an instance of the class and returning the member.

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);

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>
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>
Unsigned hyperceil(Unsigned n);

template<typename Unsigned>
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)).

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.

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