]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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/range/begin.hpp> | |
26 | #include <boost/range/end.hpp> | |
27 | ||
28 | namespace boost { namespace algorithm { | |
29 | ||
30 | /// \fn sort_subrange ( T const& val, | |
31 | /// Iterator first, Iterator last, | |
32 | /// Iterator sub_first, Iterator sub_last, | |
33 | /// Pred p ) | |
34 | /// \brief Sort the subrange [sub_first, sub_last) that is inside | |
35 | /// the range [first, last) as if you had sorted the entire range. | |
36 | /// | |
37 | /// \param first The start of the larger range | |
38 | /// \param last The end of the larger range | |
39 | /// \param sub_first The start of the sub range | |
40 | /// \param sub_last The end of the sub range | |
41 | /// \param p A predicate to use to compare the values. | |
42 | /// p ( a, b ) returns a boolean. | |
43 | /// | |
44 | template<typename Iterator, typename Pred> | |
45 | void sort_subrange ( | |
46 | Iterator first, Iterator last, | |
47 | Iterator sub_first, Iterator sub_last, | |
48 | Pred p) | |
49 | { | |
50 | if (sub_first == sub_last) return; // the empty sub-range is already sorted. | |
51 | ||
52 | if (sub_first != first) { // sub-range is at the start, don't need to partition | |
53 | (void) std::nth_element(first, sub_first, last, p); | |
54 | ++sub_first; | |
55 | } | |
56 | std::partial_sort(sub_first, sub_last, last, p); | |
57 | } | |
58 | ||
59 | ||
60 | ||
61 | template<typename Iterator> | |
62 | void sort_subrange (Iterator first, Iterator last, Iterator sub_first, Iterator sub_last) | |
63 | { | |
64 | typedef typename std::iterator_traits<Iterator>::value_type value_type; | |
65 | return sort_subrange(first, last, sub_first, sub_last, std::less<value_type>()); | |
66 | } | |
67 | ||
68 | /// range versions? | |
69 | ||
70 | ||
71 | /// \fn partition_subrange ( T const& val, | |
72 | /// Iterator first, Iterator last, | |
73 | /// Iterator sub_first, Iterator sub_last, | |
74 | /// Pred p ) | |
75 | /// \brief Gather the elements of the subrange [sub_first, sub_last) that is | |
76 | /// inside the range [first, last) as if you had sorted the entire range. | |
77 | /// | |
78 | /// \param first The start of the larger range | |
79 | /// \param last The end of the larger range | |
80 | /// \param sub_first The start of the sub range | |
81 | /// \param sub_last The end of the sub range | |
82 | /// \param p A predicate to use to compare the values. | |
83 | /// p ( a, b ) returns a boolean. | |
84 | /// | |
85 | template<typename Iterator, typename Pred> | |
86 | void partition_subrange ( | |
87 | Iterator first, Iterator last, | |
88 | Iterator sub_first, Iterator sub_last, | |
89 | Pred p) | |
90 | { | |
91 | if (sub_first != first) { | |
92 | (void) std::nth_element(first, sub_first, last, p); | |
93 | ++sub_first; | |
94 | } | |
95 | ||
96 | if (sub_last != last) | |
97 | (void) std::nth_element(sub_first, sub_last, last, p); | |
98 | } | |
99 | ||
100 | template<typename Iterator> | |
101 | void partition_subrange (Iterator first, Iterator last, Iterator sub_first, Iterator sub_last) | |
102 | { | |
103 | typedef typename std::iterator_traits<Iterator>::value_type value_type; | |
104 | return partition_subrange(first, last, sub_first, sub_last, std::less<value_type>()); | |
105 | } | |
106 | ||
107 | }} | |
108 | ||
109 | #endif // BOOST_ALGORITHM_SORT_SUBRANGE_HPP |