boost/algorithm/sort_subrange.hpp

0001 /*
0002    Copyright (c) Marshall Clow 2008-2012.
0003
0004    Distributed under the Boost Software License, Version 1.0. (See accompanying
0005    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006
0007  Revision history:
0008    28 Sep 2015 mtc First version
0009
0010 */
0011
0012 /// \file sort_subrange.hpp
0013 /// \brief Sort a subrange
0014 /// \author Marshall Clow
0015 ///
0016 /// Suggested by Sean Parent in his CppCon 2015 keynote
0017
0018 #ifndef BOOST_ALGORITHM_SORT_SUBRANGE_HPP
0019 #define BOOST_ALGORITHM_SORT_SUBRANGE_HPP
0020
0021 #include <functional>       // For std::less
0022 #include <iterator>         // For std::iterator_traits
0023 #include <algorithm>        // For nth_element and partial_sort
0024
0025 #include <boost/config.hpp>
0026 #include <boost/range/begin.hpp>
0027 #include <boost/range/end.hpp>
0028
0029 namespace boost { namespace algorithm {
0030
0031 /// \fn sort_subrange ( T const& val,
0032 ///               Iterator first,     Iterator last,
0033 ///               Iterator sub_first, Iterator sub_last,
0034 ///               Pred p )
0035 /// \brief Sort the subrange [sub_first, sub_last) that is inside
0036 ///     the range [first, last) as if you had sorted the entire range.
0037 ///
0038 /// \param first       The start of the larger range
0039 /// \param last        The end of the larger range
0040 /// \param sub_first   The start of the sub range
0041 /// \param sub_last    The end of the sub range
0042 /// \param p           A predicate to use to compare the values.
0043 ///                        p ( a, b ) returns a boolean.
0044 ///
0045   template<typename Iterator, typename Pred>
0046   void sort_subrange (
0047     Iterator first,     Iterator last,
0048     Iterator sub_first, Iterator sub_last,
0049     Pred p)
0050   {
0051     if (sub_first == sub_last) return; // the empty sub-range is already sorted.
0052
0053     if (sub_first != first) { // sub-range is at the start, don't need to partition
0054         (void) std::nth_element(first, sub_first, last, p);
0055         ++sub_first;
0056         }
0057     std::partial_sort(sub_first, sub_last, last, p);
0058   }
0059
0060
0061
0062   template<typename Iterator>
0063   void sort_subrange (Iterator first, Iterator last, Iterator sub_first, Iterator sub_last)
0064   {
0065     typedef typename std::iterator_traits<Iterator>::value_type value_type;
0066     return sort_subrange(first, last, sub_first, sub_last, std::less<value_type>());
0067   }
0068
0069 /// range versions?
0070
0071
0072 /// \fn partition_subrange ( T const& val,
0073 ///               Iterator first,     Iterator last,
0074 ///               Iterator sub_first, Iterator sub_last,
0075 ///               Pred p )
0076 /// \brief Gather the elements of the subrange [sub_first, sub_last) that is
0077 ///     inside the range [first, last) as if you had sorted the entire range.
0078 ///
0079 /// \param first       The start of the larger range
0080 /// \param last        The end of the larger range
0081 /// \param sub_first   The start of the sub range
0082 /// \param sub_last    The end of the sub range
0083 /// \param p           A predicate to use to compare the values.
0084 ///                        p ( a, b ) returns a boolean.
0085 ///
0086   template<typename Iterator, typename Pred>
0087   void partition_subrange (
0088     Iterator first,     Iterator last,
0089     Iterator sub_first, Iterator sub_last,
0090     Pred p)
0091   {
0092     if (sub_first != first) {
0093         (void) std::nth_element(first, sub_first, last, p);
0094         ++sub_first;
0095         }
0096
0097     if (sub_last != last)
0098         (void) std::nth_element(sub_first, sub_last, last, p);
0099   }
0100
0101   template<typename Iterator>
0102   void partition_subrange (Iterator first, Iterator last, Iterator sub_first, Iterator sub_last)
0103   {
0104     typedef typename std::iterator_traits<Iterator>::value_type value_type;
0105     return partition_subrange(first, last, sub_first, sub_last, std::less<value_type>());
0106   }
0107
0108 }}
0109
0110 #endif // BOOST_ALGORITHM_SORT_SUBRANGE_HPP