Skip to content

Comparators

Jump to bottom
Morwenn edited this page Aug 14, 2016 · 15 revisions

While comparators are not inherent to sorting per se, most sorting algorithms (at least in this library) are comparison sorts, hence providing some common useful comparators along with the sorters can be useful. Every comparator in this module satisfies the BinaryPredicate library concept.

Total order comparators

#include <cpp-sort/comparators/total_greater.h>
#include <cpp-sort/comparators/total_less.h>

The comparators total_less and total_order are customization points implementing a total order, inspired by the similar functions described in P0100. The provided functions handle built-in integer out of the box (using the built-in relational operators) and implement IEEE 754's totalOrder for floating point numbers (from lesser to greater):

  • positive quiet NaNs
  • positive signaling NaNs
  • positive infinity
  • positive reals
  • positive zero
  • negative zero
  • negative reals
  • negative infinity
  • negative signaling NaNs
  • negative quiet NaNs

That said, the comparators are currently unable to discriminate between quiet and signaling NaNs, so they compare equivalent. When it doesn't handle a type natively and ADL doesn't find any suitable total_less function in a class namespace, cppsort::total_less does not fall back to operator<; see P0100 for the rationale (it applies to the whole total_* family of customization points).

Weak order comparators

#include <cpp-sort/comparators/weak_greater.h>
#include <cpp-sort/comparators/weak_less.h>

The comparators weak_less and weak_order are customization points implementing a weak order, inspired by the similar functions described in P0100. The provided functions handle built-in integer out of the box (falling back to total_* functions) and implement a weak order for floating point numbers as suggested by Lawrence Crowl in his CppCon 2015 presentation (from lesser to greater):

  • all positive NaNs equivalent
  • positive infinity
  • positive reals
  • all zeros equivalent
  • negative reals
  • negative infinity
  • all negative NaNs equivalent

When it doesn't handle a type natively and ADL doesn't find any suitable weak_less function in a class namespace, cppsort::weak_less falls back to cppsort::total_less since a total order is also a weak order (it applies to the whole weak_* family of customization points).

Partial order comparators

#include <cpp-sort/comparators/partial_greater.h>
#include <cpp-sort/comparators/partial_less.h>

The comparators partial_less and partial_order are customization points implementing a partial order, inspired by the similar functions described in P0100. The provided functions handle built-in integer out of the box (falling back to weak_* functions) and implement a partial order for floating point numbers using the built-in relational operators.

When it doesn't handle a type natively and ADL doesn't find any suitable partial_less function in a class namespace, cppsort::partial_less falls back to cppsort::weak_less since a weak order is also a partial order (it applies to the whole partial_* family of customization points).

Natural order comparator

#include <cpp-sort/comparators/natural_less.h>

The comparator natural_less is a customization point that can be used to perform a natural sort. The function handles any forward iterable sequence of char out of the box using std::isdigit to identify digits (which includes std::string, std::vector<char> and char[]). Other character type and locales are currently not handled and it's unlikely that the library will evolve more than switching to <locale>'s std::isdigit instead of <cctype>'s one.

Case-insensitive comparator

#include <cpp-sort/comparators/case_insensitive_less.h>

The comparator case_insensitive_less is a customization point that be used to perform a case-insensitive sort on collections. The function handles any forward iterable sequence of char or wchar_t out of the box using std::ctype::tolower prior to character comparison. The customization point has two distinct signatures:

template<typename T>
bool case_insensitive_less(const T& lhs, const T& rhs);

template<typename T>
bool case_insensitive_less(const T& lhs, const T& rhs, const std::locale& loc);

case_insensitive_less can indeed be passed an std::locale that will be used to perform the tolower operation. If it's not passed a locale, it will use the global locale instead:

// Use global locale
sort(sequence, case_insensitive_less);

// Use classic C locale
sort(sequence, case_insensitive_less(std::locale::classic()));

The two-parameter version of the customization points calls the three-parameter one with std::locale::global() as the third argument, so customizing only the three-parameter version will also extend the customization to the two-parameter one.

Clone this wiki locally