?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
stl_algo.h (transform (both signatures), generate_n): Use __typeof__ in concept checks.
[official-gcc.git] / libstdc++-v3 / include / bits / stl_algo.h
blob653aaa6a2e128d720d961809611f981824d27f29
1 // Algorithm implementation -*- C++ -*-
2
3 // Copyright (C) 2001, 2002 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 __GLIBCPP_INTERNAL_ALGO_H
62 #define __GLIBCPP_INTERNAL_ALGO_H
63
64 #include <bits/stl_heap.h>
65 #include <bits/stl_tempbuf.h> // for _Temporary_buffer
66
67 // See concept_check.h for the __glibcpp_*_requires macros.
68
69 namespace std
70 {
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 __glibcpp_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 __glibcpp_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).
148 * @p f must not modify its argument.
149 * If @p f has a return value it is ignored.
150 */
151 template<typename _InputIter, typename _Function>
152 _Function
153 for_each(_InputIter __first, _InputIter __last, _Function __f)
154 {
155 // concept requirements
156 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
157 for ( ; __first != __last; ++__first)
158 __f(*__first);
159 return __f;
160 }
161
162 /**
163 * @maint
164 * This is an overload used by find() for the Input Iterator case.
165 * @endmaint
166 */
167 template<typename _InputIter, typename _Tp>
168 inline _InputIter
169 find(_InputIter __first, _InputIter __last,
170 const _Tp& __val,
171 input_iterator_tag)
172 {
173 while (__first != __last && !(*__first == __val))
174 ++__first;
175 return __first;
176 }
177
178 /**
179 * @maint
180 * This is an overload used by find_if() for the Input Iterator case.
181 * @endmaint
182 */
183 template<typename _InputIter, typename _Predicate>
184 inline _InputIter
185 find_if(_InputIter __first, _InputIter __last,
186 _Predicate __pred,
187 input_iterator_tag)
188 {
189 while (__first != __last && !__pred(*__first))
190 ++__first;
191 return __first;
192 }
193
194 /**
195 * @maint
196 * This is an overload used by find() for the RAI case.
197 * @endmaint
198 */
199 template<typename _RandomAccessIter, typename _Tp>
200 _RandomAccessIter
201 find(_RandomAccessIter __first, _RandomAccessIter __last,
202 const _Tp& __val,
203 random_access_iterator_tag)
204 {
205 typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
206 = (__last - __first) >> 2;
207
208 for ( ; __trip_count > 0 ; --__trip_count) {
209 if (*__first == __val) return __first;
210 ++__first;
211
212 if (*__first == __val) return __first;
213 ++__first;
214
215 if (*__first == __val) return __first;
216 ++__first;
217
218 if (*__first == __val) return __first;
219 ++__first;
220 }
221
222 switch(__last - __first) {
223 case 3:
224 if (*__first == __val) return __first;
225 ++__first;
226 case 2:
227 if (*__first == __val) return __first;
228 ++__first;
229 case 1:
230 if (*__first == __val) return __first;
231 ++__first;
232 case 0:
233 default:
234 return __last;
235 }
236 }
237
238 /**
239 * @maint
240 * This is an overload used by find_if() for the RAI case.
241 * @endmaint
242 */
243 template<typename _RandomAccessIter, typename _Predicate>
244 _RandomAccessIter
245 find_if(_RandomAccessIter __first, _RandomAccessIter __last,
246 _Predicate __pred,
247 random_access_iterator_tag)
248 {
249 typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
250 = (__last - __first) >> 2;
251
252 for ( ; __trip_count > 0 ; --__trip_count) {
253 if (__pred(*__first)) return __first;
254 ++__first;
255
256 if (__pred(*__first)) return __first;
257 ++__first;
258
259 if (__pred(*__first)) return __first;
260 ++__first;
261
262 if (__pred(*__first)) return __first;
263 ++__first;
264 }
265
266 switch(__last - __first) {
267 case 3:
268 if (__pred(*__first)) return __first;
269 ++__first;
270 case 2:
271 if (__pred(*__first)) return __first;
272 ++__first;
273 case 1:
274 if (__pred(*__first)) return __first;
275 ++__first;
276 case 0:
277 default:
278 return __last;
279 }
280 }
281
282 /**
283 * @brief Find the first occurrence of a value in a sequence.
284 * @param first An input iterator.
285 * @param last An input iterator.
286 * @param val The value to find.
287 * @return The first iterator @c i in the range @p [first,last)
288 * such that @c *i == @p val, or @p last if no such iterator exists.
289 */
290 template<typename _InputIter, typename _Tp>
291 inline _InputIter
292 find(_InputIter __first, _InputIter __last,
293 const _Tp& __val)
294 {
295 // concept requirements
296 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
297 __glibcpp_function_requires(_EqualOpConcept<
298 typename iterator_traits<_InputIter>::value_type, _Tp>)
299 return find(__first, __last, __val, __iterator_category(__first));
300 }
301
302 /**
303 * @brief Find the first element in a sequence for which a predicate is true.
304 * @param first An input iterator.
305 * @param last An input iterator.
306 * @param pred A predicate.
307 * @return The first iterator @c i in the range @p [first,last)
308 * such that @p pred(*i) is true, or @p last if no such iterator exists.
309 */
310 template<typename _InputIter, typename _Predicate>
311 inline _InputIter
312 find_if(_InputIter __first, _InputIter __last,
313 _Predicate __pred)
314 {
315 // concept requirements
316 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
317 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
318 typename iterator_traits<_InputIter>::value_type>)
319 return find_if(__first, __last, __pred, __iterator_category(__first));
320 }
321
322 /**
323 * @brief Find two adjacent values in a sequence that are equal.
324 * @param first A forward iterator.
325 * @param last A forward iterator.
326 * @return The first iterator @c i such that @c i and @c i+1 are both
327 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
328 * or @p last if no such iterator exists.
329 */
330 template<typename _ForwardIter>
331 _ForwardIter
332 adjacent_find(_ForwardIter __first, _ForwardIter __last)
333 {
334 // concept requirements
335 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
336 __glibcpp_function_requires(_EqualityComparableConcept<
337 typename iterator_traits<_ForwardIter>::value_type>)
338 if (__first == __last)
339 return __last;
340 _ForwardIter __next = __first;
341 while(++__next != __last) {
342 if (*__first == *__next)
343 return __first;
344 __first = __next;
345 }
346 return __last;
347 }
348
349 /**
350 * @brief Find two adjacent values in a sequence using a predicate.
351 * @param first A forward iterator.
352 * @param last A forward iterator.
353 * @param binary_pred A binary predicate.
354 * @return The first iterator @c i such that @c i and @c i+1 are both
355 * valid iterators in @p [first,last) and such that
356 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
357 * exists.
358 */
359 template<typename _ForwardIter, typename _BinaryPredicate>
360 _ForwardIter
361 adjacent_find(_ForwardIter __first, _ForwardIter __last,
362 _BinaryPredicate __binary_pred)
363 {
364 // concept requirements
365 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
366 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
367 typename iterator_traits<_ForwardIter>::value_type,
368 typename iterator_traits<_ForwardIter>::value_type>)
369 if (__first == __last)
370 return __last;
371 _ForwardIter __next = __first;
372 while(++__next != __last) {
373 if (__binary_pred(*__first, *__next))
374 return __first;
375 __first = __next;
376 }
377 return __last;
378 }
379
380 /**
381 * @brief Count the number of copies of a value in a sequence.
382 * @param first An input iterator.
383 * @param last An input iterator.
384 * @param value The value to be counted.
385 * @return The number of iterators @c i in the range @p [first,last)
386 * for which @c *i == @p value
387 */
388 template<typename _InputIter, typename _Tp>
389 typename iterator_traits<_InputIter>::difference_type
390 count(_InputIter __first, _InputIter __last, const _Tp& __value)
391 {
392 // concept requirements
393 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
394 __glibcpp_function_requires(_EqualityComparableConcept<
395 typename iterator_traits<_InputIter>::value_type >)
396 __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
397 typename iterator_traits<_InputIter>::difference_type __n = 0;
398 for ( ; __first != __last; ++__first)
399 if (*__first == __value)
400 ++__n;
401 return __n;
402 }
403
404 /**
405 * @brief Count the elements of a sequence for which a predicate is true.
406 * @param first An input iterator.
407 * @param last An input iterator.
408 * @param pred A predicate.
409 * @return The number of iterators @c i in the range @p [first,last)
410 * for which @p pred(*i) is true.
411 */
412 template<typename _InputIter, typename _Predicate>
413 typename iterator_traits<_InputIter>::difference_type
414 count_if(_InputIter __first, _InputIter __last, _Predicate __pred)
415 {
416 // concept requirements
417 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
418 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
419 typename iterator_traits<_InputIter>::value_type>)
420 typename iterator_traits<_InputIter>::difference_type __n = 0;
421 for ( ; __first != __last; ++__first)
422 if (__pred(*__first))
423 ++__n;
424 return __n;
425 }
426
427
428 /**
429 * @brief Search a sequence for a matching sub-sequence.
430 * @param first1 A forward iterator.
431 * @param last1 A forward iterator.
432 * @param first2 A forward iterator.
433 * @param last2 A forward iterator.
434 * @return The first iterator @c i in the range
435 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
436 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
437 * such iterator exists.
438 *
439 * Searches the range @p [first1,last1) for a sub-sequence that compares
440 * equal value-by-value with the sequence given by @p [first2,last2) and
441 * returns an iterator to the first element of the sub-sequence, or
442 * @p last1 if the sub-sequence is not found.
443 *
444 * Because the sub-sequence must lie completely within the range
445 * @p [first1,last1) it must start at a position less than
446 * @p last1-(last2-first2) where @p last2-first2 is the length of the
447 * sub-sequence.
448 * This means that the returned iterator @c i will be in the range
449 * @p [first1,last1-(last2-first2))
450 */
451 template<typename _ForwardIter1, typename _ForwardIter2>
452 _ForwardIter1
453 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
454 _ForwardIter2 __first2, _ForwardIter2 __last2)
455 {
456 // concept requirements
457 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
458 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
459 __glibcpp_function_requires(_EqualOpConcept<
460 typename iterator_traits<_ForwardIter1>::value_type,
461 typename iterator_traits<_ForwardIter2>::value_type>)
462
463 // Test for empty ranges
464 if (__first1 == __last1 || __first2 == __last2)
465 return __first1;
466
467 // Test for a pattern of length 1.
468 _ForwardIter2 __tmp(__first2);
469 ++__tmp;
470 if (__tmp == __last2)
471 return find(__first1, __last1, *__first2);
472
473 // General case.
474
475 _ForwardIter2 __p1, __p;
476
477 __p1 = __first2; ++__p1;
478
479 _ForwardIter1 __current = __first1;
480
481 while (__first1 != __last1) {
482 __first1 = find(__first1, __last1, *__first2);
483 if (__first1 == __last1)
484 return __last1;
485
486 __p = __p1;
487 __current = __first1;
488 if (++__current == __last1)
489 return __last1;
490
491 while (*__current == *__p) {
492 if (++__p == __last2)
493 return __first1;
494 if (++__current == __last1)
495 return __last1;
496 }
497
498 ++__first1;
499 }
500 return __first1;
501 }
502
503 /**
504 * @brief Search a sequence for a matching sub-sequence using a predicate.
505 * @param first1 A forward iterator.
506 * @param last1 A forward iterator.
507 * @param first2 A forward iterator.
508 * @param last2 A forward iterator.
509 * @param predicate A binary predicate.
510 * @return The first iterator @c i in the range
511 * @p [first1,last1-(last2-first2)) such that
512 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
513 * @p [0,last2-first2), or @p last1 if no such iterator exists.
514 *
515 * Searches the range @p [first1,last1) for a sub-sequence that compares
516 * equal value-by-value with the sequence given by @p [first2,last2),
517 * using @p predicate to determine equality, and returns an iterator
518 * to the first element of the sub-sequence, or @p last1 if no such
519 * iterator exists.
520 *
521 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
522 */
523 template<typename _ForwardIter1, typename _ForwardIter2, typename _BinaryPred>
524 _ForwardIter1
525 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
526 _ForwardIter2 __first2, _ForwardIter2 __last2,
527 _BinaryPred __predicate)
528 {
529 // concept requirements
530 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
531 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
532 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
533 typename iterator_traits<_ForwardIter1>::value_type,
534 typename iterator_traits<_ForwardIter2>::value_type>)
535
536 // Test for empty ranges
537 if (__first1 == __last1 || __first2 == __last2)
538 return __first1;
539
540 // Test for a pattern of length 1.
541 _ForwardIter2 __tmp(__first2);
542 ++__tmp;
543 if (__tmp == __last2) {
544 while (__first1 != __last1 && !__predicate(*__first1, *__first2))
545 ++__first1;
546 return __first1;
547 }
548
549 // General case.
550
551 _ForwardIter2 __p1, __p;
552
553 __p1 = __first2; ++__p1;
554
555 _ForwardIter1 __current = __first1;
556
557 while (__first1 != __last1) {
558 while (__first1 != __last1) {
559 if (__predicate(*__first1, *__first2))
560 break;
561 ++__first1;
562 }
563 while (__first1 != __last1 && !__predicate(*__first1, *__first2))
564 ++__first1;
565 if (__first1 == __last1)
566 return __last1;
567
568 __p = __p1;
569 __current = __first1;
570 if (++__current == __last1) return __last1;
571
572 while (__predicate(*__current, *__p)) {
573 if (++__p == __last2)
574 return __first1;
575 if (++__current == __last1)
576 return __last1;
577 }
578
579 ++__first1;
580 }
581 return __first1;
582 }
583
584 /**
585 * @brief Search a sequence for a number of consecutive values.
586 * @param first A forward iterator.
587 * @param last A forward iterator.
588 * @param count The number of consecutive values.
589 * @param val The value to find.
590 * @return The first iterator @c i in the range @p [first,last-count)
591 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
592 * or @p last if no such iterator exists.
593 *
594 * Searches the range @p [first,last) for @p count consecutive elements
595 * equal to @p val.
596 */
597 template<typename _ForwardIter, typename _Integer, typename _Tp>
598 _ForwardIter
599 search_n(_ForwardIter __first, _ForwardIter __last,
600 _Integer __count, const _Tp& __val)
601 {
602 // concept requirements
603 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
604 __glibcpp_function_requires(_EqualityComparableConcept<
605 typename iterator_traits<_ForwardIter>::value_type>)
606 __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
607
608 if (__count <= 0)
609 return __first;
610 else {
611 __first = find(__first, __last, __val);
612 while (__first != __last) {
613 _Integer __n = __count - 1;
614 _ForwardIter __i = __first;
615 ++__i;
616 while (__i != __last && __n != 0 && *__i == __val) {
617 ++__i;
618 --__n;
619 }
620 if (__n == 0)
621 return __first;
622 else
623 __first = find(__i, __last, __val);
624 }
625 return __last;
626 }
627 }
628
629 /**
630 * @brief Search a sequence for a number of consecutive values using a
631 * predicate.
632 * @param first A forward iterator.
633 * @param last A forward iterator.
634 * @param count The number of consecutive values.
635 * @param val The value to find.
636 * @param binary_pred A binary predicate.
637 * @return The first iterator @c i in the range @p [first,last-count)
638 * such that @p binary_pred(*(i+N),val) is true for each @c N in the
639 * range @p [0,count), or @p last if no such iterator exists.
640 *
641 * Searches the range @p [first,last) for @p count consecutive elements
642 * for which the predicate returns true.
643 */
644 template<typename _ForwardIter, typename _Integer, typename _Tp,
645 typename _BinaryPred>
646 _ForwardIter
647 search_n(_ForwardIter __first, _ForwardIter __last,
648 _Integer __count, const _Tp& __val,
649 _BinaryPred __binary_pred)
650 {
651 // concept requirements
652 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
653 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
654 typename iterator_traits<_ForwardIter>::value_type, _Tp>)
655
656 if (__count <= 0)
657 return __first;
658 else {
659 while (__first != __last) {
660 if (__binary_pred(*__first, __val))
661 break;
662 ++__first;
663 }
664 while (__first != __last) {
665 _Integer __n = __count - 1;
666 _ForwardIter __i = __first;
667 ++__i;
668 while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
669 ++__i;
670 --__n;
671 }
672 if (__n == 0)
673 return __first;
674 else {
675 while (__i != __last) {
676 if (__binary_pred(*__i, __val))
677 break;
678 ++__i;
679 }
680 __first = __i;
681 }
682 }
683 return __last;
684 }
685 }
686
687 /**
688 * @brief Swap the elements of two sequences.
689 * @param first1 A forward iterator.
690 * @param last1 A forward iterator.
691 * @param first2 A forward iterator.
692 * @return An iterator equal to @p first2+(last1-first1).
693 *
694 * Swaps each element in the range @p [first1,last1) with the
695 * corresponding element in the range @p [first2,(last1-first1)).
696 * The ranges must not overlap.
697 */
698 template<typename _ForwardIter1, typename _ForwardIter2>
699 _ForwardIter2
700 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
701 _ForwardIter2 __first2)
702 {
703 // concept requirements
704 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>)
705 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>)
706 __glibcpp_function_requires(_ConvertibleConcept<
707 typename iterator_traits<_ForwardIter1>::value_type,
708 typename iterator_traits<_ForwardIter2>::value_type>)
709 __glibcpp_function_requires(_ConvertibleConcept<
710 typename iterator_traits<_ForwardIter2>::value_type,
711 typename iterator_traits<_ForwardIter1>::value_type>)
712
713 for ( ; __first1 != __last1; ++__first1, ++__first2)
714 iter_swap(__first1, __first2);
715 return __first2;
716 }
717
718 /**
719 * @brief Perform an operation on a sequence.
720 * @param first An input iterator.
721 * @param last An input iterator.
722 * @param result An output iterator.
723 * @param unary_op A unary operator.
724 * @return An output iterator equal to @p result+(last-first).
725 *
726 * Applies the operator to each element in the input range and assigns
727 * the results to successive elements of the output sequence.
728 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
729 * range @p [0,last-first).
730 *
731 * @p unary_op must not alter its argument.
732 */
733 template<typename _InputIter, typename _OutputIter, typename _UnaryOperation>
734 _OutputIter
735 transform(_InputIter __first, _InputIter __last,
736 _OutputIter __result, _UnaryOperation __unary_op)
737 {
738 // concept requirements
739 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
740 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
741 // "the type returned by a _UnaryOperation"
742 __typeof__(__unary_op(*__first))>)
743
744 for ( ; __first != __last; ++__first, ++__result)
745 *__result = __unary_op(*__first);
746 return __result;
747 }
748
749 /**
750 * @brief Perform an operation on corresponding elements of two sequences.
751 * @param first1 An input iterator.
752 * @param last1 An input iterator.
753 * @param first2 An input iterator.
754 * @param result An output iterator.
755 * @param binary_op A binary operator.
756 * @return An output iterator equal to @p result+(last-first).
757 *
758 * Applies the operator to the corresponding elements in the two
759 * input ranges and assigns the results to successive elements of the
760 * output sequence.
761 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
762 * @c N in the range @p [0,last1-first1).
763 *
764 * @p binary_op must not alter either of its arguments.
765 */
766 template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
767 typename _BinaryOperation>
768 _OutputIter
769 transform(_InputIter1 __first1, _InputIter1 __last1,
770 _InputIter2 __first2, _OutputIter __result,
771 _BinaryOperation __binary_op)
772 {
773 // concept requirements
774 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
775 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
776 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
777 // "the type returned by a _BinaryOperation"
778 __typeof__(__binary_op(*__first1,*__first2))>)
779
780 for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
781 *__result = __binary_op(*__first1, *__first2);
782 return __result;
783 }
784
785 /**
786 * @brief Replace each occurrence of one value in a sequence with another
787 * value.
788 * @param first A forward iterator.
789 * @param last A forward iterator.
790 * @param old_value The value to be replaced.
791 * @param new_value The replacement value.
792 * @return replace() returns no value.
793 *
794 * For each iterator @c i in the range @p [first,last) if @c *i ==
795 * @p old_value then the assignment @c *i = @p new_value is performed.
796 */
797 template<typename _ForwardIter, typename _Tp>
798 void
799 replace(_ForwardIter __first, _ForwardIter __last,
800 const _Tp& __old_value, const _Tp& __new_value)
801 {
802 // concept requirements
803 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
804 __glibcpp_function_requires(_EqualOpConcept<
805 typename iterator_traits<_ForwardIter>::value_type, _Tp>)
806 __glibcpp_function_requires(_ConvertibleConcept<_Tp,
807 typename iterator_traits<_ForwardIter>::value_type>)
808
809 for ( ; __first != __last; ++__first)
810 if (*__first == __old_value)
811 *__first = __new_value;
812 }
813
814 /**
815 * @brief Replace each value in a sequence for which a predicate returns
816 * true with another value.
817 * @param first A forward iterator.
818 * @param last A forward iterator.
819 * @param pred A predicate.
820 * @param new_value The replacement value.
821 * @return replace_if() returns no value.
822 *
823 * For each iterator @c i in the range @p [first,last) if @p pred(*i)
824 * is true then the assignment @c *i = @p new_value is performed.
825 */
826 template<typename _ForwardIter, typename _Predicate, typename _Tp>
827 void
828 replace_if(_ForwardIter __first, _ForwardIter __last,
829 _Predicate __pred, const _Tp& __new_value)
830 {
831 // concept requirements
832 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
833 __glibcpp_function_requires(_ConvertibleConcept<_Tp,
834 typename iterator_traits<_ForwardIter>::value_type>)
835 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
836 typename iterator_traits<_ForwardIter>::value_type>)
837
838 for ( ; __first != __last; ++__first)
839 if (__pred(*__first))
840 *__first = __new_value;
841 }
842
843 /**
844 * @brief Copy a sequence, replacing each element of one value with another
845 * value.
846 * @param first An input iterator.
847 * @param last An input iterator.
848 * @param result An output iterator.
849 * @param old_value The value to be replaced.
850 * @param new_value The replacement value.
851 * @return The end of the output sequence, @p result+(last-first).
852 *
853 * Copies each element in the input range @p [first,last) to the
854 * output range @p [result,result+(last-first)) replacing elements
855 * equal to @p old_value with @p new_value.
856 */
857 template<typename _InputIter, typename _OutputIter, typename _Tp>
858 _OutputIter
859 replace_copy(_InputIter __first, _InputIter __last,
860 _OutputIter __result,
861 const _Tp& __old_value, const _Tp& __new_value)
862 {
863 // concept requirements
864 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
865 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
866 typename iterator_traits<_InputIter>::value_type>)
867 __glibcpp_function_requires(_EqualOpConcept<
868 typename iterator_traits<_InputIter>::value_type, _Tp>)
869
870 for ( ; __first != __last; ++__first, ++__result)
871 *__result = *__first == __old_value ? __new_value : *__first;
872 return __result;
873 }
874
875 /**
876 * @brief Copy a sequence, replacing each value for which a predicate
877 * returns true with another value.
878 * @param first An input iterator.
879 * @param last An input iterator.
880 * @param result An output iterator.
881 * @param pred A predicate.
882 * @param new_value The replacement value.
883 * @return The end of the output sequence, @p result+(last-first).
884 *
885 * Copies each element in the range @p [first,last) to the range
886 * @p [result,result+(last-first)) replacing elements for which
887 * @p pred returns true with @p new_value.
888 */
889 template<typename _InputIter, typename _OutputIter, typename _Predicate,
890 typename _Tp>
891 _OutputIter
892 replace_copy_if(_InputIter __first, _InputIter __last,
893 _OutputIter __result,
894 _Predicate __pred, const _Tp& __new_value)
895 {
896 // concept requirements
897 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
898 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
899 typename iterator_traits<_InputIter>::value_type>)
900 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
901 typename iterator_traits<_InputIter>::value_type>)
902
903 for ( ; __first != __last; ++__first, ++__result)
904 *__result = __pred(*__first) ? __new_value : *__first;
905 return __result;
906 }
907
908 /**
909 * @brief Assign the result of a function object to each value in a
910 * sequence.
911 * @param first A forward iterator.
912 * @param last A forward iterator.
913 * @param gen A function object taking no arguments.
914 * @return generate() returns no value.
915 *
916 * Performs the assignment @c *i = @p gen() for each @c i in the range
917 * @p [first,last).
918 */
919 template<typename _ForwardIter, typename _Generator>
920 void
921 generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen)
922 {
923 // concept requirements
924 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
925 __glibcpp_function_requires(_GeneratorConcept<_Generator,
926 typename iterator_traits<_ForwardIter>::value_type>)
927
928 for ( ; __first != __last; ++__first)
929 *__first = __gen();
930 }
931
932 /**
933 * @brief Assign the result of a function object to each value in a
934 * sequence.
935 * @param first A forward iterator.
936 * @param n The length of the sequence.
937 * @param gen A function object taking no arguments.
938 * @return The end of the sequence, @p first+n
939 *
940 * Performs the assignment @c *i = @p gen() for each @c i in the range
941 * @p [first,first+n).
942 */
943 template<typename _OutputIter, typename _Size, typename _Generator>
944 _OutputIter
945 generate_n(_OutputIter __first, _Size __n, _Generator __gen)
946 {
947 // concept requirements
948 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
949 // "the type returned by a _Generator"
950 __typeof__(gen())>)
951
952 for ( ; __n > 0; --__n, ++__first)
953 *__first = __gen();
954 return __first;
955 }
956
957 /**
958 * @brief Copy a sequence, removing elements of a given value.
959 * @param first An input iterator.
960 * @param last An input iterator.
961 * @param result An output iterator.
962 * @param value The value to be removed.
963 * @return An iterator designating the end of the resulting sequence.
964 *
965 * Copies each element in the range @p [first,last) not equal to @p value
966 * to the range beginning at @p result.
967 * remove_copy() is stable, so the relative order of elements that are
968 * copied is unchanged.
969 */
970 template<typename _InputIter, typename _OutputIter, typename _Tp>
971 _OutputIter
972 remove_copy(_InputIter __first, _InputIter __last,
973 _OutputIter __result, const _Tp& __value)
974 {
975 // concept requirements
976 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
977 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
978 typename iterator_traits<_InputIter>::value_type>)
979 __glibcpp_function_requires(_EqualOpConcept<
980 typename iterator_traits<_InputIter>::value_type, _Tp>)
981
982 for ( ; __first != __last; ++__first)
983 if (!(*__first == __value)) {
984 *__result = *__first;
985 ++__result;
986 }
987 return __result;
988 }
989
990 /**
991 * @brief Copy a sequence, removing elements for which a predicate is true.
992 * @param first An input iterator.
993 * @param last An input iterator.
994 * @param result An output iterator.
995 * @param pred A predicate.
996 * @return An iterator designating the end of the resulting sequence.
997 *
998 * Copies each element in the range @p [first,last) for which
999 * @p pred returns true to the range beginning at @p result.
1000 *
1001 * remove_copy_if() is stable, so the relative order of elements that are
1002 * copied is unchanged.
1003 */
1004 template<typename _InputIter, typename _OutputIter, typename _Predicate>
1005 _OutputIter
1006 remove_copy_if(_InputIter __first, _InputIter __last,
1007 _OutputIter __result, _Predicate __pred)
1008 {
1009 // concept requirements
1010 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
1011 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
1012 typename iterator_traits<_InputIter>::value_type>)
1013 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
1014 typename iterator_traits<_InputIter>::value_type>)
1015
1016 for ( ; __first != __last; ++__first)
1017 if (!__pred(*__first)) {
1018 *__result = *__first;
1019 ++__result;
1020 }
1021 return __result;
1022 }
1023
1024 /**
1025 * @brief Remove elements from a sequence.
1026 * @param first An input iterator.
1027 * @param last An input iterator.
1028 * @param value The value to be removed.
1029 * @return An iterator designating the end of the resulting sequence.
1030 *
1031 * All elements equal to @p value are removed from the range
1032 * @p [first,last).
1033 *
1034 * remove() is stable, so the relative order of elements that are
1035 * not removed is unchanged.
1036 *
1037 * Elements between the end of the resulting sequence and @p last
1038 * are still present, but their value is unspecified.
1039 */
1040 template<typename _ForwardIter, typename _Tp>
1041 _ForwardIter
1042 remove(_ForwardIter __first, _ForwardIter __last,
1043 const _Tp& __value)
1044 {
1045 // concept requirements
1046 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
1047 __glibcpp_function_requires(_ConvertibleConcept<_Tp,
1048 typename iterator_traits<_ForwardIter>::value_type>)
1049 __glibcpp_function_requires(_EqualOpConcept<
1050 typename iterator_traits<_ForwardIter>::value_type, _Tp>)
1051
1052 __first = find(__first, __last, __value);
1053 _ForwardIter __i = __first;
1054 return __first == __last ? __first
1055 : remove_copy(++__i, __last, __first, __value);
1056 }
1057
1058 /**
1059 * @brief Remove elements from a sequence using a predicate.
1060 * @param first A forward iterator.
1061 * @param last A forward iterator.
1062 * @param pred A predicate.
1063 * @return An iterator designating the end of the resulting sequence.
1064 *
1065 * All elements for which @p pred returns true are removed from the range
1066 * @p [first,last).
1067 *
1068 * remove_if() is stable, so the relative order of elements that are
1069 * not removed is unchanged.
1070 *
1071 * Elements between the end of the resulting sequence and @p last
1072 * are still present, but their value is unspecified.
1073 */
1074 template<typename _ForwardIter, typename _Predicate>
1075 _ForwardIter
1076 remove_if(_ForwardIter __first, _ForwardIter __last,
1077 _Predicate __pred)
1078 {
1079 // concept requirements
1080 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
1081 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
1082 typename iterator_traits<_ForwardIter>::value_type>)
1083
1084 __first = find_if(__first, __last, __pred);
1085 _ForwardIter __i = __first;
1086 return __first == __last ? __first
1087 : remove_copy_if(++__i, __last, __first, __pred);
1088 }
1089
1090 /**
1091 * @maint
1092 * This is an uglified unique_copy(_InputIter, _InputIter, _OutputIter)
1093 * overloaded for output iterators.
1094 * @endmaint
1095 */
1096 template<typename _InputIter, typename _OutputIter>
1097 _OutputIter
1098 __unique_copy(_InputIter __first, _InputIter __last,
1099 _OutputIter __result,
1100 output_iterator_tag)
1101 {
1102 // concept requirements -- taken care of in dispatching function
1103 typename iterator_traits<_InputIter>::value_type __value = *__first;
1104 *__result = __value;
1105 while (++__first != __last)
1106 if (!(__value == *__first)) {
1107 __value = *__first;
1108 *++__result = __value;
1109 }
1110 return ++__result;
1111 }
1112
1113 /**
1114 * @maint
1115 * This is an uglified unique_copy(_InputIter, _InputIter, _OutputIter)
1116 * overloaded for forward iterators.
1117 * @endmaint
1118 */
1119 template<typename _InputIter, typename _ForwardIter>
1120 _ForwardIter
1121 __unique_copy(_InputIter __first, _InputIter __last,
1122 _ForwardIter __result,
1123 forward_iterator_tag)
1124 {
1125 // concept requirements -- taken care of in dispatching function
1126 *__result = *__first;
1127 while (++__first != __last)
1128 if (!(*__result == *__first))
1129 *++__result = *__first;
1130 return ++__result;
1131 }
1132
1133 /**
1134 * @brief Copy a sequence, removing consecutive duplicate values.
1135 * @param first An input iterator.
1136 * @param last An input iterator.
1137 * @param result An output iterator.
1138 * @return An iterator designating the end of the resulting sequence.
1139 *
1140 * Copies each element in the range @p [first,last) to the range
1141 * beginning at @p result, except that only the first element is copied
1142 * from groups of consecutive elements that compare equal.
1143 */
1144 template<typename _InputIter, typename _OutputIter>
1145 inline _OutputIter
1146 unique_copy(_InputIter __first, _InputIter __last,
1147 _OutputIter __result)
1148 {
1149 // concept requirements
1150 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
1151 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
1152 typename iterator_traits<_InputIter>::value_type>)
1153 __glibcpp_function_requires(_EqualityComparableConcept<
1154 typename iterator_traits<_InputIter>::value_type>)
1155
1156 typedef typename iterator_traits<_OutputIter>::iterator_category _IterType;
1157
1158 if (__first == __last) return __result;
1159 return __unique_copy(__first, __last, __result, _IterType());
1160 }
1161
1162 /**
1163 * @maint
1164 * This is an uglified
1165 * unique_copy(_InputIter, _InputIter, _OutputIter, _BinaryPredicate)
1166 * overloaded for output iterators.
1167 * @endmaint
1168 */
1169 template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate>
1170 _OutputIter
1171 __unique_copy(_InputIter __first, _InputIter __last,
1172 _OutputIter __result,
1173 _BinaryPredicate __binary_pred,
1174 output_iterator_tag)
1175 {
1176 // concept requirements -- iterators already checked
1177 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1178 typename iterator_traits<_InputIter>::value_type,
1179 typename iterator_traits<_InputIter>::value_type>)
1180
1181 typename iterator_traits<_InputIter>::value_type __value = *__first;
1182 *__result = __value;
1183 while (++__first != __last)
1184 if (!__binary_pred(__value, *__first)) {
1185 __value = *__first;
1186 *++__result = __value;
1187 }
1188 return ++__result;
1189 }
1190
1191 /**
1192 * @maint
1193 * This is an uglified
1194 * unique_copy(_InputIter, _InputIter, _OutputIter, _BinaryPredicate)
1195 * overloaded for forward iterators.
1196 * @endmaint
1197 */
1198 template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate>
1199 _ForwardIter
1200 __unique_copy(_InputIter __first, _InputIter __last,
1201 _ForwardIter __result,
1202 _BinaryPredicate __binary_pred,
1203 forward_iterator_tag)
1204 {
1205 // concept requirements -- iterators already checked
1206 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1207 typename iterator_traits<_ForwardIter>::value_type,
1208 typename iterator_traits<_InputIter>::value_type>)
1209
1210 *__result = *__first;
1211 while (++__first != __last)
1212 if (!__binary_pred(*__result, *__first)) *++__result = *__first;
1213 return ++__result;
1214 }
1215
1216 /**
1217 * @brief Copy a sequence, removing consecutive values using a predicate.
1218 * @param first An input iterator.
1219 * @param last An input iterator.
1220 * @param result An output iterator.
1221 * @param binary_pred A binary predicate.
1222 * @return An iterator designating the end of the resulting sequence.
1223 *
1224 * Copies each element in the range @p [first,last) to the range
1225 * beginning at @p result, except that only the first element is copied
1226 * from groups of consecutive elements for which @p binary_pred returns
1227 * true.
1228 * unique_copy() is stable, so the relative order of elements that are
1229 * copied is unchanged.
1230 */
1231 template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate>
1232 inline _OutputIter
1233 unique_copy(_InputIter __first, _InputIter __last,
1234 _OutputIter __result,
1235 _BinaryPredicate __binary_pred)
1236 {
1237 // concept requirements -- predicates checked later
1238 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
1239 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
1240 typename iterator_traits<_InputIter>::value_type>)
1241
1242 typedef typename iterator_traits<_OutputIter>::iterator_category _IterType;
1243
1244 if (__first == __last) return __result;
1245 return __unique_copy(__first, __last,
1246 __result, __binary_pred, _IterType());
1247 }
1248
1249 /**
1250 * @brief Remove consecutive duplicate values from a sequence.
1251 * @param first A forward iterator.
1252 * @param last A forward iterator.
1253 * @return An iterator designating the end of the resulting sequence.
1254 *
1255 * Removes all but the first element from each group of consecutive
1256 * values that compare equal.
1257 * unique() is stable, so the relative order of elements that are
1258 * not removed is unchanged.
1259 * Elements between the end of the resulting sequence and @p last
1260 * are still present, but their value is unspecified.
1261 */
1262 template<typename _ForwardIter>
1263 _ForwardIter
1264 unique(_ForwardIter __first, _ForwardIter __last)
1265 {
1266 // concept requirements
1267 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
1268 __glibcpp_function_requires(_EqualityComparableConcept<
1269 typename iterator_traits<_ForwardIter>::value_type>)
1270
1271 __first = adjacent_find(__first, __last);
1272 return unique_copy(__first, __last, __first);
1273 }
1274
1275 /**
1276 * @brief Remove consecutive values from a sequence using a predicate.
1277 * @param first A forward iterator.
1278 * @param last A forward iterator.
1279 * @param binary_pred A binary predicate.
1280 * @return An iterator designating the end of the resulting sequence.
1281 *
1282 * Removes all but the first element from each group of consecutive
1283 * values for which @p binary_pred returns true.
1284 * unique() is stable, so the relative order of elements that are
1285 * not removed is unchanged.
1286 * Elements between the end of the resulting sequence and @p last
1287 * are still present, but their value is unspecified.
1288 */
1289 template<typename _ForwardIter, typename _BinaryPredicate>
1290 _ForwardIter
1291 unique(_ForwardIter __first, _ForwardIter __last,
1292 _BinaryPredicate __binary_pred)
1293 {
1294 // concept requirements
1295 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
1296 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1297 typename iterator_traits<_ForwardIter>::value_type,
1298 typename iterator_traits<_ForwardIter>::value_type>)
1299
1300 __first = adjacent_find(__first, __last, __binary_pred);
1301 return unique_copy(__first, __last, __first, __binary_pred);
1302 }
1303
1304 /**
1305 * @maint
1306 * This is an uglified reverse(_BidirectionalIter, _BidirectionalIter)
1307 * overloaded for bidirectional iterators.
1308 * @endmaint
1309 */
1310 template<typename _BidirectionalIter>
1311 void
1312 __reverse(_BidirectionalIter __first, _BidirectionalIter __last,
1313 bidirectional_iterator_tag)
1314 {
1315 while (true)
1316 if (__first == __last || __first == --__last)
1317 return;
1318 else
1319 iter_swap(__first++, __last);
1320 }
1321
1322 /**
1323 * @maint
1324 * This is an uglified reverse(_BidirectionalIter, _BidirectionalIter)
1325 * overloaded for bidirectional iterators.
1326 * @endmaint
1327 */
1328 template<typename _RandomAccessIter>
1329 void
1330 __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
1331 random_access_iterator_tag)
1332 {
1333 while (__first < __last)
1334 iter_swap(__first++, --__last);
1335 }
1336
1337 /**
1338 * @brief Reverse a sequence.
1339 * @param first A bidirectional iterator.
1340 * @param last A bidirectional iterator.
1341 * @return reverse() returns no value.
1342 *
1343 * Reverses the order of the elements in the range @p [first,last),
1344 * so that the first element becomes the last etc.
1345 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1346 * swaps @p *(first+i) and @p *(last-(i+1))
1347 */
1348 template<typename _BidirectionalIter>
1349 inline void
1350 reverse(_BidirectionalIter __first, _BidirectionalIter __last)
1351 {
1352 // concept requirements
1353 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
1354 _BidirectionalIter>)
1355 __reverse(__first, __last, __iterator_category(__first));
1356 }
1357
1358 /**
1359 * @brief Copy a sequence, reversing its elements.
1360 * @param first A bidirectional iterator.
1361 * @param last A bidirectional iterator.
1362 * @param result An output iterator.
1363 * @return An iterator designating the end of the resulting sequence.
1364 *
1365 * Copies the elements in the range @p [first,last) to the range
1366 * @p [result,result+(last-first)) such that the order of the
1367 * elements is reversed.
1368 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1369 * performs the assignment @p *(result+(last-first)-i) = *(first+i).
1370 * The ranges @p [first,last) and @p [result,result+(last-first))
1371 * must not overlap.
1372 */
1373 template<typename _BidirectionalIter, typename _OutputIter>
1374 _OutputIter
1375 reverse_copy(_BidirectionalIter __first, _BidirectionalIter __last,
1376 _OutputIter __result)
1377 {
1378 // concept requirements
1379 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
1380 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
1381 typename iterator_traits<_BidirectionalIter>::value_type>)
1382
1383 while (__first != __last) {
1384 --__last;
1385 *__result = *__last;
1386 ++__result;
1387 }
1388 return __result;
1389 }
1390
1391 /// This is a helper function for the rotate algorithm specialized on RAIs.
1392
1393 template<typename _EuclideanRingElement>
1394 _EuclideanRingElement
1395 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1396 {
1397 while (__n != 0) {
1398 _EuclideanRingElement __t = __m % __n;
1399 __m = __n;
1400 __n = __t;
1401 }
1402 return __m;
1403 }
1404
1405 template<typename _ForwardIter>
1406 void
1407 __rotate(_ForwardIter __first,
1408 _ForwardIter __middle,
1409 _ForwardIter __last,
1410 forward_iterator_tag)
1411 {
1412 if ((__first == __middle) || (__last == __middle))
1413 return;
1414
1415 _ForwardIter __first2 = __middle;
1416 do {
1417 swap(*__first++, *__first2++);
1418 if (__first == __middle)
1419 __middle = __first2;
1420 } while (__first2 != __last);
1421
1422 __first2 = __middle;
1423
1424 while (__first2 != __last) {
1425 swap(*__first++, *__first2++);
1426 if (__first == __middle)
1427 __middle = __first2;
1428 else if (__first2 == __last)
1429 __first2 = __middle;
1430 }
1431 }
1432
1433 template<typename _BidirectionalIter>
1434 void
1435 __rotate(_BidirectionalIter __first,
1436 _BidirectionalIter __middle,
1437 _BidirectionalIter __last,
1438 bidirectional_iterator_tag)
1439 {
1440 // concept requirements
1441 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
1442 _BidirectionalIter>)
1443
1444 if ((__first == __middle) || (__last == __middle))
1445 return;
1446
1447 __reverse(__first, __middle, bidirectional_iterator_tag());
1448 __reverse(__middle, __last, bidirectional_iterator_tag());
1449
1450 while (__first != __middle && __middle != __last)
1451 swap (*__first++, *--__last);
1452
1453 if (__first == __middle) {
1454 __reverse(__middle, __last, bidirectional_iterator_tag());
1455 }
1456 else {
1457 __reverse(__first, __middle, bidirectional_iterator_tag());
1458 }
1459 }
1460
1461 template<typename _RandomAccessIter>
1462 void
1463 __rotate(_RandomAccessIter __first,
1464 _RandomAccessIter __middle,
1465 _RandomAccessIter __last,
1466 random_access_iterator_tag)
1467 {
1468 // concept requirements
1469 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
1470 _RandomAccessIter>)
1471
1472 if ((__first == __middle) || (__last == __middle))
1473 return;
1474
1475 typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
1476 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
1477
1478 _Distance __n = __last - __first;
1479 _Distance __k = __middle - __first;
1480 _Distance __l = __n - __k;
1481
1482 if (__k == __l) {
1483 swap_ranges(__first, __middle, __middle);
1484 return;
1485 }
1486
1487 _Distance __d = __gcd(__n, __k);
1488
1489 for (_Distance __i = 0; __i < __d; __i++) {
1490 _ValueType __tmp = *__first;
1491 _RandomAccessIter __p = __first;
1492
1493 if (__k < __l) {
1494 for (_Distance __j = 0; __j < __l/__d; __j++) {
1495 if (__p > __first + __l) {
1496 *__p = *(__p - __l);
1497 __p -= __l;
1498 }
1499
1500 *__p = *(__p + __k);
1501 __p += __k;
1502 }
1503 }
1504
1505 else {
1506 for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
1507 if (__p < __last - __k) {
1508 *__p = *(__p + __k);
1509 __p += __k;
1510 }
1511
1512 *__p = * (__p - __l);
1513 __p -= __l;
1514 }
1515 }
1516
1517 *__p = __tmp;
1518 ++__first;
1519 }
1520 }
1521
1522 template<typename _ForwardIter>
1523 inline void
1524 rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last)
1525 {
1526 // concept requirements
1527 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
1528
1529 typedef typename iterator_traits<_ForwardIter>::iterator_category _IterType;
1530 __rotate(__first, __middle, __last, _IterType());
1531 }
1532
1533 template<typename _ForwardIter, typename _OutputIter>
1534 _OutputIter
1535 rotate_copy(_ForwardIter __first, _ForwardIter __middle,
1536 _ForwardIter __last, _OutputIter __result)
1537 {
1538 // concept requirements
1539 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
1540 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
1541 typename iterator_traits<_ForwardIter>::value_type>)
1542
1543 return copy(__first, __middle, copy(__middle, __last, __result));
1544 }
1545
1546 // Return a random number in the range [0, __n). This function encapsulates
1547 // whether we're using rand (part of the standard C library) or lrand48
1548 // (not standard, but a much better choice whenever it's available).
1549 template<typename _Distance>
1550 inline _Distance
1551 __random_number(_Distance __n)
1552 {
1553 #ifdef _GLIBCPP_HAVE_DRAND48
1554 return lrand48() % __n;
1555 #else
1556 return rand() % __n;
1557 #endif
1558 }
1559
1560 /// 25.2.11 random_shuffle().
1561
1562 template<typename _RandomAccessIter>
1563 inline void
1564 random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last)
1565 {
1566 // concept requirements
1567 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
1568 _RandomAccessIter>)
1569
1570 if (__first == __last) return;
1571 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1572 iter_swap(__i, __first + __random_number((__i - __first) + 1));
1573 }
1574
1575 template<typename _RandomAccessIter, typename _RandomNumberGenerator>
1576 void
1577 random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
1578 _RandomNumberGenerator& __rand)
1579 {
1580 // concept requirements
1581 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
1582 _RandomAccessIter>)
1583
1584 if (__first == __last) return;
1585 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1586 iter_swap(__i, __first + __rand((__i - __first) + 1));
1587 }
1588
1589 // partition, stable_partition, and their auxiliary functions
1590
1591 template<typename _ForwardIter, typename _Predicate>
1592 _ForwardIter
1593 __partition(_ForwardIter __first, _ForwardIter __last,
1594 _Predicate __pred,
1595 forward_iterator_tag)
1596 {
1597 if (__first == __last) return __first;
1598
1599 while (__pred(*__first))
1600 if (++__first == __last) return __first;
1601
1602 _ForwardIter __next = __first;
1603
1604 while (++__next != __last)
1605 if (__pred(*__next)) {
1606 swap(*__first, *__next);
1607 ++__first;
1608 }
1609
1610 return __first;
1611 }
1612
1613 template<typename _BidirectionalIter, typename _Predicate>
1614 _BidirectionalIter
1615 __partition(_BidirectionalIter __first, _BidirectionalIter __last,
1616 _Predicate __pred,
1617 bidirectional_iterator_tag)
1618 {
1619 while (true) {
1620 while (true)
1621 if (__first == __last)
1622 return __first;
1623 else if (__pred(*__first))
1624 ++__first;
1625 else
1626 break;
1627 --__last;
1628 while (true)
1629 if (__first == __last)
1630 return __first;
1631 else if (!__pred(*__last))
1632 --__last;
1633 else
1634 break;
1635 iter_swap(__first, __last);
1636 ++__first;
1637 }
1638 }
1639
1640 template<typename _ForwardIter, typename _Predicate>
1641 inline _ForwardIter
1642 partition(_ForwardIter __first, _ForwardIter __last,
1643 _Predicate __pred)
1644 {
1645 // concept requirements
1646 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
1647 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
1648 typename iterator_traits<_ForwardIter>::value_type>)
1649
1650 return __partition(__first, __last, __pred, __iterator_category(__first));
1651 }
1652
1653
1654 template<typename _ForwardIter, typename _Predicate, typename _Distance>
1655 _ForwardIter
1656 __inplace_stable_partition(_ForwardIter __first, _ForwardIter __last,
1657 _Predicate __pred, _Distance __len)
1658 {
1659 if (__len == 1)
1660 return __pred(*__first) ? __last : __first;
1661 _ForwardIter __middle = __first;
1662 advance(__middle, __len / 2);
1663 _ForwardIter __begin = __inplace_stable_partition(__first, __middle,
1664 __pred,
1665 __len / 2);
1666 _ForwardIter __end = __inplace_stable_partition(__middle, __last,
1667 __pred,
1668 __len - __len / 2);
1669 rotate(__begin, __middle, __end);
1670 advance(__begin, distance(__middle, __end));
1671 return __begin;
1672 }
1673
1674 template<typename _ForwardIter, typename _Pointer, typename _Predicate,
1675 typename _Distance>
1676 _ForwardIter
1677 __stable_partition_adaptive(_ForwardIter __first, _ForwardIter __last,
1678 _Predicate __pred, _Distance __len,
1679 _Pointer __buffer,
1680 _Distance __buffer_size)
1681 {
1682 if (__len <= __buffer_size) {
1683 _ForwardIter __result1 = __first;
1684 _Pointer __result2 = __buffer;
1685 for ( ; __first != __last ; ++__first)
1686 if (__pred(*__first)) {
1687 *__result1 = *__first;
1688 ++__result1;
1689 }
1690 else {
1691 *__result2 = *__first;
1692 ++__result2;
1693 }
1694 copy(__buffer, __result2, __result1);
1695 return __result1;
1696 }
1697 else {
1698 _ForwardIter __middle = __first;
1699 advance(__middle, __len / 2);
1700 _ForwardIter __begin = __stable_partition_adaptive(__first, __middle,
1701 __pred,
1702 __len / 2,
1703 __buffer, __buffer_size);
1704 _ForwardIter __end = __stable_partition_adaptive( __middle, __last,
1705 __pred,
1706 __len - __len / 2,
1707 __buffer, __buffer_size);
1708 rotate(__begin, __middle, __end);
1709 advance(__begin, distance(__middle, __end));
1710 return __begin;
1711 }
1712 }
1713
1714 template<typename _ForwardIter, typename _Predicate>
1715 _ForwardIter
1716 stable_partition(_ForwardIter __first, _ForwardIter __last,
1717 _Predicate __pred)
1718 {
1719 // concept requirements
1720 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
1721 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
1722 typename iterator_traits<_ForwardIter>::value_type>)
1723
1724 if (__first == __last)
1725 return __first;
1726 else
1727 {
1728 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
1729 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
1730
1731 _Temporary_buffer<_ForwardIter, _ValueType> __buf(__first, __last);
1732 if (__buf.size() > 0)
1733 return __stable_partition_adaptive(__first, __last, __pred,
1734 _DistanceType(__buf.requested_size()),
1735 __buf.begin(), __buf.size());
1736 else
1737 return __inplace_stable_partition(__first, __last, __pred,
1738 _DistanceType(__buf.requested_size()));
1739 }
1740 }
1741
1742 template<typename _RandomAccessIter, typename _Tp>
1743 _RandomAccessIter
1744 __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last,
1745 _Tp __pivot)
1746 {
1747 while (true) {
1748 while (*__first < __pivot)
1749 ++__first;
1750 --__last;
1751 while (__pivot < *__last)
1752 --__last;
1753 if (!(__first < __last))
1754 return __first;
1755 iter_swap(__first, __last);
1756 ++__first;
1757 }
1758 }
1759
1760 template<typename _RandomAccessIter, typename _Tp, typename _Compare>
1761 _RandomAccessIter
1762 __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last,
1763 _Tp __pivot, _Compare __comp)
1764 {
1765 while (true) {
1766 while (__comp(*__first, __pivot))
1767 ++__first;
1768 --__last;
1769 while (__comp(__pivot, *__last))
1770 --__last;
1771 if (!(__first < __last))
1772 return __first;
1773 iter_swap(__first, __last);
1774 ++__first;
1775 }
1776 }
1777
1778 const int __stl_threshold = 16;
1779
1780 // sort() and its auxiliary functions.
1781
1782 template<typename _RandomAccessIter, typename _Tp>
1783 void
1784 __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val)
1785 {
1786 _RandomAccessIter __next = __last;
1787 --__next;
1788 while (__val < *__next) {
1789 *__last = *__next;
1790 __last = __next;
1791 --__next;
1792 }
1793 *__last = __val;
1794 }
1795
1796 template<typename _RandomAccessIter, typename _Tp, typename _Compare>
1797 void
1798 __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, _Compare __comp)
1799 {
1800 _RandomAccessIter __next = __last;
1801 --__next;
1802 while (__comp(__val, *__next)) {
1803 *__last = *__next;
1804 __last = __next;
1805 --__next;
1806 }
1807 *__last = __val;
1808 }
1809
1810 template<typename _RandomAccessIter>
1811 void
1812 __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
1813 {
1814 if (__first == __last) return;
1815
1816 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1817 {
1818 typename iterator_traits<_RandomAccessIter>::value_type __val = *__i;
1819 if (__val < *__first) {
1820 copy_backward(__first, __i, __i + 1);
1821 *__first = __val;
1822 }
1823 else
1824 __unguarded_linear_insert(__i, __val);
1825 }
1826 }
1827
1828 template<typename _RandomAccessIter, typename _Compare>
1829 void
1830 __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
1831 _Compare __comp)
1832 {
1833 if (__first == __last) return;
1834
1835 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1836 {
1837 typename iterator_traits<_RandomAccessIter>::value_type __val = *__i;
1838 if (__comp(__val, *__first)) {
1839 copy_backward(__first, __i, __i + 1);
1840 *__first = __val;
1841 }
1842 else
1843 __unguarded_linear_insert(__i, __val, __comp);
1844 }
1845 }
1846
1847 template<typename _RandomAccessIter>
1848 inline void
1849 __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
1850 {
1851 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
1852
1853 for (_RandomAccessIter __i = __first; __i != __last; ++__i)
1854 __unguarded_linear_insert(__i, _ValueType(*__i));
1855 }
1856
1857 template<typename _RandomAccessIter, typename _Compare>
1858 inline void
1859 __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
1860 _Compare __comp)
1861 {
1862 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
1863
1864 for (_RandomAccessIter __i = __first; __i != __last; ++__i)
1865 __unguarded_linear_insert(__i, _ValueType(*__i), __comp);
1866 }
1867
1868 template<typename _RandomAccessIter>
1869 void
1870 __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
1871 {
1872 if (__last - __first > __stl_threshold) {
1873 __insertion_sort(__first, __first + __stl_threshold);
1874 __unguarded_insertion_sort(__first + __stl_threshold, __last);
1875 }
1876 else
1877 __insertion_sort(__first, __last);
1878 }
1879
1880 template<typename _RandomAccessIter, typename _Compare>
1881 void
1882 __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
1883 _Compare __comp)
1884 {
1885 if (__last - __first > __stl_threshold) {
1886 __insertion_sort(__first, __first + __stl_threshold, __comp);
1887 __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
1888 }
1889 else
1890 __insertion_sort(__first, __last, __comp);
1891 }
1892
1893 template<typename _Size>
1894 inline _Size
1895 __lg(_Size __n)
1896 {
1897 _Size __k;
1898 for (__k = 0; __n != 1; __n >>= 1) ++__k;
1899 return __k;
1900 }
1901
1902 template<typename _RandomAccessIter, typename _Size>
1903 void
1904 __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last,
1905 _Size __depth_limit)
1906 {
1907 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
1908
1909 while (__last - __first > __stl_threshold) {
1910 if (__depth_limit == 0) {
1911 partial_sort(__first, __last, __last);
1912 return;
1913 }
1914 --__depth_limit;
1915 _RandomAccessIter __cut =
1916 __unguarded_partition(__first, __last,
1917 _ValueType(__median(*__first,
1918 *(__first + (__last - __first)/2),
1919 *(__last - 1))));
1920 __introsort_loop(__cut, __last, __depth_limit);
1921 __last = __cut;
1922 }
1923 }
1924
1925 template<typename _RandomAccessIter, typename _Size, typename _Compare>
1926 void
1927 __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last,
1928 _Size __depth_limit, _Compare __comp)
1929 {
1930 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
1931
1932 while (__last - __first > __stl_threshold) {
1933 if (__depth_limit == 0) {
1934 partial_sort(__first, __last, __last, __comp);
1935 return;
1936 }
1937 --__depth_limit;
1938 _RandomAccessIter __cut =
1939 __unguarded_partition(__first, __last,
1940 _ValueType(__median(*__first,
1941 *(__first + (__last - __first)/2),
1942 *(__last - 1), __comp)),
1943 __comp);
1944 __introsort_loop(__cut, __last, __depth_limit, __comp);
1945 __last = __cut;
1946 }
1947 }
1948
1949 template<typename _RandomAccessIter>
1950 inline void
1951 sort(_RandomAccessIter __first, _RandomAccessIter __last)
1952 {
1953 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
1954
1955 // concept requirements
1956 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
1957 _RandomAccessIter>)
1958 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
1959
1960 if (__first != __last) {
1961 __introsort_loop(__first, __last, __lg(__last - __first) * 2);
1962 __final_insertion_sort(__first, __last);
1963 }
1964 }
1965
1966 template<typename _RandomAccessIter, typename _Compare>
1967 inline void
1968 sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
1969 {
1970 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
1971
1972 // concept requirements
1973 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
1974 _RandomAccessIter>)
1975 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _ValueType>)
1976
1977 if (__first != __last) {
1978 __introsort_loop(__first, __last, __lg(__last - __first) * 2, __comp);
1979 __final_insertion_sort(__first, __last, __comp);
1980 }
1981 }
1982
1983 // stable_sort() and its auxiliary functions.
1984
1985 template<typename _RandomAccessIter>
1986 void
1987 __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last)
1988 {
1989 if (__last - __first < 15) {
1990 __insertion_sort(__first, __last);
1991 return;
1992 }
1993 _RandomAccessIter __middle = __first + (__last - __first) / 2;
1994 __inplace_stable_sort(__first, __middle);
1995 __inplace_stable_sort(__middle, __last);
1996 __merge_without_buffer(__first, __middle, __last,
1997 __middle - __first,
1998 __last - __middle);
1999 }
2000
2001 template<typename _RandomAccessIter, typename _Compare>
2002 void
2003 __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last,
2004 _Compare __comp)
2005 {
2006 if (__last - __first < 15) {
2007 __insertion_sort(__first, __last, __comp);
2008 return;
2009 }
2010 _RandomAccessIter __middle = __first + (__last - __first) / 2;
2011 __inplace_stable_sort(__first, __middle, __comp);
2012 __inplace_stable_sort(__middle, __last, __comp);
2013 __merge_without_buffer(__first, __middle, __last,
2014 __middle - __first,
2015 __last - __middle,
2016 __comp);
2017 }
2018
2019 template<typename _RandomAccessIter1, typename _RandomAccessIter2,
2020 typename _Distance>
2021 void
2022 __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last,
2023 _RandomAccessIter2 __result, _Distance __step_size)
2024 {
2025 _Distance __two_step = 2 * __step_size;
2026
2027 while (__last - __first >= __two_step) {
2028 __result = merge(__first, __first + __step_size,
2029 __first + __step_size, __first + __two_step,
2030 __result);
2031 __first += __two_step;
2032 }
2033
2034 __step_size = min(_Distance(__last - __first), __step_size);
2035 merge(__first, __first + __step_size, __first + __step_size, __last,
2036 __result);
2037 }
2038
2039 template<typename _RandomAccessIter1, typename _RandomAccessIter2,
2040 typename _Distance, typename _Compare>
2041 void
2042 __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last,
2043 _RandomAccessIter2 __result, _Distance __step_size,
2044 _Compare __comp)
2045 {
2046 _Distance __two_step = 2 * __step_size;
2047
2048 while (__last - __first >= __two_step) {
2049 __result = merge(__first, __first + __step_size,
2050 __first + __step_size, __first + __two_step,
2051 __result,
2052 __comp);
2053 __first += __two_step;
2054 }
2055 __step_size = min(_Distance(__last - __first), __step_size);
2056
2057 merge(__first, __first + __step_size,
2058 __first + __step_size, __last,
2059 __result,
2060 __comp);
2061 }
2062
2063 const int __stl_chunk_size = 7;
2064
2065 template<typename _RandomAccessIter, typename _Distance>
2066 void
2067 __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
2068 _Distance __chunk_size)
2069 {
2070 while (__last - __first >= __chunk_size) {
2071 __insertion_sort(__first, __first + __chunk_size);
2072 __first += __chunk_size;
2073 }
2074 __insertion_sort(__first, __last);
2075 }
2076
2077 template<typename _RandomAccessIter, typename _Distance, typename _Compare>
2078 void
2079 __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
2080 _Distance __chunk_size, _Compare __comp)
2081 {
2082 while (__last - __first >= __chunk_size) {
2083 __insertion_sort(__first, __first + __chunk_size, __comp);
2084 __first += __chunk_size;
2085 }
2086 __insertion_sort(__first, __last, __comp);
2087 }
2088
2089 template<typename _RandomAccessIter, typename _Pointer>
2090 void
2091 __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last,
2092 _Pointer __buffer)
2093 {
2094 typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
2095
2096 _Distance __len = __last - __first;
2097 _Pointer __buffer_last = __buffer + __len;
2098
2099 _Distance __step_size = __stl_chunk_size;
2100 __chunk_insertion_sort(__first, __last, __step_size);
2101
2102 while (__step_size < __len) {
2103 __merge_sort_loop(__first, __last, __buffer, __step_size);
2104 __step_size *= 2;
2105 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
2106 __step_size *= 2;
2107 }
2108 }
2109
2110 template<typename _RandomAccessIter, typename _Pointer, typename _Compare>
2111 void
2112 __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last,
2113 _Pointer __buffer, _Compare __comp)
2114 {
2115 typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
2116
2117 _Distance __len = __last - __first;
2118 _Pointer __buffer_last = __buffer + __len;
2119
2120 _Distance __step_size = __stl_chunk_size;
2121 __chunk_insertion_sort(__first, __last, __step_size, __comp);
2122
2123 while (__step_size < __len) {
2124 __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
2125 __step_size *= 2;
2126 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
2127 __step_size *= 2;
2128 }
2129 }
2130
2131 template<typename _RandomAccessIter, typename _Pointer, typename _Distance>
2132 void
2133 __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last,
2134 _Pointer __buffer, _Distance __buffer_size)
2135 {
2136 _Distance __len = (__last - __first + 1) / 2;
2137 _RandomAccessIter __middle = __first + __len;
2138 if (__len > __buffer_size) {
2139 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size);
2140 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size);
2141 }
2142 else {
2143 __merge_sort_with_buffer(__first, __middle, __buffer);
2144 __merge_sort_with_buffer(__middle, __last, __buffer);
2145 }
2146 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
2147 _Distance(__last - __middle), __buffer, __buffer_size);
2148 }
2149
2150 template<typename _RandomAccessIter, typename _Pointer, typename _Distance,
2151 typename _Compare>
2152 void
2153 __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last,
2154 _Pointer __buffer, _Distance __buffer_size,
2155 _Compare __comp)
2156 {
2157 _Distance __len = (__last - __first + 1) / 2;
2158 _RandomAccessIter __middle = __first + __len;
2159 if (__len > __buffer_size) {
2160 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
2161 __comp);
2162 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
2163 __comp);
2164 }
2165 else {
2166 __merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2167 __merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2168 }
2169 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
2170 _Distance(__last - __middle), __buffer, __buffer_size,
2171 __comp);
2172 }
2173
2174 template<typename _RandomAccessIter>
2175 inline void
2176 stable_sort(_RandomAccessIter __first, _RandomAccessIter __last)
2177 {
2178 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2179 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
2180
2181 // concept requirements
2182 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
2183 _RandomAccessIter>)
2184 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
2185
2186 _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last);
2187 if (buf.begin() == 0)
2188 __inplace_stable_sort(__first, __last);
2189 else
2190 __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()));
2191 }
2192
2193 template<typename _RandomAccessIter, typename _Compare>
2194 inline void
2195 stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
2196 {
2197 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2198 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
2199
2200 // concept requirements
2201 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
2202 _RandomAccessIter>)
2203 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
2204 _ValueType, _ValueType>)
2205
2206 _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last);
2207 if (buf.begin() == 0)
2208 __inplace_stable_sort(__first, __last, __comp);
2209 else
2210 __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()),
2211 __comp);
2212 }
2213
2214 template<typename _RandomAccessIter>
2215 void
2216 partial_sort(_RandomAccessIter __first,
2217 _RandomAccessIter __middle,
2218 _RandomAccessIter __last)
2219 {
2220 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2221
2222 // concept requirements
2223 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
2224 _RandomAccessIter>)
2225 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
2226
2227 make_heap(__first, __middle);
2228 for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
2229 if (*__i < *__first)
2230 __pop_heap(__first, __middle, __i, _ValueType(*__i));
2231 sort_heap(__first, __middle);
2232 }
2233
2234 template<typename _RandomAccessIter, typename _Compare>
2235 void
2236 partial_sort(_RandomAccessIter __first,
2237 _RandomAccessIter __middle,
2238 _RandomAccessIter __last,
2239 _Compare __comp)
2240 {
2241 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2242
2243 // concept requirements
2244 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
2245 _RandomAccessIter>)
2246 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
2247 _ValueType, _ValueType>)
2248
2249 make_heap(__first, __middle, __comp);
2250 for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
2251 if (__comp(*__i, *__first))
2252 __pop_heap(__first, __middle, __i, _ValueType(*__i), __comp);
2253 sort_heap(__first, __middle, __comp);
2254 }
2255
2256 template<typename _InputIter, typename _RandomAccessIter>
2257 _RandomAccessIter
2258 partial_sort_copy(_InputIter __first, _InputIter __last,
2259 _RandomAccessIter __result_first,
2260 _RandomAccessIter __result_last)
2261 {
2262 typedef typename iterator_traits<_InputIter>::value_type _InputValueType;
2263 typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType;
2264 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
2265
2266 // concept requirements
2267 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
2268 __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>)
2269 __glibcpp_function_requires(_LessThanComparableConcept<_OutputValueType>)
2270 __glibcpp_function_requires(_LessThanComparableConcept<_InputValueType>)
2271
2272 if (__result_first == __result_last) return __result_last;
2273 _RandomAccessIter __result_real_last = __result_first;
2274 while(__first != __last && __result_real_last != __result_last) {
2275 *__result_real_last = *__first;
2276 ++__result_real_last;
2277 ++__first;
2278 }
2279 make_heap(__result_first, __result_real_last);
2280 while (__first != __last) {
2281 if (*__first < *__result_first)
2282 __adjust_heap(__result_first, _DistanceType(0),
2283 _DistanceType(__result_real_last - __result_first),
2284 _InputValueType(*__first));
2285 ++__first;
2286 }
2287 sort_heap(__result_first, __result_real_last);
2288 return __result_real_last;
2289 }
2290
2291 template<typename _InputIter, typename _RandomAccessIter, typename _Compare>
2292 _RandomAccessIter
2293 partial_sort_copy(_InputIter __first, _InputIter __last,
2294 _RandomAccessIter __result_first,
2295 _RandomAccessIter __result_last,
2296 _Compare __comp)
2297 {
2298 typedef typename iterator_traits<_InputIter>::value_type _InputValueType;
2299 typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType;
2300 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
2301
2302 // concept requirements
2303 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
2304 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>)
2305 __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>)
2306 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
2307 _OutputValueType, _OutputValueType>)
2308
2309 if (__result_first == __result_last) return __result_last;
2310 _RandomAccessIter __result_real_last = __result_first;
2311 while(__first != __last && __result_real_last != __result_last) {
2312 *__result_real_last = *__first;
2313 ++__result_real_last;
2314 ++__first;
2315 }
2316 make_heap(__result_first, __result_real_last, __comp);
2317 while (__first != __last) {
2318 if (__comp(*__first, *__result_first))
2319 __adjust_heap(__result_first, _DistanceType(0),
2320 _DistanceType(__result_real_last - __result_first),
2321 _InputValueType(*__first),
2322 __comp);
2323 ++__first;
2324 }
2325 sort_heap(__result_first, __result_real_last, __comp);
2326 return __result_real_last;
2327 }
2328
2329 template<typename _RandomAccessIter>
2330 void
2331 nth_element(_RandomAccessIter __first,
2332 _RandomAccessIter __nth,
2333 _RandomAccessIter __last)
2334 {
2335 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2336
2337 // concept requirements
2338 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>)
2339 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
2340
2341 while (__last - __first > 3) {
2342 _RandomAccessIter __cut =
2343 __unguarded_partition(__first, __last,
2344 _ValueType(__median(*__first,
2345 *(__first + (__last - __first)/2),
2346 *(__last - 1))));
2347 if (__cut <= __nth)
2348 __first = __cut;
2349 else
2350 __last = __cut;
2351 }
2352 __insertion_sort(__first, __last);
2353 }
2354
2355 template<typename _RandomAccessIter, typename _Compare>
2356 void
2357 nth_element(_RandomAccessIter __first,
2358 _RandomAccessIter __nth,
2359 _RandomAccessIter __last,
2360 _Compare __comp)
2361 {
2362 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2363
2364 // concept requirements
2365 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>)
2366 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
2367 _ValueType, _ValueType>)
2368
2369 while (__last - __first > 3) {
2370 _RandomAccessIter __cut =
2371 __unguarded_partition(__first, __last,
2372 _ValueType(__median(*__first,
2373 *(__first + (__last - __first)/2),
2374 *(__last - 1),
2375 __comp)),
2376 __comp);
2377 if (__cut <= __nth)
2378 __first = __cut;
2379 else
2380 __last = __cut;
2381 }
2382 __insertion_sort(__first, __last, __comp);
2383 }
2384
2385
2386 // Binary search (lower_bound, upper_bound, equal_range, binary_search).
2387
2388 template<typename _ForwardIter, typename _Tp>
2389 _ForwardIter
2390 lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
2391 {
2392 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
2393 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
2394
2395 // concept requirements
2396 // Note that these are slightly stricter than those of the 4-argument
2397 // version, defined next. The difference is in the strictness of the
2398 // comparison operations... so for looser checking, define your own
2399 // comparison function, as was intended.
2400 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
2401 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
2402 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
2403
2404 _DistanceType __len = distance(__first, __last);
2405 _DistanceType __half;
2406 _ForwardIter __middle;
2407
2408 while (__len > 0) {
2409 __half = __len >> 1;
2410 __middle = __first;
2411 advance(__middle, __half);
2412 if (*__middle < __val) {
2413 __first = __middle;
2414 ++__first;
2415 __len = __len - __half - 1;
2416 }
2417 else
2418 __len = __half;
2419 }
2420 return __first;
2421 }
2422
2423 template<typename _ForwardIter, typename _Tp, typename _Compare>
2424 _ForwardIter
2425 lower_bound(_ForwardIter __first, _ForwardIter __last,
2426 const _Tp& __val, _Compare __comp)
2427 {
2428 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
2429 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
2430
2431 // concept requirements
2432 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
2433 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>)
2434
2435 _DistanceType __len = distance(__first, __last);
2436 _DistanceType __half;
2437 _ForwardIter __middle;
2438
2439 while (__len > 0) {
2440 __half = __len >> 1;
2441 __middle = __first;
2442 advance(__middle, __half);
2443 if (__comp(*__middle, __val)) {
2444 __first = __middle;
2445 ++__first;
2446 __len = __len - __half - 1;
2447 }
2448 else
2449 __len = __half;
2450 }
2451 return __first;
2452 }
2453
2454 template<typename _ForwardIter, typename _Tp>
2455 _ForwardIter
2456 upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
2457 {
2458 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
2459 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
2460
2461 // concept requirements
2462 // See comments on lower_bound.
2463 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
2464 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
2465 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
2466
2467 _DistanceType __len = distance(__first, __last);
2468 _DistanceType __half;
2469 _ForwardIter __middle;
2470
2471 while (__len > 0) {
2472 __half = __len >> 1;
2473 __middle = __first;
2474 advance(__middle, __half);
2475 if (__val < *__middle)
2476 __len = __half;
2477 else {
2478 __first = __middle;
2479 ++__first;
2480 __len = __len - __half - 1;
2481 }
2482 }
2483 return __first;
2484 }
2485
2486 template<typename _ForwardIter, typename _Tp, typename _Compare>
2487 _ForwardIter
2488 upper_bound(_ForwardIter __first, _ForwardIter __last,
2489 const _Tp& __val, _Compare __comp)
2490 {
2491 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
2492 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
2493
2494 // concept requirements
2495 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
2496 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>)
2497
2498 _DistanceType __len = distance(__first, __last);
2499 _DistanceType __half;
2500 _ForwardIter __middle;
2501
2502 while (__len > 0) {
2503 __half = __len >> 1;
2504 __middle = __first;
2505 advance(__middle, __half);
2506 if (__comp(__val, *__middle))
2507 __len = __half;
2508 else {
2509 __first = __middle;
2510 ++__first;
2511 __len = __len - __half - 1;
2512 }
2513 }
2514 return __first;
2515 }
2516
2517 template<typename _ForwardIter, typename _Tp>
2518 pair<_ForwardIter, _ForwardIter>
2519 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
2520 {
2521 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
2522 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
2523
2524 // concept requirements
2525 // See comments on lower_bound.
2526 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
2527 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
2528 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
2529
2530 _DistanceType __len = distance(__first, __last);
2531 _DistanceType __half;
2532 _ForwardIter __middle, __left, __right;
2533
2534 while (__len > 0) {
2535 __half = __len >> 1;
2536 __middle = __first;
2537 advance(__middle, __half);
2538 if (*__middle < __val) {
2539 __first = __middle;
2540 ++__first;
2541 __len = __len - __half - 1;
2542 }
2543 else if (__val < *__middle)
2544 __len = __half;
2545 else {
2546 __left = lower_bound(__first, __middle, __val);
2547 advance(__first, __len);
2548 __right = upper_bound(++__middle, __first, __val);
2549 return pair<_ForwardIter, _ForwardIter>(__left, __right);
2550 }
2551 }
2552 return pair<_ForwardIter, _ForwardIter>(__first, __first);
2553 }
2554
2555 template<typename _ForwardIter, typename _Tp, typename _Compare>
2556 pair<_ForwardIter, _ForwardIter>
2557 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
2558 _Compare __comp)
2559 {
2560 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
2561 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
2562
2563 // concept requirements
2564 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
2565 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>)
2566 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>)
2567
2568 _DistanceType __len = distance(__first, __last);
2569 _DistanceType __half;
2570 _ForwardIter __middle, __left, __right;
2571
2572 while (__len > 0) {
2573 __half = __len >> 1;
2574 __middle = __first;
2575 advance(__middle, __half);
2576 if (__comp(*__middle, __val)) {
2577 __first = __middle;
2578 ++__first;
2579 __len = __len - __half - 1;
2580 }
2581 else if (__comp(__val, *__middle))
2582 __len = __half;
2583 else {
2584 __left = lower_bound(__first, __middle, __val, __comp);
2585 advance(__first, __len);
2586 __right = upper_bound(++__middle, __first, __val, __comp);
2587 return pair<_ForwardIter, _ForwardIter>(__left, __right);
2588 }
2589 }
2590 return pair<_ForwardIter, _ForwardIter>(__first, __first);
2591 }
2592
2593 template<typename _ForwardIter, typename _Tp>
2594 bool
2595 binary_search(_ForwardIter __first, _ForwardIter __last,
2596 const _Tp& __val)
2597 {
2598 // concept requirements
2599 // See comments on lower_bound.
2600 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
2601 __glibcpp_function_requires(_SameTypeConcept<_Tp,
2602 typename iterator_traits<_ForwardIter>::value_type>)
2603 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
2604
2605 _ForwardIter __i = lower_bound(__first, __last, __val);
2606 return __i != __last && !(__val < *__i);
2607 }
2608
2609 template<typename _ForwardIter, typename _Tp, typename _Compare>
2610 bool
2611 binary_search(_ForwardIter __first, _ForwardIter __last,
2612 const _Tp& __val, _Compare __comp)
2613 {
2614 // concept requirements
2615 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
2616 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
2617 typename iterator_traits<_ForwardIter>::value_type, _Tp>)
2618 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp,
2619 typename iterator_traits<_ForwardIter>::value_type>)
2620
2621 _ForwardIter __i = lower_bound(__first, __last, __val, __comp);
2622 return __i != __last && !__comp(__val, *__i);
2623 }
2624
2625 // merge, with and without an explicitly supplied comparison function.
2626
2627 template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
2628 _OutputIter
2629 merge(_InputIter1 __first1, _InputIter1 __last1,
2630 _InputIter2 __first2, _InputIter2 __last2,
2631 _OutputIter __result)
2632 {
2633 // concept requirements
2634 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
2635 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
2636 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
2637 typename iterator_traits<_InputIter1>::value_type>)
2638 __glibcpp_function_requires(_SameTypeConcept<
2639 typename iterator_traits<_InputIter1>::value_type,
2640 typename iterator_traits<_InputIter2>::value_type>)
2641 __glibcpp_function_requires(_LessThanComparableConcept<
2642 typename iterator_traits<_InputIter1>::value_type>)
2643
2644 while (__first1 != __last1 && __first2 != __last2) {
2645 if (*__first2 < *__first1) {
2646 *__result = *__first2;
2647 ++__first2;
2648 }
2649 else {
2650 *__result = *__first1;
2651 ++__first1;
2652 }
2653 ++__result;
2654 }
2655 return copy(__first2, __last2, copy(__first1, __last1, __result));
2656 }
2657
2658 template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
2659 typename _Compare>
2660 _OutputIter
2661 merge(_InputIter1 __first1, _InputIter1 __last1,
2662 _InputIter2 __first2, _InputIter2 __last2,
2663 _OutputIter __result, _Compare __comp)
2664 {
2665 // concept requirements
2666 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
2667 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
2668 __glibcpp_function_requires(_SameTypeConcept<
2669 typename iterator_traits<_InputIter1>::value_type,
2670 typename iterator_traits<_InputIter2>::value_type>)
2671 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
2672 typename iterator_traits<_InputIter1>::value_type>)
2673 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
2674 typename iterator_traits<_InputIter1>::value_type,
2675 typename iterator_traits<_InputIter2>::value_type>)
2676
2677 while (__first1 != __last1 && __first2 != __last2) {
2678 if (__comp(*__first2, *__first1)) {
2679 *__result = *__first2;
2680 ++__first2;
2681 }
2682 else {
2683 *__result = *__first1;
2684 ++__first1;
2685 }
2686 ++__result;
2687 }
2688 return copy(__first2, __last2, copy(__first1, __last1, __result));
2689 }
2690
2691 // inplace_merge and its auxiliary functions.
2692
2693 template<typename _BidirectionalIter, typename _Distance>
2694 void
2695 __merge_without_buffer(_BidirectionalIter __first,
2696 _BidirectionalIter __middle,
2697 _BidirectionalIter __last,
2698 _Distance __len1, _Distance __len2)
2699 {
2700 if (__len1 == 0 || __len2 == 0)
2701 return;
2702 if (__len1 + __len2 == 2) {
2703 if (*__middle < *__first)
2704 iter_swap(__first, __middle);
2705 return;
2706 }
2707 _BidirectionalIter __first_cut = __first;
2708 _BidirectionalIter __second_cut = __middle;
2709 _Distance __len11 = 0;
2710 _Distance __len22 = 0;
2711 if (__len1 > __len2) {
2712 __len11 = __len1 / 2;
2713 advance(__first_cut, __len11);
2714 __second_cut = lower_bound(__middle, __last, *__first_cut);
2715 __len22 = distance(__middle, __second_cut);
2716 }
2717 else {
2718 __len22 = __len2 / 2;
2719 advance(__second_cut, __len22);
2720 __first_cut = upper_bound(__first, __middle, *__second_cut);
2721 __len11 = distance(__first, __first_cut);
2722 }
2723 rotate(__first_cut, __middle, __second_cut);
2724 _BidirectionalIter __new_middle = __first_cut;
2725 advance(__new_middle, distance(__middle, __second_cut));
2726 __merge_without_buffer(__first, __first_cut, __new_middle,
2727 __len11, __len22);
2728 __merge_without_buffer(__new_middle, __second_cut, __last,
2729 __len1 - __len11, __len2 - __len22);
2730 }
2731
2732 template<typename _BidirectionalIter, typename _Distance, typename _Compare>
2733 void
2734 __merge_without_buffer(_BidirectionalIter __first,
2735 _BidirectionalIter __middle,
2736 _BidirectionalIter __last,
2737 _Distance __len1, _Distance __len2,
2738 _Compare __comp)
2739 {
2740 if (__len1 == 0 || __len2 == 0)
2741 return;
2742 if (__len1 + __len2 == 2) {
2743 if (__comp(*__middle, *__first))
2744 iter_swap(__first, __middle);
2745 return;
2746 }
2747 _BidirectionalIter __first_cut = __first;
2748 _BidirectionalIter __second_cut = __middle;
2749 _Distance __len11 = 0;
2750 _Distance __len22 = 0;
2751 if (__len1 > __len2) {
2752 __len11 = __len1 / 2;
2753 advance(__first_cut, __len11);
2754 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
2755 __len22 = distance(__middle, __second_cut);
2756 }
2757 else {
2758 __len22 = __len2 / 2;
2759 advance(__second_cut, __len22);
2760 __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
2761 __len11 = distance(__first, __first_cut);
2762 }
2763 rotate(__first_cut, __middle, __second_cut);
2764 _BidirectionalIter __new_middle = __first_cut;
2765 advance(__new_middle, distance(__middle, __second_cut));
2766 __merge_without_buffer(__first, __first_cut, __new_middle,
2767 __len11, __len22, __comp);
2768 __merge_without_buffer(__new_middle, __second_cut, __last,
2769 __len1 - __len11, __len2 - __len22, __comp);
2770 }
2771
2772 template<typename _BidirectionalIter1, typename _BidirectionalIter2,
2773 typename _Distance>
2774 _BidirectionalIter1
2775 __rotate_adaptive(_BidirectionalIter1 __first,
2776 _BidirectionalIter1 __middle,
2777 _BidirectionalIter1 __last,
2778 _Distance __len1, _Distance __len2,
2779 _BidirectionalIter2 __buffer,
2780 _Distance __buffer_size)
2781 {
2782 _BidirectionalIter2 __buffer_end;
2783 if (__len1 > __len2 && __len2 <= __buffer_size) {
2784 __buffer_end = copy(__middle, __last, __buffer);
2785 copy_backward(__first, __middle, __last);
2786 return copy(__buffer, __buffer_end, __first);
2787 }
2788 else if (__len1 <= __buffer_size) {
2789 __buffer_end = copy(__first, __middle, __buffer);
2790 copy(__middle, __last, __first);
2791 return copy_backward(__buffer, __buffer_end, __last);
2792 }
2793 else {
2794 rotate(__first, __middle, __last);
2795 advance(__first, distance(__middle, __last));
2796 return __first;
2797 }
2798 }
2799
2800 template<typename _BidirectionalIter1, typename _BidirectionalIter2,
2801 typename _BidirectionalIter3>
2802 _BidirectionalIter3
2803 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
2804 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
2805 _BidirectionalIter3 __result)
2806 {
2807 if (__first1 == __last1)
2808 return copy_backward(__first2, __last2, __result);
2809 if (__first2 == __last2)
2810 return copy_backward(__first1, __last1, __result);
2811 --__last1;
2812 --__last2;
2813 while (true) {
2814 if (*__last2 < *__last1) {
2815 *--__result = *__last1;
2816 if (__first1 == __last1)
2817 return copy_backward(__first2, ++__last2, __result);
2818 --__last1;
2819 }
2820 else {
2821 *--__result = *__last2;
2822 if (__first2 == __last2)
2823 return copy_backward(__first1, ++__last1, __result);
2824 --__last2;
2825 }
2826 }
2827 }
2828
2829 template<typename _BidirectionalIter1, typename _BidirectionalIter2,
2830 typename _BidirectionalIter3, typename _Compare>
2831 _BidirectionalIter3
2832 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
2833 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
2834 _BidirectionalIter3 __result,
2835 _Compare __comp)
2836 {
2837 if (__first1 == __last1)
2838 return copy_backward(__first2, __last2, __result);
2839 if (__first2 == __last2)
2840 return copy_backward(__first1, __last1, __result);
2841 --__last1;
2842 --__last2;
2843 while (true) {
2844 if (__comp(*__last2, *__last1)) {
2845 *--__result = *__last1;
2846 if (__first1 == __last1)
2847 return copy_backward(__first2, ++__last2, __result);
2848 --__last1;
2849 }
2850 else {
2851 *--__result = *__last2;
2852 if (__first2 == __last2)
2853 return copy_backward(__first1, ++__last1, __result);
2854 --__last2;
2855 }
2856 }
2857 }
2858
2859 template<typename _BidirectionalIter, typename _Distance, typename _Pointer>
2860 void
2861 __merge_adaptive(_BidirectionalIter __first,
2862 _BidirectionalIter __middle,
2863 _BidirectionalIter __last,
2864 _Distance __len1, _Distance __len2,
2865 _Pointer __buffer, _Distance __buffer_size)
2866 {
2867 if (__len1 <= __len2 && __len1 <= __buffer_size) {
2868 _Pointer __buffer_end = copy(__first, __middle, __buffer);
2869 merge(__buffer, __buffer_end, __middle, __last, __first);
2870 }
2871 else if (__len2 <= __buffer_size) {
2872 _Pointer __buffer_end = copy(__middle, __last, __buffer);
2873 __merge_backward(__first, __middle, __buffer, __buffer_end, __last);
2874 }
2875 else {
2876 _BidirectionalIter __first_cut = __first;
2877 _BidirectionalIter __second_cut = __middle;
2878 _Distance __len11 = 0;
2879 _Distance __len22 = 0;
2880 if (__len1 > __len2) {
2881 __len11 = __len1 / 2;
2882 advance(__first_cut, __len11);
2883 __second_cut = lower_bound(__middle, __last, *__first_cut);
2884 __len22 = distance(__middle, __second_cut);
2885 }
2886 else {
2887 __len22 = __len2 / 2;
2888 advance(__second_cut, __len22);
2889 __first_cut = upper_bound(__first, __middle, *__second_cut);
2890 __len11 = distance(__first, __first_cut);
2891 }
2892 _BidirectionalIter __new_middle =
2893 __rotate_adaptive(__first_cut, __middle, __second_cut,
2894 __len1 - __len11, __len22, __buffer,
2895 __buffer_size);
2896 __merge_adaptive(__first, __first_cut, __new_middle, __len11,
2897 __len22, __buffer, __buffer_size);
2898 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
2899 __len2 - __len22, __buffer, __buffer_size);
2900 }
2901 }
2902
2903 template<typename _BidirectionalIter, typename _Distance, typename _Pointer,
2904 typename _Compare>
2905 void
2906 __merge_adaptive(_BidirectionalIter __first,
2907 _BidirectionalIter __middle,
2908 _BidirectionalIter __last,
2909 _Distance __len1, _Distance __len2,
2910 _Pointer __buffer, _Distance __buffer_size,
2911 _Compare __comp)
2912 {
2913 if (__len1 <= __len2 && __len1 <= __buffer_size) {
2914 _Pointer __buffer_end = copy(__first, __middle, __buffer);
2915 merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
2916 }
2917 else if (__len2 <= __buffer_size) {
2918 _Pointer __buffer_end = copy(__middle, __last, __buffer);
2919 __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
2920 __comp);
2921 }
2922 else {
2923 _BidirectionalIter __first_cut = __first;
2924 _BidirectionalIter __second_cut = __middle;
2925 _Distance __len11 = 0;
2926 _Distance __len22 = 0;
2927 if (__len1 > __len2) {
2928 __len11 = __len1 / 2;
2929 advance(__first_cut, __len11);
2930 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
2931 __len22 = distance(__middle, __second_cut);
2932 }
2933 else {
2934 __len22 = __len2 / 2;
2935 advance(__second_cut, __len22);
2936 __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
2937 __len11 = distance(__first, __first_cut);
2938 }
2939 _BidirectionalIter __new_middle =
2940 __rotate_adaptive(__first_cut, __middle, __second_cut,
2941 __len1 - __len11, __len22, __buffer,
2942 __buffer_size);
2943 __merge_adaptive(__first, __first_cut, __new_middle, __len11,
2944 __len22, __buffer, __buffer_size, __comp);
2945 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
2946 __len2 - __len22, __buffer, __buffer_size, __comp);
2947 }
2948 }
2949
2950 template<typename _BidirectionalIter>
2951 void
2952 inplace_merge(_BidirectionalIter __first,
2953 _BidirectionalIter __middle,
2954 _BidirectionalIter __last)
2955 {
2956 typedef typename iterator_traits<_BidirectionalIter>::value_type
2957 _ValueType;
2958 typedef typename iterator_traits<_BidirectionalIter>::difference_type
2959 _DistanceType;
2960
2961 // concept requirements
2962 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
2963 _BidirectionalIter>)
2964 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
2965
2966 if (__first == __middle || __middle == __last)
2967 return;
2968
2969 _DistanceType __len1 = distance(__first, __middle);
2970 _DistanceType __len2 = distance(__middle, __last);
2971
2972 _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last);
2973 if (__buf.begin() == 0)
2974 __merge_without_buffer(__first, __middle, __last, __len1, __len2);
2975 else
2976 __merge_adaptive(__first, __middle, __last, __len1, __len2,
2977 __buf.begin(), _DistanceType(__buf.size()));
2978 }
2979
2980 template<typename _BidirectionalIter, typename _Compare>
2981 void
2982 inplace_merge(_BidirectionalIter __first,
2983 _BidirectionalIter __middle,
2984 _BidirectionalIter __last,
2985 _Compare __comp)
2986 {
2987 typedef typename iterator_traits<_BidirectionalIter>::value_type
2988 _ValueType;
2989 typedef typename iterator_traits<_BidirectionalIter>::difference_type
2990 _DistanceType;
2991
2992 // concept requirements
2993 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
2994 _BidirectionalIter>)
2995 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
2996 _ValueType, _ValueType>)
2997
2998 if (__first == __middle || __middle == __last)
2999 return;
3000
3001 _DistanceType __len1 = distance(__first, __middle);
3002 _DistanceType __len2 = distance(__middle, __last);
3003
3004 _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last);
3005 if (__buf.begin() == 0)
3006 __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
3007 else
3008 __merge_adaptive(__first, __middle, __last, __len1, __len2,
3009 __buf.begin(), _DistanceType(__buf.size()),
3010 __comp);
3011 }
3012
3013 // Set algorithms: includes, set_union, set_intersection, set_difference,
3014 // set_symmetric_difference. All of these algorithms have the precondition
3015 // that their input ranges are sorted and the postcondition that their output
3016 // ranges are sorted.
3017
3018 template<typename _InputIter1, typename _InputIter2>
3019 bool
3020 includes(_InputIter1 __first1, _InputIter1 __last1,
3021 _InputIter2 __first2, _InputIter2 __last2)
3022 {
3023 // concept requirements
3024 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3025 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3026 __glibcpp_function_requires(_SameTypeConcept<
3027 typename iterator_traits<_InputIter1>::value_type,
3028 typename iterator_traits<_InputIter2>::value_type>)
3029 __glibcpp_function_requires(_LessThanComparableConcept<
3030 typename iterator_traits<_InputIter1>::value_type>)
3031
3032 while (__first1 != __last1 && __first2 != __last2)
3033 if (*__first2 < *__first1)
3034 return false;
3035 else if(*__first1 < *__first2)
3036 ++__first1;
3037 else
3038 ++__first1, ++__first2;
3039
3040 return __first2 == __last2;
3041 }
3042
3043 template<typename _InputIter1, typename _InputIter2, typename _Compare>
3044 bool
3045 includes(_InputIter1 __first1, _InputIter1 __last1,
3046 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp)
3047 {
3048 // concept requirements
3049 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3050 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3051 __glibcpp_function_requires(_SameTypeConcept<
3052 typename iterator_traits<_InputIter1>::value_type,
3053 typename iterator_traits<_InputIter2>::value_type>)
3054 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3055 typename iterator_traits<_InputIter1>::value_type,
3056 typename iterator_traits<_InputIter2>::value_type>)
3057
3058 while (__first1 != __last1 && __first2 != __last2)
3059 if (__comp(*__first2, *__first1))
3060 return false;
3061 else if(__comp(*__first1, *__first2))
3062 ++__first1;
3063 else
3064 ++__first1, ++__first2;
3065
3066 return __first2 == __last2;
3067 }
3068
3069 template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
3070 _OutputIter
3071 set_union(_InputIter1 __first1, _InputIter1 __last1,
3072 _InputIter2 __first2, _InputIter2 __last2,
3073 _OutputIter __result)
3074 {
3075 // concept requirements
3076 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3077 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3078 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3079 typename iterator_traits<_InputIter1>::value_type>)
3080 __glibcpp_function_requires(_SameTypeConcept<
3081 typename iterator_traits<_InputIter1>::value_type,
3082 typename iterator_traits<_InputIter2>::value_type>)
3083 __glibcpp_function_requires(_LessThanComparableConcept<
3084 typename iterator_traits<_InputIter1>::value_type>)
3085
3086 while (__first1 != __last1 && __first2 != __last2) {
3087 if (*__first1 < *__first2) {
3088 *__result = *__first1;
3089 ++__first1;
3090 }
3091 else if (*__first2 < *__first1) {
3092 *__result = *__first2;
3093 ++__first2;
3094 }
3095 else {
3096 *__result = *__first1;
3097 ++__first1;
3098 ++__first2;
3099 }
3100 ++__result;
3101 }
3102 return copy(__first2, __last2, copy(__first1, __last1, __result));
3103 }
3104
3105 template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
3106 typename _Compare>
3107 _OutputIter
3108 set_union(_InputIter1 __first1, _InputIter1 __last1,
3109 _InputIter2 __first2, _InputIter2 __last2,
3110 _OutputIter __result, _Compare __comp)
3111 {
3112 // concept requirements
3113 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3114 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3115 __glibcpp_function_requires(_SameTypeConcept<
3116 typename iterator_traits<_InputIter1>::value_type,
3117 typename iterator_traits<_InputIter2>::value_type>)
3118 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3119 typename iterator_traits<_InputIter1>::value_type>)
3120 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3121 typename iterator_traits<_InputIter1>::value_type,
3122 typename iterator_traits<_InputIter2>::value_type>)
3123
3124 while (__first1 != __last1 && __first2 != __last2) {
3125 if (__comp(*__first1, *__first2)) {
3126 *__result = *__first1;
3127 ++__first1;
3128 }
3129 else if (__comp(*__first2, *__first1)) {
3130 *__result = *__first2;
3131 ++__first2;
3132 }
3133 else {
3134 *__result = *__first1;
3135 ++__first1;
3136 ++__first2;
3137 }
3138 ++__result;
3139 }
3140 return copy(__first2, __last2, copy(__first1, __last1, __result));
3141 }
3142
3143 template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
3144 _OutputIter
3145 set_intersection(_InputIter1 __first1, _InputIter1 __last1,
3146 _InputIter2 __first2, _InputIter2 __last2,
3147 _OutputIter __result)
3148 {
3149 // concept requirements
3150 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3151 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3152 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3153 typename iterator_traits<_InputIter1>::value_type>)
3154 __glibcpp_function_requires(_SameTypeConcept<
3155 typename iterator_traits<_InputIter1>::value_type,
3156 typename iterator_traits<_InputIter2>::value_type>)
3157 __glibcpp_function_requires(_LessThanComparableConcept<
3158 typename iterator_traits<_InputIter1>::value_type>)
3159
3160 while (__first1 != __last1 && __first2 != __last2)
3161 if (*__first1 < *__first2)
3162 ++__first1;
3163 else if (*__first2 < *__first1)
3164 ++__first2;
3165 else {
3166 *__result = *__first1;
3167 ++__first1;
3168 ++__first2;
3169 ++__result;
3170 }
3171 return __result;
3172 }
3173
3174 template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
3175 typename _Compare>
3176 _OutputIter
3177 set_intersection(_InputIter1 __first1, _InputIter1 __last1,
3178 _InputIter2 __first2, _InputIter2 __last2,
3179 _OutputIter __result, _Compare __comp)
3180 {
3181 // concept requirements
3182 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3183 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3184 __glibcpp_function_requires(_SameTypeConcept<
3185 typename iterator_traits<_InputIter1>::value_type,
3186 typename iterator_traits<_InputIter2>::value_type>)
3187 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3188 typename iterator_traits<_InputIter1>::value_type>)
3189 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3190 typename iterator_traits<_InputIter1>::value_type,
3191 typename iterator_traits<_InputIter2>::value_type>)
3192
3193 while (__first1 != __last1 && __first2 != __last2)
3194 if (__comp(*__first1, *__first2))
3195 ++__first1;
3196 else if (__comp(*__first2, *__first1))
3197 ++__first2;
3198 else {
3199 *__result = *__first1;
3200 ++__first1;
3201 ++__first2;
3202 ++__result;
3203 }
3204 return __result;
3205 }
3206
3207 template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
3208 _OutputIter
3209 set_difference(_InputIter1 __first1, _InputIter1 __last1,
3210 _InputIter2 __first2, _InputIter2 __last2,
3211 _OutputIter __result)
3212 {
3213 // concept requirements
3214 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3215 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3216 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3217 typename iterator_traits<_InputIter1>::value_type>)
3218 __glibcpp_function_requires(_SameTypeConcept<
3219 typename iterator_traits<_InputIter1>::value_type,
3220 typename iterator_traits<_InputIter2>::value_type>)
3221 __glibcpp_function_requires(_LessThanComparableConcept<
3222 typename iterator_traits<_InputIter1>::value_type>)
3223
3224 while (__first1 != __last1 && __first2 != __last2)
3225 if (*__first1 < *__first2) {
3226 *__result = *__first1;
3227 ++__first1;
3228 ++__result;
3229 }
3230 else if (*__first2 < *__first1)
3231 ++__first2;
3232 else {
3233 ++__first1;
3234 ++__first2;
3235 }
3236 return copy(__first1, __last1, __result);
3237 }
3238
3239 template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
3240 typename _Compare>
3241 _OutputIter
3242 set_difference(_InputIter1 __first1, _InputIter1 __last1,
3243 _InputIter2 __first2, _InputIter2 __last2,
3244 _OutputIter __result, _Compare __comp)
3245 {
3246 // concept requirements
3247 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3248 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3249 __glibcpp_function_requires(_SameTypeConcept<
3250 typename iterator_traits<_InputIter1>::value_type,
3251 typename iterator_traits<_InputIter2>::value_type>)
3252 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3253 typename iterator_traits<_InputIter1>::value_type>)
3254 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3255 typename iterator_traits<_InputIter1>::value_type,
3256 typename iterator_traits<_InputIter2>::value_type>)
3257
3258 while (__first1 != __last1 && __first2 != __last2)
3259 if (__comp(*__first1, *__first2)) {
3260 *__result = *__first1;
3261 ++__first1;
3262 ++__result;
3263 }
3264 else if (__comp(*__first2, *__first1))
3265 ++__first2;
3266 else {
3267 ++__first1;
3268 ++__first2;
3269 }
3270 return copy(__first1, __last1, __result);
3271 }
3272
3273 template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
3274 _OutputIter
3275 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
3276 _InputIter2 __first2, _InputIter2 __last2,
3277 _OutputIter __result)
3278 {
3279 // concept requirements
3280 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3281 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3282 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3283 typename iterator_traits<_InputIter1>::value_type>)
3284 __glibcpp_function_requires(_SameTypeConcept<
3285 typename iterator_traits<_InputIter1>::value_type,
3286 typename iterator_traits<_InputIter2>::value_type>)
3287 __glibcpp_function_requires(_LessThanComparableConcept<
3288 typename iterator_traits<_InputIter1>::value_type>)
3289
3290 while (__first1 != __last1 && __first2 != __last2)
3291 if (*__first1 < *__first2) {
3292 *__result = *__first1;
3293 ++__first1;
3294 ++__result;
3295 }
3296 else if (*__first2 < *__first1) {
3297 *__result = *__first2;
3298 ++__first2;
3299 ++__result;
3300 }
3301 else {
3302 ++__first1;
3303 ++__first2;
3304 }
3305 return copy(__first2, __last2, copy(__first1, __last1, __result));
3306 }
3307
3308 template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
3309 typename _Compare>
3310 _OutputIter
3311 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
3312 _InputIter2 __first2, _InputIter2 __last2,
3313 _OutputIter __result,
3314 _Compare __comp)
3315 {
3316 // concept requirements
3317 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3318 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3319 __glibcpp_function_requires(_SameTypeConcept<
3320 typename iterator_traits<_InputIter1>::value_type,
3321 typename iterator_traits<_InputIter2>::value_type>)
3322 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3323 typename iterator_traits<_InputIter1>::value_type>)
3324 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3325 typename iterator_traits<_InputIter1>::value_type,
3326 typename iterator_traits<_InputIter2>::value_type>)
3327
3328 while (__first1 != __last1 && __first2 != __last2)
3329 if (__comp(*__first1, *__first2)) {
3330 *__result = *__first1;
3331 ++__first1;
3332 ++__result;
3333 }
3334 else if (__comp(*__first2, *__first1)) {
3335 *__result = *__first2;
3336 ++__first2;
3337 ++__result;
3338 }
3339 else {
3340 ++__first1;
3341 ++__first2;
3342 }
3343 return copy(__first2, __last2, copy(__first1, __last1, __result));
3344 }
3345
3346 // min_element and max_element, with and without an explicitly supplied
3347 // comparison function.
3348
3349 template<typename _ForwardIter>
3350 _ForwardIter
3351 max_element(_ForwardIter __first, _ForwardIter __last)
3352 {
3353 // concept requirements
3354 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
3355 __glibcpp_function_requires(_LessThanComparableConcept<
3356 typename iterator_traits<_ForwardIter>::value_type>)
3357
3358 if (__first == __last) return __first;
3359 _ForwardIter __result = __first;
3360 while (++__first != __last)
3361 if (*__result < *__first)
3362 __result = __first;
3363 return __result;
3364 }
3365
3366 template<typename _ForwardIter, typename _Compare>
3367 _ForwardIter
3368 max_element(_ForwardIter __first, _ForwardIter __last,
3369 _Compare __comp)
3370 {
3371 // concept requirements
3372 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
3373 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3374 typename iterator_traits<_ForwardIter>::value_type,
3375 typename iterator_traits<_ForwardIter>::value_type>)
3376
3377 if (__first == __last) return __first;
3378 _ForwardIter __result = __first;
3379 while (++__first != __last)
3380 if (__comp(*__result, *__first)) __result = __first;
3381 return __result;
3382 }
3383
3384 template<typename _ForwardIter>
3385 _ForwardIter
3386 min_element(_ForwardIter __first, _ForwardIter __last)
3387 {
3388 // concept requirements
3389 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
3390 __glibcpp_function_requires(_LessThanComparableConcept<
3391 typename iterator_traits<_ForwardIter>::value_type>)
3392
3393 if (__first == __last) return __first;
3394 _ForwardIter __result = __first;
3395 while (++__first != __last)
3396 if (*__first < *__result)
3397 __result = __first;
3398 return __result;
3399 }
3400
3401 template<typename _ForwardIter, typename _Compare>
3402 _ForwardIter
3403 min_element(_ForwardIter __first, _ForwardIter __last,
3404 _Compare __comp)
3405 {
3406 // concept requirements
3407 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
3408 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3409 typename iterator_traits<_ForwardIter>::value_type,
3410 typename iterator_traits<_ForwardIter>::value_type>)
3411
3412 if (__first == __last) return __first;
3413 _ForwardIter __result = __first;
3414 while (++__first != __last)
3415 if (__comp(*__first, *__result))
3416 __result = __first;
3417 return __result;
3418 }
3419
3420 // next_permutation and prev_permutation, with and without an explicitly
3421 // supplied comparison function.
3422
3423 template<typename _BidirectionalIter>
3424 bool
3425 next_permutation(_BidirectionalIter __first, _BidirectionalIter __last)
3426 {
3427 // concept requirements
3428 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
3429 __glibcpp_function_requires(_LessThanComparableConcept<
3430 typename iterator_traits<_BidirectionalIter>::value_type>)
3431
3432 if (__first == __last)
3433 return false;
3434 _BidirectionalIter __i = __first;
3435 ++__i;
3436 if (__i == __last)
3437 return false;
3438 __i = __last;
3439 --__i;
3440
3441 for(;;) {
3442 _BidirectionalIter __ii = __i;
3443 --__i;
3444 if (*__i < *__ii) {
3445 _BidirectionalIter __j = __last;
3446 while (!(*__i < *--__j))
3447 {}
3448 iter_swap(__i, __j);
3449 reverse(__ii, __last);
3450 return true;
3451 }
3452 if (__i == __first) {
3453 reverse(__first, __last);
3454 return false;
3455 }
3456 }
3457 }
3458
3459 template<typename _BidirectionalIter, typename _Compare>
3460 bool
3461 next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
3462 _Compare __comp)
3463 {
3464 // concept requirements
3465 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
3466 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3467 typename iterator_traits<_BidirectionalIter>::value_type,
3468 typename iterator_traits<_BidirectionalIter>::value_type>)
3469
3470 if (__first == __last)
3471 return false;
3472 _BidirectionalIter __i = __first;
3473 ++__i;
3474 if (__i == __last)
3475 return false;
3476 __i = __last;
3477 --__i;
3478
3479 for(;;) {
3480 _BidirectionalIter __ii = __i;
3481 --__i;
3482 if (__comp(*__i, *__ii)) {
3483 _BidirectionalIter __j = __last;
3484 while (!__comp(*__i, *--__j))
3485 {}
3486 iter_swap(__i, __j);
3487 reverse(__ii, __last);
3488 return true;
3489 }
3490 if (__i == __first) {
3491 reverse(__first, __last);
3492 return false;
3493 }
3494 }
3495 }
3496
3497 template<typename _BidirectionalIter>
3498 bool
3499 prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last)
3500 {
3501 // concept requirements
3502 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
3503 __glibcpp_function_requires(_LessThanComparableConcept<
3504 typename iterator_traits<_BidirectionalIter>::value_type>)
3505
3506 if (__first == __last)
3507 return false;
3508 _BidirectionalIter __i = __first;
3509 ++__i;
3510 if (__i == __last)
3511 return false;
3512 __i = __last;
3513 --__i;
3514
3515 for(;;) {
3516 _BidirectionalIter __ii = __i;
3517 --__i;
3518 if (*__ii < *__i) {
3519 _BidirectionalIter __j = __last;
3520 while (!(*--__j < *__i))
3521 {}
3522 iter_swap(__i, __j);
3523 reverse(__ii, __last);
3524 return true;
3525 }
3526 if (__i == __first) {
3527 reverse(__first, __last);
3528 return false;
3529 }
3530 }
3531 }
3532
3533 template<typename _BidirectionalIter, typename _Compare>
3534 bool
3535 prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
3536 _Compare __comp)
3537 {
3538 // concept requirements
3539 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
3540 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3541 typename iterator_traits<_BidirectionalIter>::value_type,
3542 typename iterator_traits<_BidirectionalIter>::value_type>)
3543
3544 if (__first == __last)
3545 return false;
3546 _BidirectionalIter __i = __first;
3547 ++__i;
3548 if (__i == __last)
3549 return false;
3550 __i = __last;
3551 --__i;
3552
3553 for(;;) {
3554 _BidirectionalIter __ii = __i;
3555 --__i;
3556 if (__comp(*__ii, *__i)) {
3557 _BidirectionalIter __j = __last;
3558 while (!__comp(*--__j, *__i))
3559 {}
3560 iter_swap(__i, __j);
3561 reverse(__ii, __last);
3562 return true;
3563 }
3564 if (__i == __first) {
3565 reverse(__first, __last);
3566 return false;
3567 }
3568 }
3569 }
3570
3571 // find_first_of, with and without an explicitly supplied comparison function.
3572
3573 template<typename _InputIter, typename _ForwardIter>
3574 _InputIter
3575 find_first_of(_InputIter __first1, _InputIter __last1,
3576 _ForwardIter __first2, _ForwardIter __last2)
3577 {
3578 // concept requirements
3579 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
3580 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
3581 __glibcpp_function_requires(_EqualOpConcept<
3582 typename iterator_traits<_InputIter>::value_type,
3583 typename iterator_traits<_ForwardIter>::value_type>)
3584
3585 for ( ; __first1 != __last1; ++__first1)
3586 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
3587 if (*__first1 == *__iter)
3588 return __first1;
3589 return __last1;
3590 }
3591
3592 template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate>
3593 _InputIter
3594 find_first_of(_InputIter __first1, _InputIter __last1,
3595 _ForwardIter __first2, _ForwardIter __last2,
3596 _BinaryPredicate __comp)
3597 {
3598 // concept requirements
3599 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
3600 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
3601 __glibcpp_function_requires(_EqualOpConcept<
3602 typename iterator_traits<_InputIter>::value_type,
3603 typename iterator_traits<_ForwardIter>::value_type>)
3604 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3605 typename iterator_traits<_InputIter>::value_type,
3606 typename iterator_traits<_ForwardIter>::value_type>)
3607
3608 for ( ; __first1 != __last1; ++__first1)
3609 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
3610 if (__comp(*__first1, *__iter))
3611 return __first1;
3612 return __last1;
3613 }
3614
3615
3616 // find_end, with and without an explicitly supplied comparison function.
3617 // Search [first2, last2) as a subsequence in [first1, last1), and return
3618 // the *last* possible match. Note that find_end for bidirectional iterators
3619 // is much faster than for forward iterators.
3620
3621 // find_end for forward iterators.
3622 template<typename _ForwardIter1, typename _ForwardIter2>
3623 _ForwardIter1
3624 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
3625 _ForwardIter2 __first2, _ForwardIter2 __last2,
3626 forward_iterator_tag, forward_iterator_tag)
3627 {
3628 if (__first2 == __last2)
3629 return __last1;
3630 else {
3631 _ForwardIter1 __result = __last1;
3632 while (1) {
3633 _ForwardIter1 __new_result
3634 = search(__first1, __last1, __first2, __last2);
3635 if (__new_result == __last1)
3636 return __result;
3637 else {
3638 __result = __new_result;
3639 __first1 = __new_result;
3640 ++__first1;
3641 }
3642 }
3643 }
3644 }
3645
3646 template<typename _ForwardIter1, typename _ForwardIter2,
3647 typename _BinaryPredicate>
3648 _ForwardIter1
3649 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
3650 _ForwardIter2 __first2, _ForwardIter2 __last2,
3651 forward_iterator_tag, forward_iterator_tag,
3652 _BinaryPredicate __comp)
3653 {
3654 if (__first2 == __last2)
3655 return __last1;
3656 else {
3657 _ForwardIter1 __result = __last1;
3658 while (1) {
3659 _ForwardIter1 __new_result
3660 = search(__first1, __last1, __first2, __last2, __comp);
3661 if (__new_result == __last1)
3662 return __result;
3663 else {
3664 __result = __new_result;
3665 __first1 = __new_result;
3666 ++__first1;
3667 }
3668 }
3669 }
3670 }
3671
3672 // find_end for bidirectional iterators. Requires partial specialization.
3673 template<typename _BidirectionalIter1, typename _BidirectionalIter2>
3674 _BidirectionalIter1
3675 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
3676 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
3677 bidirectional_iterator_tag, bidirectional_iterator_tag)
3678 {
3679 // concept requirements
3680 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>)
3681 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>)
3682
3683 typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
3684 typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
3685
3686 _RevIter1 __rlast1(__first1);
3687 _RevIter2 __rlast2(__first2);
3688 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
3689 _RevIter2(__last2), __rlast2);
3690
3691 if (__rresult == __rlast1)
3692 return __last1;
3693 else {
3694 _BidirectionalIter1 __result = __rresult.base();
3695 advance(__result, -distance(__first2, __last2));
3696 return __result;
3697 }
3698 }
3699
3700 template<typename _BidirectionalIter1, typename _BidirectionalIter2,
3701 typename _BinaryPredicate>
3702 _BidirectionalIter1
3703 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
3704 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
3705 bidirectional_iterator_tag, bidirectional_iterator_tag,
3706 _BinaryPredicate __comp)
3707 {
3708 // concept requirements
3709 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>)
3710 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>)
3711
3712 typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
3713 typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
3714
3715 _RevIter1 __rlast1(__first1);
3716 _RevIter2 __rlast2(__first2);
3717 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
3718 _RevIter2(__last2), __rlast2,
3719 __comp);
3720
3721 if (__rresult == __rlast1)
3722 return __last1;
3723 else {
3724 _BidirectionalIter1 __result = __rresult.base();
3725 advance(__result, -distance(__first2, __last2));
3726 return __result;
3727 }
3728 }
3729
3730 // Dispatching functions for find_end.
3731
3732 template<typename _ForwardIter1, typename _ForwardIter2>
3733 inline _ForwardIter1
3734 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
3735 _ForwardIter2 __first2, _ForwardIter2 __last2)
3736 {
3737 // concept requirements
3738 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
3739 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
3740 __glibcpp_function_requires(_EqualOpConcept<
3741 typename iterator_traits<_ForwardIter1>::value_type,
3742 typename iterator_traits<_ForwardIter2>::value_type>)
3743
3744 return __find_end(__first1, __last1, __first2, __last2,
3745 __iterator_category(__first1),
3746 __iterator_category(__first2));
3747 }
3748
3749 template<typename _ForwardIter1, typename _ForwardIter2,
3750 typename _BinaryPredicate>
3751 inline _ForwardIter1
3752 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
3753 _ForwardIter2 __first2, _ForwardIter2 __last2,
3754 _BinaryPredicate __comp)
3755 {
3756 // concept requirements
3757 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
3758 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
3759 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3760 typename iterator_traits<_ForwardIter1>::value_type,
3761 typename iterator_traits<_ForwardIter2>::value_type>)
3762
3763 return __find_end(__first1, __last1, __first2, __last2,
3764 __iterator_category(__first1),
3765 __iterator_category(__first2),
3766 __comp);
3767 }
3768
3769 } // namespace std
3770
3771 #endif /* __GLIBCPP_INTERNAL_ALGO_H */
3772
Mirror of the offical gcc git repository hosted at gcc.gnu.org