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
29namespace 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
111

source code of boost/libs/algorithm/include/boost/algorithm/sort_subrange.hpp

Morty Proxy This is a proxified and sanitized view of the page, visit original site.