Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for an old version of boost. Click here for the latest Boost documentation.
PrevUpHomeNext

Float Sort

float_sort is a fast templated in-place hybrid radix/comparison algorithm much like integer_sort, but sorts IEEE floating-point numbers (positive, zero, NaN, and negative) into ascending order by casting them to integers. This works because positive IEEE floating-point numbers sort like integers with the same bits, and negative IEEE floating-point numbers sort in the reverse order of integers with the same bits. float_sort is roughly 2X as fast as std::sort.

-0.0 vs. 0.0 and NaN are given definitive ordered positions by the radix-based portion of this algorithm, where comparison-based sorting does not guarantee their relative position. The included tests avoid creating NaN and -0.0 so that results match std::sort, which is not consistent in how it handles these numbers, as they compare as equal to numbers with different values.

float_sort checks the size of the data type and whether it is castable, picking an integer type to cast to, if a casting functor isn't provided by the user.

float_mem_cast casts IEEE floating-point numbers (positive, zero, NaN, and negative) into integers. This is an essential utility for creating a custom rightshift functor for float_sort, when one is needed. Only IEEE floating-point numbers of the same size as the integer type being cast to should be used in this specialized method call. Worst-case performance is 𝑶(N * (log2(range)/s + s)), so float_sort is asymptotically faster than pure comparison-based algorithms. s is max_splits, which defaults to 11, so its worst-case with default settings for 32-bit integers is 𝑶(N * ((32/11) slow radix-based iterations + 11 fast comparison-based iterations).

Some performance plots of runtime vs. n and log2(range) are provided below:

Windows Float Sort

OSX Float Sort

See floatfunctorsample.cpp for a working example of how to sort structs with a float key:

#define CAST_TYPE int
#define KEY_TYPE float
struct DATA_TYPE {
    KEY_TYPE key;
    std::string data;
};

Right-shift functor:

// Casting to an integer before bitshifting
struct rightshift {
  int operator()(const DATA_TYPE &x, const unsigned offset) const {
    return float_mem_cast<KEY_TYPE, CAST_TYPE>(x.key) >> offset;
  }
};

Comparison lessthan operator< functor:

struct lessthan {
  bool operator()(const DATA_TYPE &x, const DATA_TYPE &y) const {
    return x.key < y.key;
  }
};

Other examples:

Sort doubles.

Sort floats using a rightshift functor.


PrevUpHomeNext