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