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