1 // (C) Copyright Herve Bronnimann 2004.
3 // Distributed under the Boost Software License, Version 1.0. (See accompanying
4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
9 Split the code into two headers to lessen dependence on
12 Added the code for the boost minmax library. (Herve)
15 #ifndef BOOST_ALGORITHM_MINMAX_ELEMENT_HPP
16 #define BOOST_ALGORITHM_MINMAX_ELEMENT_HPP
18 /* PROPOSED STANDARD EXTENSIONS:
20 * minmax_element(first, last)
21 * Effect: std::make_pair( std::min_element(first, last),
22 * std::max_element(first, last) );
24 * minmax_element(first, last, comp)
25 * Effect: std::make_pair( std::min_element(first, last, comp),
26 * std::max_element(first, last, comp) );
29 #include <utility> // for std::pair and std::make_pair
33 namespace detail { // for obtaining a uniform version of minmax_element
34 // that compiles with VC++ 6.0 -- avoid the iterator_traits by
35 // having comparison object over iterator, not over dereferenced value
37 template <typename Iterator>
38 struct less_over_iter {
39 bool operator()(Iterator const& it1,
40 Iterator const& it2) const { return *it1 < *it2; }
43 template <typename Iterator, class BinaryPredicate>
44 struct binary_pred_over_iter {
45 explicit binary_pred_over_iter(BinaryPredicate const& p ) : m_p( p ) {}
46 bool operator()(Iterator const& it1,
47 Iterator const& it2) const { return m_p(*it1, *it2); }
52 // common base for the two minmax_element overloads
54 template <typename ForwardIter, class Compare >
55 std::pair<ForwardIter,ForwardIter>
56 basic_minmax_element(ForwardIter first, ForwardIter last, Compare comp)
59 return std::make_pair(last,last);
61 ForwardIter min_result = first;
62 ForwardIter max_result = first;
64 // if only one element
65 ForwardIter second = first; ++second;
67 return std::make_pair(min_result, max_result);
69 // treat first pair separately (only one comparison for first two elements)
70 ForwardIter potential_min_result = last;
71 if (comp(first, second))
75 potential_min_result = first;
78 // then each element by pairs, with at most 3 comparisons per pair
79 first = ++second; if (first != last) ++second;
80 while (second != last) {
81 if (comp(first, second)) {
82 if (comp(first, min_result)) {
84 potential_min_result = last;
86 if (comp(max_result, second))
89 if (comp(second, min_result)) {
91 potential_min_result = first;
93 if (comp(max_result, first))
97 if (first != last) ++second;
100 // if odd number of elements, treat last element
101 if (first != last) { // odd number of elements
102 if (comp(first, min_result)) {
104 potential_min_result = last;
106 else if (comp(max_result, first))
110 // resolve min_result being incorrect with one extra comparison
111 // (in which case potential_min_result is necessarily the correct result)
112 if (potential_min_result != last
113 && !comp(min_result, potential_min_result))
114 min_result = potential_min_result;
116 return std::make_pair(min_result,max_result);
119 } // namespace detail
121 template <typename ForwardIter>
122 std::pair<ForwardIter,ForwardIter>
123 minmax_element(ForwardIter first, ForwardIter last)
125 return detail::basic_minmax_element(first, last,
126 detail::less_over_iter<ForwardIter>() );
129 template <typename ForwardIter, class BinaryPredicate>
130 std::pair<ForwardIter,ForwardIter>
131 minmax_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
133 return detail::basic_minmax_element(first, last,
134 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
139 /* PROPOSED BOOST EXTENSIONS
140 * In the description below, [rfirst,rlast) denotes the reversed range
141 * of [first,last). Even though the iterator type of first and last may
142 * be only a Forward Iterator, it is possible to explain the semantics
143 * by assuming that it is a Bidirectional Iterator. In the sequel,
144 * reverse(ForwardIterator&) returns the reverse_iterator adaptor.
145 * This is not how the functions would be implemented!
147 * first_min_element(first, last)
148 * Effect: std::min_element(first, last);
150 * first_min_element(first, last, comp)
151 * Effect: std::min_element(first, last, comp);
153 * last_min_element(first, last)
154 * Effect: reverse( std::min_element(reverse(last), reverse(first)) );
156 * last_min_element(first, last, comp)
157 * Effect: reverse( std::min_element(reverse(last), reverse(first), comp) );
159 * first_max_element(first, last)
160 * Effect: std::max_element(first, last);
162 * first_max_element(first, last, comp)
163 * Effect: max_element(first, last);
165 * last_max_element(first, last)
166 * Effect: reverse( std::max_element(reverse(last), reverse(first)) );
168 * last_max_element(first, last, comp)
169 * Effect: reverse( std::max_element(reverse(last), reverse(first), comp) );
171 * first_min_first_max_element(first, last)
172 * Effect: std::make_pair( first_min_element(first, last),
173 * first_max_element(first, last) );
175 * first_min_first_max_element(first, last, comp)
176 * Effect: std::make_pair( first_min_element(first, last, comp),
177 * first_max_element(first, last, comp) );
179 * first_min_last_max_element(first, last)
180 * Effect: std::make_pair( first_min_element(first, last),
181 * last_max_element(first, last) );
183 * first_min_last_max_element(first, last, comp)
184 * Effect: std::make_pair( first_min_element(first, last, comp),
185 * last_max_element(first, last, comp) );
187 * last_min_first_max_element(first, last)
188 * Effect: std::make_pair( last_min_element(first, last),
189 * first_max_element(first, last) );
191 * last_min_first_max_element(first, last, comp)
192 * Effect: std::make_pair( last_min_element(first, last, comp),
193 * first_max_element(first, last, comp) );
195 * last_min_last_max_element(first, last)
196 * Effect: std::make_pair( last_min_element(first, last),
197 * last_max_element(first, last) );
199 * last_min_last_max_element(first, last, comp)
200 * Effect: std::make_pair( last_min_element(first, last, comp),
201 * last_max_element(first, last, comp) );
206 // Min_element and max_element variants
208 namespace detail { // common base for the overloads
210 template <typename ForwardIter, class BinaryPredicate>
212 basic_first_min_element(ForwardIter first, ForwardIter last,
213 BinaryPredicate comp)
215 if (first == last) return last;
216 ForwardIter min_result = first;
217 while (++first != last)
218 if (comp(first, min_result))
223 template <typename ForwardIter, class BinaryPredicate>
225 basic_last_min_element(ForwardIter first, ForwardIter last,
226 BinaryPredicate comp)
228 if (first == last) return last;
229 ForwardIter min_result = first;
230 while (++first != last)
231 if (!comp(min_result, first))
236 template <typename ForwardIter, class BinaryPredicate>
238 basic_first_max_element(ForwardIter first, ForwardIter last,
239 BinaryPredicate comp)
241 if (first == last) return last;
242 ForwardIter max_result = first;
243 while (++first != last)
244 if (comp(max_result, first))
249 template <typename ForwardIter, class BinaryPredicate>
251 basic_last_max_element(ForwardIter first, ForwardIter last,
252 BinaryPredicate comp)
254 if (first == last) return last;
255 ForwardIter max_result = first;
256 while (++first != last)
257 if (!comp(first, max_result))
262 } // namespace detail
264 template <typename ForwardIter>
266 first_min_element(ForwardIter first, ForwardIter last)
268 return detail::basic_first_min_element(first, last,
269 detail::less_over_iter<ForwardIter>() );
272 template <typename ForwardIter, class BinaryPredicate>
274 first_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
276 return detail::basic_first_min_element(first, last,
277 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
280 template <typename ForwardIter>
282 last_min_element(ForwardIter first, ForwardIter last)
284 return detail::basic_last_min_element(first, last,
285 detail::less_over_iter<ForwardIter>() );
288 template <typename ForwardIter, class BinaryPredicate>
290 last_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
292 return detail::basic_last_min_element(first, last,
293 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
296 template <typename ForwardIter>
298 first_max_element(ForwardIter first, ForwardIter last)
300 return detail::basic_first_max_element(first, last,
301 detail::less_over_iter<ForwardIter>() );
304 template <typename ForwardIter, class BinaryPredicate>
306 first_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
308 return detail::basic_first_max_element(first, last,
309 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
312 template <typename ForwardIter>
314 last_max_element(ForwardIter first, ForwardIter last)
316 return detail::basic_last_max_element(first, last,
317 detail::less_over_iter<ForwardIter>() );
320 template <typename ForwardIter, class BinaryPredicate>
322 last_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
324 return detail::basic_last_max_element(first, last,
325 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
329 // Minmax_element variants -- comments removed
333 template <typename ForwardIter, class BinaryPredicate>
334 std::pair<ForwardIter,ForwardIter>
335 basic_first_min_last_max_element(ForwardIter first, ForwardIter last,
336 BinaryPredicate comp)
339 return std::make_pair(last,last);
341 ForwardIter min_result = first;
342 ForwardIter max_result = first;
344 ForwardIter second = ++first;
346 return std::make_pair(min_result, max_result);
348 if (comp(second, min_result))
353 first = ++second; if (first != last) ++second;
354 while (second != last) {
355 if (!comp(second, first)) {
356 if (comp(first, min_result))
358 if (!comp(second, max_result))
361 if (comp(second, min_result))
363 if (!comp(first, max_result))
366 first = ++second; if (first != last) ++second;
370 if (comp(first, min_result))
372 else if (!comp(first, max_result))
376 return std::make_pair(min_result, max_result);
379 template <typename ForwardIter, class BinaryPredicate>
380 std::pair<ForwardIter,ForwardIter>
381 basic_last_min_first_max_element(ForwardIter first, ForwardIter last,
382 BinaryPredicate comp)
384 if (first == last) return std::make_pair(last,last);
386 ForwardIter min_result = first;
387 ForwardIter max_result = first;
389 ForwardIter second = ++first;
391 return std::make_pair(min_result, max_result);
393 if (comp(max_result, second))
398 first = ++second; if (first != last) ++second;
399 while (second != last) {
400 if (comp(first, second)) {
401 if (!comp(min_result, first))
403 if (comp(max_result, second))
406 if (!comp(min_result, second))
408 if (comp(max_result, first))
411 first = ++second; if (first != last) ++second;
415 if (!comp(min_result, first))
417 else if (comp(max_result, first))
421 return std::make_pair(min_result, max_result);
424 template <typename ForwardIter, class BinaryPredicate>
425 std::pair<ForwardIter,ForwardIter>
426 basic_last_min_last_max_element(ForwardIter first, ForwardIter last,
427 BinaryPredicate comp)
429 if (first == last) return std::make_pair(last,last);
431 ForwardIter min_result = first;
432 ForwardIter max_result = first;
434 ForwardIter second = first; ++second;
436 return std::make_pair(min_result,max_result);
438 ForwardIter potential_max_result = last;
439 if (comp(first, second))
443 potential_max_result = second;
446 first = ++second; if (first != last) ++second;
447 while (second != last) {
448 if (comp(first, second)) {
449 if (!comp(min_result, first))
451 if (!comp(second, max_result)) {
453 potential_max_result = last;
456 if (!comp(min_result, second))
458 if (!comp(first, max_result)) {
460 potential_max_result = second;
464 if (first != last) ++second;
468 if (!comp(min_result, first))
470 if (!comp(first, max_result)) {
472 potential_max_result = last;
476 if (potential_max_result != last
477 && !comp(potential_max_result, max_result))
478 max_result = potential_max_result;
480 return std::make_pair(min_result,max_result);
483 } // namespace detail
485 template <typename ForwardIter>
486 inline std::pair<ForwardIter,ForwardIter>
487 first_min_first_max_element(ForwardIter first, ForwardIter last)
489 return minmax_element(first, last);
492 template <typename ForwardIter, class BinaryPredicate>
493 inline std::pair<ForwardIter,ForwardIter>
494 first_min_first_max_element(ForwardIter first, ForwardIter last,
495 BinaryPredicate comp)
497 return minmax_element(first, last, comp);
500 template <typename ForwardIter>
501 std::pair<ForwardIter,ForwardIter>
502 first_min_last_max_element(ForwardIter first, ForwardIter last)
504 return detail::basic_first_min_last_max_element(first, last,
505 detail::less_over_iter<ForwardIter>() );
508 template <typename ForwardIter, class BinaryPredicate>
509 inline std::pair<ForwardIter,ForwardIter>
510 first_min_last_max_element(ForwardIter first, ForwardIter last,
511 BinaryPredicate comp)
513 return detail::basic_first_min_last_max_element(first, last,
514 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
517 template <typename ForwardIter>
518 std::pair<ForwardIter,ForwardIter>
519 last_min_first_max_element(ForwardIter first, ForwardIter last)
521 return detail::basic_last_min_first_max_element(first, last,
522 detail::less_over_iter<ForwardIter>() );
525 template <typename ForwardIter, class BinaryPredicate>
526 inline std::pair<ForwardIter,ForwardIter>
527 last_min_first_max_element(ForwardIter first, ForwardIter last,
528 BinaryPredicate comp)
530 return detail::basic_last_min_first_max_element(first, last,
531 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
534 template <typename ForwardIter>
535 std::pair<ForwardIter,ForwardIter>
536 last_min_last_max_element(ForwardIter first, ForwardIter last)
538 return detail::basic_last_min_last_max_element(first, last,
539 detail::less_over_iter<ForwardIter>() );
542 template <typename ForwardIter, class BinaryPredicate>
543 inline std::pair<ForwardIter,ForwardIter>
544 last_min_last_max_element(ForwardIter first, ForwardIter last,
545 BinaryPredicate comp)
547 return detail::basic_last_min_last_max_element(first, last,
548 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
553 #endif // BOOST_ALGORITHM_MINMAX_ELEMENT_HPP