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