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