Merge branch 'master' of ssh://crater.dragonflybsd.org/repository/git/dragonfly
[dragonfly.git] / contrib / gcc-3.4 / libstdc++-v3 / include / bits / stl_algo.h
CommitLineData
003757ed
MD
1// Algorithm implementation -*- C++ -*-
2
3// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 2, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// You should have received a copy of the GNU General Public License along
17// with this library; see the file COPYING. If not, write to the Free
18// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
19// USA.
20
21// As a special exception, you may use this file as part of a free software
22// library without restriction. Specifically, if other files instantiate
23// templates or use macros or inline functions from this file, or you compile
24// this file and link it with other files to produce an executable, this
25// file does not by itself cause the resulting executable to be covered by
26// the GNU General Public License. This exception does not however
27// invalidate any other reasons why the executable file might be covered by
28// the GNU General Public License.
29
30/*
31 *
32 * Copyright (c) 1994
33 * Hewlett-Packard Company
34 *
35 * Permission to use, copy, modify, distribute and sell this software
36 * and its documentation for any purpose is hereby granted without fee,
37 * provided that the above copyright notice appear in all copies and
38 * that both that copyright notice and this permission notice appear
39 * in supporting documentation. Hewlett-Packard Company makes no
40 * representations about the suitability of this software for any
41 * purpose. It is provided "as is" without express or implied warranty.
42 *
43 *
44 * Copyright (c) 1996
45 * Silicon Graphics Computer Systems, Inc.
46 *
47 * Permission to use, copy, modify, distribute and sell this software
48 * and its documentation for any purpose is hereby granted without fee,
49 * provided that the above copyright notice appear in all copies and
50 * that both that copyright notice and this permission notice appear
51 * in supporting documentation. Silicon Graphics makes no
52 * representations about the suitability of this software for any
53 * purpose. It is provided "as is" without express or implied warranty.
54 */
55
56/** @file stl_algo.h
57 * This is an internal header file, included by other library headers.
58 * You should not attempt to use it directly.
59 */
60
61#ifndef _ALGO_H
62#define _ALGO_H 1
63
64#include <bits/stl_heap.h>
65#include <bits/stl_tempbuf.h> // for _Temporary_buffer
66#include <debug/debug.h>
67
68// See concept_check.h for the __glibcxx_*_requires macros.
69
70namespace std
71{
72 /**
73 * @brief Find the median of three values.
74 * @param a A value.
75 * @param b A value.
76 * @param c A value.
77 * @return One of @p a, @p b or @p c.
78 *
79 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
80 * then the value returned will be @c m.
81 * This is an SGI extension.
82 * @ingroup SGIextensions
83 */
84 template<typename _Tp>
85 inline const _Tp&
86 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
87 {
88 // concept requirements
89 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
90 if (__a < __b)
91 if (__b < __c)
92 return __b;
93 else if (__a < __c)
94 return __c;
95 else
96 return __a;
97 else if (__a < __c)
98 return __a;
99 else if (__b < __c)
100 return __c;
101 else
102 return __b;
103 }
104
105 /**
106 * @brief Find the median of three values using a predicate for comparison.
107 * @param a A value.
108 * @param b A value.
109 * @param c A value.
110 * @param comp A binary predicate.
111 * @return One of @p a, @p b or @p c.
112 *
113 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
114 * and @p comp(m,n) are both true then the value returned will be @c m.
115 * This is an SGI extension.
116 * @ingroup SGIextensions
117 */
118 template<typename _Tp, typename _Compare>
119 inline const _Tp&
120 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
121 {
122 // concept requirements
123 __glibcxx_function_requires(_BinaryFunctionConcept<_Compare,bool,_Tp,_Tp>)
124 if (__comp(__a, __b))
125 if (__comp(__b, __c))
126 return __b;
127 else if (__comp(__a, __c))
128 return __c;
129 else
130 return __a;
131 else if (__comp(__a, __c))
132 return __a;
133 else if (__comp(__b, __c))
134 return __c;
135 else
136 return __b;
137 }
138
139 /**
140 * @brief Apply a function to every element of a sequence.
141 * @param first An input iterator.
142 * @param last An input iterator.
143 * @param f A unary function object.
144 * @return @p f.
145 *
146 * Applies the function object @p f to each element in the range
147 * @p [first,last). @p f must not modify the order of the sequence.
148 * If @p f has a return value it is ignored.
149 */
150 template<typename _InputIterator, typename _Function>
151 _Function
152 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
153 {
154 // concept requirements
155 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
156 __glibcxx_requires_valid_range(__first, __last);
157 for ( ; __first != __last; ++__first)
158 __f(*__first);
159 return __f;
160 }
161
162 /**
163 * @if maint
164 * This is an overload used by find() for the Input Iterator case.
165 * @endif
166 */
167 template<typename _InputIterator, typename _Tp>
168 inline _InputIterator
169 find(_InputIterator __first, _InputIterator __last,
170 const _Tp& __val, input_iterator_tag)
171 {
172 while (__first != __last && !(*__first == __val))
173 ++__first;
174 return __first;
175 }
176
177 /**
178 * @if maint
179 * This is an overload used by find_if() for the Input Iterator case.
180 * @endif
181 */
182 template<typename _InputIterator, typename _Predicate>
183 inline _InputIterator
184 find_if(_InputIterator __first, _InputIterator __last,
185 _Predicate __pred, input_iterator_tag)
186 {
187 while (__first != __last && !__pred(*__first))
188 ++__first;
189 return __first;
190 }
191
192 /**
193 * @if maint
194 * This is an overload used by find() for the RAI case.
195 * @endif
196 */
197 template<typename _RandomAccessIterator, typename _Tp>
198 _RandomAccessIterator
199 find(_RandomAccessIterator __first, _RandomAccessIterator __last,
200 const _Tp& __val, random_access_iterator_tag)
201 {
202 typename iterator_traits<_RandomAccessIterator>::difference_type
203 __trip_count = (__last - __first) >> 2;
204
205 for ( ; __trip_count > 0 ; --__trip_count)
206 {
207 if (*__first == __val)
208 return __first;
209 ++__first;
210
211 if (*__first == __val)
212 return __first;
213 ++__first;
214
215 if (*__first == __val)
216 return __first;
217 ++__first;
218
219 if (*__first == __val)
220 return __first;
221 ++__first;
222 }
223
224 switch (__last - __first)
225 {
226 case 3:
227 if (*__first == __val)
228 return __first;
229 ++__first;
230 case 2:
231 if (*__first == __val)
232 return __first;
233 ++__first;
234 case 1:
235 if (*__first == __val)
236 return __first;
237 ++__first;
238 case 0:
239 default:
240 return __last;
241 }
242 }
243
244 /**
245 * @if maint
246 * This is an overload used by find_if() for the RAI case.
247 * @endif
248 */
249 template<typename _RandomAccessIterator, typename _Predicate>
250 _RandomAccessIterator
251 find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
252 _Predicate __pred, random_access_iterator_tag)
253 {
254 typename iterator_traits<_RandomAccessIterator>::difference_type
255 __trip_count = (__last - __first) >> 2;
256
257 for ( ; __trip_count > 0 ; --__trip_count)
258 {
259 if (__pred(*__first))
260 return __first;
261 ++__first;
262
263 if (__pred(*__first))
264 return __first;
265 ++__first;
266
267 if (__pred(*__first))
268 return __first;
269 ++__first;
270
271 if (__pred(*__first))
272 return __first;
273 ++__first;
274 }
275
276 switch (__last - __first)
277 {
278 case 3:
279 if (__pred(*__first))
280 return __first;
281 ++__first;
282 case 2:
283 if (__pred(*__first))
284 return __first;
285 ++__first;
286 case 1:
287 if (__pred(*__first))
288 return __first;
289 ++__first;
290 case 0:
291 default:
292 return __last;
293 }
294 }
295
296 /**
297 * @brief Find the first occurrence of a value in a sequence.
298 * @param first An input iterator.
299 * @param last An input iterator.
300 * @param val The value to find.
301 * @return The first iterator @c i in the range @p [first,last)
302 * such that @c *i == @p val, or @p last if no such iterator exists.
303 */
304 template<typename _InputIterator, typename _Tp>
305 inline _InputIterator
306 find(_InputIterator __first, _InputIterator __last,
307 const _Tp& __val)
308 {
309 // concept requirements
310 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
311 __glibcxx_function_requires(_EqualOpConcept<
312 typename iterator_traits<_InputIterator>::value_type, _Tp>)
313 __glibcxx_requires_valid_range(__first, __last);
314 return std::find(__first, __last, __val,
315 std::__iterator_category(__first));
316 }
317
318 /**
319 * @brief Find the first element in a sequence for which a predicate is true.
320 * @param first An input iterator.
321 * @param last An input iterator.
322 * @param pred A predicate.
323 * @return The first iterator @c i in the range @p [first,last)
324 * such that @p pred(*i) is true, or @p last if no such iterator exists.
325 */
326 template<typename _InputIterator, typename _Predicate>
327 inline _InputIterator
328 find_if(_InputIterator __first, _InputIterator __last,
329 _Predicate __pred)
330 {
331 // concept requirements
332 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
333 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
334 typename iterator_traits<_InputIterator>::value_type>)
335 __glibcxx_requires_valid_range(__first, __last);
336 return std::find_if(__first, __last, __pred,
337 std::__iterator_category(__first));
338 }
339
340 /**
341 * @brief Find two adjacent values in a sequence that are equal.
342 * @param first A forward iterator.
343 * @param last A forward iterator.
344 * @return The first iterator @c i such that @c i and @c i+1 are both
345 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
346 * or @p last if no such iterator exists.
347 */
348 template<typename _ForwardIterator>
349 _ForwardIterator
350 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
351 {
352 // concept requirements
353 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
354 __glibcxx_function_requires(_EqualityComparableConcept<
355 typename iterator_traits<_ForwardIterator>::value_type>)
356 __glibcxx_requires_valid_range(__first, __last);
357 if (__first == __last)
358 return __last;
359 _ForwardIterator __next = __first;
360 while(++__next != __last)
361 {
362 if (*__first == *__next)
363 return __first;
364 __first = __next;
365 }
366 return __last;
367 }
368
369 /**
370 * @brief Find two adjacent values in a sequence using a predicate.
371 * @param first A forward iterator.
372 * @param last A forward iterator.
373 * @param binary_pred A binary predicate.
374 * @return The first iterator @c i such that @c i and @c i+1 are both
375 * valid iterators in @p [first,last) and such that
376 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
377 * exists.
378 */
379 template<typename _ForwardIterator, typename _BinaryPredicate>
380 _ForwardIterator
381 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
382 _BinaryPredicate __binary_pred)
383 {
384 // concept requirements
385 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
386 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
387 typename iterator_traits<_ForwardIterator>::value_type,
388 typename iterator_traits<_ForwardIterator>::value_type>)
389 __glibcxx_requires_valid_range(__first, __last);
390 if (__first == __last)
391 return __last;
392 _ForwardIterator __next = __first;
393 while(++__next != __last)
394 {
395 if (__binary_pred(*__first, *__next))
396 return __first;
397 __first = __next;
398 }
399 return __last;
400 }
401
402 /**
403 * @brief Count the number of copies of a value in a sequence.
404 * @param first An input iterator.
405 * @param last An input iterator.
406 * @param value The value to be counted.
407 * @return The number of iterators @c i in the range @p [first,last)
408 * for which @c *i == @p value
409 */
410 template<typename _InputIterator, typename _Tp>
411 typename iterator_traits<_InputIterator>::difference_type
412 count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
413 {
414 // concept requirements
415 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
416 __glibcxx_function_requires(_EqualityComparableConcept<
417 typename iterator_traits<_InputIterator>::value_type >)
418 __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
419 __glibcxx_requires_valid_range(__first, __last);
420 typename iterator_traits<_InputIterator>::difference_type __n = 0;
421 for ( ; __first != __last; ++__first)
422 if (*__first == __value)
423 ++__n;
424 return __n;
425 }
426
427 /**
428 * @brief Count the elements of a sequence for which a predicate is true.
429 * @param first An input iterator.
430 * @param last An input iterator.
431 * @param pred A predicate.
432 * @return The number of iterators @c i in the range @p [first,last)
433 * for which @p pred(*i) is true.
434 */
435 template<typename _InputIterator, typename _Predicate>
436 typename iterator_traits<_InputIterator>::difference_type
437 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
438 {
439 // concept requirements
440 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
441 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
442 typename iterator_traits<_InputIterator>::value_type>)
443 __glibcxx_requires_valid_range(__first, __last);
444 typename iterator_traits<_InputIterator>::difference_type __n = 0;
445 for ( ; __first != __last; ++__first)
446 if (__pred(*__first))
447 ++__n;
448 return __n;
449 }
450
451 /**
452 * @brief Search a sequence for a matching sub-sequence.
453 * @param first1 A forward iterator.
454 * @param last1 A forward iterator.
455 * @param first2 A forward iterator.
456 * @param last2 A forward iterator.
457 * @return The first iterator @c i in the range
458 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
459 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
460 * such iterator exists.
461 *
462 * Searches the range @p [first1,last1) for a sub-sequence that compares
463 * equal value-by-value with the sequence given by @p [first2,last2) and
464 * returns an iterator to the first element of the sub-sequence, or
465 * @p last1 if the sub-sequence is not found.
466 *
467 * Because the sub-sequence must lie completely within the range
468 * @p [first1,last1) it must start at a position less than
469 * @p last1-(last2-first2) where @p last2-first2 is the length of the
470 * sub-sequence.
471 * This means that the returned iterator @c i will be in the range
472 * @p [first1,last1-(last2-first2))
473 */
474 template<typename _ForwardIterator1, typename _ForwardIterator2>
475 _ForwardIterator1
476 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
477 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
478 {
479 // concept requirements
480 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
481 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
482 __glibcxx_function_requires(_EqualOpConcept<
483 typename iterator_traits<_ForwardIterator1>::value_type,
484 typename iterator_traits<_ForwardIterator2>::value_type>)
485 __glibcxx_requires_valid_range(__first1, __last1);
486 __glibcxx_requires_valid_range(__first2, __last2);
487 // Test for empty ranges
488 if (__first1 == __last1 || __first2 == __last2)
489 return __first1;
490
491 // Test for a pattern of length 1.
492 _ForwardIterator2 __tmp(__first2);
493 ++__tmp;
494 if (__tmp == __last2)
495 return std::find(__first1, __last1, *__first2);
496
497 // General case.
498 _ForwardIterator2 __p1, __p;
499 __p1 = __first2; ++__p1;
500 _ForwardIterator1 __current = __first1;
501
502 while (__first1 != __last1)
503 {
504 __first1 = std::find(__first1, __last1, *__first2);
505 if (__first1 == __last1)
506 return __last1;
507
508 __p = __p1;
509 __current = __first1;
510 if (++__current == __last1)
511 return __last1;
512
513 while (*__current == *__p)
514 {
515 if (++__p == __last2)
516 return __first1;
517 if (++__current == __last1)
518 return __last1;
519 }
520 ++__first1;
521 }
522 return __first1;
523 }
524
525 /**
526 * @brief Search a sequence for a matching sub-sequence using a predicate.
527 * @param first1 A forward iterator.
528 * @param last1 A forward iterator.
529 * @param first2 A forward iterator.
530 * @param last2 A forward iterator.
531 * @param predicate A binary predicate.
532 * @return The first iterator @c i in the range
533 * @p [first1,last1-(last2-first2)) such that
534 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
535 * @p [0,last2-first2), or @p last1 if no such iterator exists.
536 *
537 * Searches the range @p [first1,last1) for a sub-sequence that compares
538 * equal value-by-value with the sequence given by @p [first2,last2),
539 * using @p predicate to determine equality, and returns an iterator
540 * to the first element of the sub-sequence, or @p last1 if no such
541 * iterator exists.
542 *
543 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
544 */
545 template<typename _ForwardIterator1, typename _ForwardIterator2,
546 typename _BinaryPredicate>
547 _ForwardIterator1
548 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
549 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
550 _BinaryPredicate __predicate)
551 {
552 // concept requirements
553 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
554 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
555 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
556 typename iterator_traits<_ForwardIterator1>::value_type,
557 typename iterator_traits<_ForwardIterator2>::value_type>)
558 __glibcxx_requires_valid_range(__first1, __last1);
559 __glibcxx_requires_valid_range(__first2, __last2);
560
561 // Test for empty ranges
562 if (__first1 == __last1 || __first2 == __last2)
563 return __first1;
564
565 // Test for a pattern of length 1.
566 _ForwardIterator2 __tmp(__first2);
567 ++__tmp;
568 if (__tmp == __last2)
569 {
570 while (__first1 != __last1 && !__predicate(*__first1, *__first2))
571 ++__first1;
572 return __first1;
573 }
574
575 // General case.
576 _ForwardIterator2 __p1, __p;
577 __p1 = __first2; ++__p1;
578 _ForwardIterator1 __current = __first1;
579
580 while (__first1 != __last1)
581 {
582 while (__first1 != __last1)
583 {
584 if (__predicate(*__first1, *__first2))
585 break;
586 ++__first1;
587 }
588 while (__first1 != __last1 && !__predicate(*__first1, *__first2))
589 ++__first1;
590 if (__first1 == __last1)
591 return __last1;
592
593 __p = __p1;
594 __current = __first1;
595 if (++__current == __last1)
596 return __last1;
597
598 while (__predicate(*__current, *__p))
599 {
600 if (++__p == __last2)
601 return __first1;
602 if (++__current == __last1)
603 return __last1;
604 }
605 ++__first1;
606 }
607 return __first1;
608 }
609
610 /**
611 * @brief Search a sequence for a number of consecutive values.
612 * @param first A forward iterator.
613 * @param last A forward iterator.
614 * @param count The number of consecutive values.
615 * @param val The value to find.
616 * @return The first iterator @c i in the range @p [first,last-count)
617 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
618 * or @p last if no such iterator exists.
619 *
620 * Searches the range @p [first,last) for @p count consecutive elements
621 * equal to @p val.
622 */
623 template<typename _ForwardIterator, typename _Integer, typename _Tp>
624 _ForwardIterator
625 search_n(_ForwardIterator __first, _ForwardIterator __last,
626 _Integer __count, const _Tp& __val)
627 {
628 // concept requirements
629 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
630 __glibcxx_function_requires(_EqualityComparableConcept<
631 typename iterator_traits<_ForwardIterator>::value_type>)
632 __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
633 __glibcxx_requires_valid_range(__first, __last);
634
635 if (__count <= 0)
636 return __first;
637 else
638 {
639 __first = std::find(__first, __last, __val);
640 while (__first != __last)
641 {
642 typename iterator_traits<_ForwardIterator>::difference_type
643 __n = __count;
644 _ForwardIterator __i = __first;
645 ++__i;
646 while (__i != __last && __n != 1 && *__i == __val)
647 {
648 ++__i;
649 --__n;
650 }
651 if (__n == 1)
652 return __first;
653 else
654 __first = std::find(__i, __last, __val);
655 }
656 return __last;
657 }
658 }
659
660 /**
661 * @brief Search a sequence for a number of consecutive values using a
662 * predicate.
663 * @param first A forward iterator.
664 * @param last A forward iterator.
665 * @param count The number of consecutive values.
666 * @param val The value to find.
667 * @param binary_pred A binary predicate.
668 * @return The first iterator @c i in the range @p [first,last-count)
669 * such that @p binary_pred(*(i+N),val) is true for each @c N in the
670 * range @p [0,count), or @p last if no such iterator exists.
671 *
672 * Searches the range @p [first,last) for @p count consecutive elements
673 * for which the predicate returns true.
674 */
675 template<typename _ForwardIterator, typename _Integer, typename _Tp,
676 typename _BinaryPredicate>
677 _ForwardIterator
678 search_n(_ForwardIterator __first, _ForwardIterator __last,
679 _Integer __count, const _Tp& __val,
680 _BinaryPredicate __binary_pred)
681 {
682 // concept requirements
683 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
684 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
685 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
686 __glibcxx_requires_valid_range(__first, __last);
687
688 if (__count <= 0)
689 return __first;
690 else
691 {
692 while (__first != __last)
693 {
694 if (__binary_pred(*__first, __val))
695 break;
696 ++__first;
697 }
698 while (__first != __last)
699 {
700 typename iterator_traits<_ForwardIterator>::difference_type
701 __n = __count;
702 _ForwardIterator __i = __first;
703 ++__i;
704 while (__i != __last && __n != 1 && __binary_pred(*__i, __val))
705 {
706 ++__i;
707 --__n;
708 }
709 if (__n == 1)
710 return __first;
711 else
712 {
713 while (__i != __last)
714 {
715 if (__binary_pred(*__i, __val))
716 break;
717 ++__i;
718 }
719 __first = __i;
720 }
721 }
722 return __last;
723 }
724 }
725
726 /**
727 * @brief Swap the elements of two sequences.
728 * @param first1 A forward iterator.
729 * @param last1 A forward iterator.
730 * @param first2 A forward iterator.
731 * @return An iterator equal to @p first2+(last1-first1).
732 *
733 * Swaps each element in the range @p [first1,last1) with the
734 * corresponding element in the range @p [first2,(last1-first1)).
735 * The ranges must not overlap.
736 */
737 template<typename _ForwardIterator1, typename _ForwardIterator2>
738 _ForwardIterator2
739 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
740 _ForwardIterator2 __first2)
741 {
742 // concept requirements
743 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
744 _ForwardIterator1>)
745 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
746 _ForwardIterator2>)
747 __glibcxx_function_requires(_ConvertibleConcept<
748 typename iterator_traits<_ForwardIterator1>::value_type,
749 typename iterator_traits<_ForwardIterator2>::value_type>)
750 __glibcxx_function_requires(_ConvertibleConcept<
751 typename iterator_traits<_ForwardIterator2>::value_type,
752 typename iterator_traits<_ForwardIterator1>::value_type>)
753 __glibcxx_requires_valid_range(__first1, __last1);
754
755 for ( ; __first1 != __last1; ++__first1, ++__first2)
756 std::iter_swap(__first1, __first2);
757 return __first2;
758 }
759
760 /**
761 * @brief Perform an operation on a sequence.
762 * @param first An input iterator.
763 * @param last An input iterator.
764 * @param result An output iterator.
765 * @param unary_op A unary operator.
766 * @return An output iterator equal to @p result+(last-first).
767 *
768 * Applies the operator to each element in the input range and assigns
769 * the results to successive elements of the output sequence.
770 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
771 * range @p [0,last-first).
772 *
773 * @p unary_op must not alter its argument.
774 */
775 template<typename _InputIterator, typename _OutputIterator,
776 typename _UnaryOperation>
777 _OutputIterator
778 transform(_InputIterator __first, _InputIterator __last,
779 _OutputIterator __result, _UnaryOperation __unary_op)
780 {
781 // concept requirements
782 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
783 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
784 // "the type returned by a _UnaryOperation"
785 __typeof__(__unary_op(*__first))>)
786 __glibcxx_requires_valid_range(__first, __last);
787
788 for ( ; __first != __last; ++__first, ++__result)
789 *__result = __unary_op(*__first);
790 return __result;
791 }
792
793 /**
794 * @brief Perform an operation on corresponding elements of two sequences.
795 * @param first1 An input iterator.
796 * @param last1 An input iterator.
797 * @param first2 An input iterator.
798 * @param result An output iterator.
799 * @param binary_op A binary operator.
800 * @return An output iterator equal to @p result+(last-first).
801 *
802 * Applies the operator to the corresponding elements in the two
803 * input ranges and assigns the results to successive elements of the
804 * output sequence.
805 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
806 * @c N in the range @p [0,last1-first1).
807 *
808 * @p binary_op must not alter either of its arguments.
809 */
810 template<typename _InputIterator1, typename _InputIterator2,
811 typename _OutputIterator, typename _BinaryOperation>
812 _OutputIterator
813 transform(_InputIterator1 __first1, _InputIterator1 __last1,
814 _InputIterator2 __first2, _OutputIterator __result,
815 _BinaryOperation __binary_op)
816 {
817 // concept requirements
818 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
819 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
820 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
821 // "the type returned by a _BinaryOperation"
822 __typeof__(__binary_op(*__first1,*__first2))>)
823 __glibcxx_requires_valid_range(__first1, __last1);
824
825 for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
826 *__result = __binary_op(*__first1, *__first2);
827 return __result;
828 }
829
830 /**
831 * @brief Replace each occurrence of one value in a sequence with another
832 * value.
833 * @param first A forward iterator.
834 * @param last A forward iterator.
835 * @param old_value The value to be replaced.
836 * @param new_value The replacement value.
837 * @return replace() returns no value.
838 *
839 * For each iterator @c i in the range @p [first,last) if @c *i ==
840 * @p old_value then the assignment @c *i = @p new_value is performed.
841 */
842 template<typename _ForwardIterator, typename _Tp>
843 void
844 replace(_ForwardIterator __first, _ForwardIterator __last,
845 const _Tp& __old_value, const _Tp& __new_value)
846 {
847 // concept requirements
848 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
849 _ForwardIterator>)
850 __glibcxx_function_requires(_EqualOpConcept<
851 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
852 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
853 typename iterator_traits<_ForwardIterator>::value_type>)
854 __glibcxx_requires_valid_range(__first, __last);
855
856 for ( ; __first != __last; ++__first)
857 if (*__first == __old_value)
858 *__first = __new_value;
859 }
860
861 /**
862 * @brief Replace each value in a sequence for which a predicate returns
863 * true with another value.
864 * @param first A forward iterator.
865 * @param last A forward iterator.
866 * @param pred A predicate.
867 * @param new_value The replacement value.
868 * @return replace_if() returns no value.
869 *
870 * For each iterator @c i in the range @p [first,last) if @p pred(*i)
871 * is true then the assignment @c *i = @p new_value is performed.
872 */
873 template<typename _ForwardIterator, typename _Predicate, typename _Tp>
874 void
875 replace_if(_ForwardIterator __first, _ForwardIterator __last,
876 _Predicate __pred, const _Tp& __new_value)
877 {
878 // concept requirements
879 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
880 _ForwardIterator>)
881 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
882 typename iterator_traits<_ForwardIterator>::value_type>)
883 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
884 typename iterator_traits<_ForwardIterator>::value_type>)
885 __glibcxx_requires_valid_range(__first, __last);
886
887 for ( ; __first != __last; ++__first)
888 if (__pred(*__first))
889 *__first = __new_value;
890 }
891
892 /**
893 * @brief Copy a sequence, replacing each element of one value with another
894 * value.
895 * @param first An input iterator.
896 * @param last An input iterator.
897 * @param result An output iterator.
898 * @param old_value The value to be replaced.
899 * @param new_value The replacement value.
900 * @return The end of the output sequence, @p result+(last-first).
901 *
902 * Copies each element in the input range @p [first,last) to the
903 * output range @p [result,result+(last-first)) replacing elements
904 * equal to @p old_value with @p new_value.
905 */
906 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
907 _OutputIterator
908 replace_copy(_InputIterator __first, _InputIterator __last,
909 _OutputIterator __result,
910 const _Tp& __old_value, const _Tp& __new_value)
911 {
912 // concept requirements
913 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
914 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
915 typename iterator_traits<_InputIterator>::value_type>)
916 __glibcxx_function_requires(_EqualOpConcept<
917 typename iterator_traits<_InputIterator>::value_type, _Tp>)
918 __glibcxx_requires_valid_range(__first, __last);
919
920 for ( ; __first != __last; ++__first, ++__result)
921 *__result = *__first == __old_value ? __new_value : *__first;
922 return __result;
923 }
924
925 /**
926 * @brief Copy a sequence, replacing each value for which a predicate
927 * returns true with another value.
928 * @param first An input iterator.
929 * @param last An input iterator.
930 * @param result An output iterator.
931 * @param pred A predicate.
932 * @param new_value The replacement value.
933 * @return The end of the output sequence, @p result+(last-first).
934 *
935 * Copies each element in the range @p [first,last) to the range
936 * @p [result,result+(last-first)) replacing elements for which
937 * @p pred returns true with @p new_value.
938 */
939 template<typename _InputIterator, typename _OutputIterator,
940 typename _Predicate, typename _Tp>
941 _OutputIterator
942 replace_copy_if(_InputIterator __first, _InputIterator __last,
943 _OutputIterator __result,
944 _Predicate __pred, const _Tp& __new_value)
945 {
946 // concept requirements
947 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
948 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
949 typename iterator_traits<_InputIterator>::value_type>)
950 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
951 typename iterator_traits<_InputIterator>::value_type>)
952 __glibcxx_requires_valid_range(__first, __last);
953
954 for ( ; __first != __last; ++__first, ++__result)
955 *__result = __pred(*__first) ? __new_value : *__first;
956 return __result;
957 }
958
959 /**
960 * @brief Assign the result of a function object to each value in a
961 * sequence.
962 * @param first A forward iterator.
963 * @param last A forward iterator.
964 * @param gen A function object taking no arguments.
965 * @return generate() returns no value.
966 *
967 * Performs the assignment @c *i = @p gen() for each @c i in the range
968 * @p [first,last).
969 */
970 template<typename _ForwardIterator, typename _Generator>
971 void
972 generate(_ForwardIterator __first, _ForwardIterator __last,
973 _Generator __gen)
974 {
975 // concept requirements
976 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
977 __glibcxx_function_requires(_GeneratorConcept<_Generator,
978 typename iterator_traits<_ForwardIterator>::value_type>)
979 __glibcxx_requires_valid_range(__first, __last);
980
981 for ( ; __first != __last; ++__first)
982 *__first = __gen();
983 }
984
985 /**
986 * @brief Assign the result of a function object to each value in a
987 * sequence.
988 * @param first A forward iterator.
989 * @param n The length of the sequence.
990 * @param gen A function object taking no arguments.
991 * @return The end of the sequence, @p first+n
992 *
993 * Performs the assignment @c *i = @p gen() for each @c i in the range
994 * @p [first,first+n).
995 */
996 template<typename _OutputIterator, typename _Size, typename _Generator>
997 _OutputIterator
998 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
999 {
1000 // concept requirements
1001 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1002 // "the type returned by a _Generator"
1003 __typeof__(__gen())>)
1004
1005 for ( ; __n > 0; --__n, ++__first)
1006 *__first = __gen();
1007 return __first;
1008 }
1009
1010 /**
1011 * @brief Copy a sequence, removing elements of a given value.
1012 * @param first An input iterator.
1013 * @param last An input iterator.
1014 * @param result An output iterator.
1015 * @param value The value to be removed.
1016 * @return An iterator designating the end of the resulting sequence.
1017 *
1018 * Copies each element in the range @p [first,last) not equal to @p value
1019 * to the range beginning at @p result.
1020 * remove_copy() is stable, so the relative order of elements that are
1021 * copied is unchanged.
1022 */
1023 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
1024 _OutputIterator
1025 remove_copy(_InputIterator __first, _InputIterator __last,
1026 _OutputIterator __result, const _Tp& __value)
1027 {
1028 // concept requirements
1029 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1030 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1031 typename iterator_traits<_InputIterator>::value_type>)
1032 __glibcxx_function_requires(_EqualOpConcept<
1033 typename iterator_traits<_InputIterator>::value_type, _Tp>)
1034 __glibcxx_requires_valid_range(__first, __last);
1035
1036 for ( ; __first != __last; ++__first)
1037 if (!(*__first == __value))
1038 {
1039 *__result = *__first;
1040 ++__result;
1041 }
1042 return __result;
1043 }
1044
1045 /**
1046 * @brief Copy a sequence, removing elements for which a predicate is true.
1047 * @param first An input iterator.
1048 * @param last An input iterator.
1049 * @param result An output iterator.
1050 * @param pred A predicate.
1051 * @return An iterator designating the end of the resulting sequence.
1052 *
1053 * Copies each element in the range @p [first,last) for which
1054 * @p pred returns true to the range beginning at @p result.
1055 *
1056 * remove_copy_if() is stable, so the relative order of elements that are
1057 * copied is unchanged.
1058 */
1059 template<typename _InputIterator, typename _OutputIterator,
1060 typename _Predicate>
1061 _OutputIterator
1062 remove_copy_if(_InputIterator __first, _InputIterator __last,
1063 _OutputIterator __result, _Predicate __pred)
1064 {
1065 // concept requirements
1066 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1067 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1068 typename iterator_traits<_InputIterator>::value_type>)
1069 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1070 typename iterator_traits<_InputIterator>::value_type>)
1071 __glibcxx_requires_valid_range(__first, __last);
1072
1073 for ( ; __first != __last; ++__first)
1074 if (!__pred(*__first))
1075 {
1076 *__result = *__first;
1077 ++__result;
1078 }
1079 return __result;
1080 }
1081
1082 /**
1083 * @brief Remove elements from a sequence.
1084 * @param first An input iterator.
1085 * @param last An input iterator.
1086 * @param value The value to be removed.
1087 * @return An iterator designating the end of the resulting sequence.
1088 *
1089 * All elements equal to @p value are removed from the range
1090 * @p [first,last).
1091 *
1092 * remove() is stable, so the relative order of elements that are
1093 * not removed is unchanged.
1094 *
1095 * Elements between the end of the resulting sequence and @p last
1096 * are still present, but their value is unspecified.
1097 */
1098 template<typename _ForwardIterator, typename _Tp>
1099 _ForwardIterator
1100 remove(_ForwardIterator __first, _ForwardIterator __last,
1101 const _Tp& __value)
1102 {
1103 // concept requirements
1104 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1105 _ForwardIterator>)
003757ed
MD
1106 __glibcxx_function_requires(_EqualOpConcept<
1107 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1108 __glibcxx_requires_valid_range(__first, __last);
1109
1110 __first = std::find(__first, __last, __value);
1111 _ForwardIterator __i = __first;
1112 return __first == __last ? __first
1113 : std::remove_copy(++__i, __last,
1114 __first, __value);
1115 }
1116
1117 /**
1118 * @brief Remove elements from a sequence using a predicate.
1119 * @param first A forward iterator.
1120 * @param last A forward iterator.
1121 * @param pred A predicate.
1122 * @return An iterator designating the end of the resulting sequence.
1123 *
1124 * All elements for which @p pred returns true are removed from the range
1125 * @p [first,last).
1126 *
1127 * remove_if() is stable, so the relative order of elements that are
1128 * not removed is unchanged.
1129 *
1130 * Elements between the end of the resulting sequence and @p last
1131 * are still present, but their value is unspecified.
1132 */
1133 template<typename _ForwardIterator, typename _Predicate>
1134 _ForwardIterator
1135 remove_if(_ForwardIterator __first, _ForwardIterator __last,
1136 _Predicate __pred)
1137 {
1138 // concept requirements
1139 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1140 _ForwardIterator>)
1141 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1142 typename iterator_traits<_ForwardIterator>::value_type>)
1143 __glibcxx_requires_valid_range(__first, __last);
1144
1145 __first = std::find_if(__first, __last, __pred);
1146 _ForwardIterator __i = __first;
1147 return __first == __last ? __first
1148 : std::remove_copy_if(++__i, __last,
1149 __first, __pred);
1150 }
1151
1152 /**
1153 * @if maint
1154 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1155 * _OutputIterator)
1156 * overloaded for output iterators.
1157 * @endif
1158 */
1159 template<typename _InputIterator, typename _OutputIterator>
1160 _OutputIterator
1161 __unique_copy(_InputIterator __first, _InputIterator __last,
1162 _OutputIterator __result,
1163 output_iterator_tag)
1164 {
1165 // concept requirements -- taken care of in dispatching function
1166 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1167 *__result = __value;
1168 while (++__first != __last)
1169 if (!(__value == *__first))
1170 {
1171 __value = *__first;
1172 *++__result = __value;
1173 }
1174 return ++__result;
1175 }
1176
1177 /**
1178 * @if maint
1179 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1180 * _OutputIterator)
1181 * overloaded for forward iterators.
1182 * @endif
1183 */
1184 template<typename _InputIterator, typename _ForwardIterator>
1185 _ForwardIterator
1186 __unique_copy(_InputIterator __first, _InputIterator __last,
1187 _ForwardIterator __result,
1188 forward_iterator_tag)
1189 {
1190 // concept requirements -- taken care of in dispatching function
1191 *__result = *__first;
1192 while (++__first != __last)
1193 if (!(*__result == *__first))
1194 *++__result = *__first;
1195 return ++__result;
1196 }
1197
1198 /**
1199 * @if maint
1200 * This is an uglified
1201 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1202 * _BinaryPredicate)
1203 * overloaded for output iterators.
1204 * @endif
1205 */
1206 template<typename _InputIterator, typename _OutputIterator,
1207 typename _BinaryPredicate>
1208 _OutputIterator
1209 __unique_copy(_InputIterator __first, _InputIterator __last,
1210 _OutputIterator __result,
1211 _BinaryPredicate __binary_pred,
1212 output_iterator_tag)
1213 {
1214 // concept requirements -- iterators already checked
1215 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1216 typename iterator_traits<_InputIterator>::value_type,
1217 typename iterator_traits<_InputIterator>::value_type>)
1218
1219 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1220 *__result = __value;
1221 while (++__first != __last)
1222 if (!__binary_pred(__value, *__first))
1223 {
1224 __value = *__first;
1225 *++__result = __value;
1226 }
1227 return ++__result;
1228 }
1229
1230 /**
1231 * @if maint
1232 * This is an uglified
1233 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1234 * _BinaryPredicate)
1235 * overloaded for forward iterators.
1236 * @endif
1237 */
1238 template<typename _InputIterator, typename _ForwardIterator,
1239 typename _BinaryPredicate>
1240 _ForwardIterator
1241 __unique_copy(_InputIterator __first, _InputIterator __last,
1242 _ForwardIterator __result,
1243 _BinaryPredicate __binary_pred,
1244 forward_iterator_tag)
1245 {
1246 // concept requirements -- iterators already checked
1247 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1248 typename iterator_traits<_ForwardIterator>::value_type,
1249 typename iterator_traits<_InputIterator>::value_type>)
1250
1251 *__result = *__first;
1252 while (++__first != __last)
1253 if (!__binary_pred(*__result, *__first)) *++__result = *__first;
1254 return ++__result;
1255 }
1256
1257 /**
1258 * @brief Copy a sequence, removing consecutive duplicate values.
1259 * @param first An input iterator.
1260 * @param last An input iterator.
1261 * @param result An output iterator.
1262 * @return An iterator designating the end of the resulting sequence.
1263 *
1264 * Copies each element in the range @p [first,last) to the range
1265 * beginning at @p result, except that only the first element is copied
1266 * from groups of consecutive elements that compare equal.
1267 * unique_copy() is stable, so the relative order of elements that are
1268 * copied is unchanged.
1269 */
1270 template<typename _InputIterator, typename _OutputIterator>
1271 inline _OutputIterator
1272 unique_copy(_InputIterator __first, _InputIterator __last,
1273 _OutputIterator __result)
1274 {
1275 // concept requirements
1276 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1277 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1278 typename iterator_traits<_InputIterator>::value_type>)
1279 __glibcxx_function_requires(_EqualityComparableConcept<
1280 typename iterator_traits<_InputIterator>::value_type>)
1281 __glibcxx_requires_valid_range(__first, __last);
1282
1283 typedef typename iterator_traits<_OutputIterator>::iterator_category
1284 _IterType;
1285
1286 if (__first == __last) return __result;
1287 return std::__unique_copy(__first, __last, __result, _IterType());
1288 }
1289
1290 /**
1291 * @brief Copy a sequence, removing consecutive values using a predicate.
1292 * @param first An input iterator.
1293 * @param last An input iterator.
1294 * @param result An output iterator.
1295 * @param binary_pred A binary predicate.
1296 * @return An iterator designating the end of the resulting sequence.
1297 *
1298 * Copies each element in the range @p [first,last) to the range
1299 * beginning at @p result, except that only the first element is copied
1300 * from groups of consecutive elements for which @p binary_pred returns
1301 * true.
1302 * unique_copy() is stable, so the relative order of elements that are
1303 * copied is unchanged.
1304 */
1305 template<typename _InputIterator, typename _OutputIterator,
1306 typename _BinaryPredicate>
1307 inline _OutputIterator
1308 unique_copy(_InputIterator __first, _InputIterator __last,
1309 _OutputIterator __result,
1310 _BinaryPredicate __binary_pred)
1311 {
1312 // concept requirements -- predicates checked later
1313 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1314 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1315 typename iterator_traits<_InputIterator>::value_type>)
1316 __glibcxx_requires_valid_range(__first, __last);
1317
1318 typedef typename iterator_traits<_OutputIterator>::iterator_category
1319 _IterType;
1320
1321 if (__first == __last) return __result;
1322 return std::__unique_copy(__first, __last, __result,
1323 __binary_pred, _IterType());
1324 }
1325
1326 /**
1327 * @brief Remove consecutive duplicate values from a sequence.
1328 * @param first A forward iterator.
1329 * @param last A forward iterator.
1330 * @return An iterator designating the end of the resulting sequence.
1331 *
1332 * Removes all but the first element from each group of consecutive
1333 * values that compare equal.
1334 * unique() is stable, so the relative order of elements that are
1335 * not removed is unchanged.
1336 * Elements between the end of the resulting sequence and @p last
1337 * are still present, but their value is unspecified.
1338 */
1339 template<typename _ForwardIterator>
1340 _ForwardIterator
1341 unique(_ForwardIterator __first, _ForwardIterator __last)
1342 {
1343 // concept requirements
1344 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1345 _ForwardIterator>)
1346 __glibcxx_function_requires(_EqualityComparableConcept<
1347 typename iterator_traits<_ForwardIterator>::value_type>)
1348 __glibcxx_requires_valid_range(__first, __last);
1349
1350 // Skip the beginning, if already unique.
1351 __first = std::adjacent_find(__first, __last);
1352 if (__first == __last)
1353 return __last;
1354
1355 // Do the real copy work.
1356 _ForwardIterator __dest = __first;
1357 ++__first;
1358 while (++__first != __last)
1359 if (!(*__dest == *__first))
1360 *++__dest = *__first;
1361 return ++__dest;
1362 }
1363
1364 /**
1365 * @brief Remove consecutive values from a sequence using a predicate.
1366 * @param first A forward iterator.
1367 * @param last A forward iterator.
1368 * @param binary_pred A binary predicate.
1369 * @return An iterator designating the end of the resulting sequence.
1370 *
1371 * Removes all but the first element from each group of consecutive
1372 * values for which @p binary_pred returns true.
1373 * unique() is stable, so the relative order of elements that are
1374 * not removed is unchanged.
1375 * Elements between the end of the resulting sequence and @p last
1376 * are still present, but their value is unspecified.
1377 */
1378 template<typename _ForwardIterator, typename _BinaryPredicate>
1379 _ForwardIterator
1380 unique(_ForwardIterator __first, _ForwardIterator __last,
1381 _BinaryPredicate __binary_pred)
1382 {
1383 // concept requirements
1384 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1385 _ForwardIterator>)
1386 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1387 typename iterator_traits<_ForwardIterator>::value_type,
1388 typename iterator_traits<_ForwardIterator>::value_type>)
1389 __glibcxx_requires_valid_range(__first, __last);
1390
1391 // Skip the beginning, if already unique.
1392 __first = std::adjacent_find(__first, __last, __binary_pred);
1393 if (__first == __last)
1394 return __last;
1395
1396 // Do the real copy work.
1397 _ForwardIterator __dest = __first;
1398 ++__first;
1399 while (++__first != __last)
1400 if (!__binary_pred(*__dest, *__first))
1401 *++__dest = *__first;
1402 return ++__dest;
1403 }
1404
1405 /**
1406 * @if maint
1407 * This is an uglified reverse(_BidirectionalIterator,
1408 * _BidirectionalIterator)
1409 * overloaded for bidirectional iterators.
1410 * @endif
1411 */
1412 template<typename _BidirectionalIterator>
1413 void
1414 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1415 bidirectional_iterator_tag)
1416 {
1417 while (true)
1418 if (__first == __last || __first == --__last)
1419 return;
1420 else
1421 std::iter_swap(__first++, __last);
1422 }
1423
1424 /**
1425 * @if maint
1426 * This is an uglified reverse(_BidirectionalIterator,
1427 * _BidirectionalIterator)
1428 * overloaded for bidirectional iterators.
1429 * @endif
1430 */
1431 template<typename _RandomAccessIterator>
1432 void
1433 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1434 random_access_iterator_tag)
1435 {
1436 while (__first < __last)
1437 std::iter_swap(__first++, --__last);
1438 }
1439
1440 /**
1441 * @brief Reverse a sequence.
1442 * @param first A bidirectional iterator.
1443 * @param last A bidirectional iterator.
1444 * @return reverse() returns no value.
1445 *
1446 * Reverses the order of the elements in the range @p [first,last),
1447 * so that the first element becomes the last etc.
1448 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1449 * swaps @p *(first+i) and @p *(last-(i+1))
1450 */
1451 template<typename _BidirectionalIterator>
1452 inline void
1453 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1454 {
1455 // concept requirements
1456 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1457 _BidirectionalIterator>)
1458 __glibcxx_requires_valid_range(__first, __last);
1459 std::__reverse(__first, __last, std::__iterator_category(__first));
1460 }
1461
1462 /**
1463 * @brief Copy a sequence, reversing its elements.
1464 * @param first A bidirectional iterator.
1465 * @param last A bidirectional iterator.
1466 * @param result An output iterator.
1467 * @return An iterator designating the end of the resulting sequence.
1468 *
1469 * Copies the elements in the range @p [first,last) to the range
1470 * @p [result,result+(last-first)) such that the order of the
1471 * elements is reversed.
1472 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1473 * performs the assignment @p *(result+(last-first)-i) = *(first+i).
1474 * The ranges @p [first,last) and @p [result,result+(last-first))
1475 * must not overlap.
1476 */
1477 template<typename _BidirectionalIterator, typename _OutputIterator>
1478 _OutputIterator
1479 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1480 _OutputIterator __result)
1481 {
1482 // concept requirements
1483 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1484 _BidirectionalIterator>)
1485 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1486 typename iterator_traits<_BidirectionalIterator>::value_type>)
1487 __glibcxx_requires_valid_range(__first, __last);
1488
1489 while (__first != __last)
1490 {
1491 --__last;
1492 *__result = *__last;
1493 ++__result;
1494 }
1495 return __result;
1496 }
1497
1498
1499 /**
1500 * @if maint
1501 * This is a helper function for the rotate algorithm specialized on RAIs.
1502 * It returns the greatest common divisor of two integer values.
1503 * @endif
1504 */
1505 template<typename _EuclideanRingElement>
1506 _EuclideanRingElement
1507 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1508 {
1509 while (__n != 0)
1510 {
1511 _EuclideanRingElement __t = __m % __n;
1512 __m = __n;
1513 __n = __t;
1514 }
1515 return __m;
1516 }
1517
1518 /**
1519 * @if maint
1520 * This is a helper function for the rotate algorithm.
1521 * @endif
1522 */
1523 template<typename _ForwardIterator>
1524 void
1525 __rotate(_ForwardIterator __first,
1526 _ForwardIterator __middle,
1527 _ForwardIterator __last,
1528 forward_iterator_tag)
1529 {
1530 if ((__first == __middle) || (__last == __middle))
1531 return;
1532
1533 _ForwardIterator __first2 = __middle;
1534 do
1535 {
1536 swap(*__first++, *__first2++);
1537 if (__first == __middle)
1538 __middle = __first2;
1539 }
1540 while (__first2 != __last);
1541
1542 __first2 = __middle;
1543
1544 while (__first2 != __last)
1545 {
1546 swap(*__first++, *__first2++);
1547 if (__first == __middle)
1548 __middle = __first2;
1549 else if (__first2 == __last)
1550 __first2 = __middle;
1551 }
1552 }
1553
1554 /**
1555 * @if maint
1556 * This is a helper function for the rotate algorithm.
1557 * @endif
1558 */
1559 template<typename _BidirectionalIterator>
1560 void
1561 __rotate(_BidirectionalIterator __first,
1562 _BidirectionalIterator __middle,
1563 _BidirectionalIterator __last,
1564 bidirectional_iterator_tag)
1565 {
1566 // concept requirements
1567 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1568 _BidirectionalIterator>)
1569
1570 if ((__first == __middle) || (__last == __middle))
1571 return;
1572
1573 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1574 std::__reverse(__middle, __last, bidirectional_iterator_tag());
1575
1576 while (__first != __middle && __middle != __last)
1577 swap(*__first++, *--__last);
1578
1579 if (__first == __middle)
1580 std::__reverse(__middle, __last, bidirectional_iterator_tag());
1581 else
1582 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1583 }
1584
1585 /**
1586 * @if maint
1587 * This is a helper function for the rotate algorithm.
1588 * @endif
1589 */
1590 template<typename _RandomAccessIterator>
1591 void
1592 __rotate(_RandomAccessIterator __first,
1593 _RandomAccessIterator __middle,
1594 _RandomAccessIterator __last,
1595 random_access_iterator_tag)
1596 {
1597 // concept requirements
1598 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1599 _RandomAccessIterator>)
1600
1601 if ((__first == __middle) || (__last == __middle))
1602 return;
1603
1604 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1605 _Distance;
1606 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1607 _ValueType;
1608
1609 const _Distance __n = __last - __first;
1610 const _Distance __k = __middle - __first;
1611 const _Distance __l = __n - __k;
1612
1613 if (__k == __l)
1614 {
1615 std::swap_ranges(__first, __middle, __middle);
1616 return;
1617 }
1618
1619 const _Distance __d = __gcd(__n, __k);
1620
1621 for (_Distance __i = 0; __i < __d; __i++)
1622 {
1623 const _ValueType __tmp = *__first;
1624 _RandomAccessIterator __p = __first;
1625
1626 if (__k < __l)
1627 {
1628 for (_Distance __j = 0; __j < __l / __d; __j++)
1629 {
1630 if (__p > __first + __l)
1631 {
1632 *__p = *(__p - __l);
1633 __p -= __l;
1634 }
1635
1636 *__p = *(__p + __k);
1637 __p += __k;
1638 }
1639 }
1640 else
1641 {
1642 for (_Distance __j = 0; __j < __k / __d - 1; __j ++)
1643 {
1644 if (__p < __last - __k)
1645 {
1646 *__p = *(__p + __k);
1647 __p += __k;
1648 }
1649 *__p = * (__p - __l);
1650 __p -= __l;
1651 }
1652 }
1653
1654 *__p = __tmp;
1655 ++__first;
1656 }
1657 }
1658
1659 /**
1660 * @brief Rotate the elements of a sequence.
1661 * @param first A forward iterator.
1662 * @param middle A forward iterator.
1663 * @param last A forward iterator.
1664 * @return Nothing.
1665 *
1666 * Rotates the elements of the range @p [first,last) by @p (middle-first)
1667 * positions so that the element at @p middle is moved to @p first, the
1668 * element at @p middle+1 is moved to @first+1 and so on for each element
1669 * in the range @p [first,last).
1670 *
1671 * This effectively swaps the ranges @p [first,middle) and
1672 * @p [middle,last).
1673 *
1674 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1675 * each @p n in the range @p [0,last-first).
1676 */
1677 template<typename _ForwardIterator>
1678 inline void
1679 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1680 _ForwardIterator __last)
1681 {
1682 // concept requirements
1683 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1684 _ForwardIterator>)
1685 __glibcxx_requires_valid_range(__first, __middle);
1686 __glibcxx_requires_valid_range(__middle, __last);
1687
1688 typedef typename iterator_traits<_ForwardIterator>::iterator_category
1689 _IterType;
1690 std::__rotate(__first, __middle, __last, _IterType());
1691 }
1692
1693 /**
1694 * @brief Copy a sequence, rotating its elements.
1695 * @param first A forward iterator.
1696 * @param middle A forward iterator.
1697 * @param last A forward iterator.
1698 * @param result An output iterator.
1699 * @return An iterator designating the end of the resulting sequence.
1700 *
1701 * Copies the elements of the range @p [first,last) to the range
1702 * beginning at @result, rotating the copied elements by @p (middle-first)
1703 * positions so that the element at @p middle is moved to @p result, the
1704 * element at @p middle+1 is moved to @result+1 and so on for each element
1705 * in the range @p [first,last).
1706 *
1707 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1708 * each @p n in the range @p [0,last-first).
1709 */
1710 template<typename _ForwardIterator, typename _OutputIterator>
1711 _OutputIterator
1712 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1713 _ForwardIterator __last, _OutputIterator __result)
1714 {
1715 // concept requirements
1716 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1717 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1718 typename iterator_traits<_ForwardIterator>::value_type>)
1719 __glibcxx_requires_valid_range(__first, __middle);
1720 __glibcxx_requires_valid_range(__middle, __last);
1721
1722 return std::copy(__first, __middle, copy(__middle, __last, __result));
1723 }
1724
1725 /**
1726 * @brief Randomly shuffle the elements of a sequence.
1727 * @param first A forward iterator.
1728 * @param last A forward iterator.
1729 * @return Nothing.
1730 *
1731 * Reorder the elements in the range @p [first,last) using a random
1732 * distribution, so that every possible ordering of the sequence is
1733 * equally likely.
1734 */
1735 template<typename _RandomAccessIterator>
1736 inline void
1737 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
1738 {
1739 // concept requirements
1740 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1741 _RandomAccessIterator>)
1742 __glibcxx_requires_valid_range(__first, __last);
1743
1744 if (__first != __last)
1745 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1746 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
1747 }
1748
1749 /**
1750 * @brief Shuffle the elements of a sequence using a random number
1751 * generator.
1752 * @param first A forward iterator.
1753 * @param last A forward iterator.
1754 * @param rand The RNG functor or function.
1755 * @return Nothing.
1756 *
1757 * Reorders the elements in the range @p [first,last) using @p rand to
1758 * provide a random distribution. Calling @p rand(N) for a positive
1759 * integer @p N should return a randomly chosen integer from the
1760 * range [0,N).
1761 */
1762 template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
1763 void
1764 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
1765 _RandomNumberGenerator& __rand)
1766 {
1767 // concept requirements
1768 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1769 _RandomAccessIterator>)
1770 __glibcxx_requires_valid_range(__first, __last);
1771
1772 if (__first == __last)
1773 return;
1774 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1775 std::iter_swap(__i, __first + __rand((__i - __first) + 1));
1776 }
1777
1778
1779 /**
1780 * @if maint
1781 * This is a helper function...
1782 * @endif
1783 */
1784 template<typename _ForwardIterator, typename _Predicate>
1785 _ForwardIterator
1786 __partition(_ForwardIterator __first, _ForwardIterator __last,
1787 _Predicate __pred,
1788 forward_iterator_tag)
1789 {
1790 if (__first == __last)
1791 return __first;
1792
1793 while (__pred(*__first))
1794 if (++__first == __last)
1795 return __first;
1796
1797 _ForwardIterator __next = __first;
1798
1799 while (++__next != __last)
1800 if (__pred(*__next))
1801 {
1802 swap(*__first, *__next);
1803 ++__first;
1804 }
1805
1806 return __first;
1807 }
1808
1809 /**
1810 * @if maint
1811 * This is a helper function...
1812 * @endif
1813 */
1814 template<typename _BidirectionalIterator, typename _Predicate>
1815 _BidirectionalIterator
1816 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1817 _Predicate __pred,
1818 bidirectional_iterator_tag)
1819 {
1820 while (true)
1821 {
1822 while (true)
1823 if (__first == __last)
1824 return __first;
1825 else if (__pred(*__first))
1826 ++__first;
1827 else
1828 break;
1829 --__last;
1830 while (true)
1831 if (__first == __last)
1832 return __first;
1833 else if (!__pred(*__last))
1834 --__last;
1835 else
1836 break;
1837 std::iter_swap(__first, __last);
1838 ++__first;
1839 }
1840 }
1841
1842 /**
1843 * @brief Move elements for which a predicate is true to the beginning
1844 * of a sequence.
1845 * @param first A forward iterator.
1846 * @param last A forward iterator.
1847 * @param pred A predicate functor.
1848 * @return An iterator @p middle such that @p pred(i) is true for each
1849 * iterator @p i in the range @p [first,middle) and false for each @p i
1850 * in the range @p [middle,last).
1851 *
1852 * @p pred must not modify its operand. @p partition() does not preserve
1853 * the relative ordering of elements in each group, use
1854 * @p stable_partition() if this is needed.
1855 */
1856 template<typename _ForwardIterator, typename _Predicate>
1857 inline _ForwardIterator
1858 partition(_ForwardIterator __first, _ForwardIterator __last,
1859 _Predicate __pred)
1860 {
1861 // concept requirements
1862 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1863 _ForwardIterator>)
1864 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1865 typename iterator_traits<_ForwardIterator>::value_type>)
1866 __glibcxx_requires_valid_range(__first, __last);
1867
1868 return std::__partition(__first, __last, __pred,
1869 std::__iterator_category(__first));
1870 }
1871
1872
1873 /**
1874 * @if maint
1875 * This is a helper function...
1876 * @endif
1877 */
1878 template<typename _ForwardIterator, typename _Predicate, typename _Distance>
1879 _ForwardIterator
1880 __inplace_stable_partition(_ForwardIterator __first,
1881 _ForwardIterator __last,
1882 _Predicate __pred, _Distance __len)
1883 {
1884 if (__len == 1)
1885 return __pred(*__first) ? __last : __first;
1886 _ForwardIterator __middle = __first;
1887 std::advance(__middle, __len / 2);
1888 _ForwardIterator __begin = std::__inplace_stable_partition(__first,
1889 __middle,
1890 __pred,
1891 __len / 2);
1892 _ForwardIterator __end = std::__inplace_stable_partition(__middle, __last,
1893 __pred,
1894 __len
1895 - __len / 2);
1896 std::rotate(__begin, __middle, __end);
1897 std::advance(__begin, std::distance(__middle, __end));
1898 return __begin;
1899 }
1900
1901 /**
1902 * @if maint
1903 * This is a helper function...
1904 * @endif
1905 */
1906 template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1907 typename _Distance>
1908 _ForwardIterator
1909 __stable_partition_adaptive(_ForwardIterator __first,
1910 _ForwardIterator __last,
1911 _Predicate __pred, _Distance __len,
1912 _Pointer __buffer,
1913 _Distance __buffer_size)
1914 {
1915 if (__len <= __buffer_size)
1916 {
1917 _ForwardIterator __result1 = __first;
1918 _Pointer __result2 = __buffer;
1919 for ( ; __first != __last ; ++__first)
1920 if (__pred(*__first))
1921 {
1922 *__result1 = *__first;
1923 ++__result1;
1924 }
1925 else
1926 {
1927 *__result2 = *__first;
1928 ++__result2;
1929 }
1930 std::copy(__buffer, __result2, __result1);
1931 return __result1;
1932 }
1933 else
1934 {
1935 _ForwardIterator __middle = __first;
1936 std::advance(__middle, __len / 2);
1937 _ForwardIterator __begin =
1938 std::__stable_partition_adaptive(__first, __middle, __pred,
1939 __len / 2, __buffer,
1940 __buffer_size);
1941 _ForwardIterator __end =
1942 std::__stable_partition_adaptive(__middle, __last, __pred,
1943 __len - __len / 2,
1944 __buffer, __buffer_size);
1945 std::rotate(__begin, __middle, __end);
1946 std::advance(__begin, std::distance(__middle, __end));
1947 return __begin;
1948 }
1949 }
1950
1951 /**
1952 * @brief Move elements for which a predicate is true to the beginning
1953 * of a sequence, preserving relative ordering.
1954 * @param first A forward iterator.
1955 * @param last A forward iterator.
1956 * @param pred A predicate functor.
1957 * @return An iterator @p middle such that @p pred(i) is true for each
1958 * iterator @p i in the range @p [first,middle) and false for each @p i
1959 * in the range @p [middle,last).
1960 *
1961 * Performs the same function as @p partition() with the additional
1962 * guarantee that the relative ordering of elements in each group is
1963 * preserved, so any two elements @p x and @p y in the range
1964 * @p [first,last) such that @p pred(x)==pred(y) will have the same
1965 * relative ordering after calling @p stable_partition().
1966 */
1967 template<typename _ForwardIterator, typename _Predicate>
1968 _ForwardIterator
1969 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1970 _Predicate __pred)
1971 {
1972 // concept requirements
1973 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1974 _ForwardIterator>)
1975 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1976 typename iterator_traits<_ForwardIterator>::value_type>)
1977 __glibcxx_requires_valid_range(__first, __last);
1978
1979 if (__first == __last)
1980 return __first;
1981 else
1982 {
1983 typedef typename iterator_traits<_ForwardIterator>::value_type
1984 _ValueType;
1985 typedef typename iterator_traits<_ForwardIterator>::difference_type
1986 _DistanceType;
1987
1988 _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
1989 __last);
1990 if (__buf.size() > 0)
1991 return
1992 std::__stable_partition_adaptive(__first, __last, __pred,
1993 _DistanceType(__buf.requested_size()),
1994 __buf.begin(), __buf.size());
1995 else
1996 return
1997 std::__inplace_stable_partition(__first, __last, __pred,
1998 _DistanceType(__buf.requested_size()));
1999 }
2000 }
2001
2002 /**
2003 * @if maint
2004 * This is a helper function...
2005 * @endif
2006 */
2007 template<typename _RandomAccessIterator, typename _Tp>
2008 _RandomAccessIterator
2009 __unguarded_partition(_RandomAccessIterator __first,
2010 _RandomAccessIterator __last, _Tp __pivot)
2011 {
2012 while (true)
2013 {
2014 while (*__first < __pivot)
2015 ++__first;
2016 --__last;
2017 while (__pivot < *__last)
2018 --__last;
2019 if (!(__first < __last))
2020 return __first;
2021 std::iter_swap(__first, __last);
2022 ++__first;
2023 }
2024 }
2025
2026 /**
2027 * @if maint
2028 * This is a helper function...
2029 * @endif
2030 */
2031 template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
2032 _RandomAccessIterator
2033 __unguarded_partition(_RandomAccessIterator __first,
2034 _RandomAccessIterator __last,
2035 _Tp __pivot, _Compare __comp)
2036 {
2037 while (true)
2038 {
2039 while (__comp(*__first, __pivot))
2040 ++__first;
2041 --__last;
2042 while (__comp(__pivot, *__last))
2043 --__last;
2044 if (!(__first < __last))
2045 return __first;
2046 std::iter_swap(__first, __last);
2047 ++__first;
2048 }
2049 }
2050
2051 /**
2052 * @if maint
2053 * @doctodo
2054 * This controls some aspect of the sort routines.
2055 * @endif
2056 */
2057 enum { _S_threshold = 16 };
2058
2059 /**
2060 * @if maint
2061 * This is a helper function for the sort routine.
2062 * @endif
2063 */
2064 template<typename _RandomAccessIterator, typename _Tp>
2065 void
2066 __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val)
2067 {
2068 _RandomAccessIterator __next = __last;
2069 --__next;
2070 while (__val < *__next)
2071 {
2072 *__last = *__next;
2073 __last = __next;
2074 --__next;
2075 }
2076 *__last = __val;
2077 }
2078
2079 /**
2080 * @if maint
2081 * This is a helper function for the sort routine.
2082 * @endif
2083 */
2084 template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
2085 void
2086 __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,
2087 _Compare __comp)
2088 {
2089 _RandomAccessIterator __next = __last;
2090 --__next;
2091 while (__comp(__val, *__next))
2092 {
2093 *__last = *__next;
2094 __last = __next;
2095 --__next;
2096 }
2097 *__last = __val;
2098 }
2099
2100 /**
2101 * @if maint
2102 * This is a helper function for the sort routine.
2103 * @endif
2104 */
2105 template<typename _RandomAccessIterator>
2106 void
2107 __insertion_sort(_RandomAccessIterator __first,
2108 _RandomAccessIterator __last)
2109 {
2110 if (__first == __last)
2111 return;
2112
2113 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2114 {
2115 typename iterator_traits<_RandomAccessIterator>::value_type
2116 __val = *__i;
2117 if (__val < *__first)
2118 {
2119 std::copy_backward(__first, __i, __i + 1);
2120 *__first = __val;
2121 }
2122 else
2123 std::__unguarded_linear_insert(__i, __val);
2124 }
2125 }
2126
2127 /**
2128 * @if maint
2129 * This is a helper function for the sort routine.
2130 * @endif
2131 */
2132 template<typename _RandomAccessIterator, typename _Compare>
2133 void
2134 __insertion_sort(_RandomAccessIterator __first,
2135 _RandomAccessIterator __last, _Compare __comp)
2136 {
2137 if (__first == __last) return;
2138
2139 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2140 {
2141 typename iterator_traits<_RandomAccessIterator>::value_type
2142 __val = *__i;
2143 if (__comp(__val, *__first))
2144 {
2145 std::copy_backward(__first, __i, __i + 1);
2146 *__first = __val;
2147 }
2148 else
2149 std::__unguarded_linear_insert(__i, __val, __comp);
2150 }
2151 }
2152
2153 /**
2154 * @if maint
2155 * This is a helper function for the sort routine.
2156 * @endif
2157 */
2158 template<typename _RandomAccessIterator>
2159 inline void
2160 __unguarded_insertion_sort(_RandomAccessIterator __first,
2161 _RandomAccessIterator __last)
2162 {
2163 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2164 _ValueType;
2165
2166 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2167 std::__unguarded_linear_insert(__i, _ValueType(*__i));
2168 }
2169
2170 /**
2171 * @if maint
2172 * This is a helper function for the sort routine.
2173 * @endif
2174 */
2175 template<typename _RandomAccessIterator, typename _Compare>
2176 inline void
2177 __unguarded_insertion_sort(_RandomAccessIterator __first,
2178 _RandomAccessIterator __last, _Compare __comp)
2179 {
2180 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2181 _ValueType;
2182
2183 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2184 std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);
2185 }
2186
2187 /**
2188 * @if maint
2189 * This is a helper function for the sort routine.
2190 * @endif
2191 */
2192 template<typename _RandomAccessIterator>
2193 void
2194 __final_insertion_sort(_RandomAccessIterator __first,
2195 _RandomAccessIterator __last)
2196 {
2197 if (__last - __first > _S_threshold)
2198 {
2199 std::__insertion_sort(__first, __first + _S_threshold);
2200 std::__unguarded_insertion_sort(__first + _S_threshold, __last);
2201 }
2202 else
2203 std::__insertion_sort(__first, __last);
2204 }
2205
2206 /**
2207 * @if maint
2208 * This is a helper function for the sort routine.
2209 * @endif
2210 */
2211 template<typename _RandomAccessIterator, typename _Compare>
2212 void
2213 __final_insertion_sort(_RandomAccessIterator __first,
2214 _RandomAccessIterator __last, _Compare __comp)
2215 {
2216 if (__last - __first > _S_threshold)
2217 {
2218 std::__insertion_sort(__first, __first + _S_threshold, __comp);
2219 std::__unguarded_insertion_sort(__first + _S_threshold, __last,
2220 __comp);
2221 }
2222 else
2223 std::__insertion_sort(__first, __last, __comp);
2224 }
2225
2226 /**
2227 * @if maint
2228 * This is a helper function for the sort routine.
2229 * @endif
2230 */
2231 template<typename _Size>
2232 inline _Size
2233 __lg(_Size __n)
2234 {
2235 _Size __k;
2236 for (__k = 0; __n != 1; __n >>= 1)
2237 ++__k;
2238 return __k;
2239 }
2240
2241 /**
2242 * @brief Sort the smallest elements of a sequence.
2243 * @param first An iterator.
2244 * @param middle Another iterator.
2245 * @param last Another iterator.
2246 * @return Nothing.
2247 *
2248 * Sorts the smallest @p (middle-first) elements in the range
2249 * @p [first,last) and moves them to the range @p [first,middle). The
2250 * order of the remaining elements in the range @p [middle,last) is
2251 * undefined.
2252 * After the sort if @p i and @j are iterators in the range
2253 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2254 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
2255 */
2256 template<typename _RandomAccessIterator>
2257 void
2258 partial_sort(_RandomAccessIterator __first,
2259 _RandomAccessIterator __middle,
2260 _RandomAccessIterator __last)
2261 {
2262 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2263 _ValueType;
2264
2265 // concept requirements
2266 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2267 _RandomAccessIterator>)
2268 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
2269 __glibcxx_requires_valid_range(__first, __middle);
2270 __glibcxx_requires_valid_range(__middle, __last);
2271
2272 std::make_heap(__first, __middle);
2273 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
2274 if (*__i < *__first)
2275 std::__pop_heap(__first, __middle, __i, _ValueType(*__i));
2276 std::sort_heap(__first, __middle);
2277 }
2278
2279 /**
2280 * @brief Sort the smallest elements of a sequence using a predicate
2281 * for comparison.
2282 * @param first An iterator.
2283 * @param middle Another iterator.
2284 * @param last Another iterator.
2285 * @param comp A comparison functor.
2286 * @return Nothing.
2287 *
2288 * Sorts the smallest @p (middle-first) elements in the range
2289 * @p [first,last) and moves them to the range @p [first,middle). The
2290 * order of the remaining elements in the range @p [middle,last) is
2291 * undefined.
2292 * After the sort if @p i and @j are iterators in the range
2293 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2294 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
2295 * are both false.
2296 */
2297 template<typename _RandomAccessIterator, typename _Compare>
2298 void
2299 partial_sort(_RandomAccessIterator __first,
2300 _RandomAccessIterator __middle,
2301 _RandomAccessIterator __last,
2302 _Compare __comp)
2303 {
2304 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2305 _ValueType;
2306
2307 // concept requirements
2308 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2309 _RandomAccessIterator>)
2310 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2311 _ValueType, _ValueType>)
2312 __glibcxx_requires_valid_range(__first, __middle);
2313 __glibcxx_requires_valid_range(__middle, __last);
2314
2315 std::make_heap(__first, __middle, __comp);
2316 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
2317 if (__comp(*__i, *__first))
2318 std::__pop_heap(__first, __middle, __i, _ValueType(*__i), __comp);
2319 std::sort_heap(__first, __middle, __comp);
2320 }
2321
2322 /**
2323 * @brief Copy the smallest elements of a sequence.
2324 * @param first An iterator.
2325 * @param last Another iterator.
2326 * @param result_first A random-access iterator.
2327 * @param result_last Another random-access iterator.
2328 * @return An iterator indicating the end of the resulting sequence.
2329 *
2330 * Copies and sorts the smallest N values from the range @p [first,last)
2331 * to the range beginning at @p result_first, where the number of
2332 * elements to be copied, @p N, is the smaller of @p (last-first) and
2333 * @p (result_last-result_first).
2334 * After the sort if @p i and @j are iterators in the range
2335 * @p [result_first,result_first+N) such that @i precedes @j then
2336 * @p *j<*i is false.
2337 * The value returned is @p result_first+N.
2338 */
2339 template<typename _InputIterator, typename _RandomAccessIterator>
2340 _RandomAccessIterator
2341 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2342 _RandomAccessIterator __result_first,
2343 _RandomAccessIterator __result_last)
2344 {
2345 typedef typename iterator_traits<_InputIterator>::value_type
2346 _InputValueType;
2347 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2348 _OutputValueType;
2349 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2350 _DistanceType;
2351
2352 // concept requirements
2353 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2354 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2355 _OutputValueType>)
2356 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
2357 __glibcxx_function_requires(_LessThanComparableConcept<_InputValueType>)
2358 __glibcxx_requires_valid_range(__first, __last);
2359 __glibcxx_requires_valid_range(__result_first, __result_last);
2360
2361 if (__result_first == __result_last)
2362 return __result_last;
2363 _RandomAccessIterator __result_real_last = __result_first;
2364 while(__first != __last && __result_real_last != __result_last)
2365 {
2366 *__result_real_last = *__first;
2367 ++__result_real_last;
2368 ++__first;
2369 }
2370 std::make_heap(__result_first, __result_real_last);
2371 while (__first != __last)
2372 {
2373 if (*__first < *__result_first)
2374 std::__adjust_heap(__result_first, _DistanceType(0),
2375 _DistanceType(__result_real_last
2376 - __result_first),
2377 _InputValueType(*__first));
2378 ++__first;
2379 }
2380 std::sort_heap(__result_first, __result_real_last);
2381 return __result_real_last;
2382 }
2383
2384 /**
2385 * @brief Copy the smallest elements of a sequence using a predicate for
2386 * comparison.
2387 * @param first An input iterator.
2388 * @param last Another input iterator.
2389 * @param result_first A random-access iterator.
2390 * @param result_last Another random-access iterator.
2391 * @param comp A comparison functor.
2392 * @return An iterator indicating the end of the resulting sequence.
2393 *
2394 * Copies and sorts the smallest N values from the range @p [first,last)
2395 * to the range beginning at @p result_first, where the number of
2396 * elements to be copied, @p N, is the smaller of @p (last-first) and
2397 * @p (result_last-result_first).
2398 * After the sort if @p i and @j are iterators in the range
2399 * @p [result_first,result_first+N) such that @i precedes @j then
2400 * @p comp(*j,*i) is false.
2401 * The value returned is @p result_first+N.
2402 */
2403 template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
2404 _RandomAccessIterator
2405 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2406 _RandomAccessIterator __result_first,
2407 _RandomAccessIterator __result_last,
2408 _Compare __comp)
2409 {
2410 typedef typename iterator_traits<_InputIterator>::value_type
2411 _InputValueType;
2412 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2413 _OutputValueType;
2414 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2415 _DistanceType;
2416
2417 // concept requirements
2418 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2419 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2420 _RandomAccessIterator>)
2421 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2422 _OutputValueType>)
2423 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2424 _OutputValueType, _OutputValueType>)
2425 __glibcxx_requires_valid_range(__first, __last);
2426 __glibcxx_requires_valid_range(__result_first, __result_last);
2427
2428 if (__result_first == __result_last)
2429 return __result_last;
2430 _RandomAccessIterator __result_real_last = __result_first;
2431 while(__first != __last && __result_real_last != __result_last)
2432 {
2433 *__result_real_last = *__first;
2434 ++__result_real_last;
2435 ++__first;
2436 }
2437 std::make_heap(__result_first, __result_real_last, __comp);
2438 while (__first != __last)
2439 {
2440 if (__comp(*__first, *__result_first))
2441 std::__adjust_heap(__result_first, _DistanceType(0),
2442 _DistanceType(__result_real_last
2443 - __result_first),
2444 _InputValueType(*__first),
2445 __comp);
2446 ++__first;
2447 }
2448 std::sort_heap(__result_first, __result_real_last, __comp);
2449 return __result_real_last;
2450 }
2451
2452 /**
2453 * @if maint
2454 * This is a helper function for the sort routine.
2455 * @endif
2456 */
2457 template<typename _RandomAccessIterator, typename _Size>
2458 void
2459 __introsort_loop(_RandomAccessIterator __first,
2460 _RandomAccessIterator __last,
2461 _Size __depth_limit)
2462 {
2463 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2464 _ValueType;
2465
2466 while (__last - __first > _S_threshold)
2467 {
2468 if (__depth_limit == 0)
2469 {
2470 std::partial_sort(__first, __last, __last);
2471 return;
2472 }
2473 --__depth_limit;
2474 _RandomAccessIterator __cut =
2475 std::__unguarded_partition(__first, __last,
2476 _ValueType(std::__median(*__first,
2477 *(__first
2478 + (__last
2479 - __first)
2480 / 2),
2481 *(__last
2482 - 1))));
2483 std::__introsort_loop(__cut, __last, __depth_limit);
2484 __last = __cut;
2485 }
2486 }
2487
2488 /**
2489 * @if maint
2490 * This is a helper function for the sort routine.
2491 * @endif
2492 */
2493 template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2494 void
2495 __introsort_loop(_RandomAccessIterator __first,
2496 _RandomAccessIterator __last,
2497 _Size __depth_limit, _Compare __comp)
2498 {