-//Templated Spreadsort-based implementation of integer_sort\r
-\r
-// Copyright Steven J. Ross 2001 - 2014.\r
-// Distributed under the Boost Software License, Version 1.0.\r
-// (See accompanying file LICENSE_1_0.txt or copy at\r
-// http://www.boost.org/LICENSE_1_0.txt)\r
-\r
-// See http://www.boost.org/libs/sort/ for library home page.\r
-\r
-/*\r
-Some improvements suggested by:\r
-Phil Endecott and Frank Gennari\r
-\r
-Doxygen comments by Paul A. Bristow Jan 2015\r
-\r
-*/\r
-\r
-#ifndef BOOST_INTEGER_SORT_HPP\r
-#define BOOST_INTEGER_SORT_HPP\r
-#include <algorithm>\r
-#include <vector>\r
-#include <cstring>\r
-#include <limits>\r
-#include <boost/static_assert.hpp>\r
-#include <boost/sort/spreadsort/detail/constants.hpp>\r
-#include <boost/sort/spreadsort/detail/integer_sort.hpp>\r
-\r
-namespace boost {\r
-namespace sort {\r
-namespace spreadsort {\r
- //Top-level sorting call for integers.\r
-\r
-\r
-/*! \brief Integer sort algorithm using random access iterators.\r
- (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size).\r
-\r
- \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,\r
-which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n\r
-Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,\r
-so @c integer_sort is asymptotically faster\r
-than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,\r
-so its worst-case with default settings for 32-bit integers is\r
-<em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n\r
-Some performance plots of runtime vs. n and log(range) are provided:\n\r
- <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>\r
- \n\r
- <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>\r
-\r
- \param[in] first Iterator pointer to first element.\r
- \param[in] last Iterator pointing to one beyond the end of data.\r
-\r
- \pre [@c first, @c last) is a valid range.\r
- \pre @c RandomAccessIter @c value_type is mutable.\r
- \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>\r
- \pre @c RandomAccessIter @c value_type supports the @c operator>>,\r
- which returns an integer-type right-shifted a specified number of bits.\r
- \post The elements in the range [@c first, @c last) are sorted in ascending order.\r
-\r
- \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),\r
- the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.\r
-\r
- \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss.\r
- \warning Invalid arguments cause undefined behaviour.\r
- \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,\r
- enabling faster generic-programming.\r
-\r
- \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:\r
- \remark * N is @c last - @c first,\r
- \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),\r
- \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).\r
-\r
-*/\r
- template <class RandomAccessIter>\r
- inline void integer_sort(RandomAccessIter first, RandomAccessIter last)\r
- {\r
- // Don't sort if it's too small to optimize.\r
- if (last - first < detail::min_sort_size)\r
- std::sort(first, last);\r
- else\r
- detail::integer_sort(first, last, *first >> 0);\r
- }\r
-\r
-/*! \brief Integer sort algorithm using random access iterators with both right-shift and user-defined comparison operator.\r
- (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size).\r
-\r
- \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,\r
-which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n\r
-Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,\r
-so @c integer_sort is asymptotically faster\r
-than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,\r
-so its worst-case with default settings for 32-bit integers is\r
-<em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n\r
-Some performance plots of runtime vs. n and log(range) are provided:\n\r
- <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>\r
- \n\r
- <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>\r
-\r
- \param[in] first Iterator pointer to first element.\r
- \param[in] last Iterator pointing to one beyond the end of data.\r
- \param[in] shift Functor that returns the result of shifting the value_type right a specified number of bits.\r
- \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order.\r
-\r
- \pre [@c first, @c last) is a valid range.\r
- \pre @c RandomAccessIter @c value_type is mutable.\r
- \post The elements in the range [@c first, @c last) are sorted in ascending order.\r
-\r
- \return @c void.\r
-\r
- \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),\r
- the right shift, subtraction of right-shifted elements, functors,\r
- or any operations on iterators throw.\r
-\r
- \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss.\r
- \warning Invalid arguments cause undefined behaviour.\r
- \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,\r
- enabling faster generic-programming.\r
-\r
- \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:\r
- \remark * N is @c last - @c first,\r
- \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),\r
- \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).\r
-*/\r
- template <class RandomAccessIter, class Right_shift, class Compare>\r
- inline void integer_sort(RandomAccessIter first, RandomAccessIter last,\r
- Right_shift shift, Compare comp) {\r
- if (last - first < detail::min_sort_size)\r
- std::sort(first, last, comp);\r
- else\r
- detail::integer_sort(first, last, shift(*first, 0), shift, comp);\r
- }\r
-\r
-/*! \brief Integer sort algorithm using random access iterators with just right-shift functor.\r
- (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size).\r
-\r
- \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,\r
-which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n\r
-\r
-\par Performance:\r
-Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,\r
-so @c integer_sort is asymptotically faster\r
-than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,\r
-so its worst-case with default settings for 32-bit integers is\r
-<em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n\r
-Some performance plots of runtime vs. n and log(range) are provided:\n\r
- * <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>\n\r
- * <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>\r
-\r
- \param[in] first Iterator pointer to first element.\r
- \param[in] last Iterator pointing to one beyond the end of data.\r
- \param[in] shift A functor that returns the result of shifting the value_type right a specified number of bits.\r
-\r
- \pre [@c first, @c last) is a valid range.\r
- \pre @c RandomAccessIter @c value_type is mutable.\r
- \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>\r
- \post The elements in the range [@c first, @c last) are sorted in ascending order.\r
-\r
- \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),\r
- the right shift, subtraction of right-shifted elements, functors,\r
- or any operations on iterators throw.\r
-\r
- \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss.\r
- \warning Invalid arguments cause undefined behaviour.\r
- \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,\r
- enabling faster generic-programming.\r
-\r
- \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:\r
- \remark * N is @c last - @c first,\r
- \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),\r
- \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).\r
-\r
-*/\r
- template <class RandomAccessIter, class Right_shift>\r
- inline void integer_sort(RandomAccessIter first, RandomAccessIter last,\r
- Right_shift shift) {\r
- if (last - first < detail::min_sort_size)\r
- std::sort(first, last);\r
- else\r
- detail::integer_sort(first, last, shift(*first, 0), shift);\r
- }\r
-}\r
-}\r
-}\r
-\r
-#endif\r
-\r
+//Templated Spreadsort-based implementation of integer_sort
+
+// Copyright Steven J. Ross 2001 - 2014.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/libs/sort/ for library home page.
+
+/*
+Some improvements suggested by:
+Phil Endecott and Frank Gennari
+
+Doxygen comments by Paul A. Bristow Jan 2015
+
+*/
+
+#ifndef BOOST_INTEGER_SORT_HPP
+#define BOOST_INTEGER_SORT_HPP
+#include <algorithm>
+#include <vector>
+#include <cstring>
+#include <limits>
+#include <boost/static_assert.hpp>
+#include <boost/sort/spreadsort/detail/constants.hpp>
+#include <boost/sort/spreadsort/detail/integer_sort.hpp>
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+
+namespace boost {
+namespace sort {
+namespace spreadsort {
+ //Top-level sorting call for integers.
+
+
+/*! \brief Integer sort algorithm using random access iterators.
+ (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size).
+
+ \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
+which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
+Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,
+so @c integer_sort is asymptotically faster
+than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
+so its worst-case with default settings for 32-bit integers is
+<em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
+Some performance plots of runtime vs. n and log(range) are provided:\n
+ <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>
+ \n
+ <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
+
+ \param[in] first Iterator pointer to first element.
+ \param[in] last Iterator pointing to one beyond the end of data.
+
+ \pre [@c first, @c last) is a valid range.
+ \pre @c RandomAccessIter @c value_type is mutable.
+ \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>
+ \pre @c RandomAccessIter @c value_type supports the @c operator>>,
+ which returns an integer-type right-shifted a specified number of bits.
+ \post The elements in the range [@c first, @c last) are sorted in ascending order.
+
+ \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
+ the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.
+
+ \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss.
+ \warning Invalid arguments cause undefined behaviour.
+ \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
+ enabling faster generic-programming.
+
+ \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
+ \remark * N is @c last - @c first,
+ \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),
+ \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
+
+*/
+ template <class RandomAccessIter>
+ inline void integer_sort(RandomAccessIter first, RandomAccessIter last)
+ {
+ // Don't sort if it's too small to optimize.
+ if (last - first < detail::min_sort_size)
+ std::sort(first, last);
+ else
+ detail::integer_sort(first, last, *first >> 0);
+ }
+
+/*! \brief Integer sort algorithm using range.
+ (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size).
+
+ \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
+which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
+Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,
+so @c integer_sort is asymptotically faster
+than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
+so its worst-case with default settings for 32-bit integers is
+<em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
+Some performance plots of runtime vs. n and log(range) are provided:\n
+ <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>
+ \n
+ <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
+
+ \param[in] range Range [first, last) for sorting.
+
+ \pre [@c first, @c last) is a valid range.
+ \post The elements in the range [@c first, @c last) are sorted in ascending order.
+
+ \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
+ the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.
+
+ \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss.
+ \warning Invalid arguments cause undefined behaviour.
+ \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
+ enabling faster generic-programming.
+
+ \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
+ \remark * N is @c last - @c first,
+ \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),
+ \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
+
+*/
+template <class Range>
+inline void integer_sort(Range& range)
+{
+ integer_sort(boost::begin(range), boost::end(range));
+}
+
+/*! \brief Integer sort algorithm using random access iterators with both right-shift and user-defined comparison operator.
+ (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size).
+
+ \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
+which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
+Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,
+so @c integer_sort is asymptotically faster
+than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
+so its worst-case with default settings for 32-bit integers is
+<em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
+Some performance plots of runtime vs. n and log(range) are provided:\n
+ <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>
+ \n
+ <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
+
+ \param[in] first Iterator pointer to first element.
+ \param[in] last Iterator pointing to one beyond the end of data.
+ \param[in] shift Functor that returns the result of shifting the value_type right a specified number of bits.
+ \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order.
+
+ \pre [@c first, @c last) is a valid range.
+ \pre @c RandomAccessIter @c value_type is mutable.
+ \post The elements in the range [@c first, @c last) are sorted in ascending order.
+
+ \return @c void.
+
+ \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
+ the right shift, subtraction of right-shifted elements, functors,
+ or any operations on iterators throw.
+
+ \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss.
+ \warning Invalid arguments cause undefined behaviour.
+ \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
+ enabling faster generic-programming.
+
+ \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
+ \remark * N is @c last - @c first,
+ \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),
+ \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
+*/
+ template <class RandomAccessIter, class Right_shift, class Compare>
+ inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
+ Right_shift shift, Compare comp) {
+ if (last - first < detail::min_sort_size)
+ std::sort(first, last, comp);
+ else
+ detail::integer_sort(first, last, shift(*first, 0), shift, comp);
+ }
+
+/*! \brief Integer sort algorithm using range with both right-shift and user-defined comparison operator.
+ (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size).
+
+ \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
+which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
+Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,
+so @c integer_sort is asymptotically faster
+than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
+so its worst-case with default settings for 32-bit integers is
+<em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
+Some performance plots of runtime vs. n and log(range) are provided:\n
+ <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>
+ \n
+ <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
+
+ \param[in] range Range [first, last) for sorting.
+ \param[in] shift Functor that returns the result of shifting the value_type right a specified number of bits.
+ \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order.
+
+ \pre [@c first, @c last) is a valid range.
+ \post The elements in the range [@c first, @c last) are sorted in ascending order.
+
+ \return @c void.
+
+ \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
+ the right shift, subtraction of right-shifted elements, functors,
+ or any operations on iterators throw.
+
+ \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss.
+ \warning Invalid arguments cause undefined behaviour.
+ \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
+ enabling faster generic-programming.
+
+ \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
+ \remark * N is @c last - @c first,
+ \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),
+ \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
+*/
+template <class Range, class Right_shift, class Compare>
+inline void integer_sort(Range& range, Right_shift shift, Compare comp)
+{
+ integer_sort(boost::begin(range), boost::end(range), shift, comp);
+}
+
+/*! \brief Integer sort algorithm using random access iterators with just right-shift functor.
+ (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size).
+
+ \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
+which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
+
+\par Performance:
+Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,
+so @c integer_sort is asymptotically faster
+than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
+so its worst-case with default settings for 32-bit integers is
+<em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
+Some performance plots of runtime vs. n and log(range) are provided:\n
+ * <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>\n
+ * <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
+
+ \param[in] first Iterator pointer to first element.
+ \param[in] last Iterator pointing to one beyond the end of data.
+ \param[in] shift A functor that returns the result of shifting the value_type right a specified number of bits.
+
+ \pre [@c first, @c last) is a valid range.
+ \pre @c RandomAccessIter @c value_type is mutable.
+ \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>
+ \post The elements in the range [@c first, @c last) are sorted in ascending order.
+
+ \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
+ the right shift, subtraction of right-shifted elements, functors,
+ or any operations on iterators throw.
+
+ \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss.
+ \warning Invalid arguments cause undefined behaviour.
+ \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
+ enabling faster generic-programming.
+
+ \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
+ \remark * N is @c last - @c first,
+ \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),
+ \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
+
+*/
+ template <class RandomAccessIter, class Right_shift>
+ inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
+ Right_shift shift) {
+ if (last - first < detail::min_sort_size)
+ std::sort(first, last);
+ else
+ detail::integer_sort(first, last, shift(*first, 0), shift);
+ }
+
+
+/*! \brief Integer sort algorithm using range with just right-shift functor.
+ (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size).
+
+ \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
+which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
+
+\par Performance:
+Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>,
+so @c integer_sort is asymptotically faster
+than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
+so its worst-case with default settings for 32-bit integers is
+<em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
+Some performance plots of runtime vs. n and log(range) are provided:\n
+ * <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>\n
+ * <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
+
+ \param[in] range Range [first, last) for sorting.
+ \param[in] shift A functor that returns the result of shifting the value_type right a specified number of bits.
+
+ \pre [@c first, @c last) is a valid range.
+ \post The elements in the range [@c first, @c last) are sorted in ascending order.
+
+ \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
+ the right shift, subtraction of right-shifted elements, functors,
+ or any operations on iterators throw.
+
+ \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss.
+ \warning Invalid arguments cause undefined behaviour.
+ \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
+ enabling faster generic-programming.
+
+ \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
+ \remark * N is @c last - @c first,
+ \remark * K is the log of the range in bits (32 for 32-bit integers using their full range),
+ \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
+
+*/
+template <class Range, class Right_shift>
+inline void integer_sort(Range& range, Right_shift shift)
+{
+ integer_sort(boost::begin(range), boost::end(range), shift);
+}
+}
+}
+}
+
+#endif
+
projects / ceph.git / blobdiff