Chris@16
|
1 // (C) Copyright Herve Bronnimann 2004.
|
Chris@16
|
2 //
|
Chris@16
|
3 // Distributed under the Boost Software License, Version 1.0. (See accompanying
|
Chris@16
|
4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
|
Chris@16
|
5
|
Chris@16
|
6 /*
|
Chris@16
|
7 Revision history:
|
Chris@16
|
8 1 July 2004
|
Chris@16
|
9 Split the code into two headers to lessen dependence on
|
Chris@16
|
10 Boost.tuple. (Herve)
|
Chris@16
|
11 26 June 2004
|
Chris@16
|
12 Added the code for the boost minmax library. (Herve)
|
Chris@16
|
13 */
|
Chris@16
|
14
|
Chris@16
|
15 #ifndef BOOST_ALGORITHM_MINMAX_ELEMENT_HPP
|
Chris@16
|
16 #define BOOST_ALGORITHM_MINMAX_ELEMENT_HPP
|
Chris@16
|
17
|
Chris@16
|
18 /* PROPOSED STANDARD EXTENSIONS:
|
Chris@16
|
19 *
|
Chris@16
|
20 * minmax_element(first, last)
|
Chris@16
|
21 * Effect: std::make_pair( std::min_element(first, last),
|
Chris@16
|
22 * std::max_element(first, last) );
|
Chris@16
|
23 *
|
Chris@16
|
24 * minmax_element(first, last, comp)
|
Chris@16
|
25 * Effect: std::make_pair( std::min_element(first, last, comp),
|
Chris@16
|
26 * std::max_element(first, last, comp) );
|
Chris@16
|
27 */
|
Chris@16
|
28
|
Chris@16
|
29 #include <utility> // for std::pair and std::make_pair
|
Chris@16
|
30
|
Chris@16
|
31 namespace boost {
|
Chris@16
|
32
|
Chris@16
|
33 namespace detail { // for obtaining a uniform version of minmax_element
|
Chris@16
|
34 // that compiles with VC++ 6.0 -- avoid the iterator_traits by
|
Chris@16
|
35 // having comparison object over iterator, not over dereferenced value
|
Chris@16
|
36
|
Chris@16
|
37 template <typename Iterator>
|
Chris@16
|
38 struct less_over_iter {
|
Chris@16
|
39 bool operator()(Iterator const& it1,
|
Chris@16
|
40 Iterator const& it2) const { return *it1 < *it2; }
|
Chris@16
|
41 };
|
Chris@16
|
42
|
Chris@16
|
43 template <typename Iterator, class BinaryPredicate>
|
Chris@16
|
44 struct binary_pred_over_iter {
|
Chris@16
|
45 explicit binary_pred_over_iter(BinaryPredicate const& p ) : m_p( p ) {}
|
Chris@16
|
46 bool operator()(Iterator const& it1,
|
Chris@16
|
47 Iterator const& it2) const { return m_p(*it1, *it2); }
|
Chris@16
|
48 private:
|
Chris@16
|
49 BinaryPredicate m_p;
|
Chris@16
|
50 };
|
Chris@16
|
51
|
Chris@16
|
52 // common base for the two minmax_element overloads
|
Chris@16
|
53
|
Chris@16
|
54 template <typename ForwardIter, class Compare >
|
Chris@16
|
55 std::pair<ForwardIter,ForwardIter>
|
Chris@16
|
56 basic_minmax_element(ForwardIter first, ForwardIter last, Compare comp)
|
Chris@16
|
57 {
|
Chris@16
|
58 if (first == last)
|
Chris@16
|
59 return std::make_pair(last,last);
|
Chris@16
|
60
|
Chris@16
|
61 ForwardIter min_result = first;
|
Chris@16
|
62 ForwardIter max_result = first;
|
Chris@16
|
63
|
Chris@16
|
64 // if only one element
|
Chris@16
|
65 ForwardIter second = first; ++second;
|
Chris@16
|
66 if (second == last)
|
Chris@16
|
67 return std::make_pair(min_result, max_result);
|
Chris@16
|
68
|
Chris@16
|
69 // treat first pair separately (only one comparison for first two elements)
|
Chris@16
|
70 ForwardIter potential_min_result = last;
|
Chris@16
|
71 if (comp(first, second))
|
Chris@16
|
72 max_result = second;
|
Chris@16
|
73 else {
|
Chris@16
|
74 min_result = second;
|
Chris@16
|
75 potential_min_result = first;
|
Chris@16
|
76 }
|
Chris@16
|
77
|
Chris@16
|
78 // then each element by pairs, with at most 3 comparisons per pair
|
Chris@16
|
79 first = ++second; if (first != last) ++second;
|
Chris@16
|
80 while (second != last) {
|
Chris@16
|
81 if (comp(first, second)) {
|
Chris@16
|
82 if (comp(first, min_result)) {
|
Chris@16
|
83 min_result = first;
|
Chris@16
|
84 potential_min_result = last;
|
Chris@16
|
85 }
|
Chris@16
|
86 if (comp(max_result, second))
|
Chris@16
|
87 max_result = second;
|
Chris@16
|
88 } else {
|
Chris@16
|
89 if (comp(second, min_result)) {
|
Chris@16
|
90 min_result = second;
|
Chris@16
|
91 potential_min_result = first;
|
Chris@16
|
92 }
|
Chris@16
|
93 if (comp(max_result, first))
|
Chris@16
|
94 max_result = first;
|
Chris@16
|
95 }
|
Chris@16
|
96 first = ++second;
|
Chris@16
|
97 if (first != last) ++second;
|
Chris@16
|
98 }
|
Chris@16
|
99
|
Chris@16
|
100 // if odd number of elements, treat last element
|
Chris@16
|
101 if (first != last) { // odd number of elements
|
Chris@16
|
102 if (comp(first, min_result)) {
|
Chris@16
|
103 min_result = first;
|
Chris@16
|
104 potential_min_result = last;
|
Chris@16
|
105 }
|
Chris@16
|
106 else if (comp(max_result, first))
|
Chris@16
|
107 max_result = first;
|
Chris@16
|
108 }
|
Chris@16
|
109
|
Chris@16
|
110 // resolve min_result being incorrect with one extra comparison
|
Chris@16
|
111 // (in which case potential_min_result is necessarily the correct result)
|
Chris@16
|
112 if (potential_min_result != last
|
Chris@16
|
113 && !comp(min_result, potential_min_result))
|
Chris@16
|
114 min_result = potential_min_result;
|
Chris@16
|
115
|
Chris@16
|
116 return std::make_pair(min_result,max_result);
|
Chris@16
|
117 }
|
Chris@16
|
118
|
Chris@16
|
119 } // namespace detail
|
Chris@16
|
120
|
Chris@16
|
121 template <typename ForwardIter>
|
Chris@16
|
122 std::pair<ForwardIter,ForwardIter>
|
Chris@16
|
123 minmax_element(ForwardIter first, ForwardIter last)
|
Chris@16
|
124 {
|
Chris@16
|
125 return detail::basic_minmax_element(first, last,
|
Chris@16
|
126 detail::less_over_iter<ForwardIter>() );
|
Chris@16
|
127 }
|
Chris@16
|
128
|
Chris@16
|
129 template <typename ForwardIter, class BinaryPredicate>
|
Chris@16
|
130 std::pair<ForwardIter,ForwardIter>
|
Chris@16
|
131 minmax_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
|
Chris@16
|
132 {
|
Chris@16
|
133 return detail::basic_minmax_element(first, last,
|
Chris@16
|
134 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
|
Chris@16
|
135 }
|
Chris@16
|
136
|
Chris@16
|
137 }
|
Chris@16
|
138
|
Chris@16
|
139 /* PROPOSED BOOST EXTENSIONS
|
Chris@16
|
140 * In the description below, [rfirst,rlast) denotes the reversed range
|
Chris@16
|
141 * of [first,last). Even though the iterator type of first and last may
|
Chris@16
|
142 * be only a Forward Iterator, it is possible to explain the semantics
|
Chris@16
|
143 * by assuming that it is a Bidirectional Iterator. In the sequel,
|
Chris@16
|
144 * reverse(ForwardIterator&) returns the reverse_iterator adaptor.
|
Chris@16
|
145 * This is not how the functions would be implemented!
|
Chris@16
|
146 *
|
Chris@16
|
147 * first_min_element(first, last)
|
Chris@16
|
148 * Effect: std::min_element(first, last);
|
Chris@16
|
149 *
|
Chris@16
|
150 * first_min_element(first, last, comp)
|
Chris@16
|
151 * Effect: std::min_element(first, last, comp);
|
Chris@16
|
152 *
|
Chris@16
|
153 * last_min_element(first, last)
|
Chris@16
|
154 * Effect: reverse( std::min_element(reverse(last), reverse(first)) );
|
Chris@16
|
155 *
|
Chris@16
|
156 * last_min_element(first, last, comp)
|
Chris@16
|
157 * Effect: reverse( std::min_element(reverse(last), reverse(first), comp) );
|
Chris@16
|
158 *
|
Chris@16
|
159 * first_max_element(first, last)
|
Chris@16
|
160 * Effect: std::max_element(first, last);
|
Chris@16
|
161 *
|
Chris@16
|
162 * first_max_element(first, last, comp)
|
Chris@16
|
163 * Effect: max_element(first, last);
|
Chris@16
|
164 *
|
Chris@16
|
165 * last_max_element(first, last)
|
Chris@16
|
166 * Effect: reverse( std::max_element(reverse(last), reverse(first)) );
|
Chris@16
|
167 *
|
Chris@16
|
168 * last_max_element(first, last, comp)
|
Chris@16
|
169 * Effect: reverse( std::max_element(reverse(last), reverse(first), comp) );
|
Chris@16
|
170 *
|
Chris@16
|
171 * first_min_first_max_element(first, last)
|
Chris@16
|
172 * Effect: std::make_pair( first_min_element(first, last),
|
Chris@16
|
173 * first_max_element(first, last) );
|
Chris@16
|
174 *
|
Chris@16
|
175 * first_min_first_max_element(first, last, comp)
|
Chris@16
|
176 * Effect: std::make_pair( first_min_element(first, last, comp),
|
Chris@16
|
177 * first_max_element(first, last, comp) );
|
Chris@16
|
178 *
|
Chris@16
|
179 * first_min_last_max_element(first, last)
|
Chris@16
|
180 * Effect: std::make_pair( first_min_element(first, last),
|
Chris@16
|
181 * last_max_element(first, last) );
|
Chris@16
|
182 *
|
Chris@16
|
183 * first_min_last_max_element(first, last, comp)
|
Chris@16
|
184 * Effect: std::make_pair( first_min_element(first, last, comp),
|
Chris@16
|
185 * last_max_element(first, last, comp) );
|
Chris@16
|
186 *
|
Chris@16
|
187 * last_min_first_max_element(first, last)
|
Chris@16
|
188 * Effect: std::make_pair( last_min_element(first, last),
|
Chris@16
|
189 * first_max_element(first, last) );
|
Chris@16
|
190 *
|
Chris@16
|
191 * last_min_first_max_element(first, last, comp)
|
Chris@16
|
192 * Effect: std::make_pair( last_min_element(first, last, comp),
|
Chris@16
|
193 * first_max_element(first, last, comp) );
|
Chris@16
|
194 *
|
Chris@16
|
195 * last_min_last_max_element(first, last)
|
Chris@16
|
196 * Effect: std::make_pair( last_min_element(first, last),
|
Chris@16
|
197 * last_max_element(first, last) );
|
Chris@16
|
198 *
|
Chris@16
|
199 * last_min_last_max_element(first, last, comp)
|
Chris@16
|
200 * Effect: std::make_pair( last_min_element(first, last, comp),
|
Chris@16
|
201 * last_max_element(first, last, comp) );
|
Chris@16
|
202 */
|
Chris@16
|
203
|
Chris@16
|
204 namespace boost {
|
Chris@16
|
205
|
Chris@16
|
206 // Min_element and max_element variants
|
Chris@16
|
207
|
Chris@16
|
208 namespace detail { // common base for the overloads
|
Chris@16
|
209
|
Chris@16
|
210 template <typename ForwardIter, class BinaryPredicate>
|
Chris@16
|
211 ForwardIter
|
Chris@16
|
212 basic_first_min_element(ForwardIter first, ForwardIter last,
|
Chris@16
|
213 BinaryPredicate comp)
|
Chris@16
|
214 {
|
Chris@16
|
215 if (first == last) return last;
|
Chris@16
|
216 ForwardIter min_result = first;
|
Chris@16
|
217 while (++first != last)
|
Chris@16
|
218 if (comp(first, min_result))
|
Chris@16
|
219 min_result = first;
|
Chris@16
|
220 return min_result;
|
Chris@16
|
221 }
|
Chris@16
|
222
|
Chris@16
|
223 template <typename ForwardIter, class BinaryPredicate>
|
Chris@16
|
224 ForwardIter
|
Chris@16
|
225 basic_last_min_element(ForwardIter first, ForwardIter last,
|
Chris@16
|
226 BinaryPredicate comp)
|
Chris@16
|
227 {
|
Chris@16
|
228 if (first == last) return last;
|
Chris@16
|
229 ForwardIter min_result = first;
|
Chris@16
|
230 while (++first != last)
|
Chris@16
|
231 if (!comp(min_result, first))
|
Chris@16
|
232 min_result = first;
|
Chris@16
|
233 return min_result;
|
Chris@16
|
234 }
|
Chris@16
|
235
|
Chris@16
|
236 template <typename ForwardIter, class BinaryPredicate>
|
Chris@16
|
237 ForwardIter
|
Chris@16
|
238 basic_first_max_element(ForwardIter first, ForwardIter last,
|
Chris@16
|
239 BinaryPredicate comp)
|
Chris@16
|
240 {
|
Chris@16
|
241 if (first == last) return last;
|
Chris@16
|
242 ForwardIter max_result = first;
|
Chris@16
|
243 while (++first != last)
|
Chris@16
|
244 if (comp(max_result, first))
|
Chris@16
|
245 max_result = first;
|
Chris@16
|
246 return max_result;
|
Chris@16
|
247 }
|
Chris@16
|
248
|
Chris@16
|
249 template <typename ForwardIter, class BinaryPredicate>
|
Chris@16
|
250 ForwardIter
|
Chris@16
|
251 basic_last_max_element(ForwardIter first, ForwardIter last,
|
Chris@16
|
252 BinaryPredicate comp)
|
Chris@16
|
253 {
|
Chris@16
|
254 if (first == last) return last;
|
Chris@16
|
255 ForwardIter max_result = first;
|
Chris@16
|
256 while (++first != last)
|
Chris@16
|
257 if (!comp(first, max_result))
|
Chris@16
|
258 max_result = first;
|
Chris@16
|
259 return max_result;
|
Chris@16
|
260 }
|
Chris@16
|
261
|
Chris@16
|
262 } // namespace detail
|
Chris@16
|
263
|
Chris@16
|
264 template <typename ForwardIter>
|
Chris@16
|
265 ForwardIter
|
Chris@16
|
266 first_min_element(ForwardIter first, ForwardIter last)
|
Chris@16
|
267 {
|
Chris@16
|
268 return detail::basic_first_min_element(first, last,
|
Chris@16
|
269 detail::less_over_iter<ForwardIter>() );
|
Chris@16
|
270 }
|
Chris@16
|
271
|
Chris@16
|
272 template <typename ForwardIter, class BinaryPredicate>
|
Chris@16
|
273 ForwardIter
|
Chris@16
|
274 first_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
|
Chris@16
|
275 {
|
Chris@16
|
276 return detail::basic_first_min_element(first, last,
|
Chris@16
|
277 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
|
Chris@16
|
278 }
|
Chris@16
|
279
|
Chris@16
|
280 template <typename ForwardIter>
|
Chris@16
|
281 ForwardIter
|
Chris@16
|
282 last_min_element(ForwardIter first, ForwardIter last)
|
Chris@16
|
283 {
|
Chris@16
|
284 return detail::basic_last_min_element(first, last,
|
Chris@16
|
285 detail::less_over_iter<ForwardIter>() );
|
Chris@16
|
286 }
|
Chris@16
|
287
|
Chris@16
|
288 template <typename ForwardIter, class BinaryPredicate>
|
Chris@16
|
289 ForwardIter
|
Chris@16
|
290 last_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
|
Chris@16
|
291 {
|
Chris@16
|
292 return detail::basic_last_min_element(first, last,
|
Chris@16
|
293 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
|
Chris@16
|
294 }
|
Chris@16
|
295
|
Chris@16
|
296 template <typename ForwardIter>
|
Chris@16
|
297 ForwardIter
|
Chris@16
|
298 first_max_element(ForwardIter first, ForwardIter last)
|
Chris@16
|
299 {
|
Chris@16
|
300 return detail::basic_first_max_element(first, last,
|
Chris@16
|
301 detail::less_over_iter<ForwardIter>() );
|
Chris@16
|
302 }
|
Chris@16
|
303
|
Chris@16
|
304 template <typename ForwardIter, class BinaryPredicate>
|
Chris@16
|
305 ForwardIter
|
Chris@16
|
306 first_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
|
Chris@16
|
307 {
|
Chris@16
|
308 return detail::basic_first_max_element(first, last,
|
Chris@16
|
309 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
|
Chris@16
|
310 }
|
Chris@16
|
311
|
Chris@16
|
312 template <typename ForwardIter>
|
Chris@16
|
313 ForwardIter
|
Chris@16
|
314 last_max_element(ForwardIter first, ForwardIter last)
|
Chris@16
|
315 {
|
Chris@16
|
316 return detail::basic_last_max_element(first, last,
|
Chris@16
|
317 detail::less_over_iter<ForwardIter>() );
|
Chris@16
|
318 }
|
Chris@16
|
319
|
Chris@16
|
320 template <typename ForwardIter, class BinaryPredicate>
|
Chris@16
|
321 ForwardIter
|
Chris@16
|
322 last_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
|
Chris@16
|
323 {
|
Chris@16
|
324 return detail::basic_last_max_element(first, last,
|
Chris@16
|
325 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
|
Chris@16
|
326 }
|
Chris@16
|
327
|
Chris@16
|
328
|
Chris@16
|
329 // Minmax_element variants -- comments removed
|
Chris@16
|
330
|
Chris@16
|
331 namespace detail {
|
Chris@16
|
332
|
Chris@16
|
333 template <typename ForwardIter, class BinaryPredicate>
|
Chris@16
|
334 std::pair<ForwardIter,ForwardIter>
|
Chris@16
|
335 basic_first_min_last_max_element(ForwardIter first, ForwardIter last,
|
Chris@16
|
336 BinaryPredicate comp)
|
Chris@16
|
337 {
|
Chris@16
|
338 if (first == last)
|
Chris@16
|
339 return std::make_pair(last,last);
|
Chris@16
|
340
|
Chris@16
|
341 ForwardIter min_result = first;
|
Chris@16
|
342 ForwardIter max_result = first;
|
Chris@16
|
343
|
Chris@16
|
344 ForwardIter second = ++first;
|
Chris@16
|
345 if (second == last)
|
Chris@16
|
346 return std::make_pair(min_result, max_result);
|
Chris@16
|
347
|
Chris@16
|
348 if (comp(second, min_result))
|
Chris@16
|
349 min_result = second;
|
Chris@16
|
350 else
|
Chris@16
|
351 max_result = second;
|
Chris@16
|
352
|
Chris@16
|
353 first = ++second; if (first != last) ++second;
|
Chris@16
|
354 while (second != last) {
|
Chris@16
|
355 if (!comp(second, first)) {
|
Chris@16
|
356 if (comp(first, min_result))
|
Chris@16
|
357 min_result = first;
|
Chris@16
|
358 if (!comp(second, max_result))
|
Chris@16
|
359 max_result = second;
|
Chris@16
|
360 } else {
|
Chris@16
|
361 if (comp(second, min_result))
|
Chris@16
|
362 min_result = second;
|
Chris@16
|
363 if (!comp(first, max_result))
|
Chris@16
|
364 max_result = first;
|
Chris@16
|
365 }
|
Chris@16
|
366 first = ++second; if (first != last) ++second;
|
Chris@16
|
367 }
|
Chris@16
|
368
|
Chris@16
|
369 if (first != last) {
|
Chris@16
|
370 if (comp(first, min_result))
|
Chris@16
|
371 min_result = first;
|
Chris@16
|
372 else if (!comp(first, max_result))
|
Chris@16
|
373 max_result = first;
|
Chris@16
|
374 }
|
Chris@16
|
375
|
Chris@16
|
376 return std::make_pair(min_result, max_result);
|
Chris@16
|
377 }
|
Chris@16
|
378
|
Chris@16
|
379 template <typename ForwardIter, class BinaryPredicate>
|
Chris@16
|
380 std::pair<ForwardIter,ForwardIter>
|
Chris@16
|
381 basic_last_min_first_max_element(ForwardIter first, ForwardIter last,
|
Chris@16
|
382 BinaryPredicate comp)
|
Chris@16
|
383 {
|
Chris@16
|
384 if (first == last) return std::make_pair(last,last);
|
Chris@16
|
385
|
Chris@16
|
386 ForwardIter min_result = first;
|
Chris@16
|
387 ForwardIter max_result = first;
|
Chris@16
|
388
|
Chris@16
|
389 ForwardIter second = ++first;
|
Chris@16
|
390 if (second == last)
|
Chris@16
|
391 return std::make_pair(min_result, max_result);
|
Chris@16
|
392
|
Chris@16
|
393 if (comp(max_result, second))
|
Chris@16
|
394 max_result = second;
|
Chris@16
|
395 else
|
Chris@16
|
396 min_result = second;
|
Chris@16
|
397
|
Chris@16
|
398 first = ++second; if (first != last) ++second;
|
Chris@16
|
399 while (second != last) {
|
Chris@16
|
400 if (comp(first, second)) {
|
Chris@16
|
401 if (!comp(min_result, first))
|
Chris@16
|
402 min_result = first;
|
Chris@16
|
403 if (comp(max_result, second))
|
Chris@16
|
404 max_result = second;
|
Chris@16
|
405 } else {
|
Chris@16
|
406 if (!comp(min_result, second))
|
Chris@16
|
407 min_result = second;
|
Chris@16
|
408 if (comp(max_result, first))
|
Chris@16
|
409 max_result = first;
|
Chris@16
|
410 }
|
Chris@16
|
411 first = ++second; if (first != last) ++second;
|
Chris@16
|
412 }
|
Chris@16
|
413
|
Chris@16
|
414 if (first != last) {
|
Chris@16
|
415 if (!comp(min_result, first))
|
Chris@16
|
416 min_result = first;
|
Chris@16
|
417 else if (comp(max_result, first))
|
Chris@16
|
418 max_result = first;
|
Chris@16
|
419 }
|
Chris@16
|
420
|
Chris@16
|
421 return std::make_pair(min_result, max_result);
|
Chris@16
|
422 }
|
Chris@16
|
423
|
Chris@16
|
424 template <typename ForwardIter, class BinaryPredicate>
|
Chris@16
|
425 std::pair<ForwardIter,ForwardIter>
|
Chris@16
|
426 basic_last_min_last_max_element(ForwardIter first, ForwardIter last,
|
Chris@16
|
427 BinaryPredicate comp)
|
Chris@16
|
428 {
|
Chris@16
|
429 if (first == last) return std::make_pair(last,last);
|
Chris@16
|
430
|
Chris@16
|
431 ForwardIter min_result = first;
|
Chris@16
|
432 ForwardIter max_result = first;
|
Chris@16
|
433
|
Chris@16
|
434 ForwardIter second = first; ++second;
|
Chris@16
|
435 if (second == last)
|
Chris@16
|
436 return std::make_pair(min_result,max_result);
|
Chris@16
|
437
|
Chris@16
|
438 ForwardIter potential_max_result = last;
|
Chris@16
|
439 if (comp(first, second))
|
Chris@16
|
440 max_result = second;
|
Chris@16
|
441 else {
|
Chris@16
|
442 min_result = second;
|
Chris@16
|
443 potential_max_result = second;
|
Chris@16
|
444 }
|
Chris@16
|
445
|
Chris@16
|
446 first = ++second; if (first != last) ++second;
|
Chris@16
|
447 while (second != last) {
|
Chris@16
|
448 if (comp(first, second)) {
|
Chris@16
|
449 if (!comp(min_result, first))
|
Chris@16
|
450 min_result = first;
|
Chris@16
|
451 if (!comp(second, max_result)) {
|
Chris@16
|
452 max_result = second;
|
Chris@16
|
453 potential_max_result = last;
|
Chris@16
|
454 }
|
Chris@16
|
455 } else {
|
Chris@16
|
456 if (!comp(min_result, second))
|
Chris@16
|
457 min_result = second;
|
Chris@16
|
458 if (!comp(first, max_result)) {
|
Chris@16
|
459 max_result = first;
|
Chris@16
|
460 potential_max_result = second;
|
Chris@16
|
461 }
|
Chris@16
|
462 }
|
Chris@16
|
463 first = ++second;
|
Chris@16
|
464 if (first != last) ++second;
|
Chris@16
|
465 }
|
Chris@16
|
466
|
Chris@16
|
467 if (first != last) {
|
Chris@16
|
468 if (!comp(min_result, first))
|
Chris@16
|
469 min_result = first;
|
Chris@16
|
470 if (!comp(first, max_result)) {
|
Chris@16
|
471 max_result = first;
|
Chris@16
|
472 potential_max_result = last;
|
Chris@16
|
473 }
|
Chris@16
|
474 }
|
Chris@16
|
475
|
Chris@16
|
476 if (potential_max_result != last
|
Chris@16
|
477 && !comp(potential_max_result, max_result))
|
Chris@16
|
478 max_result = potential_max_result;
|
Chris@16
|
479
|
Chris@16
|
480 return std::make_pair(min_result,max_result);
|
Chris@16
|
481 }
|
Chris@16
|
482
|
Chris@16
|
483 } // namespace detail
|
Chris@16
|
484
|
Chris@16
|
485 template <typename ForwardIter>
|
Chris@16
|
486 inline std::pair<ForwardIter,ForwardIter>
|
Chris@16
|
487 first_min_first_max_element(ForwardIter first, ForwardIter last)
|
Chris@16
|
488 {
|
Chris@16
|
489 return minmax_element(first, last);
|
Chris@16
|
490 }
|
Chris@16
|
491
|
Chris@16
|
492 template <typename ForwardIter, class BinaryPredicate>
|
Chris@16
|
493 inline std::pair<ForwardIter,ForwardIter>
|
Chris@16
|
494 first_min_first_max_element(ForwardIter first, ForwardIter last,
|
Chris@16
|
495 BinaryPredicate comp)
|
Chris@16
|
496 {
|
Chris@16
|
497 return minmax_element(first, last, comp);
|
Chris@16
|
498 }
|
Chris@16
|
499
|
Chris@16
|
500 template <typename ForwardIter>
|
Chris@16
|
501 std::pair<ForwardIter,ForwardIter>
|
Chris@16
|
502 first_min_last_max_element(ForwardIter first, ForwardIter last)
|
Chris@16
|
503 {
|
Chris@16
|
504 return detail::basic_first_min_last_max_element(first, last,
|
Chris@16
|
505 detail::less_over_iter<ForwardIter>() );
|
Chris@16
|
506 }
|
Chris@16
|
507
|
Chris@16
|
508 template <typename ForwardIter, class BinaryPredicate>
|
Chris@16
|
509 inline std::pair<ForwardIter,ForwardIter>
|
Chris@16
|
510 first_min_last_max_element(ForwardIter first, ForwardIter last,
|
Chris@16
|
511 BinaryPredicate comp)
|
Chris@16
|
512 {
|
Chris@16
|
513 return detail::basic_first_min_last_max_element(first, last,
|
Chris@16
|
514 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
|
Chris@16
|
515 }
|
Chris@16
|
516
|
Chris@16
|
517 template <typename ForwardIter>
|
Chris@16
|
518 std::pair<ForwardIter,ForwardIter>
|
Chris@16
|
519 last_min_first_max_element(ForwardIter first, ForwardIter last)
|
Chris@16
|
520 {
|
Chris@16
|
521 return detail::basic_last_min_first_max_element(first, last,
|
Chris@16
|
522 detail::less_over_iter<ForwardIter>() );
|
Chris@16
|
523 }
|
Chris@16
|
524
|
Chris@16
|
525 template <typename ForwardIter, class BinaryPredicate>
|
Chris@16
|
526 inline std::pair<ForwardIter,ForwardIter>
|
Chris@16
|
527 last_min_first_max_element(ForwardIter first, ForwardIter last,
|
Chris@16
|
528 BinaryPredicate comp)
|
Chris@16
|
529 {
|
Chris@16
|
530 return detail::basic_last_min_first_max_element(first, last,
|
Chris@16
|
531 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
|
Chris@16
|
532 }
|
Chris@16
|
533
|
Chris@16
|
534 template <typename ForwardIter>
|
Chris@16
|
535 std::pair<ForwardIter,ForwardIter>
|
Chris@16
|
536 last_min_last_max_element(ForwardIter first, ForwardIter last)
|
Chris@16
|
537 {
|
Chris@16
|
538 return detail::basic_last_min_last_max_element(first, last,
|
Chris@16
|
539 detail::less_over_iter<ForwardIter>() );
|
Chris@16
|
540 }
|
Chris@16
|
541
|
Chris@16
|
542 template <typename ForwardIter, class BinaryPredicate>
|
Chris@16
|
543 inline std::pair<ForwardIter,ForwardIter>
|
Chris@16
|
544 last_min_last_max_element(ForwardIter first, ForwardIter last,
|
Chris@16
|
545 BinaryPredicate comp)
|
Chris@16
|
546 {
|
Chris@16
|
547 return detail::basic_last_min_last_max_element(first, last,
|
Chris@16
|
548 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
|
Chris@16
|
549 }
|
Chris@16
|
550
|
Chris@16
|
551 } // namespace boost
|
Chris@16
|
552
|
Chris@16
|
553 #endif // BOOST_ALGORITHM_MINMAX_ELEMENT_HPP
|