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