boost/algorithm/sort_subrange.hpp

   1 /*
   2    Copyright (c) Marshall Clow 2008-2012.
   3
   4    Distributed under the Boost Software License, Version 1.0. (See accompanying
   5    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6
   7  Revision history:
   8    28 Sep 2015 mtc First version
   9
  10 */
  11
  12 /// \file sort_subrange.hpp
  13 /// \brief Sort a subrange
  14 /// \author Marshall Clow
  15 ///
  16 /// Suggested by Sean Parent in his CppCon 2015 keynote
  17
  18 #ifndef BOOST_ALGORITHM_SORT_SUBRANGE_HPP
  19 #define BOOST_ALGORITHM_SORT_SUBRANGE_HPP
  20
  21 #include <functional>       // For std::less
  22 #include <iterator>         // For std::iterator_traits
  23 #include <algorithm>        // For nth_element and partial_sort
  24
  25 #include <boost/config.hpp>
  26 #include <boost/range/begin.hpp>
  27 #include <boost/range/end.hpp>
  28
  29 namespace boost { namespace algorithm {
  30
  31 /// \fn sort_subrange ( T const& val,
  32 ///               Iterator first,     Iterator last,
  33 ///               Iterator sub_first, Iterator sub_last,
  34 ///               Pred p )
  35 /// \brief Sort the subrange [sub_first, sub_last) that is inside
  36 ///     the range [first, last) as if you had sorted the entire range.
  37 ///
  38 /// \param first       The start of the larger range
  39 /// \param last        The end of the larger range
  40 /// \param sub_first   The start of the sub range
  41 /// \param sub_last    The end of the sub range
  42 /// \param p           A predicate to use to compare the values.
  43 ///                        p ( a, b ) returns a boolean.
  44 ///
  45   template<typename Iterator, typename Pred>
  46   void sort_subrange (
  47         Iterator first,     Iterator last,
  48         Iterator sub_first, Iterator sub_last,
  49         Pred p)
  50   {
  51         if (sub_first == sub_last) return; // the empty sub-range is already sorted.
  52
  53         if (sub_first != first) { // sub-range is at the start, don't need to partition
  54                 (void) std::nth_element(first, sub_first, last, p);
  55                 ++sub_first;
  56                 }
  57         std::partial_sort(sub_first, sub_last, last, p);
  58   }
  59
  60
  61
  62   template<typename Iterator>
  63   void sort_subrange (Iterator first, Iterator last, Iterator sub_first, Iterator sub_last)
  64   {
  65         typedef typename std::iterator_traits<Iterator>::value_type value_type;
  66         return sort_subrange(first, last, sub_first, sub_last, std::less<value_type>());
  67   }
  68
  69 /// range versions?
  70
  71
  72 /// \fn partition_subrange ( T const& val,
  73 ///               Iterator first,     Iterator last,
  74 ///               Iterator sub_first, Iterator sub_last,
  75 ///               Pred p )
  76 /// \brief Gather the elements of the subrange [sub_first, sub_last) that is
  77 ///     inside the range [first, last) as if you had sorted the entire range.
  78 ///
  79 /// \param first       The start of the larger range
  80 /// \param last        The end of the larger range
  81 /// \param sub_first   The start of the sub range
  82 /// \param sub_last    The end of the sub range
  83 /// \param p           A predicate to use to compare the values.
  84 ///                        p ( a, b ) returns a boolean.
  85 ///
  86   template<typename Iterator, typename Pred>
  87   void partition_subrange (
  88         Iterator first,     Iterator last,
  89         Iterator sub_first, Iterator sub_last,
  90         Pred p)
  91   {
  92         if (sub_first != first) {
  93                 (void) std::nth_element(first, sub_first, last, p);
  94                 ++sub_first;
  95                 }
  96
  97         if (sub_last != last)
  98                 (void) std::nth_element(sub_first, sub_last, last, p);
  99   }
 100
 101   template<typename Iterator>
 102   void partition_subrange (Iterator first, Iterator last, Iterator sub_first, Iterator sub_last)
 103   {
 104         typedef typename std::iterator_traits<Iterator>::value_type value_type;
 105         return partition_subrange(first, last, sub_first, sub_last, std::less<value_type>());
 106   }
 107
 108 }}
 109
 110 #endif // BOOST_ALGORITHM_SORT_SUBRANGE_HPP