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