projects / gcc.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
stl_algo.h (search(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardI...
[gcc.git] / libstdc++-v3 / include / bits / stl_algo.h
1 // Algorithm implementation -*- C++ -*-
2
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 2, or (at your option)
10 // any later version.
11
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16
17 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
20 // USA.
21
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
30
31 /*
32 *
33 * Copyright (c) 1994
34 * Hewlett-Packard Company
35 *
36 * Permission to use, copy, modify, distribute and sell this software
37 * and its documentation for any purpose is hereby granted without fee,
38 * provided that the above copyright notice appear in all copies and
39 * that both that copyright notice and this permission notice appear
40 * in supporting documentation. Hewlett-Packard Company makes no
41 * representations about the suitability of this software for any
42 * purpose. It is provided "as is" without express or implied warranty.
43 *
44 *
45 * Copyright (c) 1996
46 * Silicon Graphics Computer Systems, Inc.
47 *
48 * Permission to use, copy, modify, distribute and sell this software
49 * and its documentation for any purpose is hereby granted without fee,
50 * provided that the above copyright notice appear in all copies and
51 * that both that copyright notice and this permission notice appear
52 * in supporting documentation. Silicon Graphics makes no
53 * representations about the suitability of this software for any
54 * purpose. It is provided "as is" without express or implied warranty.
55 */
56
57 /** @file stl_algo.h
58 * This is an internal header file, included by other library headers.
59 * You should not attempt to use it directly.
60 */
61
62 #ifndef _STL_ALGO_H
63 #define _STL_ALGO_H 1
64
65 #include <bits/stl_heap.h>
66 #include <bits/stl_tempbuf.h> // for _Temporary_buffer
67 #include <cstdlib> // for rand
68 #include <debug/debug.h>
69
70 // See concept_check.h for the __glibcxx_*_requires macros.
71
72 _GLIBCXX_BEGIN_NAMESPACE(std)
73
74 /**
75 * @brief Find the median of three values.
76 * @param a A value.
77 * @param b A value.
78 * @param c A value.
79 * @return One of @p a, @p b or @p c.
80 *
81 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
82 * then the value returned will be @c m.
83 * This is an SGI extension.
84 * @ingroup SGIextensions
85 */
86 template<typename _Tp>
87 inline const _Tp&
88 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
89 {
90 // concept requirements
91 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
92 if (__a < __b)
93 if (__b < __c)
94 return __b;
95 else if (__a < __c)
96 return __c;
97 else
98 return __a;
99 else if (__a < __c)
100 return __a;
101 else if (__b < __c)
102 return __c;
103 else
104 return __b;
105 }
106
107 /**
108 * @brief Find the median of three values using a predicate for comparison.
109 * @param a A value.
110 * @param b A value.
111 * @param c A value.
112 * @param comp A binary predicate.
113 * @return One of @p a, @p b or @p c.
114 *
115 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
116 * and @p comp(m,n) are both true then the value returned will be @c m.
117 * This is an SGI extension.
118 * @ingroup SGIextensions
119 */
120 template<typename _Tp, typename _Compare>
121 inline const _Tp&
122 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
123 {
124 // concept requirements
125 __glibcxx_function_requires(_BinaryFunctionConcept<_Compare,bool,_Tp,_Tp>)
126 if (__comp(__a, __b))
127 if (__comp(__b, __c))
128 return __b;
129 else if (__comp(__a, __c))
130 return __c;
131 else
132 return __a;
133 else if (__comp(__a, __c))
134 return __a;
135 else if (__comp(__b, __c))
136 return __c;
137 else
138 return __b;
139 }
140
141 /**
142 * @brief Apply a function to every element of a sequence.
143 * @param first An input iterator.
144 * @param last An input iterator.
145 * @param f A unary function object.
146 * @return @p f.
147 *
148 * Applies the function object @p f to each element in the range
149 * @p [first,last). @p f must not modify the order of the sequence.
150 * If @p f has a return value it is ignored.
151 */
152 template<typename _InputIterator, typename _Function>
153 _Function
154 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
155 {
156 // concept requirements
157 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
158 __glibcxx_requires_valid_range(__first, __last);
159 for (; __first != __last; ++__first)
160 __f(*__first);
161 return __f;
162 }
163
164 /**
165 * @if maint
166 * This is an overload used by find() for the Input Iterator case.
167 * @endif
168 */
169 template<typename _InputIterator, typename _Tp>
170 inline _InputIterator
171 __find(_InputIterator __first, _InputIterator __last,
172 const _Tp& __val, input_iterator_tag)
173 {
174 while (__first != __last && !(*__first == __val))
175 ++__first;
176 return __first;
177 }
178
179 /**
180 * @if maint
181 * This is an overload used by find_if() for the Input Iterator case.
182 * @endif
183 */
184 template<typename _InputIterator, typename _Predicate>
185 inline _InputIterator
186 __find_if(_InputIterator __first, _InputIterator __last,
187 _Predicate __pred, input_iterator_tag)
188 {
189 while (__first != __last && !bool(__pred(*__first)))
190 ++__first;
191 return __first;
192 }
193
194 /**
195 * @if maint
196 * This is an overload used by find() for the RAI case.
197 * @endif
198 */
199 template<typename _RandomAccessIterator, typename _Tp>
200 _RandomAccessIterator
201 __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
202 const _Tp& __val, random_access_iterator_tag)
203 {
204 typename iterator_traits<_RandomAccessIterator>::difference_type
205 __trip_count = (__last - __first) >> 2;
206
207 for (; __trip_count > 0; --__trip_count)
208 {
209 if (*__first == __val)
210 return __first;
211 ++__first;
212
213 if (*__first == __val)
214 return __first;
215 ++__first;
216
217 if (*__first == __val)
218 return __first;
219 ++__first;
220
221 if (*__first == __val)
222 return __first;
223 ++__first;
224 }
225
226 switch (__last - __first)
227 {
228 case 3:
229 if (*__first == __val)
230 return __first;
231 ++__first;
232 case 2:
233 if (*__first == __val)
234 return __first;
235 ++__first;
236 case 1:
237 if (*__first == __val)
238 return __first;
239 ++__first;
240 case 0:
241 default:
242 return __last;
243 }
244 }
245
246 /**
247 * @if maint
248 * This is an overload used by find_if() for the RAI case.
249 * @endif
250 */
251 template<typename _RandomAccessIterator, typename _Predicate>
252 _RandomAccessIterator
253 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
254 _Predicate __pred, random_access_iterator_tag)
255 {
256 typename iterator_traits<_RandomAccessIterator>::difference_type
257 __trip_count = (__last - __first) >> 2;
258
259 for (; __trip_count > 0; --__trip_count)
260 {
261 if (__pred(*__first))
262 return __first;
263 ++__first;
264
265 if (__pred(*__first))
266 return __first;
267 ++__first;
268
269 if (__pred(*__first))
270 return __first;
271 ++__first;
272
273 if (__pred(*__first))
274 return __first;
275 ++__first;
276 }
277
278 switch (__last - __first)
279 {
280 case 3:
281 if (__pred(*__first))
282 return __first;
283 ++__first;
284 case 2:
285 if (__pred(*__first))
286 return __first;
287 ++__first;
288 case 1:
289 if (__pred(*__first))
290 return __first;
291 ++__first;
292 case 0:
293 default:
294 return __last;
295 }
296 }
297
298 /**
299 * @brief Find the first occurrence of a value in a sequence.
300 * @param first An input iterator.
301 * @param last An input iterator.
302 * @param val The value to find.
303 * @return The first iterator @c i in the range @p [first,last)
304 * such that @c *i == @p val, or @p last if no such iterator exists.
305 */
306 template<typename _InputIterator, typename _Tp>
307 inline _InputIterator
308 find(_InputIterator __first, _InputIterator __last,
309 const _Tp& __val)
310 {
311 // concept requirements
312 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
313 __glibcxx_function_requires(_EqualOpConcept<
314 typename iterator_traits<_InputIterator>::value_type, _Tp>)
315 __glibcxx_requires_valid_range(__first, __last);
316 return std::__find(__first, __last, __val,
317 std::__iterator_category(__first));
318 }
319
320 /**
321 * @brief Find the first element in a sequence for which a predicate is true.
322 * @param first An input iterator.
323 * @param last An input iterator.
324 * @param pred A predicate.
325 * @return The first iterator @c i in the range @p [first,last)
326 * such that @p pred(*i) is true, or @p last if no such iterator exists.
327 */
328 template<typename _InputIterator, typename _Predicate>
329 inline _InputIterator
330 find_if(_InputIterator __first, _InputIterator __last,
331 _Predicate __pred)
332 {
333 // concept requirements
334 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
335 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
336 typename iterator_traits<_InputIterator>::value_type>)
337 __glibcxx_requires_valid_range(__first, __last);
338 return std::__find_if(__first, __last, __pred,
339 std::__iterator_category(__first));
340 }
341
342 /**
343 * @brief Find element from a set in a sequence.
344 * @param first1 Start of range to search.
345 * @param last1 End of range to search.
346 * @param first2 Start of match candidates.
347 * @param last2 End of match candidates.
348 * @return The first iterator @c i in the range
349 * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
350 * interator in [first2,last2), or @p last1 if no such iterator exists.
351 *
352 * Searches the range @p [first1,last1) for an element that is equal to
353 * some element in the range [first2,last2). If found, returns an iterator
354 * in the range [first1,last1), otherwise returns @p last1.
355 */
356 template<typename _InputIterator, typename _ForwardIterator>
357 _InputIterator
358 find_first_of(_InputIterator __first1, _InputIterator __last1,
359 _ForwardIterator __first2, _ForwardIterator __last2)
360 {
361 // concept requirements
362 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
363 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
364 __glibcxx_function_requires(_EqualOpConcept<
365 typename iterator_traits<_InputIterator>::value_type,
366 typename iterator_traits<_ForwardIterator>::value_type>)
367 __glibcxx_requires_valid_range(__first1, __last1);
368 __glibcxx_requires_valid_range(__first2, __last2);
369
370 for (; __first1 != __last1; ++__first1)
371 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
372 if (*__first1 == *__iter)
373 return __first1;
374 return __last1;
375 }
376
377 /**
378 * @brief Find element from a set in a sequence using a predicate.
379 * @param first1 Start of range to search.
380 * @param last1 End of range to search.
381 * @param first2 Start of match candidates.
382 * @param last2 End of match candidates.
383 * @param comp Predicate to use.
384 * @return The first iterator @c i in the range
385 * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
386 * interator in [first2,last2), or @p last1 if no such iterator exists.
387 *
388 * Searches the range @p [first1,last1) for an element that is equal to
389 * some element in the range [first2,last2). If found, returns an iterator in
390 * the range [first1,last1), otherwise returns @p last1.
391 */
392 template<typename _InputIterator, typename _ForwardIterator,
393 typename _BinaryPredicate>
394 _InputIterator
395 find_first_of(_InputIterator __first1, _InputIterator __last1,
396 _ForwardIterator __first2, _ForwardIterator __last2,
397 _BinaryPredicate __comp)
398 {
399 // concept requirements
400 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
401 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
402 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
403 typename iterator_traits<_InputIterator>::value_type,
404 typename iterator_traits<_ForwardIterator>::value_type>)
405 __glibcxx_requires_valid_range(__first1, __last1);
406 __glibcxx_requires_valid_range(__first2, __last2);
407
408 for (; __first1 != __last1; ++__first1)
409 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
410 if (__comp(*__first1, *__iter))
411 return __first1;
412 return __last1;
413 }
414
415 /**
416 * @brief Find two adjacent values in a sequence that are equal.
417 * @param first A forward iterator.
418 * @param last A forward iterator.
419 * @return The first iterator @c i such that @c i and @c i+1 are both
420 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
421 * or @p last if no such iterator exists.
422 */
423 template<typename _ForwardIterator>
424 _ForwardIterator
425 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
426 {
427 // concept requirements
428 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
429 __glibcxx_function_requires(_EqualityComparableConcept<
430 typename iterator_traits<_ForwardIterator>::value_type>)
431 __glibcxx_requires_valid_range(__first, __last);
432 if (__first == __last)
433 return __last;
434 _ForwardIterator __next = __first;
435 while(++__next != __last)
436 {
437 if (*__first == *__next)
438 return __first;
439 __first = __next;
440 }
441 return __last;
442 }
443
444 /**
445 * @brief Find two adjacent values in a sequence using a predicate.
446 * @param first A forward iterator.
447 * @param last A forward iterator.
448 * @param binary_pred A binary predicate.
449 * @return The first iterator @c i such that @c i and @c i+1 are both
450 * valid iterators in @p [first,last) and such that
451 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
452 * exists.
453 */
454 template<typename _ForwardIterator, typename _BinaryPredicate>
455 _ForwardIterator
456 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
457 _BinaryPredicate __binary_pred)
458 {
459 // concept requirements
460 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
461 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
462 typename iterator_traits<_ForwardIterator>::value_type,
463 typename iterator_traits<_ForwardIterator>::value_type>)
464 __glibcxx_requires_valid_range(__first, __last);
465 if (__first == __last)
466 return __last;
467 _ForwardIterator __next = __first;
468 while(++__next != __last)
469 {
470 if (__binary_pred(*__first, *__next))
471 return __first;
472 __first = __next;
473 }
474 return __last;
475 }
476
477 /**
478 * @brief Count the number of copies of a value in a sequence.
479 * @param first An input iterator.
480 * @param last An input iterator.
481 * @param value The value to be counted.
482 * @return The number of iterators @c i in the range @p [first,last)
483 * for which @c *i == @p value
484 */
485 template<typename _InputIterator, typename _Tp>
486 typename iterator_traits<_InputIterator>::difference_type
487 count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
488 {
489 // concept requirements
490 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
491 __glibcxx_function_requires(_EqualOpConcept<
492 typename iterator_traits<_InputIterator>::value_type, _Tp>)
493 __glibcxx_requires_valid_range(__first, __last);
494 typename iterator_traits<_InputIterator>::difference_type __n = 0;
495 for (; __first != __last; ++__first)
496 if (*__first == __value)
497 ++__n;
498 return __n;
499 }
500
501 /**
502 * @brief Count the elements of a sequence for which a predicate is true.
503 * @param first An input iterator.
504 * @param last An input iterator.
505 * @param pred A predicate.
506 * @return The number of iterators @c i in the range @p [first,last)
507 * for which @p pred(*i) is true.
508 */
509 template<typename _InputIterator, typename _Predicate>
510 typename iterator_traits<_InputIterator>::difference_type
511 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
512 {
513 // concept requirements
514 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
515 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
516 typename iterator_traits<_InputIterator>::value_type>)
517 __glibcxx_requires_valid_range(__first, __last);
518 typename iterator_traits<_InputIterator>::difference_type __n = 0;
519 for (; __first != __last; ++__first)
520 if (__pred(*__first))
521 ++__n;
522 return __n;
523 }
524
525 /**
526 * @brief Finds the places in ranges which don't match.
527 * @param first1 An input iterator.
528 * @param last1 An input iterator.
529 * @param first2 An input iterator.
530 * @return A pair of iterators pointing to the first mismatch.
531 *
532 * This compares the elements of two ranges using @c == and returns a pair
533 * of iterators. The first iterator points into the first range, the
534 * second iterator points into the second range, and the elements pointed
535 * to by the iterators are not equal.
536 */
537 template<typename _InputIterator1, typename _InputIterator2>
538 pair<_InputIterator1, _InputIterator2>
539 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
540 _InputIterator2 __first2)
541 {
542 // concept requirements
543 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
544 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
545 __glibcxx_function_requires(_EqualOpConcept<
546 typename iterator_traits<_InputIterator1>::value_type,
547 typename iterator_traits<_InputIterator2>::value_type>)
548 __glibcxx_requires_valid_range(__first1, __last1);
549
550 while (__first1 != __last1 && *__first1 == *__first2)
551 {
552 ++__first1;
553 ++__first2;
554 }
555 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
556 }
557
558 /**
559 * @brief Finds the places in ranges which don't match.
560 * @param first1 An input iterator.
561 * @param last1 An input iterator.
562 * @param first2 An input iterator.
563 * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink.
564 * @return A pair of iterators pointing to the first mismatch.
565 *
566 * This compares the elements of two ranges using the binary_pred
567 * parameter, and returns a pair
568 * of iterators. The first iterator points into the first range, the
569 * second iterator points into the second range, and the elements pointed
570 * to by the iterators are not equal.
571 */
572 template<typename _InputIterator1, typename _InputIterator2,
573 typename _BinaryPredicate>
574 pair<_InputIterator1, _InputIterator2>
575 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
576 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
577 {
578 // concept requirements
579 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
580 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
581 __glibcxx_requires_valid_range(__first1, __last1);
582
583 while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2)))
584 {
585 ++__first1;
586 ++__first2;
587 }
588 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
589 }
590
591 /**
592 * @brief Search a sequence for a matching sub-sequence.
593 * @param first1 A forward iterator.
594 * @param last1 A forward iterator.
595 * @param first2 A forward iterator.
596 * @param last2 A forward iterator.
597 * @return The first iterator @c i in the range
598 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
599 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
600 * such iterator exists.
601 *
602 * Searches the range @p [first1,last1) for a sub-sequence that compares
603 * equal value-by-value with the sequence given by @p [first2,last2) and
604 * returns an iterator to the first element of the sub-sequence, or
605 * @p last1 if the sub-sequence is not found.
606 *
607 * Because the sub-sequence must lie completely within the range
608 * @p [first1,last1) it must start at a position less than
609 * @p last1-(last2-first2) where @p last2-first2 is the length of the
610 * sub-sequence.
611 * This means that the returned iterator @c i will be in the range
612 * @p [first1,last1-(last2-first2))
613 */
614 template<typename _ForwardIterator1, typename _ForwardIterator2>
615 _ForwardIterator1
616 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
617 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
618 {
619 // concept requirements
620 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
621 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
622 __glibcxx_function_requires(_EqualOpConcept<
623 typename iterator_traits<_ForwardIterator1>::value_type,
624 typename iterator_traits<_ForwardIterator2>::value_type>)
625 __glibcxx_requires_valid_range(__first1, __last1);
626 __glibcxx_requires_valid_range(__first2, __last2);
627 // Test for empty ranges
628 if (__first1 == __last1 || __first2 == __last2)
629 return __first1;
630
631 // Test for a pattern of length 1.
632 _ForwardIterator2 __tmp(__first2);
633 ++__tmp;
634 if (__tmp == __last2)
635 return std::find(__first1, __last1, *__first2);
636
637 // General case.
638 _ForwardIterator2 __p1, __p;
639 __p1 = __first2; ++__p1;
640 _ForwardIterator1 __current = __first1;
641
642 for (;;)
643 {
644 __first1 = std::find(__first1, __last1, *__first2);
645 if (__first1 == __last1)
646 return __last1;
647
648 __p = __p1;
649 __current = __first1;
650 if (++__current == __last1)
651 return __last1;
652
653 while (*__current == *__p)
654 {
655 if (++__p == __last2)
656 return __first1;
657 if (++__current == __last1)
658 return __last1;
659 }
660 ++__first1;
661 }
662 return __first1;
663 }
664
665 /**
666 * @brief Search a sequence for a matching sub-sequence using a predicate.
667 * @param first1 A forward iterator.
668 * @param last1 A forward iterator.
669 * @param first2 A forward iterator.
670 * @param last2 A forward iterator.
671 * @param predicate A binary predicate.
672 * @return The first iterator @c i in the range
673 * @p [first1,last1-(last2-first2)) such that
674 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
675 * @p [0,last2-first2), or @p last1 if no such iterator exists.
676 *
677 * Searches the range @p [first1,last1) for a sub-sequence that compares
678 * equal value-by-value with the sequence given by @p [first2,last2),
679 * using @p predicate to determine equality, and returns an iterator
680 * to the first element of the sub-sequence, or @p last1 if no such
681 * iterator exists.
682 *
683 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
684 */
685 template<typename _ForwardIterator1, typename _ForwardIterator2,
686 typename _BinaryPredicate>
687 _ForwardIterator1
688 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
689 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
690 _BinaryPredicate __predicate)
691 {
692 // concept requirements
693 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
694 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
695 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
696 typename iterator_traits<_ForwardIterator1>::value_type,
697 typename iterator_traits<_ForwardIterator2>::value_type>)
698 __glibcxx_requires_valid_range(__first1, __last1);
699 __glibcxx_requires_valid_range(__first2, __last2);
700
701 // Test for empty ranges
702 if (__first1 == __last1 || __first2 == __last2)
703 return __first1;
704
705 // Test for a pattern of length 1.
706 _ForwardIterator2 __tmp(__first2);
707 ++__tmp;
708 if (__tmp == __last2)
709 {
710 while (__first1 != __last1
711 && !bool(__predicate(*__first1, *__first2)))
712 ++__first1;
713 return __first1;
714 }
715
716 // General case.
717 _ForwardIterator2 __p1, __p;
718 __p1 = __first2; ++__p1;
719 _ForwardIterator1 __current = __first1;
720
721 for (;;)
722 {
723 while (__first1 != __last1
724 && !bool(__predicate(*__first1, *__first2)))
725 ++__first1;
726 if (__first1 == __last1)
727 return __last1;
728
729 __p = __p1;
730 __current = __first1;
731 if (++__current == __last1)
732 return __last1;
733
734 while (__predicate(*__current, *__p))
735 {
736 if (++__p == __last2)
737 return __first1;
738 if (++__current == __last1)
739 return __last1;
740 }
741 ++__first1;
742 }
743 return __first1;
744 }
745
746 /**
747 * @if maint
748 * This is an uglified
749 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
750 * overloaded for forward iterators.
751 * @endif
752 */
753 template<typename _ForwardIterator, typename _Integer, typename _Tp>
754 _ForwardIterator
755 __search_n(_ForwardIterator __first, _ForwardIterator __last,
756 _Integer __count, const _Tp& __val,
757 std::forward_iterator_tag)
758 {
759 __first = std::find(__first, __last, __val);
760 while (__first != __last)
761 {
762 typename iterator_traits<_ForwardIterator>::difference_type
763 __n = __count;
764 _ForwardIterator __i = __first;
765 ++__i;
766 while (__i != __last && __n != 1 && *__i == __val)
767 {
768 ++__i;
769 --__n;
770 }
771 if (__n == 1)
772 return __first;
773 if (__i == __last)
774 return __last;
775 __first = std::find(++__i, __last, __val);
776 }
777 return __last;
778 }
779
780 /**
781 * @if maint
782 * This is an uglified
783 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
784 * overloaded for random access iterators.
785 * @endif
786 */
787 template<typename _RandomAccessIter, typename _Integer, typename _Tp>
788 _RandomAccessIter
789 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
790 _Integer __count, const _Tp& __val,
791 std::random_access_iterator_tag)
792 {
793
794 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
795 _DistanceType;
796
797 _DistanceType __tailSize = __last - __first;
798 const _DistanceType __pattSize = __count;
799
800 if (__tailSize < __pattSize)
801 return __last;
802
803 const _DistanceType __skipOffset = __pattSize - 1;
804 _RandomAccessIter __lookAhead = __first + __skipOffset;
805 __tailSize -= __pattSize;
806
807 while (1) // the main loop...
808 {
809 // __lookAhead here is always pointing to the last element of next
810 // possible match.
811 while (!(*__lookAhead == __val)) // the skip loop...
812 {
813 if (__tailSize < __pattSize)
814 return __last; // Failure
815 __lookAhead += __pattSize;
816 __tailSize -= __pattSize;
817 }
818 _DistanceType __remainder = __skipOffset;
819 for (_RandomAccessIter __backTrack = __lookAhead - 1;
820 *__backTrack == __val; --__backTrack)
821 {
822 if (--__remainder == 0)
823 return (__lookAhead - __skipOffset); // Success
824 }
825 if (__remainder > __tailSize)
826 return __last; // Failure
827 __lookAhead += __remainder;
828 __tailSize -= __remainder;
829 }
830 }
831
832 /**
833 * @brief Search a sequence for a number of consecutive values.
834 * @param first A forward iterator.
835 * @param last A forward iterator.
836 * @param count The number of consecutive values.
837 * @param val The value to find.
838 * @return The first iterator @c i in the range @p [first,last-count)
839 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
840 * or @p last if no such iterator exists.
841 *
842 * Searches the range @p [first,last) for @p count consecutive elements
843 * equal to @p val.
844 */
845 template<typename _ForwardIterator, typename _Integer, typename _Tp>
846 _ForwardIterator
847 search_n(_ForwardIterator __first, _ForwardIterator __last,
848 _Integer __count, const _Tp& __val)
849 {
850 // concept requirements
851 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
852 __glibcxx_function_requires(_EqualOpConcept<
853 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
854 __glibcxx_requires_valid_range(__first, __last);
855
856 if (__count <= 0)
857 return __first;
858 if (__count == 1)
859 return std::find(__first, __last, __val);
860 return std::__search_n(__first, __last, __count, __val,
861 std::__iterator_category(__first));
862 }
863
864 /**
865 * @if maint
866 * This is an uglified
867 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
868 * _BinaryPredicate)
869 * overloaded for forward iterators.
870 * @endif
871 */
872 template<typename _ForwardIterator, typename _Integer, typename _Tp,
873 typename _BinaryPredicate>
874 _ForwardIterator
875 __search_n(_ForwardIterator __first, _ForwardIterator __last,
876 _Integer __count, const _Tp& __val,
877 _BinaryPredicate __binary_pred, std::forward_iterator_tag)
878 {
879 while (__first != __last && !bool(__binary_pred(*__first, __val)))
880 ++__first;
881
882 while (__first != __last)
883 {
884 typename iterator_traits<_ForwardIterator>::difference_type
885 __n = __count;
886 _ForwardIterator __i = __first;
887 ++__i;
888 while (__i != __last && __n != 1 && bool(__binary_pred(*__i, __val)))
889 {
890 ++__i;
891 --__n;
892 }
893 if (__n == 1)
894 return __first;
895 if (__i == __last)
896 return __last;
897 __first = ++__i;
898 while (__first != __last
899 && !bool(__binary_pred(*__first, __val)))
900 ++__first;
901 }
902 return __last;
903 }
904
905 /**
906 * @if maint
907 * This is an uglified
908 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
909 * _BinaryPredicate)
910 * overloaded for random access iterators.
911 * @endif
912 */
913 template<typename _RandomAccessIter, typename _Integer, typename _Tp,
914 typename _BinaryPredicate>
915 _RandomAccessIter
916 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
917 _Integer __count, const _Tp& __val,
918 _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
919 {
920
921 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
922 _DistanceType;
923
924 _DistanceType __tailSize = __last - __first;
925 const _DistanceType __pattSize = __count;
926
927 if (__tailSize < __pattSize)
928 return __last;
929
930 const _DistanceType __skipOffset = __pattSize - 1;
931 _RandomAccessIter __lookAhead = __first + __skipOffset;
932 __tailSize -= __pattSize;
933
934 while (1) // the main loop...
935 {
936 // __lookAhead here is always pointing to the last element of next
937 // possible match.
938 while (!bool(__binary_pred(*__lookAhead, __val))) // the skip loop...
939 {
940 if (__tailSize < __pattSize)
941 return __last; // Failure
942 __lookAhead += __pattSize;
943 __tailSize -= __pattSize;
944 }
945 _DistanceType __remainder = __skipOffset;
946 for (_RandomAccessIter __backTrack = __lookAhead - 1;
947 __binary_pred(*__backTrack, __val); --__backTrack)
948 {
949 if (--__remainder == 0)
950 return (__lookAhead - __skipOffset); // Success
951 }
952 if (__remainder > __tailSize)
953 return __last; // Failure
954 __lookAhead += __remainder;
955 __tailSize -= __remainder;
956 }
957 }
958
959 /**
960 * @brief Search a sequence for a number of consecutive values using a
961 * predicate.
962 * @param first A forward iterator.
963 * @param last A forward iterator.
964 * @param count The number of consecutive values.
965 * @param val The value to find.
966 * @param binary_pred A binary predicate.
967 * @return The first iterator @c i in the range @p [first,last-count)
968 * such that @p binary_pred(*(i+N),val) is true for each @c N in the
969 * range @p [0,count), or @p last if no such iterator exists.
970 *
971 * Searches the range @p [first,last) for @p count consecutive elements
972 * for which the predicate returns true.
973 */
974 template<typename _ForwardIterator, typename _Integer, typename _Tp,
975 typename _BinaryPredicate>
976 _ForwardIterator
977 search_n(_ForwardIterator __first, _ForwardIterator __last,
978 _Integer __count, const _Tp& __val,
979 _BinaryPredicate __binary_pred)
980 {
981 // concept requirements
982 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
983 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
984 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
985 __glibcxx_requires_valid_range(__first, __last);
986
987 if (__count <= 0)
988 return __first;
989 if (__count == 1)
990 {
991 while (__first != __last && !bool(__binary_pred(*__first, __val)))
992 ++__first;
993 return __first;
994 }
995 return std::__search_n(__first, __last, __count, __val, __binary_pred,
996 std::__iterator_category(__first));
997 }
998
999 // find_end for forward iterators.
1000 template<typename _ForwardIterator1, typename _ForwardIterator2>
1001 _ForwardIterator1
1002 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1003 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1004 forward_iterator_tag, forward_iterator_tag)
1005 {
1006 if (__first2 == __last2)
1007 return __last1;
1008 else
1009 {
1010 _ForwardIterator1 __result = __last1;
1011 while (1)
1012 {
1013 _ForwardIterator1 __new_result
1014 = std::search(__first1, __last1, __first2, __last2);
1015 if (__new_result == __last1)
1016 return __result;
1017 else
1018 {
1019 __result = __new_result;
1020 __first1 = __new_result;
1021 ++__first1;
1022 }
1023 }
1024 }
1025 }
1026
1027 template<typename _ForwardIterator1, typename _ForwardIterator2,
1028 typename _BinaryPredicate>
1029 _ForwardIterator1
1030 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1031 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1032 forward_iterator_tag, forward_iterator_tag,
1033 _BinaryPredicate __comp)
1034 {
1035 if (__first2 == __last2)
1036 return __last1;
1037 else
1038 {
1039 _ForwardIterator1 __result = __last1;
1040 while (1)
1041 {
1042 _ForwardIterator1 __new_result
1043 = std::search(__first1, __last1, __first2, __last2, __comp);
1044 if (__new_result == __last1)
1045 return __result;
1046 else
1047 {
1048 __result = __new_result;
1049 __first1 = __new_result;
1050 ++__first1;
1051 }
1052 }
1053 }
1054 }
1055
1056 // find_end for bidirectional iterators (much faster).
1057 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
1058 _BidirectionalIterator1
1059 __find_end(_BidirectionalIterator1 __first1,
1060 _BidirectionalIterator1 __last1,
1061 _BidirectionalIterator2 __first2,
1062 _BidirectionalIterator2 __last2,
1063 bidirectional_iterator_tag, bidirectional_iterator_tag)
1064 {
1065 // concept requirements
1066 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1067 _BidirectionalIterator1>)
1068 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1069 _BidirectionalIterator2>)
1070
1071 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
1072 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
1073
1074 _RevIterator1 __rlast1(__first1);
1075 _RevIterator2 __rlast2(__first2);
1076 _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
1077 _RevIterator2(__last2), __rlast2);
1078
1079 if (__rresult == __rlast1)
1080 return __last1;
1081 else
1082 {
1083 _BidirectionalIterator1 __result = __rresult.base();
1084 std::advance(__result, -std::distance(__first2, __last2));
1085 return __result;
1086 }
1087 }
1088
1089 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
1090 typename _BinaryPredicate>
1091 _BidirectionalIterator1
1092 __find_end(_BidirectionalIterator1 __first1,
1093 _BidirectionalIterator1 __last1,
1094 _BidirectionalIterator2 __first2,
1095 _BidirectionalIterator2 __last2,
1096 bidirectional_iterator_tag, bidirectional_iterator_tag,
1097 _BinaryPredicate __comp)
1098 {
1099 // concept requirements
1100 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1101 _BidirectionalIterator1>)
1102 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1103 _BidirectionalIterator2>)
1104
1105 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
1106 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
1107
1108 _RevIterator1 __rlast1(__first1);
1109 _RevIterator2 __rlast2(__first2);
1110 _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
1111 _RevIterator2(__last2), __rlast2,
1112 __comp);
1113
1114 if (__rresult == __rlast1)
1115 return __last1;
1116 else
1117 {
1118 _BidirectionalIterator1 __result = __rresult.base();
1119 std::advance(__result, -std::distance(__first2, __last2));
1120 return __result;
1121 }
1122 }
1123
1124 /**
1125 * @brief Find last matching subsequence in a sequence.
1126 * @param first1 Start of range to search.
1127 * @param last1 End of range to search.
1128 * @param first2 Start of sequence to match.
1129 * @param last2 End of sequence to match.
1130 * @return The last iterator @c i in the range
1131 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
1132 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
1133 * such iterator exists.
1134 *
1135 * Searches the range @p [first1,last1) for a sub-sequence that compares
1136 * equal value-by-value with the sequence given by @p [first2,last2) and
1137 * returns an iterator to the first element of the sub-sequence, or
1138 * @p last1 if the sub-sequence is not found. The sub-sequence will be the
1139 * last such subsequence contained in [first,last1).
1140 *
1141 * Because the sub-sequence must lie completely within the range
1142 * @p [first1,last1) it must start at a position less than
1143 * @p last1-(last2-first2) where @p last2-first2 is the length of the
1144 * sub-sequence.
1145 * This means that the returned iterator @c i will be in the range
1146 * @p [first1,last1-(last2-first2))
1147 */
1148 template<typename _ForwardIterator1, typename _ForwardIterator2>
1149 inline _ForwardIterator1
1150 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1151 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1152 {
1153 // concept requirements
1154 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
1155 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
1156 __glibcxx_function_requires(_EqualOpConcept<
1157 typename iterator_traits<_ForwardIterator1>::value_type,
1158 typename iterator_traits<_ForwardIterator2>::value_type>)
1159 __glibcxx_requires_valid_range(__first1, __last1);
1160 __glibcxx_requires_valid_range(__first2, __last2);
1161
1162 return std::__find_end(__first1, __last1, __first2, __last2,
1163 std::__iterator_category(__first1),
1164 std::__iterator_category(__first2));
1165 }
1166
1167 /**
1168 * @brief Find last matching subsequence in a sequence using a predicate.
1169 * @param first1 Start of range to search.
1170 * @param last1 End of range to search.
1171 * @param first2 Start of sequence to match.
1172 * @param last2 End of sequence to match.
1173 * @param comp The predicate to use.
1174 * @return The last iterator @c i in the range
1175 * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
1176 * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
1177 * @p last1 if no such iterator exists.
1178 *
1179 * Searches the range @p [first1,last1) for a sub-sequence that compares
1180 * equal value-by-value with the sequence given by @p [first2,last2) using
1181 * comp as a predicate and returns an iterator to the first element of the
1182 * sub-sequence, or @p last1 if the sub-sequence is not found. The
1183 * sub-sequence will be the last such subsequence contained in
1184 * [first,last1).
1185 *
1186 * Because the sub-sequence must lie completely within the range
1187 * @p [first1,last1) it must start at a position less than
1188 * @p last1-(last2-first2) where @p last2-first2 is the length of the
1189 * sub-sequence.
1190 * This means that the returned iterator @c i will be in the range
1191 * @p [first1,last1-(last2-first2))
1192 */
1193 template<typename _ForwardIterator1, typename _ForwardIterator2,
1194 typename _BinaryPredicate>
1195 inline _ForwardIterator1
1196 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1197 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
1198 _BinaryPredicate __comp)
1199 {
1200 // concept requirements
1201 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
1202 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
1203 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1204 typename iterator_traits<_ForwardIterator1>::value_type,
1205 typename iterator_traits<_ForwardIterator2>::value_type>)
1206 __glibcxx_requires_valid_range(__first1, __last1);
1207 __glibcxx_requires_valid_range(__first2, __last2);
1208
1209 return std::__find_end(__first1, __last1, __first2, __last2,
1210 std::__iterator_category(__first1),
1211 std::__iterator_category(__first2),
1212 __comp);
1213 }
1214
1215 /**
1216 * @brief Perform an operation on a sequence.
1217 * @param first An input iterator.
1218 * @param last An input iterator.
1219 * @param result An output iterator.
1220 * @param unary_op A unary operator.
1221 * @return An output iterator equal to @p result+(last-first).
1222 *
1223 * Applies the operator to each element in the input range and assigns
1224 * the results to successive elements of the output sequence.
1225 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
1226 * range @p [0,last-first).
1227 *
1228 * @p unary_op must not alter its argument.
1229 */
1230 template<typename _InputIterator, typename _OutputIterator,
1231 typename _UnaryOperation>
1232 _OutputIterator
1233 transform(_InputIterator __first, _InputIterator __last,
1234 _OutputIterator __result, _UnaryOperation __unary_op)
1235 {
1236 // concept requirements
1237 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1238 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1239 // "the type returned by a _UnaryOperation"
1240 __typeof__(__unary_op(*__first))>)
1241 __glibcxx_requires_valid_range(__first, __last);
1242
1243 for (; __first != __last; ++__first, ++__result)
1244 *__result = __unary_op(*__first);
1245 return __result;
1246 }
1247
1248 /**
1249 * @brief Perform an operation on corresponding elements of two sequences.
1250 * @param first1 An input iterator.
1251 * @param last1 An input iterator.
1252 * @param first2 An input iterator.
1253 * @param result An output iterator.
1254 * @param binary_op A binary operator.
1255 * @return An output iterator equal to @p result+(last-first).
1256 *
1257 * Applies the operator to the corresponding elements in the two
1258 * input ranges and assigns the results to successive elements of the
1259 * output sequence.
1260 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
1261 * @c N in the range @p [0,last1-first1).
1262 *
1263 * @p binary_op must not alter either of its arguments.
1264 */
1265 template<typename _InputIterator1, typename _InputIterator2,
1266 typename _OutputIterator, typename _BinaryOperation>
1267 _OutputIterator
1268 transform(_InputIterator1 __first1, _InputIterator1 __last1,
1269 _InputIterator2 __first2, _OutputIterator __result,
1270 _BinaryOperation __binary_op)
1271 {
1272 // concept requirements
1273 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1274 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1275 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1276 // "the type returned by a _BinaryOperation"
1277 __typeof__(__binary_op(*__first1,*__first2))>)
1278 __glibcxx_requires_valid_range(__first1, __last1);
1279
1280 for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
1281 *__result = __binary_op(*__first1, *__first2);
1282 return __result;
1283 }
1284
1285 /**
1286 * @brief Replace each occurrence of one value in a sequence with another
1287 * value.
1288 * @param first A forward iterator.
1289 * @param last A forward iterator.
1290 * @param old_value The value to be replaced.
1291 * @param new_value The replacement value.
1292 * @return replace() returns no value.
1293 *
1294 * For each iterator @c i in the range @p [first,last) if @c *i ==
1295 * @p old_value then the assignment @c *i = @p new_value is performed.
1296 */
1297 template<typename _ForwardIterator, typename _Tp>
1298 void
1299 replace(_ForwardIterator __first, _ForwardIterator __last,
1300 const _Tp& __old_value, const _Tp& __new_value)
1301 {
1302 // concept requirements
1303 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1304 _ForwardIterator>)
1305 __glibcxx_function_requires(_EqualOpConcept<
1306 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1307 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
1308 typename iterator_traits<_ForwardIterator>::value_type>)
1309 __glibcxx_requires_valid_range(__first, __last);
1310
1311 for (; __first != __last; ++__first)
1312 if (*__first == __old_value)
1313 *__first = __new_value;
1314 }
1315
1316 /**
1317 * @brief Replace each value in a sequence for which a predicate returns
1318 * true with another value.
1319 * @param first A forward iterator.
1320 * @param last A forward iterator.
1321 * @param pred A predicate.
1322 * @param new_value The replacement value.
1323 * @return replace_if() returns no value.
1324 *
1325 * For each iterator @c i in the range @p [first,last) if @p pred(*i)
1326 * is true then the assignment @c *i = @p new_value is performed.
1327 */
1328 template<typename _ForwardIterator, typename _Predicate, typename _Tp>
1329 void
1330 replace_if(_ForwardIterator __first, _ForwardIterator __last,
1331 _Predicate __pred, const _Tp& __new_value)
1332 {
1333 // concept requirements
1334 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1335 _ForwardIterator>)
1336 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
1337 typename iterator_traits<_ForwardIterator>::value_type>)
1338 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1339 typename iterator_traits<_ForwardIterator>::value_type>)
1340 __glibcxx_requires_valid_range(__first, __last);
1341
1342 for (; __first != __last; ++__first)
1343 if (__pred(*__first))
1344 *__first = __new_value;
1345 }
1346
1347 /**
1348 * @brief Copy a sequence, replacing each element of one value with another
1349 * value.
1350 * @param first An input iterator.
1351 * @param last An input iterator.
1352 * @param result An output iterator.
1353 * @param old_value The value to be replaced.
1354 * @param new_value The replacement value.
1355 * @return The end of the output sequence, @p result+(last-first).
1356 *
1357 * Copies each element in the input range @p [first,last) to the
1358 * output range @p [result,result+(last-first)) replacing elements
1359 * equal to @p old_value with @p new_value.
1360 */
1361 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
1362 _OutputIterator
1363 replace_copy(_InputIterator __first, _InputIterator __last,
1364 _OutputIterator __result,
1365 const _Tp& __old_value, const _Tp& __new_value)
1366 {
1367 // concept requirements
1368 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1369 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1370 typename iterator_traits<_InputIterator>::value_type>)
1371 __glibcxx_function_requires(_EqualOpConcept<
1372 typename iterator_traits<_InputIterator>::value_type, _Tp>)
1373 __glibcxx_requires_valid_range(__first, __last);
1374
1375 for (; __first != __last; ++__first, ++__result)
1376 if (*__first == __old_value)
1377 *__result = __new_value;
1378 else
1379 *__result = *__first;
1380 return __result;
1381 }
1382
1383 /**
1384 * @brief Copy a sequence, replacing each value for which a predicate
1385 * returns true with another value.
1386 * @param first An input iterator.
1387 * @param last An input iterator.
1388 * @param result An output iterator.
1389 * @param pred A predicate.
1390 * @param new_value The replacement value.
1391 * @return The end of the output sequence, @p result+(last-first).
1392 *
1393 * Copies each element in the range @p [first,last) to the range
1394 * @p [result,result+(last-first)) replacing elements for which
1395 * @p pred returns true with @p new_value.
1396 */
1397 template<typename _InputIterator, typename _OutputIterator,
1398 typename _Predicate, typename _Tp>
1399 _OutputIterator
1400 replace_copy_if(_InputIterator __first, _InputIterator __last,
1401 _OutputIterator __result,
1402 _Predicate __pred, const _Tp& __new_value)
1403 {
1404 // concept requirements
1405 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1406 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1407 typename iterator_traits<_InputIterator>::value_type>)
1408 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1409 typename iterator_traits<_InputIterator>::value_type>)
1410 __glibcxx_requires_valid_range(__first, __last);
1411
1412 for (; __first != __last; ++__first, ++__result)
1413 if (__pred(*__first))
1414 *__result = __new_value;
1415 else
1416 *__result = *__first;
1417 return __result;
1418 }
1419
1420 /**
1421 * @brief Assign the result of a function object to each value in a
1422 * sequence.
1423 * @param first A forward iterator.
1424 * @param last A forward iterator.
1425 * @param gen A function object taking no arguments.
1426 * @return generate() returns no value.
1427 *
1428 * Performs the assignment @c *i = @p gen() for each @c i in the range
1429 * @p [first,last).
1430 */
1431 template<typename _ForwardIterator, typename _Generator>
1432 void
1433 generate(_ForwardIterator __first, _ForwardIterator __last,
1434 _Generator __gen)
1435 {
1436 // concept requirements
1437 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1438 __glibcxx_function_requires(_GeneratorConcept<_Generator,
1439 typename iterator_traits<_ForwardIterator>::value_type>)
1440 __glibcxx_requires_valid_range(__first, __last);
1441
1442 for (; __first != __last; ++__first)
1443 *__first = __gen();
1444 }
1445
1446 /**
1447 * @brief Assign the result of a function object to each value in a
1448 * sequence.
1449 * @param first A forward iterator.
1450 * @param n The length of the sequence.
1451 * @param gen A function object taking no arguments.
1452 * @return The end of the sequence, @p first+n
1453 *
1454 * Performs the assignment @c *i = @p gen() for each @c i in the range
1455 * @p [first,first+n).
1456 */
1457 template<typename _OutputIterator, typename _Size, typename _Generator>
1458 _OutputIterator
1459 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
1460 {
1461 // concept requirements
1462 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1463 // "the type returned by a _Generator"
1464 __typeof__(__gen())>)
1465
1466 for (; __n > 0; --__n, ++__first)
1467 *__first = __gen();
1468 return __first;
1469 }
1470
1471 /**
1472 * @brief Copy a sequence, removing elements of a given value.
1473 * @param first An input iterator.
1474 * @param last An input iterator.
1475 * @param result An output iterator.
1476 * @param value The value to be removed.
1477 * @return An iterator designating the end of the resulting sequence.
1478 *
1479 * Copies each element in the range @p [first,last) not equal to @p value
1480 * to the range beginning at @p result.
1481 * remove_copy() is stable, so the relative order of elements that are
1482 * copied is unchanged.
1483 */
1484 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
1485 _OutputIterator
1486 remove_copy(_InputIterator __first, _InputIterator __last,
1487 _OutputIterator __result, const _Tp& __value)
1488 {
1489 // concept requirements
1490 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1491 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1492 typename iterator_traits<_InputIterator>::value_type>)
1493 __glibcxx_function_requires(_EqualOpConcept<
1494 typename iterator_traits<_InputIterator>::value_type, _Tp>)
1495 __glibcxx_requires_valid_range(__first, __last);
1496
1497 for (; __first != __last; ++__first)
1498 if (!(*__first == __value))
1499 {
1500 *__result = *__first;
1501 ++__result;
1502 }
1503 return __result;
1504 }
1505
1506 /**
1507 * @brief Copy a sequence, removing elements for which a predicate is true.
1508 * @param first An input iterator.
1509 * @param last An input iterator.
1510 * @param result An output iterator.
1511 * @param pred A predicate.
1512 * @return An iterator designating the end of the resulting sequence.
1513 *
1514 * Copies each element in the range @p [first,last) for which
1515 * @p pred returns true to the range beginning at @p result.
1516 *
1517 * remove_copy_if() is stable, so the relative order of elements that are
1518 * copied is unchanged.
1519 */
1520 template<typename _InputIterator, typename _OutputIterator,
1521 typename _Predicate>
1522 _OutputIterator
1523 remove_copy_if(_InputIterator __first, _InputIterator __last,
1524 _OutputIterator __result, _Predicate __pred)
1525 {
1526 // concept requirements
1527 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1528 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1529 typename iterator_traits<_InputIterator>::value_type>)
1530 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1531 typename iterator_traits<_InputIterator>::value_type>)
1532 __glibcxx_requires_valid_range(__first, __last);
1533
1534 for (; __first != __last; ++__first)
1535 if (!bool(__pred(*__first)))
1536 {
1537 *__result = *__first;
1538 ++__result;
1539 }
1540 return __result;
1541 }
1542
1543 /**
1544 * @brief Remove elements from a sequence.
1545 * @param first An input iterator.
1546 * @param last An input iterator.
1547 * @param value The value to be removed.
1548 * @return An iterator designating the end of the resulting sequence.
1549 *
1550 * All elements equal to @p value are removed from the range
1551 * @p [first,last).
1552 *
1553 * remove() is stable, so the relative order of elements that are
1554 * not removed is unchanged.
1555 *
1556 * Elements between the end of the resulting sequence and @p last
1557 * are still present, but their value is unspecified.
1558 */
1559 template<typename _ForwardIterator, typename _Tp>
1560 _ForwardIterator
1561 remove(_ForwardIterator __first, _ForwardIterator __last,
1562 const _Tp& __value)
1563 {
1564 // concept requirements
1565 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1566 _ForwardIterator>)
1567 __glibcxx_function_requires(_EqualOpConcept<
1568 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1569 __glibcxx_requires_valid_range(__first, __last);
1570
1571 __first = std::find(__first, __last, __value);
1572 _ForwardIterator __i = __first;
1573 return __first == __last ? __first
1574 : std::remove_copy(++__i, __last,
1575 __first, __value);
1576 }
1577
1578 /**
1579 * @brief Remove elements from a sequence using a predicate.
1580 * @param first A forward iterator.
1581 * @param last A forward iterator.
1582 * @param pred A predicate.
1583 * @return An iterator designating the end of the resulting sequence.
1584 *
1585 * All elements for which @p pred returns true are removed from the range
1586 * @p [first,last).
1587 *
1588 * remove_if() is stable, so the relative order of elements that are
1589 * not removed is unchanged.
1590 *
1591 * Elements between the end of the resulting sequence and @p last
1592 * are still present, but their value is unspecified.
1593 */
1594 template<typename _ForwardIterator, typename _Predicate>
1595 _ForwardIterator
1596 remove_if(_ForwardIterator __first, _ForwardIterator __last,
1597 _Predicate __pred)
1598 {
1599 // concept requirements
1600 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1601 _ForwardIterator>)
1602 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1603 typename iterator_traits<_ForwardIterator>::value_type>)
1604 __glibcxx_requires_valid_range(__first, __last);
1605
1606 __first = std::find_if(__first, __last, __pred);
1607 _ForwardIterator __i = __first;
1608 return __first == __last ? __first
1609 : std::remove_copy_if(++__i, __last,
1610 __first, __pred);
1611 }
1612
1613 /**
1614 * @brief Remove consecutive duplicate values from a sequence.
1615 * @param first A forward iterator.
1616 * @param last A forward iterator.
1617 * @return An iterator designating the end of the resulting sequence.
1618 *
1619 * Removes all but the first element from each group of consecutive
1620 * values that compare equal.
1621 * unique() is stable, so the relative order of elements that are
1622 * not removed is unchanged.
1623 * Elements between the end of the resulting sequence and @p last
1624 * are still present, but their value is unspecified.
1625 */
1626 template<typename _ForwardIterator>
1627 _ForwardIterator
1628 unique(_ForwardIterator __first, _ForwardIterator __last)
1629 {
1630 // concept requirements
1631 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1632 _ForwardIterator>)
1633 __glibcxx_function_requires(_EqualityComparableConcept<
1634 typename iterator_traits<_ForwardIterator>::value_type>)
1635 __glibcxx_requires_valid_range(__first, __last);
1636
1637 // Skip the beginning, if already unique.
1638 __first = std::adjacent_find(__first, __last);
1639 if (__first == __last)
1640 return __last;
1641
1642 // Do the real copy work.
1643 _ForwardIterator __dest = __first;
1644 ++__first;
1645 while (++__first != __last)
1646 if (!(*__dest == *__first))
1647 *++__dest = *__first;
1648 return ++__dest;
1649 }
1650
1651 /**
1652 * @brief Remove consecutive values from a sequence using a predicate.
1653 * @param first A forward iterator.
1654 * @param last A forward iterator.
1655 * @param binary_pred A binary predicate.
1656 * @return An iterator designating the end of the resulting sequence.
1657 *
1658 * Removes all but the first element from each group of consecutive
1659 * values for which @p binary_pred returns true.
1660 * unique() is stable, so the relative order of elements that are
1661 * not removed is unchanged.
1662 * Elements between the end of the resulting sequence and @p last
1663 * are still present, but their value is unspecified.
1664 */
1665 template<typename _ForwardIterator, typename _BinaryPredicate>
1666 _ForwardIterator
1667 unique(_ForwardIterator __first, _ForwardIterator __last,
1668 _BinaryPredicate __binary_pred)
1669 {
1670 // concept requirements
1671 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1672 _ForwardIterator>)
1673 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1674 typename iterator_traits<_ForwardIterator>::value_type,
1675 typename iterator_traits<_ForwardIterator>::value_type>)
1676 __glibcxx_requires_valid_range(__first, __last);
1677
1678 // Skip the beginning, if already unique.
1679 __first = std::adjacent_find(__first, __last, __binary_pred);
1680 if (__first == __last)
1681 return __last;
1682
1683 // Do the real copy work.
1684 _ForwardIterator __dest = __first;
1685 ++__first;
1686 while (++__first != __last)
1687 if (!bool(__binary_pred(*__dest, *__first)))
1688 *++__dest = *__first;
1689 return ++__dest;
1690 }
1691
1692 /**
1693 * @if maint
1694 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1695 * _OutputIterator)
1696 * overloaded for forward iterators and output iterator as result.
1697 * @endif
1698 */
1699 template<typename _ForwardIterator, typename _OutputIterator>
1700 _OutputIterator
1701 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1702 _OutputIterator __result,
1703 forward_iterator_tag, output_iterator_tag)
1704 {
1705 // concept requirements -- taken care of in dispatching function
1706 _ForwardIterator __next = __first;
1707 *__result = *__first;
1708 while (++__next != __last)
1709 if (!(*__first == *__next))
1710 {
1711 __first = __next;
1712 *++__result = *__first;
1713 }
1714 return ++__result;
1715 }
1716
1717 /**
1718 * @if maint
1719 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1720 * _OutputIterator)
1721 * overloaded for input iterators and output iterator as result.
1722 * @endif
1723 */
1724 template<typename _InputIterator, typename _OutputIterator>
1725 _OutputIterator
1726 __unique_copy(_InputIterator __first, _InputIterator __last,
1727 _OutputIterator __result,
1728 input_iterator_tag, output_iterator_tag)
1729 {
1730 // concept requirements -- taken care of in dispatching function
1731 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1732 *__result = __value;
1733 while (++__first != __last)
1734 if (!(__value == *__first))
1735 {
1736 __value = *__first;
1737 *++__result = __value;
1738 }
1739 return ++__result;
1740 }
1741
1742 /**
1743 * @if maint
1744 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1745 * _OutputIterator)
1746 * overloaded for input iterators and forward iterator as result.
1747 * @endif
1748 */
1749 template<typename _InputIterator, typename _ForwardIterator>
1750 _ForwardIterator
1751 __unique_copy(_InputIterator __first, _InputIterator __last,
1752 _ForwardIterator __result,
1753 input_iterator_tag, forward_iterator_tag)
1754 {
1755 // concept requirements -- taken care of in dispatching function
1756 *__result = *__first;
1757 while (++__first != __last)
1758 if (!(*__result == *__first))
1759 *++__result = *__first;
1760 return ++__result;
1761 }
1762
1763 /**
1764 * @if maint
1765 * This is an uglified
1766 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1767 * _BinaryPredicate)
1768 * overloaded for forward iterators and output iterator as result.
1769 * @endif
1770 */
1771 template<typename _ForwardIterator, typename _OutputIterator,
1772 typename _BinaryPredicate>
1773 _OutputIterator
1774 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1775 _OutputIterator __result, _BinaryPredicate __binary_pred,
1776 forward_iterator_tag, output_iterator_tag)
1777 {
1778 // concept requirements -- iterators already checked
1779 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1780 typename iterator_traits<_ForwardIterator>::value_type,
1781 typename iterator_traits<_ForwardIterator>::value_type>)
1782
1783 _ForwardIterator __next = __first;
1784 *__result = *__first;
1785 while (++__next != __last)
1786 if (!bool(__binary_pred(*__first, *__next)))
1787 {
1788 __first = __next;
1789 *++__result = *__first;
1790 }
1791 return ++__result;
1792 }
1793
1794 /**
1795 * @if maint
1796 * This is an uglified
1797 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1798 * _BinaryPredicate)
1799 * overloaded for input iterators and output iterator as result.
1800 * @endif
1801 */
1802 template<typename _InputIterator, typename _OutputIterator,
1803 typename _BinaryPredicate>
1804 _OutputIterator
1805 __unique_copy(_InputIterator __first, _InputIterator __last,
1806 _OutputIterator __result, _BinaryPredicate __binary_pred,
1807 input_iterator_tag, output_iterator_tag)
1808 {
1809 // concept requirements -- iterators already checked
1810 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1811 typename iterator_traits<_InputIterator>::value_type,
1812 typename iterator_traits<_InputIterator>::value_type>)
1813
1814 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1815 *__result = __value;
1816 while (++__first != __last)
1817 if (!bool(__binary_pred(__value, *__first)))
1818 {
1819 __value = *__first;
1820 *++__result = __value;
1821 }
1822 return ++__result;
1823 }
1824
1825 /**
1826 * @if maint
1827 * This is an uglified
1828 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1829 * _BinaryPredicate)
1830 * overloaded for input iterators and forward iterator as result.
1831 * @endif
1832 */
1833 template<typename _InputIterator, typename _ForwardIterator,
1834 typename _BinaryPredicate>
1835 _ForwardIterator
1836 __unique_copy(_InputIterator __first, _InputIterator __last,
1837 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1838 input_iterator_tag, forward_iterator_tag)
1839 {
1840 // concept requirements -- iterators already checked
1841 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1842 typename iterator_traits<_ForwardIterator>::value_type,
1843 typename iterator_traits<_InputIterator>::value_type>)
1844
1845 *__result = *__first;
1846 while (++__first != __last)
1847 if (!bool(__binary_pred(*__result, *__first)))
1848 *++__result = *__first;
1849 return ++__result;
1850 }
1851
1852 /**
1853 * @brief Copy a sequence, removing consecutive duplicate values.
1854 * @param first An input iterator.
1855 * @param last An input iterator.
1856 * @param result An output iterator.
1857 * @return An iterator designating the end of the resulting sequence.
1858 *
1859 * Copies each element in the range @p [first,last) to the range
1860 * beginning at @p result, except that only the first element is copied
1861 * from groups of consecutive elements that compare equal.
1862 * unique_copy() is stable, so the relative order of elements that are
1863 * copied is unchanged.
1864 *
1865 * @if maint
1866 * _GLIBCXX_RESOLVE_LIB_DEFECTS
1867 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
1868 *
1869 * _GLIBCXX_RESOLVE_LIB_DEFECTS
1870 * DR 538. 241 again: Does unique_copy() require CopyConstructible and
1871 * Assignable?
1872 * @endif
1873 */
1874 template<typename _InputIterator, typename _OutputIterator>
1875 inline _OutputIterator
1876 unique_copy(_InputIterator __first, _InputIterator __last,
1877 _OutputIterator __result)
1878 {
1879 // concept requirements
1880 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1881 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1882 typename iterator_traits<_InputIterator>::value_type>)
1883 __glibcxx_function_requires(_EqualityComparableConcept<
1884 typename iterator_traits<_InputIterator>::value_type>)
1885 __glibcxx_requires_valid_range(__first, __last);
1886
1887 if (__first == __last)
1888 return __result;
1889 return std::__unique_copy(__first, __last, __result,
1890 std::__iterator_category(__first),
1891 std::__iterator_category(__result));
1892 }
1893
1894 /**
1895 * @brief Copy a sequence, removing consecutive values using a predicate.
1896 * @param first An input iterator.
1897 * @param last An input iterator.
1898 * @param result An output iterator.
1899 * @param binary_pred A binary predicate.
1900 * @return An iterator designating the end of the resulting sequence.
1901 *
1902 * Copies each element in the range @p [first,last) to the range
1903 * beginning at @p result, except that only the first element is copied
1904 * from groups of consecutive elements for which @p binary_pred returns
1905 * true.
1906 * unique_copy() is stable, so the relative order of elements that are
1907 * copied is unchanged.
1908 *
1909 * @if maint
1910 * _GLIBCXX_RESOLVE_LIB_DEFECTS
1911 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
1912 * @endif
1913 */
1914 template<typename _InputIterator, typename _OutputIterator,
1915 typename _BinaryPredicate>
1916 inline _OutputIterator
1917 unique_copy(_InputIterator __first, _InputIterator __last,
1918 _OutputIterator __result,
1919 _BinaryPredicate __binary_pred)
1920 {
1921 // concept requirements -- predicates checked later
1922 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1923 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1924 typename iterator_traits<_InputIterator>::value_type>)
1925 __glibcxx_requires_valid_range(__first, __last);
1926
1927 if (__first == __last)
1928 return __result;
1929 return std::__unique_copy(__first, __last, __result, __binary_pred,
1930 std::__iterator_category(__first),
1931 std::__iterator_category(__result));
1932 }
1933
1934 /**
1935 * @if maint
1936 * This is an uglified reverse(_BidirectionalIterator,
1937 * _BidirectionalIterator)
1938 * overloaded for bidirectional iterators.
1939 * @endif
1940 */
1941 template<typename _BidirectionalIterator>
1942 void
1943 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1944 bidirectional_iterator_tag)
1945 {
1946 while (true)
1947 if (__first == __last || __first == --__last)
1948 return;
1949 else
1950 {
1951 std::iter_swap(__first, __last);
1952 ++__first;
1953 }
1954 }
1955
1956 /**
1957 * @if maint
1958 * This is an uglified reverse(_BidirectionalIterator,
1959 * _BidirectionalIterator)
1960 * overloaded for random access iterators.
1961 * @endif
1962 */
1963 template<typename _RandomAccessIterator>
1964 void
1965 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1966 random_access_iterator_tag)
1967 {
1968 if (__first == __last)
1969 return;
1970 --__last;
1971 while (__first < __last)
1972 {
1973 std::iter_swap(__first, __last);
1974 ++__first;
1975 --__last;
1976 }
1977 }
1978
1979 /**
1980 * @brief Reverse a sequence.
1981 * @param first A bidirectional iterator.
1982 * @param last A bidirectional iterator.
1983 * @return reverse() returns no value.
1984 *
1985 * Reverses the order of the elements in the range @p [first,last),
1986 * so that the first element becomes the last etc.
1987 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1988 * swaps @p *(first+i) and @p *(last-(i+1))
1989 */
1990 template<typename _BidirectionalIterator>
1991 inline void
1992 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1993 {
1994 // concept requirements
1995 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1996 _BidirectionalIterator>)
1997 __glibcxx_requires_valid_range(__first, __last);
1998 std::__reverse(__first, __last, std::__iterator_category(__first));
1999 }
2000
2001 /**
2002 * @brief Copy a sequence, reversing its elements.
2003 * @param first A bidirectional iterator.
2004 * @param last A bidirectional iterator.
2005 * @param result An output iterator.
2006 * @return An iterator designating the end of the resulting sequence.
2007 *
2008 * Copies the elements in the range @p [first,last) to the range
2009 * @p [result,result+(last-first)) such that the order of the
2010 * elements is reversed.
2011 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
2012 * performs the assignment @p *(result+(last-first)-i) = *(first+i).
2013 * The ranges @p [first,last) and @p [result,result+(last-first))
2014 * must not overlap.
2015 */
2016 template<typename _BidirectionalIterator, typename _OutputIterator>
2017 _OutputIterator
2018 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
2019 _OutputIterator __result)
2020 {
2021 // concept requirements
2022 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2023 _BidirectionalIterator>)
2024 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
2025 typename iterator_traits<_BidirectionalIterator>::value_type>)
2026 __glibcxx_requires_valid_range(__first, __last);
2027
2028 while (__first != __last)
2029 {
2030 --__last;
2031 *__result = *__last;
2032 ++__result;
2033 }
2034 return __result;
2035 }
2036
2037 /**
2038 * @if maint
2039 * This is a helper function for the rotate algorithm specialized on RAIs.
2040 * It returns the greatest common divisor of two integer values.
2041 * @endif
2042 */
2043 template<typename _EuclideanRingElement>
2044 _EuclideanRingElement
2045 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
2046 {
2047 while (__n != 0)
2048 {
2049 _EuclideanRingElement __t = __m % __n;
2050 __m = __n;
2051 __n = __t;
2052 }
2053 return __m;
2054 }
2055
2056 /**
2057 * @if maint
2058 * This is a helper function for the rotate algorithm.
2059 * @endif
2060 */
2061 template<typename _ForwardIterator>
2062 void
2063 __rotate(_ForwardIterator __first,
2064 _ForwardIterator __middle,
2065 _ForwardIterator __last,
2066 forward_iterator_tag)
2067 {
2068 if (__first == __middle || __last == __middle)
2069 return;
2070
2071 _ForwardIterator __first2 = __middle;
2072 do
2073 {
2074 swap(*__first, *__first2);
2075 ++__first;
2076 ++__first2;
2077 if (__first == __middle)
2078 __middle = __first2;
2079 }
2080 while (__first2 != __last);
2081
2082 __first2 = __middle;
2083
2084 while (__first2 != __last)
2085 {
2086 swap(*__first, *__first2);
2087 ++__first;
2088 ++__first2;
2089 if (__first == __middle)
2090 __middle = __first2;
2091 else if (__first2 == __last)
2092 __first2 = __middle;
2093 }
2094 }
2095
2096 /**
2097 * @if maint
2098 * This is a helper function for the rotate algorithm.
2099 * @endif
2100 */
2101 template<typename _BidirectionalIterator>
2102 void
2103 __rotate(_BidirectionalIterator __first,
2104 _BidirectionalIterator __middle,
2105 _BidirectionalIterator __last,
2106 bidirectional_iterator_tag)
2107 {
2108 // concept requirements
2109 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2110 _BidirectionalIterator>)
2111
2112 if (__first == __middle || __last == __middle)
2113 return;
2114
2115 std::__reverse(__first, __middle, bidirectional_iterator_tag());
2116 std::__reverse(__middle, __last, bidirectional_iterator_tag());
2117
2118 while (__first != __middle && __middle != __last)
2119 {
2120 swap(*__first, *--__last);
2121 ++__first;
2122 }
2123
2124 if (__first == __middle)
2125 std::__reverse(__middle, __last, bidirectional_iterator_tag());
2126 else
2127 std::__reverse(__first, __middle, bidirectional_iterator_tag());
2128 }
2129
2130 /**
2131 * @if maint
2132 * This is a helper function for the rotate algorithm.
2133 * @endif
2134 */
2135 template<typename _RandomAccessIterator>
2136 void
2137 __rotate(_RandomAccessIterator __first,
2138 _RandomAccessIterator __middle,
2139 _RandomAccessIterator __last,
2140 random_access_iterator_tag)
2141 {
2142 // concept requirements
2143 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2144 _RandomAccessIterator>)
2145
2146 if (__first == __middle || __last == __middle)
2147 return;
2148
2149 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2150 _Distance;
2151 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2152 _ValueType;
2153
2154 const _Distance __n = __last - __first;
2155 const _Distance __k = __middle - __first;
2156 const _Distance __l = __n - __k;
2157
2158 if (__k == __l)
2159 {
2160 std::swap_ranges(__first, __middle, __middle);
2161 return;
2162 }
2163
2164 const _Distance __d = std::__gcd(__n, __k);
2165
2166 for (_Distance __i = 0; __i < __d; __i++)
2167 {
2168 _ValueType __tmp = *__first;
2169 _RandomAccessIterator __p = __first;
2170
2171 if (__k < __l)
2172 {
2173 for (_Distance __j = 0; __j < __l / __d; __j++)
2174 {
2175 if (__p > __first + __l)
2176 {
2177 *__p = *(__p - __l);
2178 __p -= __l;
2179 }
2180
2181 *__p = *(__p + __k);
2182 __p += __k;
2183 }
2184 }
2185 else
2186 {
2187 for (_Distance __j = 0; __j < __k / __d - 1; __j ++)
2188 {
2189 if (__p < __last - __k)
2190 {
2191 *__p = *(__p + __k);
2192 __p += __k;
2193 }
2194 *__p = * (__p - __l);
2195 __p -= __l;
2196 }
2197 }
2198
2199 *__p = __tmp;
2200 ++__first;
2201 }
2202 }
2203
2204 /**
2205 * @brief Rotate the elements of a sequence.
2206 * @param first A forward iterator.
2207 * @param middle A forward iterator.
2208 * @param last A forward iterator.
2209 * @return Nothing.
2210 *
2211 * Rotates the elements of the range @p [first,last) by @p (middle-first)
2212 * positions so that the element at @p middle is moved to @p first, the
2213 * element at @p middle+1 is moved to @first+1 and so on for each element
2214 * in the range @p [first,last).
2215 *
2216 * This effectively swaps the ranges @p [first,middle) and
2217 * @p [middle,last).
2218 *
2219 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
2220 * each @p n in the range @p [0,last-first).
2221 */
2222 template<typename _ForwardIterator>
2223 inline void
2224 rotate(_ForwardIterator __first, _ForwardIterator __middle,
2225 _ForwardIterator __last)
2226 {
2227 // concept requirements
2228 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
2229 _ForwardIterator>)
2230 __glibcxx_requires_valid_range(__first, __middle);
2231 __glibcxx_requires_valid_range(__middle, __last);
2232
2233 typedef typename iterator_traits<_ForwardIterator>::iterator_category
2234 _IterType;
2235 std::__rotate(__first, __middle, __last, _IterType());
2236 }
2237
2238 /**
2239 * @brief Copy a sequence, rotating its elements.
2240 * @param first A forward iterator.
2241 * @param middle A forward iterator.
2242 * @param last A forward iterator.
2243 * @param result An output iterator.
2244 * @return An iterator designating the end of the resulting sequence.
2245 *
2246 * Copies the elements of the range @p [first,last) to the range
2247 * beginning at @result, rotating the copied elements by @p (middle-first)
2248 * positions so that the element at @p middle is moved to @p result, the
2249 * element at @p middle+1 is moved to @result+1 and so on for each element
2250 * in the range @p [first,last).
2251 *
2252 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
2253 * each @p n in the range @p [0,last-first).
2254 */
2255 template<typename _ForwardIterator, typename _OutputIterator>
2256 _OutputIterator
2257 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
2258 _ForwardIterator __last, _OutputIterator __result)
2259 {
2260 // concept requirements
2261 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2262 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
2263 typename iterator_traits<_ForwardIterator>::value_type>)
2264 __glibcxx_requires_valid_range(__first, __middle);
2265 __glibcxx_requires_valid_range(__middle, __last);
2266
2267 return std::copy(__first, __middle,
2268 std::copy(__middle, __last, __result));
2269 }
2270
2271 /**
2272 * @brief Randomly shuffle the elements of a sequence.
2273 * @param first A forward iterator.
2274 * @param last A forward iterator.
2275 * @return Nothing.
2276 *
2277 * Reorder the elements in the range @p [first,last) using a random
2278 * distribution, so that every possible ordering of the sequence is
2279 * equally likely.
2280 */
2281 template<typename _RandomAccessIterator>
2282 inline void
2283 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
2284 {
2285 // concept requirements
2286 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2287 _RandomAccessIterator>)
2288 __glibcxx_requires_valid_range(__first, __last);
2289
2290 if (__first != __last)
2291 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2292 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
2293 }
2294
2295 /**
2296 * @brief Shuffle the elements of a sequence using a random number
2297 * generator.
2298 * @param first A forward iterator.
2299 * @param last A forward iterator.
2300 * @param rand The RNG functor or function.
2301 * @return Nothing.
2302 *
2303 * Reorders the elements in the range @p [first,last) using @p rand to
2304 * provide a random distribution. Calling @p rand(N) for a positive
2305 * integer @p N should return a randomly chosen integer from the
2306 * range [0,N).
2307 */
2308 template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
2309 void
2310 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
2311 _RandomNumberGenerator& __rand)
2312 {
2313 // concept requirements
2314 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2315 _RandomAccessIterator>)
2316 __glibcxx_requires_valid_range(__first, __last);
2317
2318 if (__first == __last)
2319 return;
2320 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2321 std::iter_swap(__i, __first + __rand((__i - __first) + 1));
2322 }
2323
2324
2325 /**
2326 * @if maint
2327 * This is a helper function...
2328 * @endif
2329 */
2330 template<typename _ForwardIterator, typename _Predicate>
2331 _ForwardIterator
2332 __partition(_ForwardIterator __first, _ForwardIterator __last,
2333 _Predicate __pred,
2334 forward_iterator_tag)
2335 {
2336 if (__first == __last)
2337 return __first;
2338
2339 while (__pred(*__first))
2340 if (++__first == __last)
2341 return __first;
2342
2343 _ForwardIterator __next = __first;
2344
2345 while (++__next != __last)
2346 if (__pred(*__next))
2347 {
2348 swap(*__first, *__next);
2349 ++__first;
2350 }
2351
2352 return __first;
2353 }
2354
2355 /**
2356 * @if maint
2357 * This is a helper function...
2358 * @endif
2359 */
2360 template<typename _BidirectionalIterator, typename _Predicate>
2361 _BidirectionalIterator
2362 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
2363 _Predicate __pred,
2364 bidirectional_iterator_tag)
2365 {
2366 while (true)
2367 {
2368 while (true)
2369 if (__first == __last)
2370 return __first;
2371 else if (__pred(*__first))
2372 ++__first;
2373 else
2374 break;
2375 --__last;
2376 while (true)
2377 if (__first == __last)
2378 return __first;
2379 else if (!bool(__pred(*__last)))
2380 --__last;
2381 else
2382 break;
2383 std::iter_swap(__first, __last);
2384 ++__first;
2385 }
2386 }
2387
2388 /**
2389 * @brief Move elements for which a predicate is true to the beginning
2390 * of a sequence.
2391 * @param first A forward iterator.
2392 * @param last A forward iterator.
2393 * @param pred A predicate functor.
2394 * @return An iterator @p middle such that @p pred(i) is true for each
2395 * iterator @p i in the range @p [first,middle) and false for each @p i
2396 * in the range @p [middle,last).
2397 *
2398 * @p pred must not modify its operand. @p partition() does not preserve
2399 * the relative ordering of elements in each group, use
2400 * @p stable_partition() if this is needed.
2401 */
2402 template<typename _ForwardIterator, typename _Predicate>
2403 inline _ForwardIterator
2404 partition(_ForwardIterator __first, _ForwardIterator __last,
2405 _Predicate __pred)
2406 {
2407 // concept requirements
2408 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
2409 _ForwardIterator>)
2410 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
2411 typename iterator_traits<_ForwardIterator>::value_type>)
2412 __glibcxx_requires_valid_range(__first, __last);
2413
2414 return std::__partition(__first, __last, __pred,
2415 std::__iterator_category(__first));
2416 }
2417
2418
2419 /**
2420 * @if maint
2421 * This is a helper function...
2422 * @endif
2423 */
2424 template<typename _ForwardIterator, typename _Predicate, typename _Distance>
2425 _ForwardIterator
2426 __inplace_stable_partition(_ForwardIterator __first,
2427 _ForwardIterator __last,
2428 _Predicate __pred, _Distance __len)
2429 {
2430 if (__len == 1)
2431 return __pred(*__first) ? __last : __first;
2432 _ForwardIterator __middle = __first;
2433 std::advance(__middle, __len / 2);
2434 _ForwardIterator __begin = std::__inplace_stable_partition(__first,
2435 __middle,
2436 __pred,
2437 __len / 2);
2438 _ForwardIterator __end = std::__inplace_stable_partition(__middle, __last,
2439 __pred,
2440 __len
2441 - __len / 2);
2442 std::rotate(__begin, __middle, __end);
2443 std::advance(__begin, std::distance(__middle, __end));
2444 return __begin;
2445 }
2446
2447 /**
2448 * @if maint
2449 * This is a helper function...
2450 * @endif
2451 */
2452 template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
2453 typename _Distance>
2454 _ForwardIterator
2455 __stable_partition_adaptive(_ForwardIterator __first,
2456 _ForwardIterator __last,
2457 _Predicate __pred, _Distance __len,
2458 _Pointer __buffer,
2459 _Distance __buffer_size)
2460 {
2461 if (__len <= __buffer_size)
2462 {
2463 _ForwardIterator __result1 = __first;
2464 _Pointer __result2 = __buffer;
2465 for (; __first != __last; ++__first)
2466 if (__pred(*__first))
2467 {
2468 *__result1 = *__first;
2469 ++__result1;
2470 }
2471 else
2472 {
2473 *__result2 = *__first;
2474 ++__result2;
2475 }
2476 std::copy(__buffer, __result2, __result1);
2477 return __result1;
2478 }
2479 else
2480 {
2481 _ForwardIterator __middle = __first;
2482 std::advance(__middle, __len / 2);
2483 _ForwardIterator __begin =
2484 std::__stable_partition_adaptive(__first, __middle, __pred,
2485 __len / 2, __buffer,
2486 __buffer_size);
2487 _ForwardIterator __end =
2488 std::__stable_partition_adaptive(__middle, __last, __pred,
2489 __len - __len / 2,
2490 __buffer, __buffer_size);
2491 std::rotate(__begin, __middle, __end);
2492 std::advance(__begin, std::distance(__middle, __end));
2493 return __begin;
2494 }
2495 }
2496
2497 /**
2498 * @brief Move elements for which a predicate is true to the beginning
2499 * of a sequence, preserving relative ordering.
2500 * @param first A forward iterator.
2501 * @param last A forward iterator.
2502 * @param pred A predicate functor.
2503 * @return An iterator @p middle such that @p pred(i) is true for each
2504 * iterator @p i in the range @p [first,middle) and false for each @p i
2505 * in the range @p [middle,last).
2506 *
2507 * Performs the same function as @p partition() with the additional
2508 * guarantee that the relative ordering of elements in each group is
2509 * preserved, so any two elements @p x and @p y in the range
2510 * @p [first,last) such that @p pred(x)==pred(y) will have the same
2511 * relative ordering after calling @p stable_partition().
2512 */
2513 template<typename _ForwardIterator, typename _Predicate>
2514 _ForwardIterator
2515 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
2516 _Predicate __pred)
2517 {
2518 // concept requirements
2519 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
2520 _ForwardIterator>)
2521 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
2522 typename iterator_traits<_ForwardIterator>::value_type>)
2523 __glibcxx_requires_valid_range(__first, __last);
2524
2525 if (__first == __last)
2526 return __first;
2527 else
2528 {
2529 typedef typename iterator_traits<_ForwardIterator>::value_type
2530 _ValueType;
2531 typedef typename iterator_traits<_ForwardIterator>::difference_type
2532 _DistanceType;
2533
2534 _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
2535 __last);
2536 if (__buf.size() > 0)
2537 return
2538 std::__stable_partition_adaptive(__first, __last, __pred,
2539 _DistanceType(__buf.requested_size()),
2540 __buf.begin(),
2541 _DistanceType(__buf.size()));
2542 else
2543 return
2544 std::__inplace_stable_partition(__first, __last, __pred,
2545 _DistanceType(__buf.requested_size()));
2546 }
2547 }
2548
2549 /**
2550 * @if maint
2551 * This is a helper function for the sort routines.
2552 * @endif
2553 */
2554 template<typename _RandomAccessIterator>
2555 void
2556 __heap_select(_RandomAccessIterator __first,
2557 _RandomAccessIterator __middle,
2558 _RandomAccessIterator __last)
2559 {
2560 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2561 _ValueType;
2562
2563 std::make_heap(__first, __middle);
2564 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
2565 if (*__i < *__first)
2566 std::__pop_heap(__first, __middle, __i, _ValueType(*__i));
2567 }
2568
2569 /**
2570 * @if maint
2571 * This is a helper function for the sort routines.
2572 * @endif
2573 */
2574 template<typename _RandomAccessIterator, typename _Compare>
2575 void
2576 __heap_select(_RandomAccessIterator __first,
2577 _RandomAccessIterator __middle,
2578 _RandomAccessIterator __last, _Compare __comp)
2579 {
2580 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2581 _ValueType;
2582
2583 std::make_heap(__first, __middle, __comp);
2584 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
2585 if (__comp(*__i, *__first))
2586 std::__pop_heap(__first, __middle, __i, _ValueType(*__i), __comp);
2587 }
2588
2589 /**
2590 * @brief Sort the smallest elements of a sequence.
2591 * @param first An iterator.
2592 * @param middle Another iterator.
2593 * @param last Another iterator.
2594 * @return Nothing.
2595 *
2596 * Sorts the smallest @p (middle-first) elements in the range
2597 * @p [first,last) and moves them to the range @p [first,middle). The
2598 * order of the remaining elements in the range @p [middle,last) is
2599 * undefined.
2600 * After the sort if @p i and @j are iterators in the range
2601 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2602 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
2603 */
2604 template<typename _RandomAccessIterator>
2605 inline void
2606 partial_sort(_RandomAccessIterator __first,
2607 _RandomAccessIterator __middle,
2608 _RandomAccessIterator __last)
2609 {
2610 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2611 _ValueType;
2612
2613 // concept requirements
2614 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2615 _RandomAccessIterator>)
2616 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
2617 __glibcxx_requires_valid_range(__first, __middle);
2618 __glibcxx_requires_valid_range(__middle, __last);
2619
2620 std::__heap_select(__first, __middle, __last);
2621 std::sort_heap(__first, __middle);
2622 }
2623
2624 /**
2625 * @brief Sort the smallest elements of a sequence using a predicate
2626 * for comparison.
2627 * @param first An iterator.
2628 * @param middle Another iterator.
2629 * @param last Another iterator.
2630 * @param comp A comparison functor.
2631 * @return Nothing.
2632 *
2633 * Sorts the smallest @p (middle-first) elements in the range
2634 * @p [first,last) and moves them to the range @p [first,middle). The
2635 * order of the remaining elements in the range @p [middle,last) is
2636 * undefined.
2637 * After the sort if @p i and @j are iterators in the range
2638 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2639 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
2640 * are both false.
2641 */
2642 template<typename _RandomAccessIterator, typename _Compare>
2643 inline void
2644 partial_sort(_RandomAccessIterator __first,
2645 _RandomAccessIterator __middle,
2646 _RandomAccessIterator __last,
2647 _Compare __comp)
2648 {
2649 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2650 _ValueType;
2651
2652 // concept requirements
2653 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2654 _RandomAccessIterator>)
2655 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2656 _ValueType, _ValueType>)
2657 __glibcxx_requires_valid_range(__first, __middle);
2658 __glibcxx_requires_valid_range(__middle, __last);
2659
2660 std::__heap_select(__first, __middle, __last, __comp);
2661 std::sort_heap(__first, __middle, __comp);
2662 }
2663
2664 /**
2665 * @brief Copy the smallest elements of a sequence.
2666 * @param first An iterator.
2667 * @param last Another iterator.
2668 * @param result_first A random-access iterator.
2669 * @param result_last Another random-access iterator.
2670 * @return An iterator indicating the end of the resulting sequence.
2671 *
2672 * Copies and sorts the smallest N values from the range @p [first,last)
2673 * to the range beginning at @p result_first, where the number of
2674 * elements to be copied, @p N, is the smaller of @p (last-first) and
2675 * @p (result_last-result_first).
2676 * After the sort if @p i and @j are iterators in the range
2677 * @p [result_first,result_first+N) such that @i precedes @j then
2678 * @p *j<*i is false.
2679 * The value returned is @p result_first+N.
2680 */
2681 template<typename _InputIterator, typename _RandomAccessIterator>
2682 _RandomAccessIterator
2683 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2684 _RandomAccessIterator __result_first,
2685 _RandomAccessIterator __result_last)
2686 {
2687 typedef typename iterator_traits<_InputIterator>::value_type
2688 _InputValueType;
2689 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2690 _OutputValueType;
2691 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2692 _DistanceType;
2693
2694 // concept requirements
2695 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2696 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2697 _OutputValueType>)
2698 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
2699 _OutputValueType>)
2700 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
2701 __glibcxx_requires_valid_range(__first, __last);
2702 __glibcxx_requires_valid_range(__result_first, __result_last);
2703
2704 if (__result_first == __result_last)
2705 return __result_last;
2706 _RandomAccessIterator __result_real_last = __result_first;
2707 while(__first != __last && __result_real_last != __result_last)
2708 {
2709 *__result_real_last = *__first;
2710 ++__result_real_last;
2711 ++__first;
2712 }
2713 std::make_heap(__result_first, __result_real_last);
2714 while (__first != __last)
2715 {
2716 if (*__first < *__result_first)
2717 std::__adjust_heap(__result_first, _DistanceType(0),
2718 _DistanceType(__result_real_last
2719 - __result_first),
2720 _InputValueType(*__first));
2721 ++__first;
2722 }
2723 std::sort_heap(__result_first, __result_real_last);
2724 return __result_real_last;
2725 }
2726
2727 /**
2728 * @brief Copy the smallest elements of a sequence using a predicate for
2729 * comparison.
2730 * @param first An input iterator.
2731 * @param last Another input iterator.
2732 * @param result_first A random-access iterator.
2733 * @param result_last Another random-access iterator.
2734 * @param comp A comparison functor.
2735 * @return An iterator indicating the end of the resulting sequence.
2736 *
2737 * Copies and sorts the smallest N values from the range @p [first,last)
2738 * to the range beginning at @p result_first, where the number of
2739 * elements to be copied, @p N, is the smaller of @p (last-first) and
2740 * @p (result_last-result_first).
2741 * After the sort if @p i and @j are iterators in the range
2742 * @p [result_first,result_first+N) such that @i precedes @j then
2743 * @p comp(*j,*i) is false.
2744 * The value returned is @p result_first+N.
2745 */
2746 template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
2747 _RandomAccessIterator
2748 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2749 _RandomAccessIterator __result_first,
2750 _RandomAccessIterator __result_last,
2751 _Compare __comp)
2752 {
2753 typedef typename iterator_traits<_InputIterator>::value_type
2754 _InputValueType;
2755 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2756 _OutputValueType;
2757 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2758 _DistanceType;
2759
2760 // concept requirements
2761 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2762 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2763 _RandomAccessIterator>)
2764 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2765 _OutputValueType>)
2766 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2767 _InputValueType, _OutputValueType>)
2768 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2769 _OutputValueType, _OutputValueType>)
2770 __glibcxx_requires_valid_range(__first, __last);
2771 __glibcxx_requires_valid_range(__result_first, __result_last);
2772
2773 if (__result_first == __result_last)
2774 return __result_last;
2775 _RandomAccessIterator __result_real_last = __result_first;
2776 while(__first != __last && __result_real_last != __result_last)
2777 {
2778 *__result_real_last = *__first;
2779 ++__result_real_last;
2780 ++__first;
2781 }
2782 std::make_heap(__result_first, __result_real_last, __comp);
2783 while (__first != __last)
2784 {
2785 if (__comp(*__first, *__result_first))
2786 std::__adjust_heap(__result_first, _DistanceType(0),
2787 _DistanceType(__result_real_last
2788 - __result_first),
2789 _InputValueType(*__first),
2790 __comp);
2791 ++__first;
2792 }
2793 std::sort_heap(__result_first, __result_real_last, __comp);
2794 return __result_real_last;
2795 }
2796
2797 /**
2798 * @if maint
2799 * This is a helper function for the sort routine.
2800 * @endif
2801 */
2802 template<typename _RandomAccessIterator, typename _Tp>
2803 void
2804 __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val)
2805 {
2806 _RandomAccessIterator __next = __last;
2807 --__next;
2808 while (__val < *__next)
2809 {
2810 *__last = *__next;
2811 __last = __next;
2812 --__next;
2813 }
2814 *__last = __val;
2815 }
2816
2817 /**
2818 * @if maint
2819 * This is a helper function for the sort routine.
2820 * @endif
2821 */
2822 template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
2823 void
2824 __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,
2825 _Compare __comp)
2826 {
2827 _RandomAccessIterator __next = __last;
2828 --__next;
2829 while (__comp(__val, *__next))
2830 {
2831 *__last = *__next;
2832 __last = __next;
2833 --__next;
2834 }
2835 *__last = __val;
2836 }
2837
2838 /**
2839 * @if maint
2840 * This is a helper function for the sort routine.
2841 * @endif
2842 */
2843 template<typename _RandomAccessIterator>
2844 void
2845 __insertion_sort(_RandomAccessIterator __first,
2846 _RandomAccessIterator __last)
2847 {
2848 if (__first == __last)
2849 return;
2850
2851 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2852 {
2853 typename iterator_traits<_RandomAccessIterator>::value_type
2854 __val = *__i;
2855 if (__val < *__first)
2856 {
2857 std::copy_backward(__first, __i, __i + 1);
2858 *__first = __val;
2859 }
2860 else
2861 std::__unguarded_linear_insert(__i, __val);
2862 }
2863 }
2864
2865 /**
2866 * @if maint
2867 * This is a helper function for the sort routine.
2868 * @endif
2869 */
2870 template<typename _RandomAccessIterator, typename _Compare>
2871 void
2872 __insertion_sort(_RandomAccessIterator __first,
2873 _RandomAccessIterator __last, _Compare __comp)
2874 {
2875 if (__first == __last) return;
2876
2877 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2878 {
2879 typename iterator_traits<_RandomAccessIterator>::value_type
2880 __val = *__i;
2881 if (__comp(__val, *__first))
2882 {
2883 std::copy_backward(__first, __i, __i + 1);
2884 *__first = __val;
2885 }
2886 else
2887 std::__unguarded_linear_insert(__i, __val, __comp);
2888 }
2889 }
2890
2891 /**
2892 * @if maint
2893 * This is a helper function for the sort routine.
2894 * @endif
2895 */
2896 template<typename _RandomAccessIterator>
2897 inline void
2898 __unguarded_insertion_sort(_RandomAccessIterator __first,
2899 _RandomAccessIterator __last)
2900 {
2901 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2902 _ValueType;
2903
2904 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2905 std::__unguarded_linear_insert(__i, _ValueType(*__i));
2906 }
2907
2908 /**
2909 * @if maint
2910 * This is a helper function for the sort routine.
2911 * @endif
2912 */
2913 template<typename _RandomAccessIterator, typename _Compare>
2914 inline void
2915 __unguarded_insertion_sort(_RandomAccessIterator __first,
2916 _RandomAccessIterator __last, _Compare __comp)
2917 {
2918 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2919 _ValueType;
2920
2921 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2922 std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);
2923 }
2924
2925 /**
2926 * @if maint
2927 * @doctodo
2928 * This controls some aspect of the sort routines.
2929 * @endif
2930 */
2931 enum { _S_threshold = 16 };
2932
2933 /**
2934 * @if maint
2935 * This is a helper function for the sort routine.
2936 * @endif
2937 */
2938 template<typename _RandomAccessIterator>
2939 void
2940 __final_insertion_sort(_RandomAccessIterator __first,
2941 _RandomAccessIterator __last)
2942 {
2943 if (__last - __first > int(_S_threshold))
2944 {
2945 std::__insertion_sort(__first, __first + int(_S_threshold));
2946 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
2947 }
2948 else
2949 std::__insertion_sort(__first, __last);
2950 }
2951
2952 /**
2953 * @if maint
2954 * This is a helper function for the sort routine.
2955 * @endif
2956 */
2957 template<typename _RandomAccessIterator, typename _Compare>
2958 void
2959 __final_insertion_sort(_RandomAccessIterator __first,
2960 _RandomAccessIterator __last, _Compare __comp)
2961 {
2962 if (__last - __first > int(_S_threshold))
2963 {
2964 std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
2965 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
2966 __comp);
2967 }
2968 else
2969 std::__insertion_sort(__first, __last, __comp);
2970 }
2971
2972 /**
2973 * @if maint
2974 * This is a helper function...
2975 * @endif
2976 */
2977 template<typename _RandomAccessIterator, typename _Tp>
2978 _RandomAccessIterator
2979 __unguarded_partition(_RandomAccessIterator __first,
2980 _RandomAccessIterator __last, _Tp __pivot)
2981 {
2982 while (true)
2983 {
2984 while (*__first < __pivot)
2985 ++__first;
2986 --__last;
2987 while (__pivot < *__last)
2988 --__last;
2989 if (!(__first < __last))
2990 return __first;
2991 std::iter_swap(__first, __last);
2992 ++__first;
2993 }
2994 }
2995
2996 /**
2997 * @if maint
2998 * This is a helper function...
2999 * @endif
3000 */
3001 template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
3002 _RandomAccessIterator
3003 __unguarded_partition(_RandomAccessIterator __first,
3004 _RandomAccessIterator __last,
3005 _Tp __pivot, _Compare __comp)
3006 {
3007 while (true)
3008 {
3009 while (__comp(*__first, __pivot))
3010 ++__first;
3011 --__last;
3012 while (__comp(__pivot, *__last))
3013 --__last;
3014 if (!(__first < __last))
3015 return __first;
3016 std::iter_swap(__first, __last);
3017 ++__first;
3018 }
3019 }
3020
3021 /**
3022 * @if maint
3023 * This is a helper function for the sort routine.
3024 * @endif
3025 */
3026 template<typename _RandomAccessIterator, typename _Size>
3027 void
3028 __introsort_loop(_RandomAccessIterator __first,
3029 _RandomAccessIterator __last,
3030 _Size __depth_limit)
3031 {
3032 typedef typename iterator_traits<_RandomAccessIterator>::value_type
3033 _ValueType;
3034
3035 while (__last - __first > int(_S_threshold))
3036 {
3037 if (__depth_limit == 0)
3038 {
3039 std::partial_sort(__first, __last, __last);
3040 return;
3041 }
3042 --__depth_limit;
3043 _RandomAccessIterator __cut =
3044 std::__unguarded_partition(__first, __last,
3045 _ValueType(std::__median(*__first,
3046 *(__first
3047 + (__last
3048 - __first)
3049 / 2),
3050 *(__last
3051 - 1))));
3052 std::__introsort_loop(__cut, __last, __depth_limit);
3053 __last = __cut;
3054 }
3055 }
3056
3057 /**
3058 * @if maint
3059 * This is a helper function for the sort routine.
3060 * @endif
3061 */
3062 template<typename _RandomAccessIterator, typename _Size, typename _Compare>
3063 void
3064 __introsort_loop(_RandomAccessIterator __first,
3065 _RandomAccessIterator __last,
3066 _Size __depth_limit, _Compare __comp)
3067 {
3068 typedef typename iterator_traits<_RandomAccessIterator>::value_type
3069 _ValueType;
3070
3071 while (__last - __first > int(_S_threshold))
3072 {
3073 if (__depth_limit == 0)
3074 {
3075 std::partial_sort(__first, __last, __last, __comp);
3076 return;
3077 }
3078 --__depth_limit;
3079 _RandomAccessIterator __cut =
3080 std::__unguarded_partition(__first, __last,
3081 _ValueType(std::__median(*__first,
3082 *(__first
3083 + (__last
3084 - __first)
3085 / 2),
3086 *(__last - 1),
3087 __comp)),
3088 __comp);
3089 std::__introsort_loop(__cut, __last, __depth_limit, __comp);
3090 __last = __cut;
3091 }
3092 }
3093
3094 /**
3095 * @if maint
3096 * This is a helper function for the sort routines.
3097 * @endif
3098 */
3099 template<typename _Size>
3100 inline _Size
3101 __lg(_Size __n)
3102 {
3103 _Size __k;
3104 for (__k = 0; __n != 1; __n >>= 1)
3105 ++__k;
3106 return __k;
3107 }
3108
3109 /**
3110 * @brief Sort the elements of a sequence.
3111 * @param first An iterator.
3112 * @param last Another iterator.
3113 * @return Nothing.
3114 *
3115 * Sorts the elements in the range @p [first,last) in ascending order,
3116 * such that @p *(i+1)<*i is false for each iterator @p i in the range
3117 * @p [first,last-1).
3118 *
3119 * The relative ordering of equivalent elements is not preserved, use
3120 * @p stable_sort() if this is needed.
3121 */
3122 template<typename _RandomAccessIterator>
3123 inline void
3124 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
3125 {
3126 typedef typename iterator_traits<_RandomAccessIterator>::value_type
3127 _ValueType;
3128
3129 // concept requirements
3130 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3131 _RandomAccessIterator>)
3132 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3133 __glibcxx_requires_valid_range(__first, __last);
3134
3135 if (__first != __last)
3136 {
3137 std::__introsort_loop(__first, __last,
3138 std::__lg(__last - __first) * 2);
3139 std::__final_insertion_sort(__first, __last);
3140 }
3141 }
3142
3143 /**
3144 * @brief Sort the elements of a sequence using a predicate for comparison.
3145 * @param first An iterator.
3146 * @param last Another iterator.
3147 * @param comp A comparison functor.
3148 * @return Nothing.
3149 *
3150 * Sorts the elements in the range @p [first,last) in ascending order,
3151 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the
3152 * range @p [first,last-1).
3153 *
3154 * The relative ordering of equivalent elements is not preserved, use
3155 * @p stable_sort() if this is needed.
3156 */
3157 template<typename _RandomAccessIterator, typename _Compare>
3158 inline void
3159 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
3160 _Compare __comp)
3161 {
3162 typedef typename iterator_traits<_RandomAccessIterator>::value_type
3163 _ValueType;
3164
3165 // concept requirements
3166 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3167 _RandomAccessIterator>)
3168 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
3169 _ValueType>)
3170 __glibcxx_requires_valid_range(__first, __last);
3171
3172 if (__first != __last)
3173 {
3174 std::__introsort_loop(__first, __last,
3175 std::__lg(__last - __first) * 2, __comp);
3176 std::__final_insertion_sort(__first, __last, __comp);
3177 }
3178 }
3179
3180 template<typename _RandomAccessIterator, typename _Size>
3181 void
3182 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
3183 _RandomAccessIterator __last, _Size __depth_limit)
3184 {
3185 typedef typename iterator_traits<_RandomAccessIterator>::value_type
3186 _ValueType;
3187
3188 while (__last - __first > 3)
3189 {
3190 if (__depth_limit == 0)
3191 {
3192 std::__heap_select(__first, __nth + 1, __last);
3193 // Place the nth largest element in its final position.
3194 std::iter_swap(__first, __nth);
3195 return;
3196 }
3197 --__depth_limit;
3198 _RandomAccessIterator __cut =
3199 std::__unguarded_partition(__first, __last,
3200 _ValueType(std::__median(*__first,
3201 *(__first
3202 + (__last
3203 - __first)
3204 / 2),
3205 *(__last
3206 - 1))));
3207 if (__cut <= __nth)
3208 __first = __cut;
3209 else
3210 __last = __cut;
3211 }
3212 std::__insertion_sort(__first, __last);
3213 }
3214
3215 template<typename _RandomAccessIterator, typename _Size, typename _Compare>
3216 void
3217 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
3218 _RandomAccessIterator __last, _Size __depth_limit,
3219 _Compare __comp)
3220 {
3221 typedef typename iterator_traits<_RandomAccessIterator>::value_type
3222 _ValueType;
3223
3224 while (__last - __first > 3)
3225 {
3226 if (__depth_limit == 0)
3227 {
3228 std::__heap_select(__first, __nth + 1, __last, __comp);
3229 // Place the nth largest element in its final position.
3230 std::iter_swap(__first, __nth);
3231 return;
3232 }
3233 --__depth_limit;
3234 _RandomAccessIterator __cut =
3235 std::__unguarded_partition(__first, __last,
3236 _ValueType(std::__median(*__first,
3237 *(__first
3238 + (__last
3239 - __first)
3240 / 2),
3241 *(__last - 1),
3242 __comp)),
3243 __comp);
3244 if (__cut <= __nth)
3245 __first = __cut;
3246 else
3247 __last = __cut;
3248 }
3249 std::__insertion_sort(__first, __last, __comp);
3250 }
3251
3252 /**
3253 * @brief Sort a sequence just enough to find a particular position.
3254 * @param first An iterator.
3255 * @param nth Another iterator.
3256 * @param last Another iterator.
3257 * @return Nothing.
3258 *
3259 * Rearranges the elements in the range @p [first,last) so that @p *nth
3260 * is the same element that would have been in that position had the
3261 * whole sequence been sorted.
3262 * whole sequence been sorted. The elements either side of @p *nth are
3263 * not completely sorted, but for any iterator @i in the range
3264 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
3265 * holds that @p *j<*i is false.
3266 */
3267 template<typename _RandomAccessIterator>
3268 inline void
3269 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
3270 _RandomAccessIterator __last)
3271 {
3272 typedef typename iterator_traits<_RandomAccessIterator>::value_type
3273 _ValueType;
3274
3275 // concept requirements
3276 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3277 _RandomAccessIterator>)
3278 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3279 __glibcxx_requires_valid_range(__first, __nth);
3280 __glibcxx_requires_valid_range(__nth, __last);
3281
3282 if (__first == __last || __nth == __last)
3283 return;
3284
3285 std::__introselect(__first, __nth, __last,
3286 std::__lg(__last - __first) * 2);
3287 }
3288
3289 /**
3290 * @brief Sort a sequence just enough to find a particular position
3291 * using a predicate for comparison.
3292 * @param first An iterator.
3293 * @param nth Another iterator.
3294 * @param last Another iterator.
3295 * @param comp A comparison functor.
3296 * @return Nothing.
3297 *
3298 * Rearranges the elements in the range @p [first,last) so that @p *nth
3299 * is the same element that would have been in that position had the
3300 * whole sequence been sorted. The elements either side of @p *nth are
3301 * not completely sorted, but for any iterator @i in the range
3302 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
3303 * holds that @p comp(*j,*i) is false.
3304 */
3305 template<typename _RandomAccessIterator, typename _Compare>
3306 inline void
3307 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
3308 _RandomAccessIterator __last, _Compare __comp)
3309 {
3310 typedef typename iterator_traits<_RandomAccessIterator>::value_type
3311 _ValueType;
3312
3313 // concept requirements
3314 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3315 _RandomAccessIterator>)
3316 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3317 _ValueType, _ValueType>)
3318 __glibcxx_requires_valid_range(__first, __nth);
3319 __glibcxx_requires_valid_range(__nth, __last);
3320
3321 if (__first == __last || __nth == __last)
3322 return;
3323
3324 std::__introselect(__first, __nth, __last,
3325 std::__lg(__last - __first) * 2, __comp);
3326 }
3327
3328 /**
3329 * @brief Finds the first position in which @a val could be inserted
3330 * without changing the ordering.
3331 * @param first An iterator.
3332 * @param last Another iterator.
3333 * @param val The search term.
3334 * @return An iterator pointing to the first element "not less than" @a val,
3335 * or end() if every element is less than @a val.
3336 * @ingroup binarysearch
3337 */
3338 template<typename _ForwardIterator, typename _Tp>
3339 _ForwardIterator
3340 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
3341 const _Tp& __val)
3342 {
3343 typedef typename iterator_traits<_ForwardIterator>::value_type
3344 _ValueType;
3345 typedef typename iterator_traits<_ForwardIterator>::difference_type
3346 _DistanceType;
3347
3348 // concept requirements
3349 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3350 __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
3351 __glibcxx_requires_partitioned(__first, __last, __val);
3352
3353 _DistanceType __len = std::distance(__first, __last);
3354 _DistanceType __half;
3355 _ForwardIterator __middle;
3356
3357 while (__len > 0)
3358 {
3359 __half = __len >> 1;
3360 __middle = __first;
3361 std::advance(__middle, __half);
3362 if (*__middle < __val)
3363 {
3364 __first = __middle;
3365 ++__first;
3366 __len = __len - __half - 1;
3367 }
3368 else
3369 __len = __half;
3370 }
3371 return __first;
3372 }
3373
3374 /**
3375 * @brief Finds the first position in which @a val could be inserted
3376 * without changing the ordering.
3377 * @param first An iterator.
3378 * @param last Another iterator.
3379 * @param val The search term.
3380 * @param comp A functor to use for comparisons.
3381 * @return An iterator pointing to the first element "not less than" @a val,
3382 * or end() if every element is less than @a val.
3383 * @ingroup binarysearch
3384 *
3385 * The comparison function should have the same effects on ordering as
3386 * the function used for the initial sort.
3387 */
3388 template<typename _ForwardIterator, typename _Tp, typename _Compare>
3389 _ForwardIterator
3390 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
3391 const _Tp& __val, _Compare __comp)
3392 {
3393 typedef typename iterator_traits<_ForwardIterator>::value_type
3394 _ValueType;
3395 typedef typename iterator_traits<_ForwardIterator>::difference_type
3396 _DistanceType;
3397
3398 // concept requirements
3399 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3400 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3401 _ValueType, _Tp>)
3402 __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
3403
3404 _DistanceType __len = std::distance(__first, __last);
3405 _DistanceType __half;
3406 _ForwardIterator __middle;
3407
3408 while (__len > 0)
3409 {
3410 __half = __len >> 1;
3411 __middle = __first;
3412 std::advance(__middle, __half);
3413 if (__comp(*__middle, __val))
3414 {
3415 __first = __middle;
3416 ++__first;
3417 __len = __len - __half - 1;
3418 }
3419 else
3420 __len = __half;
3421 }
3422 return __first;
3423 }
3424
3425 /**
3426 * @brief Finds the last position in which @a val could be inserted
3427 * without changing the ordering.
3428 * @param first An iterator.
3429 * @param last Another iterator.
3430 * @param val The search term.
3431 * @return An iterator pointing to the first element greater than @a val,
3432 * or end() if no elements are greater than @a val.
3433 * @ingroup binarysearch
3434 */
3435 template<typename _ForwardIterator, typename _Tp>
3436 _ForwardIterator
3437 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
3438 const _Tp& __val)
3439 {
3440 typedef typename iterator_traits<_ForwardIterator>::value_type
3441 _ValueType;
3442 typedef typename iterator_traits<_ForwardIterator>::difference_type
3443 _DistanceType;
3444
3445 // concept requirements
3446 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3447 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
3448 __glibcxx_requires_partitioned(__first, __last, __val);
3449
3450 _DistanceType __len = std::distance(__first, __last);
3451 _DistanceType __half;
3452 _ForwardIterator __middle;
3453
3454 while (__len > 0)
3455 {
3456 __half = __len >> 1;
3457 __middle = __first;
3458 std::advance(__middle, __half);
3459 if (__val < *__middle)
3460 __len = __half;
3461 else
3462 {
3463 __first = __middle;
3464 ++__first;
3465 __len = __len - __half - 1;
3466 }
3467 }
3468 return __first;
3469 }
3470
3471 /**
3472 * @brief Finds the last position in which @a val could be inserted
3473 * without changing the ordering.
3474 * @param first An iterator.
3475 * @param last Another iterator.
3476 * @param val The search term.
3477 * @param comp A functor to use for comparisons.
3478 * @return An iterator pointing to the first element greater than @a val,
3479 * or end() if no elements are greater than @a val.
3480 * @ingroup binarysearch
3481 *
3482 * The comparison function should have the same effects on ordering as
3483 * the function used for the initial sort.
3484 */
3485 template<typename _ForwardIterator, typename _Tp, typename _Compare>
3486 _ForwardIterator
3487 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
3488 const _Tp& __val, _Compare __comp)
3489 {
3490 typedef typename iterator_traits<_ForwardIterator>::value_type
3491 _ValueType;
3492 typedef typename iterator_traits<_ForwardIterator>::difference_type
3493 _DistanceType;
3494
3495 // concept requirements
3496 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3497 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3498 _Tp, _ValueType>)
3499 __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
3500
3501 _DistanceType __len = std::distance(__first, __last);
3502 _DistanceType __half;
3503 _ForwardIterator __middle;
3504
3505 while (__len > 0)
3506 {
3507 __half = __len >> 1;
3508 __middle = __first;
3509 std::advance(__middle, __half);
3510 if (__comp(__val, *__middle))
3511 __len = __half;
3512 else
3513 {
3514 __first = __middle;
3515 ++__first;
3516 __len = __len - __half - 1;
3517 }
3518 }
3519 return __first;
3520 }
3521
3522 /**
3523 * @brief Finds the largest subrange in which @a val could be inserted
3524 * at any place in it without changing the ordering.
3525 * @param first An iterator.
3526 * @param last Another iterator.
3527 * @param val The search term.
3528 * @return An pair of iterators defining the subrange.
3529 * @ingroup binarysearch
3530 *
3531 * This is equivalent to
3532 * @code
3533 * std::make_pair(lower_bound(first, last, val),
3534 * upper_bound(first, last, val))
3535 * @endcode
3536 * but does not actually call those functions.
3537 */
3538 template<typename _ForwardIterator, typename _Tp>
3539 pair<_ForwardIterator, _ForwardIterator>
3540 equal_range(_ForwardIterator __first, _ForwardIterator __last,
3541 const _Tp& __val)
3542 {
3543 typedef typename iterator_traits<_ForwardIterator>::value_type
3544 _ValueType;
3545 typedef typename iterator_traits<_ForwardIterator>::difference_type
3546 _DistanceType;
3547
3548 // concept requirements
3549 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3550 __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
3551 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
3552 __glibcxx_requires_partitioned(__first, __last, __val);
3553
3554 _DistanceType __len = std::distance(__first, __last);
3555 _DistanceType __half;
3556 _ForwardIterator __middle, __left, __right;
3557
3558 while (__len > 0)
3559 {
3560 __half = __len >> 1;
3561 __middle = __first;
3562 std::advance(__middle, __half);
3563 if (*__middle < __val)
3564 {
3565 __first = __middle;
3566 ++__first;
3567 __len = __len - __half - 1;
3568 }
3569 else if (__val < *__middle)
3570 __len = __half;
3571 else
3572 {
3573 __left = std::lower_bound(__first, __middle, __val);
3574 std::advance(__first, __len);
3575 __right = std::upper_bound(++__middle, __first, __val);
3576 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
3577 }
3578 }
3579 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
3580 }
3581
3582 /**
3583 * @brief Finds the largest subrange in which @a val could be inserted
3584 * at any place in it without changing the ordering.
3585 * @param first An iterator.
3586 * @param last Another iterator.
3587 * @param val The search term.
3588 * @param comp A functor to use for comparisons.
3589 * @return An pair of iterators defining the subrange.
3590 * @ingroup binarysearch
3591 *
3592 * This is equivalent to
3593 * @code
3594 * std::make_pair(lower_bound(first, last, val, comp),
3595 * upper_bound(first, last, val, comp))
3596 * @endcode
3597 * but does not actually call those functions.
3598 */
3599 template<typename _ForwardIterator, typename _Tp, typename _Compare>
3600 pair<_ForwardIterator, _ForwardIterator>
3601 equal_range(_ForwardIterator __first, _ForwardIterator __last,
3602 const _Tp& __val,
3603 _Compare __comp)
3604 {
3605 typedef typename iterator_traits<_ForwardIterator>::value_type
3606 _ValueType;
3607 typedef typename iterator_traits<_ForwardIterator>::difference_type
3608 _DistanceType;
3609
3610 // concept requirements
3611 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3612 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3613 _ValueType, _Tp>)
3614 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3615 _Tp, _ValueType>)
3616 __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
3617
3618 _DistanceType __len = std::distance(__first, __last);
3619 _DistanceType __half;
3620 _ForwardIterator __middle, __left, __right;
3621
3622 while (__len > 0)
3623 {
3624 __half = __len >> 1;
3625 __middle = __first;
3626 std::advance(__middle, __half);
3627 if (__comp(*__middle, __val))
3628 {
3629 __first = __middle;
3630 ++__first;
3631 __len = __len - __half - 1;
3632 }
3633 else if (__comp(__val, *__middle))
3634 __len = __half;
3635 else
3636 {
3637 __left = std::lower_bound(__first, __middle, __val, __comp);
3638 std::advance(__first, __len);
3639 __right = std::upper_bound(++__middle, __first, __val, __comp);
3640 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
3641 }
3642 }
3643 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
3644 }
3645
3646 /**
3647 * @brief Determines whether an element exists in a range.
3648 * @param first An iterator.
3649 * @param last Another iterator.
3650 * @param val The search term.
3651 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
3652 * @ingroup binarysearch
3653 *
3654 * Note that this does not actually return an iterator to @a val. For
3655 * that, use std::find or a container's specialized find member functions.
3656 */
3657 template<typename _ForwardIterator, typename _Tp>
3658 bool
3659 binary_search(_ForwardIterator __first, _ForwardIterator __last,
3660 const _Tp& __val)
3661 {
3662 typedef typename iterator_traits<_ForwardIterator>::value_type
3663 _ValueType;
3664
3665 // concept requirements
3666 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3667 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
3668 __glibcxx_requires_partitioned(__first, __last, __val);
3669
3670 _ForwardIterator __i = std::lower_bound(__first, __last, __val);
3671 return __i != __last && !(__val < *__i);
3672 }
3673
3674 /**
3675 * @brief Determines whether an element exists in a range.
3676 * @param first An iterator.
3677 * @param last Another iterator.
3678 * @param val The search term.
3679 * @param comp A functor to use for comparisons.
3680 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
3681 * @ingroup binarysearch
3682 *
3683 * Note that this does not actually return an iterator to @a val. For
3684 * that, use std::find or a container's specialized find member functions.
3685 *
3686 * The comparison function should have the same effects on ordering as
3687 * the function used for the initial sort.
3688 */
3689 template<typename _ForwardIterator, typename _Tp, typename _Compare>
3690 bool
3691 binary_search(_ForwardIterator __first, _ForwardIterator __last,
3692 const _Tp& __val, _Compare __comp)
3693 {
3694 typedef typename iterator_traits<_ForwardIterator>::value_type
3695 _ValueType;
3696
3697 // concept requirements
3698 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3699 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3700 _Tp, _ValueType>)
3701 __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
3702
3703 _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
3704 return __i != __last && !bool(__comp(__val, *__i));
3705 }
3706
3707 /**
3708 * @brief Merges two sorted ranges.
3709 * @param first1 An iterator.
3710 * @param first2 Another iterator.
3711 * @param last1 Another iterator.
3712 * @param last2 Another iterator.
3713 * @param result An iterator pointing to the end of the merged range.
3714 * @return An iterator pointing to the first element "not less than" @a val.
3715 *
3716 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3717 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
3718 * must be sorted, and the output range must not overlap with either of
3719 * the input ranges. The sort is @e stable, that is, for equivalent
3720 * elements in the two ranges, elements from the first range will always
3721 * come before elements from the second.
3722 */
3723 template<typename _InputIterator1, typename _InputIterator2,
3724 typename _OutputIterator>
3725 _OutputIterator
3726 merge(_InputIterator1 __first1, _InputIterator1 __last1,
3727 _InputIterator2 __first2, _InputIterator2 __last2,
3728 _OutputIterator __result)
3729 {
3730 typedef typename iterator_traits<_InputIterator1>::value_type
3731 _ValueType1;
3732 typedef typename iterator_traits<_InputIterator2>::value_type
3733 _ValueType2;
3734
3735 // concept requirements
3736 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3737 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3738 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3739 _ValueType1>)
3740 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3741 _ValueType2>)
3742 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
3743 __glibcxx_requires_sorted(__first1, __last1);
3744 __glibcxx_requires_sorted(__first2, __last2);
3745
3746 while (__first1 != __last1 && __first2 != __last2)
3747 {
3748 if (*__first2 < *__first1)
3749 {
3750 *__result = *__first2;
3751 ++__first2;
3752 }
3753 else
3754 {
3755 *__result = *__first1;
3756 ++__first1;
3757 }
3758 ++__result;
3759 }
3760 return std::copy(__first2, __last2, std::copy(__first1, __last1,
3761 __result));
3762 }
3763
3764 /**
3765 * @brief Merges two sorted ranges.
3766 * @param first1 An iterator.
3767 * @param first2 Another iterator.
3768 * @param last1 Another iterator.
3769 * @param last2 Another iterator.
3770 * @param result An iterator pointing to the end of the merged range.
3771 * @param comp A functor to use for comparisons.
3772 * @return An iterator pointing to the first element "not less than" @a val.
3773 *
3774 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3775 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
3776 * must be sorted, and the output range must not overlap with either of
3777 * the input ranges. The sort is @e stable, that is, for equivalent
3778 * elements in the two ranges, elements from the first range will always
3779 * come before elements from the second.
3780 *
3781 * The comparison function should have the same effects on ordering as
3782 * the function used for the initial sort.
3783 */
3784 template<typename _InputIterator1, typename _InputIterator2,
3785 typename _OutputIterator, typename _Compare>
3786 _OutputIterator
3787 merge(_InputIterator1 __first1, _InputIterator1 __last1,
3788 _InputIterator2 __first2, _InputIterator2 __last2,
3789 _OutputIterator __result, _Compare __comp)
3790 {
3791 typedef typename iterator_traits<_InputIterator1>::value_type
3792 _ValueType1;
3793 typedef typename iterator_traits<_InputIterator2>::value_type
3794 _ValueType2;
3795
3796 // concept requirements
3797 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3798 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3799 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3800 _ValueType1>)
3801 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3802 _ValueType2>)
3803 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3804 _ValueType2, _ValueType1>)
3805 __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
3806 __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
3807
3808 while (__first1 != __last1 && __first2 != __last2)
3809 {
3810 if (__comp(*__first2, *__first1))
3811 {
3812 *__result = *__first2;
3813 ++__first2;
3814 }
3815 else
3816 {
3817 *__result = *__first1;
3818 ++__first1;
3819 }
3820 ++__result;
3821 }
3822 return std::copy(__first2, __last2, std::copy(__first1, __last1,
3823 __result));
3824 }
3825
3826 /**
3827 * @if maint
3828 * This is a helper function for the merge routines.
3829 * @endif
3830 */
3831 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
3832 typename _BidirectionalIterator3>
3833 _BidirectionalIterator3
3834 __merge_backward(_BidirectionalIterator1 __first1,
3835 _BidirectionalIterator1 __last1,
3836 _BidirectionalIterator2 __first2,
3837 _BidirectionalIterator2 __last2,
3838 _BidirectionalIterator3 __result)
3839 {
3840 if (__first1 == __last1)
3841 return std::copy_backward(__first2, __last2, __result);
3842 if (__first2 == __last2)
3843 return std::copy_backward(__first1, __last1, __result);
3844 --__last1;
3845 --__last2;
3846 while (true)
3847 {
3848 if (*__last2 < *__last1)
3849 {
3850 *--__result = *__last1;
3851 if (__first1 == __last1)
3852 return std::copy_backward(__first2, ++__last2, __result);
3853 --__last1;
3854 }
3855 else
3856 {
3857 *--__result = *__last2;
3858 if (__first2 == __last2)
3859 return std::copy_backward(__first1, ++__last1, __result);
3860 --__last2;
3861 }
3862 }
3863 }
3864
3865 /**
3866 * @if maint
3867 * This is a helper function for the merge routines.
3868 * @endif
3869 */
3870 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
3871 typename _BidirectionalIterator3, typename _Compare>
3872 _BidirectionalIterator3
3873 __merge_backward(_BidirectionalIterator1 __first1,
3874 _BidirectionalIterator1 __last1,
3875 _BidirectionalIterator2 __first2,
3876 _BidirectionalIterator2 __last2,
3877 _BidirectionalIterator3 __result,
3878 _Compare __comp)
3879 {
3880 if (__first1 == __last1)
3881 return std::copy_backward(__first2, __last2, __result);
3882 if (__first2 == __last2)
3883 return std::copy_backward(__first1, __last1, __result);
3884 --__last1;
3885 --__last2;
3886 while (true)
3887 {
3888 if (__comp(*__last2, *__last1))
3889 {
3890 *--__result = *__last1;
3891 if (__first1 == __last1)
3892 return std::copy_backward(__first2, ++__last2, __result);
3893 --__last1;
3894 }
3895 else
3896 {
3897 *--__result = *__last2;
3898 if (__first2 == __last2)
3899 return std::copy_backward(__first1, ++__last1, __result);
3900 --__last2;
3901 }
3902 }
3903 }
3904
3905 /**
3906 * @if maint
3907 * This is a helper function for the merge routines.
3908 * @endif
3909 */
3910 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
3911 typename _Distance>
3912 _BidirectionalIterator1
3913 __rotate_adaptive(_BidirectionalIterator1 __first,
3914 _BidirectionalIterator1 __middle,
3915 _BidirectionalIterator1 __last,
3916 _Distance __len1, _Distance __len2,
3917 _BidirectionalIterator2 __buffer,
3918 _Distance __buffer_size)
3919 {
3920 _BidirectionalIterator2 __buffer_end;
3921 if (__len1 > __len2 && __len2 <= __buffer_size)
3922 {
3923 __buffer_end = std::copy(__middle, __last, __buffer);
3924 std::copy_backward(__first, __middle, __last);
3925 return std::copy(__buffer, __buffer_end, __first);
3926 }
3927 else if (__len1 <= __buffer_size)
3928 {
3929 __buffer_end = std::copy(__first, __middle, __buffer);
3930 std::copy(__middle, __last, __first);
3931 return std::copy_backward(__buffer, __buffer_end, __last);
3932 }
3933 else
3934 {
3935 std::rotate(__first, __middle, __last);
3936 std::advance(__first, std::distance(__middle, __last));
3937 return __first;
3938 }
3939 }
3940
3941 /**
3942 * @if maint
3943 * This is a helper function for the merge routines.
3944 * @endif
3945 */
3946 template<typename _BidirectionalIterator, typename _Distance,
3947 typename _Pointer>
3948 void
3949 __merge_adaptive(_BidirectionalIterator __first,
3950 _BidirectionalIterator __middle,
3951 _BidirectionalIterator __last,
3952 _Distance __len1, _Distance __len2,
3953 _Pointer __buffer, _Distance __buffer_size)
3954 {
3955 if (__len1 <= __len2 && __len1 <= __buffer_size)
3956 {
3957 _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
3958 std::merge(__buffer, __buffer_end, __middle, __last, __first);
3959 }
3960 else if (__len2 <= __buffer_size)
3961 {
3962 _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
3963 std::__merge_backward(__first, __middle, __buffer,
3964 __buffer_end, __last);
3965 }
3966 else
3967 {
3968 _BidirectionalIterator __first_cut = __first;
3969 _BidirectionalIterator __second_cut = __middle;
3970 _Distance __len11 = 0;
3971 _Distance __len22 = 0;
3972 if (__len1 > __len2)
3973 {
3974 __len11 = __len1 / 2;
3975 std::advance(__first_cut, __len11);
3976 __second_cut = std::lower_bound(__middle, __last,
3977 *__first_cut);
3978 __len22 = std::distance(__middle, __second_cut);
3979 }
3980 else
3981 {
3982 __len22 = __len2 / 2;
3983 std::advance(__second_cut, __len22);
3984 __first_cut = std::upper_bound(__first, __middle,
3985 *__second_cut);
3986 __len11 = std::distance(__first, __first_cut);
3987 }
3988 _BidirectionalIterator __new_middle =
3989 std::__rotate_adaptive(__first_cut, __middle, __second_cut,
3990 __len1 - __len11, __len22, __buffer,
3991 __buffer_size);
3992 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3993 __len22, __buffer, __buffer_size);
3994 std::__merge_adaptive(__new_middle, __second_cut, __last,
3995 __len1 - __len11,
3996 __len2 - __len22, __buffer, __buffer_size);
3997 }
3998 }
3999
4000 /**
4001 * @if maint
4002 * This is a helper function for the merge routines.
4003 * @endif
4004 */
4005 template<typename _BidirectionalIterator, typename _Distance, typename _Pointer,
4006 typename _Compare>
4007 void
4008 __merge_adaptive(_BidirectionalIterator __first,
4009 _BidirectionalIterator __middle,
4010 _BidirectionalIterator __last,
4011 _Distance __len1, _Distance __len2,
4012 _Pointer __buffer, _Distance __buffer_size,
4013 _Compare __comp)
4014 {
4015 if (__len1 <= __len2 && __len1 <= __buffer_size)
4016 {
4017 _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
4018 std::merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
4019 }
4020 else if (__len2 <= __buffer_size)
4021 {
4022 _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
4023 std::__merge_backward(__first, __middle, __buffer, __buffer_end,
4024 __last, __comp);
4025 }
4026 else
4027 {
4028 _BidirectionalIterator __first_cut = __first;
4029 _BidirectionalIterator __second_cut = __middle;
4030 _Distance __len11 = 0;
4031 _Distance __len22 = 0;
4032 if (__len1 > __len2)
4033 {
4034 __len11 = __len1 / 2;
4035 std::advance(__first_cut, __len11);
4036 __second_cut = std::lower_bound(__middle, __last, *__first_cut,
4037 __comp);
4038 __len22 = std::distance(__middle, __second_cut);
4039 }
4040 else
4041 {
4042 __len22 = __len2 / 2;
4043 std::advance(__second_cut, __len22);
4044 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
4045 __comp);
4046 __len11 = std::distance(__first, __first_cut);
4047 }
4048 _BidirectionalIterator __new_middle =
4049 std::__rotate_adaptive(__first_cut, __middle, __second_cut,
4050 __len1 - __len11, __len22, __buffer,
4051 __buffer_size);
4052 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
4053 __len22, __buffer, __buffer_size, __comp);
4054 std::__merge_adaptive(__new_middle, __second_cut, __last,
4055 __len1 - __len11,
4056 __len2 - __len22, __buffer,
4057 __buffer_size, __comp);
4058 }
4059 }
4060
4061 /**
4062 * @if maint
4063 * This is a helper function for the merge routines.
4064 * @endif
4065 */
4066 template<typename _BidirectionalIterator, typename _Distance>
4067 void
4068 __merge_without_buffer(_BidirectionalIterator __first,
4069 _BidirectionalIterator __middle,
4070 _BidirectionalIterator __last,
4071 _Distance __len1, _Distance __len2)
4072 {
4073 if (__len1 == 0 || __len2 == 0)
4074 return;
4075 if (__len1 + __len2 == 2)
4076 {
4077 if (*__middle < *__first)
4078 std::iter_swap(__first, __middle);
4079 return;
4080 }
4081 _BidirectionalIterator __first_cut = __first;
4082 _BidirectionalIterator __second_cut = __middle;
4083 _Distance __len11 = 0;
4084 _Distance __len22 = 0;
4085 if (__len1 > __len2)
4086 {
4087 __len11 = __len1 / 2;
4088 std::advance(__first_cut, __len11);
4089 __second_cut = std::lower_bound(__middle, __last, *__first_cut);
4090 __len22 = std::distance(__middle, __second_cut);
4091 }
4092 else
4093 {
4094 __len22 = __len2 / 2;
4095 std::advance(__second_cut, __len22);
4096 __first_cut = std::upper_bound(__first, __middle, *__second_cut);
4097 __len11 = std::distance(__first, __first_cut);
4098 }
4099 std::rotate(__first_cut, __middle, __second_cut);
4100 _BidirectionalIterator __new_middle = __first_cut;
4101 std::advance(__new_middle, std::distance(__middle, __second_cut));
4102 std::__merge_without_buffer(__first, __first_cut, __new_middle,
4103 __len11, __len22);
4104 std::__merge_without_buffer(__new_middle, __second_cut, __last,
4105 __len1 - __len11, __len2 - __len22);
4106 }
4107
4108 /**
4109 * @if maint
4110 * This is a helper function for the merge routines.
4111 * @endif
4112 */
4113 template<typename _BidirectionalIterator, typename _Distance,
4114 typename _Compare>
4115 void
4116 __merge_without_buffer(_BidirectionalIterator __first,
4117 _BidirectionalIterator __middle,
4118 _BidirectionalIterator __last,
4119 _Distance __len1, _Distance __len2,
4120 _Compare __comp)
4121 {
4122 if (__len1 == 0 || __len2 == 0)
4123 return;
4124 if (__len1 + __len2 == 2)
4125 {
4126 if (__comp(*__middle, *__first))
4127 std::iter_swap(__first, __middle);
4128 return;
4129 }
4130 _BidirectionalIterator __first_cut = __first;
4131 _BidirectionalIterator __second_cut = __middle;
4132 _Distance __len11 = 0;
4133 _Distance __len22 = 0;
4134 if (__len1 > __len2)
4135 {
4136 __len11 = __len1 / 2;
4137 std::advance(__first_cut, __len11);
4138 __second_cut = std::lower_bound(__middle, __last, *__first_cut,
4139 __comp);
4140 __len22 = std::distance(__middle, __second_cut);
4141 }
4142 else
4143 {
4144 __len22 = __len2 / 2;
4145 std::advance(__second_cut, __len22);
4146 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
4147 __comp);
4148 __len11 = std::distance(__first, __first_cut);
4149 }
4150 std::rotate(__first_cut, __middle, __second_cut);
4151 _BidirectionalIterator __new_middle = __first_cut;
4152 std::advance(__new_middle, std::distance(__middle, __second_cut));
4153 std::__merge_without_buffer(__first, __first_cut, __new_middle,
4154 __len11, __len22, __comp);
4155 std::__merge_without_buffer(__new_middle, __second_cut, __last,
4156 __len1 - __len11, __len2 - __len22, __comp);
4157 }
4158
4159 /**
4160 * @brief Merges two sorted ranges in place.
4161 * @param first An iterator.
4162 * @param middle Another iterator.
4163 * @param last Another iterator.
4164 * @return Nothing.
4165 *
4166 * Merges two sorted and consecutive ranges, [first,middle) and
4167 * [middle,last), and puts the result in [first,last). The output will
4168 * be sorted. The sort is @e stable, that is, for equivalent
4169 * elements in the two ranges, elements from the first range will always
4170 * come before elements from the second.
4171 *
4172 * If enough additional memory is available, this takes (last-first)-1
4173 * comparisons. Otherwise an NlogN algorithm is used, where N is
4174 * distance(first,last).
4175 */
4176 template<typename _BidirectionalIterator>
4177 void
4178 inplace_merge(_BidirectionalIterator __first,
4179 _BidirectionalIterator __middle,
4180 _BidirectionalIterator __last)
4181 {
4182 typedef typename iterator_traits<_BidirectionalIterator>::value_type
4183 _ValueType;
4184 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
4185 _DistanceType;
4186
4187 // concept requirements
4188 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
4189 _BidirectionalIterator>)
4190 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
4191 __glibcxx_requires_sorted(__first, __middle);
4192 __glibcxx_requires_sorted(__middle, __last);
4193
4194 if (__first == __middle || __middle == __last)
4195 return;
4196
4197 _DistanceType __len1 = std::distance(__first, __middle);
4198 _DistanceType __len2 = std::distance(__middle, __last);
4199
4200 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
4201 __last);
4202 if (__buf.begin() == 0)
4203 std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
4204 else
4205 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
4206 __buf.begin(), _DistanceType(__buf.size()));
4207 }
4208
4209 /**
4210 * @brief Merges two sorted ranges in place.
4211 * @param first An iterator.
4212 * @param middle Another iterator.
4213 * @param last Another iterator.
4214 * @param comp A functor to use for comparisons.
4215 * @return Nothing.
4216 *
4217 * Merges two sorted and consecutive ranges, [first,middle) and
4218 * [middle,last), and puts the result in [first,last). The output will
4219 * be sorted. The sort is @e stable, that is, for equivalent
4220 * elements in the two ranges, elements from the first range will always
4221 * come before elements from the second.
4222 *
4223 * If enough additional memory is available, this takes (last-first)-1
4224 * comparisons. Otherwise an NlogN algorithm is used, where N is
4225 * distance(first,last).
4226 *
4227 * The comparison function should have the same effects on ordering as
4228 * the function used for the initial sort.
4229 */
4230 template<typename _BidirectionalIterator, typename _Compare>
4231 void
4232 inplace_merge(_BidirectionalIterator __first,
4233 _BidirectionalIterator __middle,
4234 _BidirectionalIterator __last,
4235 _Compare __comp)
4236 {
4237 typedef typename iterator_traits<_BidirectionalIterator>::value_type
4238 _ValueType;
4239 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
4240 _DistanceType;
4241
4242 // concept requirements
4243 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
4244 _BidirectionalIterator>)
4245 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4246 _ValueType, _ValueType>)
4247 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
4248 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
4249
4250 if (__first == __middle || __middle == __last)
4251 return;
4252
4253 const _DistanceType __len1 = std::distance(__first, __middle);
4254 const _DistanceType __len2 = std::distance(__middle, __last);
4255
4256 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
4257 __last);
4258 if (__buf.begin() == 0)
4259 std::__merge_without_buffer(__first, __middle, __last, __len1,
4260 __len2, __comp);
4261 else
4262 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
4263 __buf.begin(), _DistanceType(__buf.size()),
4264 __comp);
4265 }
4266
4267 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
4268 typename _Distance>
4269 void
4270 __merge_sort_loop(_RandomAccessIterator1 __first,
4271 _RandomAccessIterator1 __last,
4272 _RandomAccessIterator2 __result,
4273 _Distance __step_size)
4274 {
4275 const _Distance __two_step = 2 * __step_size;
4276
4277 while (__last - __first >= __two_step)
4278 {
4279 __result = std::merge(__first, __first + __step_size,
4280 __first + __step_size, __first + __two_step,
4281 __result);
4282 __first += __two_step;
4283 }
4284
4285 __step_size = std::min(_Distance(__last - __first), __step_size);
4286 std::merge(__first, __first + __step_size, __first + __step_size, __last,
4287 __result);
4288 }
4289
4290 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
4291 typename _Distance, typename _Compare>
4292 void
4293 __merge_sort_loop(_RandomAccessIterator1 __first,
4294 _RandomAccessIterator1 __last,
4295 _RandomAccessIterator2 __result, _Distance __step_size,
4296 _Compare __comp)
4297 {
4298 const _Distance __two_step = 2 * __step_size;
4299
4300 while (__last - __first >= __two_step)
4301 {
4302 __result = std::merge(__first, __first + __step_size,
4303 __first + __step_size, __first + __two_step,
4304 __result,
4305 __comp);
4306 __first += __two_step;
4307 }
4308 __step_size = std::min(_Distance(__last - __first), __step_size);
4309
4310 std::merge(__first, __first + __step_size,
4311 __first + __step_size, __last,
4312 __result,
4313 __comp);
4314 }
4315
4316 template<typename _RandomAccessIterator, typename _Distance>
4317 void
4318 __chunk_insertion_sort(_RandomAccessIterator __first,
4319 _RandomAccessIterator __last,
4320 _Distance __chunk_size)
4321 {
4322 while (__last - __first >= __chunk_size)
4323 {
4324 std::__insertion_sort(__first, __first + __chunk_size);
4325 __first += __chunk_size;
4326 }
4327 std::__insertion_sort(__first, __last);
4328 }
4329
4330 template<typename _RandomAccessIterator, typename _Distance, typename _Compare>
4331 void
4332 __chunk_insertion_sort(_RandomAccessIterator __first,
4333 _RandomAccessIterator __last,
4334 _Distance __chunk_size, _Compare __comp)
4335 {
4336 while (__last - __first >= __chunk_size)
4337 {
4338 std::__insertion_sort(__first, __first + __chunk_size, __comp);
4339 __first += __chunk_size;
4340 }
4341 std::__insertion_sort(__first, __last, __comp);
4342 }
4343
4344 enum { _S_chunk_size = 7 };
4345
4346 template<typename _RandomAccessIterator, typename _Pointer>
4347 void
4348 __merge_sort_with_buffer(_RandomAccessIterator __first,
4349 _RandomAccessIterator __last,
4350 _Pointer __buffer)
4351 {
4352 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4353 _Distance;
4354
4355 const _Distance __len = __last - __first;
4356 const _Pointer __buffer_last = __buffer + __len;
4357
4358 _Distance __step_size = _S_chunk_size;
4359 std::__chunk_insertion_sort(__first, __last, __step_size);
4360
4361 while (__step_size < __len)
4362 {
4363 std::__merge_sort_loop(__first, __last, __buffer, __step_size);
4364 __step_size *= 2;
4365 std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
4366 __step_size *= 2;
4367 }
4368 }
4369
4370 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
4371 void
4372 __merge_sort_with_buffer(_RandomAccessIterator __first,
4373 _RandomAccessIterator __last,
4374 _Pointer __buffer, _Compare __comp)
4375 {
4376 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4377 _Distance;
4378
4379 const _Distance __len = __last - __first;
4380 const _Pointer __buffer_last = __buffer + __len;
4381
4382 _Distance __step_size = _S_chunk_size;
4383 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
4384
4385 while (__step_size < __len)
4386 {
4387 std::__merge_sort_loop(__first, __last, __buffer,
4388 __step_size, __comp);
4389 __step_size *= 2;
4390 std::__merge_sort_loop(__buffer, __buffer_last, __first,
4391 __step_size, __comp);
4392 __step_size *= 2;
4393 }
4394 }
4395
4396 template<typename _RandomAccessIterator, typename _Pointer,
4397 typename _Distance>
4398 void
4399 __stable_sort_adaptive(_RandomAccessIterator __first,
4400 _RandomAccessIterator __last,
4401 _Pointer __buffer, _Distance __buffer_size)
4402 {
4403 const _Distance __len = (__last - __first + 1) / 2;
4404 const _RandomAccessIterator __middle = __first + __len;
4405 if (__len > __buffer_size)
4406 {
4407 std::__stable_sort_adaptive(__first, __middle,
4408 __buffer, __buffer_size);
4409 std::__stable_sort_adaptive(__middle, __last,
4410 __buffer, __buffer_size);
4411 }
4412 else
4413 {
4414 std::__merge_sort_with_buffer(__first, __middle, __buffer);
4415 std::__merge_sort_with_buffer(__middle, __last, __buffer);
4416 }
4417 std::__merge_adaptive(__first, __middle, __last,
4418 _Distance(__middle - __first),
4419 _Distance(__last - __middle),
4420 __buffer, __buffer_size);
4421 }
4422
4423 template<typename _RandomAccessIterator, typename _Pointer,
4424 typename _Distance, typename _Compare>
4425 void
4426 __stable_sort_adaptive(_RandomAccessIterator __first,
4427 _RandomAccessIterator __last,
4428 _Pointer __buffer, _Distance __buffer_size,
4429 _Compare __comp)
4430 {
4431 const _Distance __len = (__last - __first + 1) / 2;
4432 const _RandomAccessIterator __middle = __first + __len;
4433 if (__len > __buffer_size)
4434 {
4435 std::__stable_sort_adaptive(__first, __middle, __buffer,
4436 __buffer_size, __comp);
4437 std::__stable_sort_adaptive(__middle, __last, __buffer,
4438 __buffer_size, __comp);
4439 }
4440 else
4441 {
4442 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
4443 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
4444 }
4445 std::__merge_adaptive(__first, __middle, __last,
4446 _Distance(__middle - __first),
4447 _Distance(__last - __middle),
4448 __buffer, __buffer_size,
4449 __comp);
4450 }
4451
4452 /**
4453 * @if maint
4454 * This is a helper function for the stable sorting routines.
4455 * @endif
4456 */
4457 template<typename _RandomAccessIterator>
4458 void
4459 __inplace_stable_sort(_RandomAccessIterator __first,
4460 _RandomAccessIterator __last)
4461 {
4462 if (__last - __first < 15)
4463 {
4464 std::__insertion_sort(__first, __last);
4465 return;
4466 }
4467 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
4468 std::__inplace_stable_sort(__first, __middle);
4469 std::__inplace_stable_sort(__middle, __last);
4470 std::__merge_without_buffer(__first, __middle, __last,
4471 __middle - __first,
4472 __last - __middle);
4473 }
4474
4475 /**
4476 * @if maint
4477 * This is a helper function for the stable sorting routines.
4478 * @endif
4479 */
4480 template<typename _RandomAccessIterator, typename _Compare>
4481 void
4482 __inplace_stable_sort(_RandomAccessIterator __first,
4483 _RandomAccessIterator __last, _Compare __comp)
4484 {
4485 if (__last - __first < 15)
4486 {
4487 std::__insertion_sort(__first, __last, __comp);
4488 return;
4489 }
4490 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
4491 std::__inplace_stable_sort(__first, __middle, __comp);
4492 std::__inplace_stable_sort(__middle, __last, __comp);
4493 std::__merge_without_buffer(__first, __middle, __last,
4494 __middle - __first,
4495 __last - __middle,
4496 __comp);
4497 }
4498
4499 /**
4500 * @brief Sort the elements of a sequence, preserving the relative order
4501 * of equivalent elements.
4502 * @param first An iterator.
4503 * @param last Another iterator.
4504 * @return Nothing.
4505 *
4506 * Sorts the elements in the range @p [first,last) in ascending order,
4507 * such that @p *(i+1)<*i is false for each iterator @p i in the range
4508 * @p [first,last-1).
4509 *
4510 * The relative ordering of equivalent elements is preserved, so any two
4511 * elements @p x and @p y in the range @p [first,last) such that
4512 * @p x<y is false and @p y<x is false will have the same relative
4513 * ordering after calling @p stable_sort().
4514 */
4515 template<typename _RandomAccessIterator>
4516 inline void
4517 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4518 {
4519 typedef typename iterator_traits<_RandomAccessIterator>::value_type
4520 _ValueType;
4521 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4522 _DistanceType;
4523
4524 // concept requirements
4525 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4526 _RandomAccessIterator>)
4527 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
4528 __glibcxx_requires_valid_range(__first, __last);
4529
4530 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
4531 __last);
4532 if (__buf.begin() == 0)
4533 std::__inplace_stable_sort(__first, __last);
4534 else
4535 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
4536 _DistanceType(__buf.size()));
4537 }
4538
4539 /**
4540 * @brief Sort the elements of a sequence using a predicate for comparison,
4541 * preserving the relative order of equivalent elements.
4542 * @param first An iterator.
4543 * @param last Another iterator.
4544 * @param comp A comparison functor.
4545 * @return Nothing.
4546 *
4547 * Sorts the elements in the range @p [first,last) in ascending order,
4548 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the
4549 * range @p [first,last-1).
4550 *
4551 * The relative ordering of equivalent elements is preserved, so any two
4552 * elements @p x and @p y in the range @p [first,last) such that
4553 * @p comp(x,y) is false and @p comp(y,x) is false will have the same
4554 * relative ordering after calling @p stable_sort().
4555 */
4556 template<typename _RandomAccessIterator, typename _Compare>
4557 inline void
4558 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4559 _Compare __comp)
4560 {
4561 typedef typename iterator_traits<_RandomAccessIterator>::value_type
4562 _ValueType;
4563 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4564 _DistanceType;
4565
4566 // concept requirements
4567 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4568 _RandomAccessIterator>)
4569 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4570 _ValueType,
4571 _ValueType>)
4572 __glibcxx_requires_valid_range(__first, __last);
4573
4574 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
4575 __last);
4576 if (__buf.begin() == 0)
4577 std::__inplace_stable_sort(__first, __last, __comp);
4578 else
4579 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
4580 _DistanceType(__buf.size()), __comp);
4581 }
4582
4583 // Set algorithms: includes, set_union, set_intersection, set_difference,
4584 // set_symmetric_difference. All of these algorithms have the precondition
4585 // that their input ranges are sorted and the postcondition that their output
4586 // ranges are sorted.
4587
4588 /**
4589 * @brief Determines whether all elements of a sequence exists in a range.
4590 * @param first1 Start of search range.
4591 * @param last1 End of search range.
4592 * @param first2 Start of sequence
4593 * @param last2 End of sequence.
4594 * @return True if each element in [first2,last2) is contained in order
4595 * within [first1,last1). False otherwise.
4596 * @ingroup setoperations
4597 *
4598 * This operation expects both [first1,last1) and [first2,last2) to be
4599 * sorted. Searches for the presence of each element in [first2,last2)
4600 * within [first1,last1). The iterators over each range only move forward,
4601 * so this is a linear algorithm. If an element in [first2,last2) is not
4602 * found before the search iterator reaches @a last2, false is returned.
4603 */
4604 template<typename _InputIterator1, typename _InputIterator2>
4605 bool
4606 includes(_InputIterator1 __first1, _InputIterator1 __last1,
4607 _InputIterator2 __first2, _InputIterator2 __last2)
4608 {
4609 typedef typename iterator_traits<_InputIterator1>::value_type
4610 _ValueType1;
4611 typedef typename iterator_traits<_InputIterator2>::value_type
4612 _ValueType2;
4613
4614 // concept requirements
4615 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4616 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4617 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
4618 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
4619 __glibcxx_requires_sorted(__first1, __last1);
4620 __glibcxx_requires_sorted(__first2, __last2);
4621
4622 while (__first1 != __last1 && __first2 != __last2)
4623 if (*__first2 < *__first1)
4624 return false;
4625 else if(*__first1 < *__first2)
4626 ++__first1;
4627 else
4628 ++__first1, ++__first2;
4629
4630 return __first2 == __last2;
4631 }
4632
4633 /**
4634 * @brief Determines whether all elements of a sequence exists in a range
4635 * using comparison.
4636 * @param first1 Start of search range.
4637 * @param last1 End of search range.
4638 * @param first2 Start of sequence
4639 * @param last2 End of sequence.
4640 * @param comp Comparison function to use.
4641 * @return True if each element in [first2,last2) is contained in order
4642 * within [first1,last1) according to comp. False otherwise.
4643 * @ingroup setoperations
4644 *
4645 * This operation expects both [first1,last1) and [first2,last2) to be
4646 * sorted. Searches for the presence of each element in [first2,last2)
4647 * within [first1,last1), using comp to decide. The iterators over each
4648 * range only move forward, so this is a linear algorithm. If an element
4649 * in [first2,last2) is not found before the search iterator reaches @a
4650 * last2, false is returned.
4651 */
4652 template<typename _InputIterator1, typename _InputIterator2,
4653 typename _Compare>
4654 bool
4655 includes(_InputIterator1 __first1, _InputIterator1 __last1,
4656 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
4657 {
4658 typedef typename iterator_traits<_InputIterator1>::value_type
4659 _ValueType1;
4660 typedef typename iterator_traits<_InputIterator2>::value_type
4661 _ValueType2;
4662
4663 // concept requirements
4664 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4665 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4666 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4667 _ValueType1, _ValueType2>)
4668 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4669 _ValueType2, _ValueType1>)
4670 __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
4671 __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
4672
4673 while (__first1 != __last1 && __first2 != __last2)
4674 if (__comp(*__first2, *__first1))
4675 return false;
4676 else if(__comp(*__first1, *__first2))
4677 ++__first1;
4678 else
4679 ++__first1, ++__first2;
4680
4681 return __first2 == __last2;
4682 }
4683
4684 /**
4685 * @brief Return the union of two sorted ranges.
4686 * @param first1 Start of first range.
4687 * @param last1 End of first range.
4688 * @param first2 Start of second range.
4689 * @param last2 End of second range.
4690 * @return End of the output range.
4691 * @ingroup setoperations
4692 *
4693 * This operation iterates over both ranges, copying elements present in
4694 * each range in order to the output range. Iterators increment for each
4695 * range. When the current element of one range is less than the other,
4696 * that element is copied and the iterator advanced. If an element is
4697 * contained in both ranges, the element from the first range is copied and
4698 * both ranges advance. The output range may not overlap either input
4699 * range.
4700 */
4701 template<typename _InputIterator1, typename _InputIterator2,
4702 typename _OutputIterator>
4703 _OutputIterator
4704 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4705 _InputIterator2 __first2, _InputIterator2 __last2,
4706 _OutputIterator __result)
4707 {
4708 typedef typename iterator_traits<_InputIterator1>::value_type
4709 _ValueType1;
4710 typedef typename iterator_traits<_InputIterator2>::value_type
4711 _ValueType2;
4712
4713 // concept requirements
4714 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4715 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4716 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4717 _ValueType1>)
4718 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4719 _ValueType2>)
4720 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
4721 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
4722 __glibcxx_requires_sorted(__first1, __last1);
4723 __glibcxx_requires_sorted(__first2, __last2);
4724
4725 while (__first1 != __last1 && __first2 != __last2)
4726 {
4727 if (*__first1 < *__first2)
4728 {
4729 *__result = *__first1;
4730 ++__first1;
4731 }
4732 else if (*__first2 < *__first1)
4733 {
4734 *__result = *__first2;
4735 ++__first2;
4736 }
4737 else
4738 {
4739 *__result = *__first1;
4740 ++__first1;
4741 ++__first2;
4742 }
4743 ++__result;
4744 }
4745 return std::copy(__first2, __last2, std::copy(__first1, __last1,
4746 __result));
4747 }
4748
4749 /**
4750 * @brief Return the union of two sorted ranges using a comparison functor.
4751 * @param first1 Start of first range.
4752 * @param last1 End of first range.
4753 * @param first2 Start of second range.
4754 * @param last2 End of second range.
4755 * @param comp The comparison functor.
4756 * @return End of the output range.
4757 * @ingroup setoperations
4758 *
4759 * This operation iterates over both ranges, copying elements present in
4760 * each range in order to the output range. Iterators increment for each
4761 * range. When the current element of one range is less than the other
4762 * according to @a comp, that element is copied and the iterator advanced.
4763 * If an equivalent element according to @a comp is contained in both
4764 * ranges, the element from the first range is copied and both ranges
4765 * advance. The output range may not overlap either input range.
4766 */
4767 template<typename _InputIterator1, typename _InputIterator2,
4768 typename _OutputIterator, typename _Compare>
4769 _OutputIterator
4770 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4771 _InputIterator2 __first2, _InputIterator2 __last2,
4772 _OutputIterator __result, _Compare __comp)
4773 {
4774 typedef typename iterator_traits<_InputIterator1>::value_type
4775 _ValueType1;
4776 typedef typename iterator_traits<_InputIterator2>::value_type
4777 _ValueType2;
4778
4779 // concept requirements
4780 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4781 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4782 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4783 _ValueType1>)
4784 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4785 _ValueType2>)
4786 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4787 _ValueType1, _ValueType2>)
4788 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4789 _ValueType2, _ValueType1>)
4790 __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
4791 __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
4792
4793 while (__first1 != __last1 && __first2 != __last2)
4794 {
4795 if (__comp(*__first1, *__first2))
4796 {
4797 *__result = *__first1;
4798 ++__first1;
4799 }
4800 else if (__comp(*__first2, *__first1))
4801 {
4802 *__result = *__first2;
4803 ++__first2;
4804 }
4805 else
4806 {
4807 *__result = *__first1;
4808 ++__first1;
4809 ++__first2;
4810 }
4811 ++__result;
4812 }
4813 return std::copy(__first2, __last2, std::copy(__first1, __last1,
4814 __result));
4815 }
4816
4817 /**
4818 * @brief Return the intersection of two sorted ranges.
4819 * @param first1 Start of first range.
4820 * @param last1 End of first range.
4821 * @param first2 Start of second range.
4822 * @param last2 End of second range.
4823 * @return End of the output range.
4824 * @ingroup setoperations
4825 *
4826 * This operation iterates over both ranges, copying elements present in
4827 * both ranges in order to the output range. Iterators increment for each
4828 * range. When the current element of one range is less than the other,
4829 * that iterator advances. If an element is contained in both ranges, the
4830 * element from the first range is copied and both ranges advance. The
4831 * output range may not overlap either input range.
4832 */
4833 template<typename _InputIterator1, typename _InputIterator2,
4834 typename _OutputIterator>
4835 _OutputIterator
4836 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
4837 _InputIterator2 __first2, _InputIterator2 __last2,
4838 _OutputIterator __result)
4839 {
4840 typedef typename iterator_traits<_InputIterator1>::value_type
4841 _ValueType1;
4842 typedef typename iterator_traits<_InputIterator2>::value_type
4843 _ValueType2;
4844
4845 // concept requirements
4846 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4847 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4848 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4849 _ValueType1>)
4850 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
4851 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
4852 __glibcxx_requires_sorted(__first1, __last1);
4853 __glibcxx_requires_sorted(__first2, __last2);
4854
4855 while (__first1 != __last1 && __first2 != __last2)
4856 if (*__first1 < *__first2)
4857 ++__first1;
4858 else if (*__first2 < *__first1)
4859 ++__first2;
4860 else
4861 {
4862 *__result = *__first1;
4863 ++__first1;
4864 ++__first2;
4865 ++__result;
4866 }
4867 return __result;
4868 }
4869
4870 /**
4871 * @brief Return the intersection of two sorted ranges using comparison
4872 * functor.
4873 * @param first1 Start of first range.
4874 * @param last1 End of first range.
4875 * @param first2 Start of second range.
4876 * @param last2 End of second range.
4877 * @param comp The comparison functor.
4878 * @return End of the output range.
4879 * @ingroup setoperations
4880 *
4881 * This operation iterates over both ranges, copying elements present in
4882 * both ranges in order to the output range. Iterators increment for each
4883 * range. When the current element of one range is less than the other
4884 * according to @a comp, that iterator advances. If an element is
4885 * contained in both ranges according to @a comp, the element from the
4886 * first range is copied and both ranges advance. The output range may not
4887 * overlap either input range.
4888 */
4889 template<typename _InputIterator1, typename _InputIterator2,
4890 typename _OutputIterator, typename _Compare>
4891 _OutputIterator
4892 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
4893 _InputIterator2 __first2, _InputIterator2 __last2,
4894 _OutputIterator __result, _Compare __comp)
4895 {
4896 typedef typename iterator_traits<_InputIterator1>::value_type
4897 _ValueType1;
4898 typedef typename iterator_traits<_InputIterator2>::value_type
4899 _ValueType2;
4900
4901 // concept requirements
4902 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4903 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4904 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4905 _ValueType1>)
4906 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4907 _ValueType1, _ValueType2>)
4908 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4909 _ValueType2, _ValueType1>)
4910 __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
4911 __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
4912
4913 while (__first1 != __last1 && __first2 != __last2)
4914 if (__comp(*__first1, *__first2))
4915 ++__first1;
4916 else if (__comp(*__first2, *__first1))
4917 ++__first2;
4918 else
4919 {
4920 *__result = *__first1;
4921 ++__first1;
4922 ++__first2;
4923 ++__result;
4924 }
4925 return __result;
4926 }
4927
4928 /**
4929 * @brief Return the difference of two sorted ranges.
4930 * @param first1 Start of first range.
4931 * @param last1 End of first range.
4932 * @param first2 Start of second range.
4933 * @param last2 End of second range.
4934 * @return End of the output range.
4935 * @ingroup setoperations
4936 *
4937 * This operation iterates over both ranges, copying elements present in
4938 * the first range but not the second in order to the output range.
4939 * Iterators increment for each range. When the current element of the
4940 * first range is less than the second, that element is copied and the
4941 * iterator advances. If the current element of the second range is less,
4942 * the iterator advances, but no element is copied. If an element is
4943 * contained in both ranges, no elements are copied and both ranges
4944 * advance. The output range may not overlap either input range.
4945 */
4946 template<typename _InputIterator1, typename _InputIterator2,
4947 typename _OutputIterator>
4948 _OutputIterator
4949 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
4950 _InputIterator2 __first2, _InputIterator2 __last2,
4951 _OutputIterator __result)
4952 {
4953 typedef typename iterator_traits<_InputIterator1>::value_type
4954 _ValueType1;
4955 typedef typename iterator_traits<_InputIterator2>::value_type
4956 _ValueType2;
4957
4958 // concept requirements
4959 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4960 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4961 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4962 _ValueType1>)
4963 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
4964 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
4965 __glibcxx_requires_sorted(__first1, __last1);
4966 __glibcxx_requires_sorted(__first2, __last2);
4967
4968 while (__first1 != __last1 && __first2 != __last2)
4969 if (*__first1 < *__first2)
4970 {
4971 *__result = *__first1;
4972 ++__first1;
4973 ++__result;
4974 }
4975 else if (*__first2 < *__first1)
4976 ++__first2;
4977 else
4978 {
4979 ++__first1;
4980 ++__first2;
4981 }
4982 return std::copy(__first1, __last1, __result);
4983 }
4984
4985 /**
4986 * @brief Return the difference of two sorted ranges using comparison
4987 * functor.
4988 * @param first1 Start of first range.
4989 * @param last1 End of first range.
4990 * @param first2 Start of second range.
4991 * @param last2 End of second range.
4992 * @param comp The comparison functor.
4993 * @return End of the output range.
4994 * @ingroup setoperations
4995 *
4996 * This operation iterates over both ranges, copying elements present in
4997 * the first range but not the second in order to the output range.
4998 * Iterators increment for each range. When the current element of the
4999 * first range is less than the second according to @a comp, that element
5000 * is copied and the iterator advances. If the current element of the
5001 * second range is less, no element is copied and the iterator advances.
5002 * If an element is contained in both ranges according to @a comp, no
5003 * elements are copied and both ranges advance. The output range may not
5004 * overlap either input range.
5005 */
5006 template<typename _InputIterator1, typename _InputIterator2,
5007 typename _OutputIterator, typename _Compare>
5008 _OutputIterator
5009 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5010 _InputIterator2 __first2, _InputIterator2 __last2,
5011 _OutputIterator __result, _Compare __comp)
5012 {
5013 typedef typename iterator_traits<_InputIterator1>::value_type
5014 _ValueType1;
5015 typedef typename iterator_traits<_InputIterator2>::value_type
5016 _ValueType2;
5017
5018 // concept requirements
5019 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5020 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5021 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5022 _ValueType1>)
5023 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5024 _ValueType1, _ValueType2>)
5025 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5026 _ValueType2, _ValueType1>)
5027 __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
5028 __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
5029
5030 while (__first1 != __last1 && __first2 != __last2)
5031 if (__comp(*__first1, *__first2))
5032 {
5033 *__result = *__first1;
5034 ++__first1;
5035 ++__result;
5036 }
5037 else if (__comp(*__first2, *__first1))
5038 ++__first2;
5039 else
5040 {
5041 ++__first1;
5042 ++__first2;
5043 }
5044 return std::copy(__first1, __last1, __result);
5045 }
5046
5047 /**
5048 * @brief Return the symmetric difference of two sorted ranges.
5049 * @param first1 Start of first range.
5050 * @param last1 End of first range.
5051 * @param first2 Start of second range.
5052 * @param last2 End of second range.
5053 * @return End of the output range.
5054 * @ingroup setoperations
5055 *
5056 * This operation iterates over both ranges, copying elements present in
5057 * one range but not the other in order to the output range. Iterators
5058 * increment for each range. When the current element of one range is less
5059 * than the other, that element is copied and the iterator advances. If an
5060 * element is contained in both ranges, no elements are copied and both
5061 * ranges advance. The output range may not overlap either input range.
5062 */
5063 template<typename _InputIterator1, typename _InputIterator2,
5064 typename _OutputIterator>
5065 _OutputIterator
5066 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5067 _InputIterator2 __first2, _InputIterator2 __last2,
5068 _OutputIterator __result)
5069 {
5070 typedef typename iterator_traits<_InputIterator1>::value_type
5071 _ValueType1;
5072 typedef typename iterator_traits<_InputIterator2>::value_type
5073 _ValueType2;
5074
5075 // concept requirements
5076 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5077 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5078 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5079 _ValueType1>)
5080 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5081 _ValueType2>)
5082 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5083 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5084 __glibcxx_requires_sorted(__first1, __last1);
5085 __glibcxx_requires_sorted(__first2, __last2);
5086
5087 while (__first1 != __last1 && __first2 != __last2)
5088 if (*__first1 < *__first2)
5089 {
5090 *__result = *__first1;
5091 ++__first1;
5092 ++__result;
5093 }
5094 else if (*__first2 < *__first1)
5095 {
5096 *__result = *__first2;
5097 ++__first2;
5098 ++__result;
5099 }
5100 else
5101 {
5102 ++__first1;
5103 ++__first2;
5104 }
5105 return std::copy(__first2, __last2, std::copy(__first1,
5106 __last1, __result));
5107 }
5108
5109 /**
5110 * @brief Return the symmetric difference of two sorted ranges using
5111 * comparison functor.
5112 * @param first1 Start of first range.
5113 * @param last1 End of first range.
5114 * @param first2 Start of second range.
5115 * @param last2 End of second range.
5116 * @param comp The comparison functor.
5117 * @return End of the output range.
5118 * @ingroup setoperations
5119 *
5120 * This operation iterates over both ranges, copying elements present in
5121 * one range but not the other in order to the output range. Iterators
5122 * increment for each range. When the current element of one range is less
5123 * than the other according to @a comp, that element is copied and the
5124 * iterator advances. If an element is contained in both ranges according
5125 * to @a comp, no elements are copied and both ranges advance. The output
5126 * range may not overlap either input range.
5127 */
5128 template<typename _InputIterator1, typename _InputIterator2,
5129 typename _OutputIterator, typename _Compare>
5130 _OutputIterator
5131 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5132 _InputIterator2 __first2, _InputIterator2 __last2,
5133 _OutputIterator __result,
5134 _Compare __comp)
5135 {
5136 typedef typename iterator_traits<_InputIterator1>::value_type
5137 _ValueType1;
5138 typedef typename iterator_traits<_InputIterator2>::value_type
5139 _ValueType2;
5140
5141 // concept requirements
5142 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5143 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5144 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5145 _ValueType1>)
5146 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5147 _ValueType2>)
5148 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5149 _ValueType1, _ValueType2>)
5150 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5151 _ValueType2, _ValueType1>)
5152 __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
5153 __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
5154
5155 while (__first1 != __last1 && __first2 != __last2)
5156 if (__comp(*__first1, *__first2))
5157 {
5158 *__result = *__first1;
5159 ++__first1;
5160 ++__result;
5161 }
5162 else if (__comp(*__first2, *__first1))
5163 {
5164 *__result = *__first2;
5165 ++__first2;
5166 ++__result;
5167 }
5168 else
5169 {
5170 ++__first1;
5171 ++__first2;
5172 }
5173 return std::copy(__first2, __last2, std::copy(__first1,
5174 __last1, __result));
5175 }
5176
5177 // min_element and max_element, with and without an explicitly supplied
5178 // comparison function.
5179
5180 /**
5181 * @brief Return the minimum element in a range.
5182 * @param first Start of range.
5183 * @param last End of range.
5184 * @return Iterator referencing the first instance of the smallest value.
5185 */
5186 template<typename _ForwardIterator>
5187 _ForwardIterator
5188 min_element(_ForwardIterator __first, _ForwardIterator __last)
5189 {
5190 // concept requirements
5191 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5192 __glibcxx_function_requires(_LessThanComparableConcept<
5193 typename iterator_traits<_ForwardIterator>::value_type>)
5194 __glibcxx_requires_valid_range(__first, __last);
5195
5196 if (__first == __last)
5197 return __first;
5198 _ForwardIterator __result = __first;
5199 while (++__first != __last)
5200 if (*__first < *__result)
5201 __result = __first;
5202 return __result;
5203 }
5204
5205 /**
5206 * @brief Return the minimum element in a range using comparison functor.
5207 * @param first Start of range.
5208 * @param last End of range.
5209 * @param comp Comparison functor.
5210 * @return Iterator referencing the first instance of the smallest value
5211 * according to comp.
5212 */
5213 template<typename _ForwardIterator, typename _Compare>
5214 _ForwardIterator
5215 min_element(_ForwardIterator __first, _ForwardIterator __last,
5216 _Compare __comp)
5217 {
5218 // concept requirements
5219 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5220 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5221 typename iterator_traits<_ForwardIterator>::value_type,
5222 typename iterator_traits<_ForwardIterator>::value_type>)
5223 __glibcxx_requires_valid_range(__first, __last);
5224
5225 if (__first == __last)
5226 return __first;
5227 _ForwardIterator __result = __first;
5228 while (++__first != __last)
5229 if (__comp(*__first, *__result))
5230 __result = __first;
5231 return __result;
5232 }
5233
5234 /**
5235 * @brief Return the maximum element in a range.
5236 * @param first Start of range.
5237 * @param last End of range.
5238 * @return Iterator referencing the first instance of the largest value.
5239 */
5240 template<typename _ForwardIterator>
5241 _ForwardIterator
5242 max_element(_ForwardIterator __first, _ForwardIterator __last)
5243 {
5244 // concept requirements
5245 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5246 __glibcxx_function_requires(_LessThanComparableConcept<
5247 typename iterator_traits<_ForwardIterator>::value_type>)
5248 __glibcxx_requires_valid_range(__first, __last);
5249
5250 if (__first == __last)
5251 return __first;
5252 _ForwardIterator __result = __first;
5253 while (++__first != __last)
5254 if (*__result < *__first)
5255 __result = __first;
5256 return __result;
5257 }
5258
5259 /**
5260 * @brief Return the maximum element in a range using comparison functor.
5261 * @param first Start of range.
5262 * @param last End of range.
5263 * @param comp Comparison functor.
5264 * @return Iterator referencing the first instance of the largest value
5265 * according to comp.
5266 */
5267 template<typename _ForwardIterator, typename _Compare>
5268 _ForwardIterator
5269 max_element(_ForwardIterator __first, _ForwardIterator __last,
5270 _Compare __comp)
5271 {
5272 // concept requirements
5273 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5274 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5275 typename iterator_traits<_ForwardIterator>::value_type,
5276 typename iterator_traits<_ForwardIterator>::value_type>)
5277 __glibcxx_requires_valid_range(__first, __last);
5278
5279 if (__first == __last) return __first;
5280 _ForwardIterator __result = __first;
5281 while (++__first != __last)
5282 if (__comp(*__result, *__first))
5283 __result = __first;
5284 return __result;
5285 }
5286
5287 // next_permutation and prev_permutation, with and without an explicitly
5288 // supplied comparison function.
5289
5290 /**
5291 * @brief Permute range into the next "dictionary" ordering.
5292 * @param first Start of range.
5293 * @param last End of range.
5294 * @return False if wrapped to first permutation, true otherwise.
5295 *
5296 * Treats all permutations of the range as a set of "dictionary" sorted
5297 * sequences. Permutes the current sequence into the next one of this set.
5298 * Returns true if there are more sequences to generate. If the sequence
5299 * is the largest of the set, the smallest is generated and false returned.
5300 */
5301 template<typename _BidirectionalIterator>
5302 bool
5303 next_permutation(_BidirectionalIterator __first,
5304 _BidirectionalIterator __last)
5305 {
5306 // concept requirements
5307 __glibcxx_function_requires(_BidirectionalIteratorConcept<
5308 _BidirectionalIterator>)
5309 __glibcxx_function_requires(_LessThanComparableConcept<
5310 typename iterator_traits<_BidirectionalIterator>::value_type>)
5311 __glibcxx_requires_valid_range(__first, __last);
5312
5313 if (__first == __last)
5314 return false;
5315 _BidirectionalIterator __i = __first;
5316 ++__i;
5317 if (__i == __last)
5318 return false;
5319 __i = __last;
5320 --__i;
5321
5322 for(;;)
5323 {
5324 _BidirectionalIterator __ii = __i;
5325 --__i;
5326 if (*__i < *__ii)
5327 {
5328 _BidirectionalIterator __j = __last;
5329 while (!(*__i < *--__j))
5330 {}
5331 std::iter_swap(__i, __j);
5332 std::reverse(__ii, __last);
5333 return true;
5334 }
5335 if (__i == __first)
5336 {
5337 std::reverse(__first, __last);
5338 return false;
5339 }
5340 }
5341 }
5342
5343 /**
5344 * @brief Permute range into the next "dictionary" ordering using
5345 * comparison functor.
5346 * @param first Start of range.
5347 * @param last End of range.
5348 * @param comp
5349 * @return False if wrapped to first permutation, true otherwise.
5350 *
5351 * Treats all permutations of the range [first,last) as a set of
5352 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
5353 * sequence into the next one of this set. Returns true if there are more
5354 * sequences to generate. If the sequence is the largest of the set, the
5355 * smallest is generated and false returned.
5356 */
5357 template<typename _BidirectionalIterator, typename _Compare>
5358 bool
5359 next_permutation(_BidirectionalIterator __first,
5360 _BidirectionalIterator __last, _Compare __comp)
5361 {
5362 // concept requirements
5363 __glibcxx_function_requires(_BidirectionalIteratorConcept<
5364 _BidirectionalIterator>)
5365 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5366 typename iterator_traits<_BidirectionalIterator>::value_type,
5367 typename iterator_traits<_BidirectionalIterator>::value_type>)
5368 __glibcxx_requires_valid_range(__first, __last);
5369
5370 if (__first == __last)
5371 return false;
5372 _BidirectionalIterator __i = __first;
5373 ++__i;
5374 if (__i == __last)
5375 return false;
5376 __i = __last;
5377 --__i;
5378
5379 for(;;)
5380 {
5381 _BidirectionalIterator __ii = __i;
5382 --__i;
5383 if (__comp(*__i, *__ii))
5384 {
5385 _BidirectionalIterator __j = __last;
5386 while (!bool(__comp(*__i, *--__j)))
5387 {}
5388 std::iter_swap(__i, __j);
5389 std::reverse(__ii, __last);
5390 return true;
5391 }
5392 if (__i == __first)
5393 {
5394 std::reverse(__first, __last);
5395 return false;
5396 }
5397 }
5398 }
5399
5400 /**
5401 * @brief Permute range into the previous "dictionary" ordering.
5402 * @param first Start of range.
5403 * @param last End of range.
5404 * @return False if wrapped to last permutation, true otherwise.
5405 *
5406 * Treats all permutations of the range as a set of "dictionary" sorted
5407 * sequences. Permutes the current sequence into the previous one of this
5408 * set. Returns true if there are more sequences to generate. If the
5409 * sequence is the smallest of the set, the largest is generated and false
5410 * returned.
5411 */
5412 template<typename _BidirectionalIterator>
5413 bool
5414 prev_permutation(_BidirectionalIterator __first,
5415 _BidirectionalIterator __last)
5416 {
5417 // concept requirements
5418 __glibcxx_function_requires(_BidirectionalIteratorConcept<
5419 _BidirectionalIterator>)
5420 __glibcxx_function_requires(_LessThanComparableConcept<
5421 typename iterator_traits<_BidirectionalIterator>::value_type>)
5422 __glibcxx_requires_valid_range(__first, __last);
5423
5424 if (__first == __last)
5425 return false;
5426 _BidirectionalIterator __i = __first;
5427 ++__i;
5428 if (__i == __last)
5429 return false;
5430 __i = __last;
5431 --__i;
5432
5433 for(;;)
5434 {
5435 _BidirectionalIterator __ii = __i;
5436 --__i;
5437 if (*__ii < *__i)
5438 {
5439 _BidirectionalIterator __j = __last;
5440 while (!(*--__j < *__i))
5441 {}
5442 std::iter_swap(__i, __j);
5443 std::reverse(__ii, __last);
5444 return true;
5445 }
5446 if (__i == __first)
5447 {
5448 std::reverse(__first, __last);
5449 return false;
5450 }
5451 }
5452 }
5453
5454 /**
5455 * @brief Permute range into the previous "dictionary" ordering using
5456 * comparison functor.
5457 * @param first Start of range.
5458 * @param last End of range.
5459 * @param comp
5460 * @return False if wrapped to last permutation, true otherwise.
5461 *
5462 * Treats all permutations of the range [first,last) as a set of
5463 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
5464 * sequence into the previous one of this set. Returns true if there are
5465 * more sequences to generate. If the sequence is the smallest of the set,
5466 * the largest is generated and false returned.
5467 */
5468 template<typename _BidirectionalIterator, typename _Compare>
5469 bool
5470 prev_permutation(_BidirectionalIterator __first,
5471 _BidirectionalIterator __last, _Compare __comp)
5472 {
5473 // concept requirements
5474 __glibcxx_function_requires(_BidirectionalIteratorConcept<
5475 _BidirectionalIterator>)
5476 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5477 typename iterator_traits<_BidirectionalIterator>::value_type,
5478 typename iterator_traits<_BidirectionalIterator>::value_type>)
5479 __glibcxx_requires_valid_range(__first, __last);
5480
5481 if (__first == __last)
5482 return false;
5483 _BidirectionalIterator __i = __first;
5484 ++__i;
5485 if (__i == __last)
5486 return false;
5487 __i = __last;
5488 --__i;
5489
5490 for(;;)
5491 {
5492 _BidirectionalIterator __ii = __i;
5493 --__i;
5494 if (__comp(*__ii, *__i))
5495 {
5496 _BidirectionalIterator __j = __last;
5497 while (!bool(__comp(*--__j, *__i)))
5498 {}
5499 std::iter_swap(__i, __j);
5500 std::reverse(__ii, __last);
5501 return true;
5502 }
5503 if (__i == __first)
5504 {
5505 std::reverse(__first, __last);
5506 return false;
5507 }
5508 }
5509 }
5510
5511 _GLIBCXX_END_NAMESPACE
5512
5513 #endif /* _STL_ALGO_H */