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> sort_subrange(Iterator first,Iterator last,Iterator sub_first,Iterator sub_last,Pred p)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> sort_subrange(Iterator first,Iterator last,Iterator sub_first,Iterator sub_last)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> partition_subrange(Iterator first,Iterator last,Iterator sub_first,Iterator sub_last,Pred p)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> partition_subrange(Iterator first,Iterator last,Iterator sub_first,Iterator sub_last)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 111