5.10. sorting_utils.hpp

Full path: graph_canon/sorting_utils.hpp

template<typename Iter, typename Pred, typename Swap>
Iter partition_range(Iter first, Iter last, Pred pred, Swap swapper)

A function template equivalent to std::partition, except that element swapping is delegated to the given swapper.

Requires (in addition to the requirements by std::partition), that for two dereferenceable iterators a and b in the given range, the expression swapper(a, b) swaps the values represented by the iterators. For example, Swap may be a predicate simply calling std::iter_swap.

template<typename SizeType, SizeType Max>
class counting_sorter

An object for performing counting sort of values in the range 0 to Max. Requires Max >= 2.

template<typename Iterator, typename ToValue, typename Callback, typename PutValue>
void operator()(const Iterator first, const Iterator last, ToValue toValue, Callback callback, PutValue putter)

Sort the range first to last.

Requires:

  • Iterator must model a RandomAccessIterator.

  • ToValue: for a dereferenceable iterator iter, the expression toValue(*iter) must return an integer in the range 0 to Max.

  • Callback: for a range of integers ends representing the end of each bucket, as offsets from first, the expression callback(ends) must be valid.

  • PutValue: for a dereferenceable iterator iter and an element elem, the expression putter(iter, elem) must be valid, and ensure that *iter == elem becomes true.