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