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