2 Copyright (c) Marshall Clow 2008-2012.
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)
8 28 Sep 2015 mtc First version
12 /// \file sort_subrange.hpp
13 /// \brief Sort a subrange
14 /// \author Marshall Clow
16 /// Suggested by Sean Parent in his CppCon 2015 keynote
18 #ifndef BOOST_ALGORITHM_SORT_SUBRANGE_HPP
19 #define BOOST_ALGORITHM_SORT_SUBRANGE_HPP
21 #include <functional> // For std::less
22 #include <iterator> // For std::iterator_traits
23 #include <algorithm> // For nth_element and partial_sort
25 #include <boost/config.hpp>
26 #include <boost/range/begin.hpp>
27 #include <boost/range/end.hpp>
29 namespace boost { namespace algorithm {
31 /// \fn sort_subrange ( T const& val,
32 /// Iterator first, Iterator last,
33 /// Iterator sub_first, Iterator sub_last,
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.
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.
45 template<typename Iterator, typename Pred>
47 Iterator first, Iterator last,
48 Iterator sub_first, Iterator sub_last,
51 if (sub_first == sub_last) return; // the empty sub-range is already sorted.
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);
57 std::partial_sort(sub_first, sub_last, last, p);
62 template<typename Iterator>
63 void sort_subrange (Iterator first, Iterator last, Iterator sub_first, Iterator sub_last)
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>());
72 /// \fn partition_subrange ( T const& val,
73 /// Iterator first, Iterator last,
74 /// Iterator sub_first, Iterator sub_last,
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.
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.
86 template<typename Iterator, typename Pred>
87 void partition_subrange (
88 Iterator first, Iterator last,
89 Iterator sub_first, Iterator sub_last,
92 if (sub_first != first) {
93 (void) std::nth_element(first, sub_first, last, p);
98 (void) std::nth_element(sub_first, sub_last, last, p);
101 template<typename Iterator>
102 void partition_subrange (Iterator first, Iterator last, Iterator sub_first, Iterator sub_last)
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>());
110 #endif // BOOST_ALGORITHM_SORT_SUBRANGE_HPP