1// Algorithm implementation -*- C++ -*-
2
3// Copyright (C) 2001-2019 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 <bits/uniform_int_dist.h>
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, (void) ++__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 if (__first == __last)
587 return true;
588 ++__first;
589 return std::none_of(__first, __last, __pred);
590 }
591
592 /**
593 * @brief Find the partition point of a partitioned range.
594 * @ingroup mutating_algorithms
595 * @param __first An iterator.
596 * @param __last Another iterator.
597 * @param __pred A predicate.
598 * @return An iterator @p mid such that @p all_of(__first, mid, __pred)
599 * and @p none_of(mid, __last, __pred) are both true.
600 */
601 template<typename _ForwardIterator, typename _Predicate>
602 _ForwardIterator
603 partition_point(_ForwardIterator __first, _ForwardIterator __last,
604 _Predicate __pred)
605 {
606 // concept requirements
607 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
608 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
609 typename iterator_traits<_ForwardIterator>::value_type>)
610
611 // A specific debug-mode test will be necessary...
612 __glibcxx_requires_valid_range(__first, __last);
613
614 typedef typename iterator_traits<_ForwardIterator>::difference_type
615 _DistanceType;
616
617 _DistanceType __len = std::distance(__first, __last);
618 _DistanceType __half;
619 _ForwardIterator __middle;
620
621 while (__len > 0)
622 {
623 __half = __len >> 1;
624 __middle = __first;
625 std::advance(__middle, __half);
626 if (__pred(*__middle))
627 {
628 __first = __middle;
629 ++__first;
630 __len = __len - __half - 1;
631 }
632 else
633 __len = __half;
634 }
635 return __first;
636 }
637#endif
638
639 template<typename _InputIterator, typename _OutputIterator,
640 typename _Predicate>
641 _OutputIterator
642 __remove_copy_if(_InputIterator __first, _InputIterator __last,
643 _OutputIterator __result, _Predicate __pred)
644 {
645 for (; __first != __last; ++__first)
646 if (!__pred(__first))
647 {
648 *__result = *__first;
649 ++__result;
650 }
651 return __result;
652 }
653
654 /**
655 * @brief Copy a sequence, removing elements of a given value.
656 * @ingroup mutating_algorithms
657 * @param __first An input iterator.
658 * @param __last An input iterator.
659 * @param __result An output iterator.
660 * @param __value The value to be removed.
661 * @return An iterator designating the end of the resulting sequence.
662 *
663 * Copies each element in the range @p [__first,__last) not equal
664 * to @p __value to the range beginning at @p __result.
665 * remove_copy() is stable, so the relative order of elements that
666 * are copied is unchanged.
667 */
668 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
669 inline _OutputIterator
670 remove_copy(_InputIterator __first, _InputIterator __last,
671 _OutputIterator __result, const _Tp& __value)
672 {
673 // concept requirements
674 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
675 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
676 typename iterator_traits<_InputIterator>::value_type>)
677 __glibcxx_function_requires(_EqualOpConcept<
678 typename iterator_traits<_InputIterator>::value_type, _Tp>)
679 __glibcxx_requires_valid_range(__first, __last);
680
681 return std::__remove_copy_if(__first, __last, __result,
682 __gnu_cxx::__ops::__iter_equals_val(__value));
683 }
684
685 /**
686 * @brief Copy a sequence, removing elements for which a predicate is true.
687 * @ingroup mutating_algorithms
688 * @param __first An input iterator.
689 * @param __last An input iterator.
690 * @param __result An output iterator.
691 * @param __pred A predicate.
692 * @return An iterator designating the end of the resulting sequence.
693 *
694 * Copies each element in the range @p [__first,__last) for which
695 * @p __pred returns false to the range beginning at @p __result.
696 *
697 * remove_copy_if() is stable, so the relative order of elements that are
698 * copied is unchanged.
699 */
700 template<typename _InputIterator, typename _OutputIterator,
701 typename _Predicate>
702 inline _OutputIterator
703 remove_copy_if(_InputIterator __first, _InputIterator __last,
704 _OutputIterator __result, _Predicate __pred)
705 {
706 // concept requirements
707 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
708 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
709 typename iterator_traits<_InputIterator>::value_type>)
710 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
711 typename iterator_traits<_InputIterator>::value_type>)
712 __glibcxx_requires_valid_range(__first, __last);
713
714 return std::__remove_copy_if(__first, __last, __result,
715 __gnu_cxx::__ops::__pred_iter(__pred));
716 }
717
718#if __cplusplus >= 201103L
719 /**
720 * @brief Copy the elements of a sequence for which a predicate is true.
721 * @ingroup mutating_algorithms
722 * @param __first An input iterator.
723 * @param __last An input iterator.
724 * @param __result An output iterator.
725 * @param __pred A predicate.
726 * @return An iterator designating the end of the resulting sequence.
727 *
728 * Copies each element in the range @p [__first,__last) for which
729 * @p __pred returns true to the range beginning at @p __result.
730 *
731 * copy_if() is stable, so the relative order of elements that are
732 * copied is unchanged.
733 */
734 template<typename _InputIterator, typename _OutputIterator,
735 typename _Predicate>
736 _OutputIterator
737 copy_if(_InputIterator __first, _InputIterator __last,
738 _OutputIterator __result, _Predicate __pred)
739 {
740 // concept requirements
741 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
742 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
743 typename iterator_traits<_InputIterator>::value_type>)
744 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
745 typename iterator_traits<_InputIterator>::value_type>)
746 __glibcxx_requires_valid_range(__first, __last);
747
748 for (; __first != __last; ++__first)
749 if (__pred(*__first))
750 {
751 *__result = *__first;
752 ++__result;
753 }
754 return __result;
755 }
756
757 template<typename _InputIterator, typename _Size, typename _OutputIterator>
758 _OutputIterator
759 __copy_n(_InputIterator __first, _Size __n,
760 _OutputIterator __result, input_iterator_tag)
761 {
762 if (__n > 0)
763 {
764 while (true)
765 {
766 *__result = *__first;
767 ++__result;
768 if (--__n > 0)
769 ++__first;
770 else
771 break;
772 }
773 }
774 return __result;
775 }
776
777 template<typename _RandomAccessIterator, typename _Size,
778 typename _OutputIterator>
779 inline _OutputIterator
780 __copy_n(_RandomAccessIterator __first, _Size __n,
781 _OutputIterator __result, random_access_iterator_tag)
782 { return std::copy(__first, __first + __n, __result); }
783
784 /**
785 * @brief Copies the range [first,first+n) into [result,result+n).
786 * @ingroup mutating_algorithms
787 * @param __first An input iterator.
788 * @param __n The number of elements to copy.
789 * @param __result An output iterator.
790 * @return result+n.
791 *
792 * This inline function will boil down to a call to @c memmove whenever
793 * possible. Failing that, if random access iterators are passed, then the
794 * loop count will be known (and therefore a candidate for compiler
795 * optimizations such as unrolling).
796 */
797 template<typename _InputIterator, typename _Size, typename _OutputIterator>
798 inline _OutputIterator
799 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
800 {
801 // concept requirements
802 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
803 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
804 typename iterator_traits<_InputIterator>::value_type>)
805
806 return std::__copy_n(__first, __n, __result,
807 std::__iterator_category(__first));
808 }
809
810 /**
811 * @brief Copy the elements of a sequence to separate output sequences
812 * depending on the truth value of a predicate.
813 * @ingroup mutating_algorithms
814 * @param __first An input iterator.
815 * @param __last An input iterator.
816 * @param __out_true An output iterator.
817 * @param __out_false An output iterator.
818 * @param __pred A predicate.
819 * @return A pair designating the ends of the resulting sequences.
820 *
821 * Copies each element in the range @p [__first,__last) for which
822 * @p __pred returns true to the range beginning at @p out_true
823 * and each element for which @p __pred returns false to @p __out_false.
824 */
825 template<typename _InputIterator, typename _OutputIterator1,
826 typename _OutputIterator2, typename _Predicate>
827 pair<_OutputIterator1, _OutputIterator2>
828 partition_copy(_InputIterator __first, _InputIterator __last,
829 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
830 _Predicate __pred)
831 {
832 // concept requirements
833 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
834 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
835 typename iterator_traits<_InputIterator>::value_type>)
836 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
837 typename iterator_traits<_InputIterator>::value_type>)
838 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
839 typename iterator_traits<_InputIterator>::value_type>)
840 __glibcxx_requires_valid_range(__first, __last);
841
842 for (; __first != __last; ++__first)
843 if (__pred(*__first))
844 {
845 *__out_true = *__first;
846 ++__out_true;
847 }
848 else
849 {
850 *__out_false = *__first;
851 ++__out_false;
852 }
853
854 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
855 }
856#endif
857
858 template<typename _ForwardIterator, typename _Predicate>
859 _ForwardIterator
860 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
861 _Predicate __pred)
862 {
863 __first = std::__find_if(__first, __last, __pred);
864 if (__first == __last)
865 return __first;
866 _ForwardIterator __result = __first;
867 ++__first;
868 for (; __first != __last; ++__first)
869 if (!__pred(__first))
870 {
871 *__result = _GLIBCXX_MOVE(*__first);
872 ++__result;
873 }
874 return __result;
875 }
876
877 /**
878 * @brief Remove elements from a sequence.
879 * @ingroup mutating_algorithms
880 * @param __first An input iterator.
881 * @param __last An input iterator.
882 * @param __value The value to be removed.
883 * @return An iterator designating the end of the resulting sequence.
884 *
885 * All elements equal to @p __value are removed from the range
886 * @p [__first,__last).
887 *
888 * remove() is stable, so the relative order of elements that are
889 * not removed is unchanged.
890 *
891 * Elements between the end of the resulting sequence and @p __last
892 * are still present, but their value is unspecified.
893 */
894 template<typename _ForwardIterator, typename _Tp>
895 inline _ForwardIterator
896 remove(_ForwardIterator __first, _ForwardIterator __last,
897 const _Tp& __value)
898 {
899 // concept requirements
900 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
901 _ForwardIterator>)
902 __glibcxx_function_requires(_EqualOpConcept<
903 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
904 __glibcxx_requires_valid_range(__first, __last);
905
906 return std::__remove_if(__first, __last,
907 __gnu_cxx::__ops::__iter_equals_val(__value));
908 }
909
910 /**
911 * @brief Remove elements from a sequence using a predicate.
912 * @ingroup mutating_algorithms
913 * @param __first A forward iterator.
914 * @param __last A forward iterator.
915 * @param __pred A predicate.
916 * @return An iterator designating the end of the resulting sequence.
917 *
918 * All elements for which @p __pred returns true are removed from the range
919 * @p [__first,__last).
920 *
921 * remove_if() is stable, so the relative order of elements that are
922 * not removed is unchanged.
923 *
924 * Elements between the end of the resulting sequence and @p __last
925 * are still present, but their value is unspecified.
926 */
927 template<typename _ForwardIterator, typename _Predicate>
928 inline _ForwardIterator
929 remove_if(_ForwardIterator __first, _ForwardIterator __last,
930 _Predicate __pred)
931 {
932 // concept requirements
933 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
934 _ForwardIterator>)
935 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
936 typename iterator_traits<_ForwardIterator>::value_type>)
937 __glibcxx_requires_valid_range(__first, __last);
938
939 return std::__remove_if(__first, __last,
940 __gnu_cxx::__ops::__pred_iter(__pred));
941 }
942
943 template<typename _ForwardIterator, typename _BinaryPredicate>
944 _ForwardIterator
945 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
946 _BinaryPredicate __binary_pred)
947 {
948 if (__first == __last)
949 return __last;
950 _ForwardIterator __next = __first;
951 while (++__next != __last)
952 {
953 if (__binary_pred(__first, __next))
954 return __first;
955 __first = __next;
956 }
957 return __last;
958 }
959
960 template<typename _ForwardIterator, typename _BinaryPredicate>
961 _ForwardIterator
962 __unique(_ForwardIterator __first, _ForwardIterator __last,
963 _BinaryPredicate __binary_pred)
964 {
965 // Skip the beginning, if already unique.
966 __first = std::__adjacent_find(__first, __last, __binary_pred);
967 if (__first == __last)
968 return __last;
969
970 // Do the real copy work.
971 _ForwardIterator __dest = __first;
972 ++__first;
973 while (++__first != __last)
974 if (!__binary_pred(__dest, __first))
975 *++__dest = _GLIBCXX_MOVE(*__first);
976 return ++__dest;
977 }
978
979 /**
980 * @brief Remove consecutive duplicate values from a sequence.
981 * @ingroup mutating_algorithms
982 * @param __first A forward iterator.
983 * @param __last A forward iterator.
984 * @return An iterator designating the end of the resulting sequence.
985 *
986 * Removes all but the first element from each group of consecutive
987 * values that compare equal.
988 * unique() is stable, so the relative order of elements that are
989 * not removed is unchanged.
990 * Elements between the end of the resulting sequence and @p __last
991 * are still present, but their value is unspecified.
992 */
993 template<typename _ForwardIterator>
994 inline _ForwardIterator
995 unique(_ForwardIterator __first, _ForwardIterator __last)
996 {
997 // concept requirements
998 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
999 _ForwardIterator>)
1000 __glibcxx_function_requires(_EqualityComparableConcept<
1001 typename iterator_traits<_ForwardIterator>::value_type>)
1002 __glibcxx_requires_valid_range(__first, __last);
1003
1004 return std::__unique(__first, __last,
1005 __gnu_cxx::__ops::__iter_equal_to_iter());
1006 }
1007
1008 /**
1009 * @brief Remove consecutive values from a sequence using a predicate.
1010 * @ingroup mutating_algorithms
1011 * @param __first A forward iterator.
1012 * @param __last A forward iterator.
1013 * @param __binary_pred A binary predicate.
1014 * @return An iterator designating the end of the resulting sequence.
1015 *
1016 * Removes all but the first element from each group of consecutive
1017 * values for which @p __binary_pred returns true.
1018 * unique() is stable, so the relative order of elements that are
1019 * not removed is unchanged.
1020 * Elements between the end of the resulting sequence and @p __last
1021 * are still present, but their value is unspecified.
1022 */
1023 template<typename _ForwardIterator, typename _BinaryPredicate>
1024 inline _ForwardIterator
1025 unique(_ForwardIterator __first, _ForwardIterator __last,
1026 _BinaryPredicate __binary_pred)
1027 {
1028 // concept requirements
1029 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1030 _ForwardIterator>)
1031 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1032 typename iterator_traits<_ForwardIterator>::value_type,
1033 typename iterator_traits<_ForwardIterator>::value_type>)
1034 __glibcxx_requires_valid_range(__first, __last);
1035
1036 return std::__unique(__first, __last,
1037 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1038 }
1039
1040 /**
1041 * This is an uglified
1042 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1043 * _BinaryPredicate)
1044 * overloaded for forward iterators and output iterator as result.
1045 */
1046 template<typename _ForwardIterator, typename _OutputIterator,
1047 typename _BinaryPredicate>
1048 _OutputIterator
1049 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1050 _OutputIterator __result, _BinaryPredicate __binary_pred,
1051 forward_iterator_tag, output_iterator_tag)
1052 {
1053 // concept requirements -- iterators already checked
1054 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1055 typename iterator_traits<_ForwardIterator>::value_type,
1056 typename iterator_traits<_ForwardIterator>::value_type>)
1057
1058 _ForwardIterator __next = __first;
1059 *__result = *__first;
1060 while (++__next != __last)
1061 if (!__binary_pred(__first, __next))
1062 {
1063 __first = __next;
1064 *++__result = *__first;
1065 }
1066 return ++__result;
1067 }
1068
1069 /**
1070 * This is an uglified
1071 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1072 * _BinaryPredicate)
1073 * overloaded for input iterators and output iterator as result.
1074 */
1075 template<typename _InputIterator, typename _OutputIterator,
1076 typename _BinaryPredicate>
1077 _OutputIterator
1078 __unique_copy(_InputIterator __first, _InputIterator __last,
1079 _OutputIterator __result, _BinaryPredicate __binary_pred,
1080 input_iterator_tag, output_iterator_tag)
1081 {
1082 // concept requirements -- iterators already checked
1083 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1084 typename iterator_traits<_InputIterator>::value_type,
1085 typename iterator_traits<_InputIterator>::value_type>)
1086
1087 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1088 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
1089 __rebound_pred
1090 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
1091 *__result = __value;
1092 while (++__first != __last)
1093 if (!__rebound_pred(__first, __value))
1094 {
1095 __value = *__first;
1096 *++__result = __value;
1097 }
1098 return ++__result;
1099 }
1100
1101 /**
1102 * This is an uglified
1103 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1104 * _BinaryPredicate)
1105 * overloaded for input iterators and forward iterator as result.
1106 */
1107 template<typename _InputIterator, typename _ForwardIterator,
1108 typename _BinaryPredicate>
1109 _ForwardIterator
1110 __unique_copy(_InputIterator __first, _InputIterator __last,
1111 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1112 input_iterator_tag, forward_iterator_tag)
1113 {
1114 // concept requirements -- iterators already checked
1115 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1116 typename iterator_traits<_ForwardIterator>::value_type,
1117 typename iterator_traits<_InputIterator>::value_type>)
1118 *__result = *__first;
1119 while (++__first != __last)
1120 if (!__binary_pred(__result, __first))
1121 *++__result = *__first;
1122 return ++__result;
1123 }
1124
1125 /**
1126 * This is an uglified reverse(_BidirectionalIterator,
1127 * _BidirectionalIterator)
1128 * overloaded for bidirectional iterators.
1129 */
1130 template<typename _BidirectionalIterator>
1131 void
1132 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1133 bidirectional_iterator_tag)
1134 {
1135 while (true)
1136 if (__first == __last || __first == --__last)
1137 return;
1138 else
1139 {
1140 std::iter_swap(__first, __last);
1141 ++__first;
1142 }
1143 }
1144
1145 /**
1146 * This is an uglified reverse(_BidirectionalIterator,
1147 * _BidirectionalIterator)
1148 * overloaded for random access iterators.
1149 */
1150 template<typename _RandomAccessIterator>
1151 void
1152 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1153 random_access_iterator_tag)
1154 {
1155 if (__first == __last)
1156 return;
1157 --__last;
1158 while (__first < __last)
1159 {
1160 std::iter_swap(__first, __last);
1161 ++__first;
1162 --__last;
1163 }
1164 }
1165
1166 /**
1167 * @brief Reverse a sequence.
1168 * @ingroup mutating_algorithms
1169 * @param __first A bidirectional iterator.
1170 * @param __last A bidirectional iterator.
1171 * @return reverse() returns no value.
1172 *
1173 * Reverses the order of the elements in the range @p [__first,__last),
1174 * so that the first element becomes the last etc.
1175 * For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
1176 * swaps @p *(__first+i) and @p *(__last-(i+1))
1177 */
1178 template<typename _BidirectionalIterator>
1179 inline void
1180 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1181 {
1182 // concept requirements
1183 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1184 _BidirectionalIterator>)
1185 __glibcxx_requires_valid_range(__first, __last);
1186 std::__reverse(__first, __last, std::__iterator_category(__first));
1187 }
1188
1189 /**
1190 * @brief Copy a sequence, reversing its elements.
1191 * @ingroup mutating_algorithms
1192 * @param __first A bidirectional iterator.
1193 * @param __last A bidirectional iterator.
1194 * @param __result An output iterator.
1195 * @return An iterator designating the end of the resulting sequence.
1196 *
1197 * Copies the elements in the range @p [__first,__last) to the
1198 * range @p [__result,__result+(__last-__first)) such that the
1199 * order of the elements is reversed. For every @c i such that @p
1200 * 0<=i<=(__last-__first), @p reverse_copy() performs the
1201 * assignment @p *(__result+(__last-__first)-1-i) = *(__first+i).
1202 * The ranges @p [__first,__last) and @p
1203 * [__result,__result+(__last-__first)) must not overlap.
1204 */
1205 template<typename _BidirectionalIterator, typename _OutputIterator>
1206 _OutputIterator
1207 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1208 _OutputIterator __result)
1209 {
1210 // concept requirements
1211 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1212 _BidirectionalIterator>)
1213 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1214 typename iterator_traits<_BidirectionalIterator>::value_type>)
1215 __glibcxx_requires_valid_range(__first, __last);
1216
1217 while (__first != __last)
1218 {
1219 --__last;
1220 *__result = *__last;
1221 ++__result;
1222 }
1223 return __result;
1224 }
1225
1226 /**
1227 * This is a helper function for the rotate algorithm specialized on RAIs.
1228 * It returns the greatest common divisor of two integer values.
1229 */
1230 template<typename _EuclideanRingElement>
1231 _EuclideanRingElement
1232 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1233 {
1234 while (__n != 0)
1235 {
1236 _EuclideanRingElement __t = __m % __n;
1237 __m = __n;
1238 __n = __t;
1239 }
1240 return __m;
1241 }
1242
1243 inline namespace _V2
1244 {
1245
1246 /// This is a helper function for the rotate algorithm.
1247 template<typename _ForwardIterator>
1248 _ForwardIterator
1249 __rotate(_ForwardIterator __first,
1250 _ForwardIterator __middle,
1251 _ForwardIterator __last,
1252 forward_iterator_tag)
1253 {
1254 if (__first == __middle)
1255 return __last;
1256 else if (__last == __middle)
1257 return __first;
1258
1259 _ForwardIterator __first2 = __middle;
1260 do
1261 {
1262 std::iter_swap(__first, __first2);
1263 ++__first;
1264 ++__first2;
1265 if (__first == __middle)
1266 __middle = __first2;
1267 }
1268 while (__first2 != __last);
1269
1270 _ForwardIterator __ret = __first;
1271
1272 __first2 = __middle;
1273
1274 while (__first2 != __last)
1275 {
1276 std::iter_swap(__first, __first2);
1277 ++__first;
1278 ++__first2;
1279 if (__first == __middle)
1280 __middle = __first2;
1281 else if (__first2 == __last)
1282 __first2 = __middle;
1283 }
1284 return __ret;
1285 }
1286
1287 /// This is a helper function for the rotate algorithm.
1288 template<typename _BidirectionalIterator>
1289 _BidirectionalIterator
1290 __rotate(_BidirectionalIterator __first,
1291 _BidirectionalIterator __middle,
1292 _BidirectionalIterator __last,
1293 bidirectional_iterator_tag)
1294 {
1295 // concept requirements
1296 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1297 _BidirectionalIterator>)
1298
1299 if (__first == __middle)
1300 return __last;
1301 else if (__last == __middle)
1302 return __first;
1303
1304 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1305 std::__reverse(__middle, __last, bidirectional_iterator_tag());
1306
1307 while (__first != __middle && __middle != __last)
1308 {
1309 std::iter_swap(__first, --__last);
1310 ++__first;
1311 }
1312
1313 if (__first == __middle)
1314 {
1315 std::__reverse(__middle, __last, bidirectional_iterator_tag());
1316 return __last;
1317 }
1318 else
1319 {
1320 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1321 return __first;
1322 }
1323 }
1324
1325 /// This is a helper function for the rotate algorithm.
1326 template<typename _RandomAccessIterator>
1327 _RandomAccessIterator
1328 __rotate(_RandomAccessIterator __first,
1329 _RandomAccessIterator __middle,
1330 _RandomAccessIterator __last,
1331 random_access_iterator_tag)
1332 {
1333 // concept requirements
1334 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1335 _RandomAccessIterator>)
1336
1337 if (__first == __middle)
1338 return __last;
1339 else if (__last == __middle)
1340 return __first;
1341
1342 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1343 _Distance;
1344 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1345 _ValueType;
1346
1347 _Distance __n = __last - __first;
1348 _Distance __k = __middle - __first;
1349
1350 if (__k == __n - __k)
1351 {
1352 std::swap_ranges(__first, __middle, __middle);
1353 return __middle;
1354 }
1355
1356 _RandomAccessIterator __p = __first;
1357 _RandomAccessIterator __ret = __first + (__last - __middle);
1358
1359 for (;;)
1360 {
1361 if (__k < __n - __k)
1362 {
1363 if (__is_pod(_ValueType) && __k == 1)
1364 {
1365 _ValueType __t = _GLIBCXX_MOVE(*__p);
1366 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1367 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1368 return __ret;
1369 }
1370 _RandomAccessIterator __q = __p + __k;
1371 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1372 {
1373 std::iter_swap(__p, __q);
1374 ++__p;
1375 ++__q;
1376 }
1377 __n %= __k;
1378 if (__n == 0)
1379 return __ret;
1380 std::swap(__n, __k);
1381 __k = __n - __k;
1382 }
1383 else
1384 {
1385 __k = __n - __k;
1386 if (__is_pod(_ValueType) && __k == 1)
1387 {
1388 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1389 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1390 *__p = _GLIBCXX_MOVE(__t);
1391 return __ret;
1392 }
1393 _RandomAccessIterator __q = __p + __n;
1394 __p = __q - __k;
1395 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1396 {
1397 --__p;
1398 --__q;
1399 std::iter_swap(__p, __q);
1400 }
1401 __n %= __k;
1402 if (__n == 0)
1403 return __ret;
1404 std::swap(__n, __k);
1405 }
1406 }
1407 }
1408
1409 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1410 // DR 488. rotate throws away useful information
1411 /**
1412 * @brief Rotate the elements of a sequence.
1413 * @ingroup mutating_algorithms
1414 * @param __first A forward iterator.
1415 * @param __middle A forward iterator.
1416 * @param __last A forward iterator.
1417 * @return first + (last - middle).
1418 *
1419 * Rotates the elements of the range @p [__first,__last) by
1420 * @p (__middle - __first) positions so that the element at @p __middle
1421 * is moved to @p __first, the element at @p __middle+1 is moved to
1422 * @p __first+1 and so on for each element in the range
1423 * @p [__first,__last).
1424 *
1425 * This effectively swaps the ranges @p [__first,__middle) and
1426 * @p [__middle,__last).
1427 *
1428 * Performs
1429 * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1430 * for each @p n in the range @p [0,__last-__first).
1431 */
1432 template<typename _ForwardIterator>
1433 inline _ForwardIterator
1434 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1435 _ForwardIterator __last)
1436 {
1437 // concept requirements
1438 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1439 _ForwardIterator>)
1440 __glibcxx_requires_valid_range(__first, __middle);
1441 __glibcxx_requires_valid_range(__middle, __last);
1442
1443 return std::__rotate(__first, __middle, __last,
1444 std::__iterator_category(__first));
1445 }
1446
1447 } // namespace _V2
1448
1449 /**
1450 * @brief Copy a sequence, rotating its elements.
1451 * @ingroup mutating_algorithms
1452 * @param __first A forward iterator.
1453 * @param __middle A forward iterator.
1454 * @param __last A forward iterator.
1455 * @param __result An output iterator.
1456 * @return An iterator designating the end of the resulting sequence.
1457 *
1458 * Copies the elements of the range @p [__first,__last) to the
1459 * range beginning at @result, rotating the copied elements by
1460 * @p (__middle-__first) positions so that the element at @p __middle
1461 * is moved to @p __result, the element at @p __middle+1 is moved
1462 * to @p __result+1 and so on for each element in the range @p
1463 * [__first,__last).
1464 *
1465 * Performs
1466 * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1467 * for each @p n in the range @p [0,__last-__first).
1468 */
1469 template<typename _ForwardIterator, typename _OutputIterator>
1470 inline _OutputIterator
1471 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1472 _ForwardIterator __last, _OutputIterator __result)
1473 {
1474 // concept requirements
1475 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1476 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1477 typename iterator_traits<_ForwardIterator>::value_type>)
1478 __glibcxx_requires_valid_range(__first, __middle);
1479 __glibcxx_requires_valid_range(__middle, __last);
1480
1481 return std::copy(__first, __middle,
1482 std::copy(__middle, __last, __result));
1483 }
1484
1485 /// This is a helper function...
1486 template<typename _ForwardIterator, typename _Predicate>
1487 _ForwardIterator
1488 __partition(_ForwardIterator __first, _ForwardIterator __last,
1489 _Predicate __pred, forward_iterator_tag)
1490 {
1491 if (__first == __last)
1492 return __first;
1493
1494 while (__pred(*__first))
1495 if (++__first == __last)
1496 return __first;
1497
1498 _ForwardIterator __next = __first;
1499
1500 while (++__next != __last)
1501 if (__pred(*__next))
1502 {
1503 std::iter_swap(__first, __next);
1504 ++__first;
1505 }
1506
1507 return __first;
1508 }
1509
1510 /// This is a helper function...
1511 template<typename _BidirectionalIterator, typename _Predicate>
1512 _BidirectionalIterator
1513 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1514 _Predicate __pred, bidirectional_iterator_tag)
1515 {
1516 while (true)
1517 {
1518 while (true)
1519 if (__first == __last)
1520 return __first;
1521 else if (__pred(*__first))
1522 ++__first;
1523 else
1524 break;
1525 --__last;
1526 while (true)
1527 if (__first == __last)
1528 return __first;
1529 else if (!bool(__pred(*__last)))
1530 --__last;
1531 else
1532 break;
1533 std::iter_swap(__first, __last);
1534 ++__first;
1535 }
1536 }
1537
1538 // partition
1539
1540 /// This is a helper function...
1541 /// Requires __first != __last and !__pred(__first)
1542 /// and __len == distance(__first, __last).
1543 ///
1544 /// !__pred(__first) allows us to guarantee that we don't
1545 /// move-assign an element onto itself.
1546 template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1547 typename _Distance>
1548 _ForwardIterator
1549 __stable_partition_adaptive(_ForwardIterator __first,
1550 _ForwardIterator __last,
1551 _Predicate __pred, _Distance __len,
1552 _Pointer __buffer,
1553 _Distance __buffer_size)
1554 {
1555 if (__len == 1)
1556 return __first;
1557
1558 if (__len <= __buffer_size)
1559 {
1560 _ForwardIterator __result1 = __first;
1561 _Pointer __result2 = __buffer;
1562
1563 // The precondition guarantees that !__pred(__first), so
1564 // move that element to the buffer before starting the loop.
1565 // This ensures that we only call __pred once per element.
1566 *__result2 = _GLIBCXX_MOVE(*__first);
1567 ++__result2;
1568 ++__first;
1569 for (; __first != __last; ++__first)
1570 if (__pred(__first))
1571 {
1572 *__result1 = _GLIBCXX_MOVE(*__first);
1573 ++__result1;
1574 }
1575 else
1576 {
1577 *__result2 = _GLIBCXX_MOVE(*__first);
1578 ++__result2;
1579 }
1580
1581 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1582 return __result1;
1583 }
1584
1585 _ForwardIterator __middle = __first;
1586 std::advance(__middle, __len / 2);
1587 _ForwardIterator __left_split =
1588 std::__stable_partition_adaptive(__first, __middle, __pred,
1589 __len / 2, __buffer,
1590 __buffer_size);
1591
1592 // Advance past true-predicate values to satisfy this
1593 // function's preconditions.
1594 _Distance __right_len = __len - __len / 2;
1595 _ForwardIterator __right_split =
1596 std::__find_if_not_n(__middle, __right_len, __pred);
1597
1598 if (__right_len)
1599 __right_split =
1600 std::__stable_partition_adaptive(__right_split, __last, __pred,
1601 __right_len,
1602 __buffer, __buffer_size);
1603
1604 return std::rotate(__left_split, __middle, __right_split);
1605 }
1606
1607 template<typename _ForwardIterator, typename _Predicate>
1608 _ForwardIterator
1609 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1610 _Predicate __pred)
1611 {
1612 __first = std::__find_if_not(__first, __last, __pred);
1613
1614 if (__first == __last)
1615 return __first;
1616
1617 typedef typename iterator_traits<_ForwardIterator>::value_type
1618 _ValueType;
1619 typedef typename iterator_traits<_ForwardIterator>::difference_type
1620 _DistanceType;
1621
1622 _Temporary_buffer<_ForwardIterator, _ValueType>
1623 __buf(__first, std::distance(__first, __last));
1624 return
1625 std::__stable_partition_adaptive(__first, __last, __pred,
1626 _DistanceType(__buf.requested_size()),
1627 __buf.begin(),
1628 _DistanceType(__buf.size()));
1629 }
1630
1631 /**
1632 * @brief Move elements for which a predicate is true to the beginning
1633 * of a sequence, preserving relative ordering.
1634 * @ingroup mutating_algorithms
1635 * @param __first A forward iterator.
1636 * @param __last A forward iterator.
1637 * @param __pred A predicate functor.
1638 * @return An iterator @p middle such that @p __pred(i) is true for each
1639 * iterator @p i in the range @p [first,middle) and false for each @p i
1640 * in the range @p [middle,last).
1641 *
1642 * Performs the same function as @p partition() with the additional
1643 * guarantee that the relative ordering of elements in each group is
1644 * preserved, so any two elements @p x and @p y in the range
1645 * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1646 * relative ordering after calling @p stable_partition().
1647 */
1648 template<typename _ForwardIterator, typename _Predicate>
1649 inline _ForwardIterator
1650 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1651 _Predicate __pred)
1652 {
1653 // concept requirements
1654 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1655 _ForwardIterator>)
1656 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1657 typename iterator_traits<_ForwardIterator>::value_type>)
1658 __glibcxx_requires_valid_range(__first, __last);
1659
1660 return std::__stable_partition(__first, __last,
1661 __gnu_cxx::__ops::__pred_iter(__pred));
1662 }
1663
1664 /// This is a helper function for the sort routines.
1665 template<typename _RandomAccessIterator, typename _Compare>
1666 void
1667 __heap_select(_RandomAccessIterator __first,
1668 _RandomAccessIterator __middle,
1669 _RandomAccessIterator __last, _Compare __comp)
1670 {
1671 std::__make_heap(__first, __middle, __comp);
1672 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1673 if (__comp(__i, __first))
1674 std::__pop_heap(__first, __middle, __i, __comp);
1675 }
1676
1677 // partial_sort
1678
1679 template<typename _InputIterator, typename _RandomAccessIterator,
1680 typename _Compare>
1681 _RandomAccessIterator
1682 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1683 _RandomAccessIterator __result_first,
1684 _RandomAccessIterator __result_last,
1685 _Compare __comp)
1686 {
1687 typedef typename iterator_traits<_InputIterator>::value_type
1688 _InputValueType;
1689 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1690 typedef typename _RItTraits::difference_type _DistanceType;
1691
1692 if (__result_first == __result_last)
1693 return __result_last;
1694 _RandomAccessIterator __result_real_last = __result_first;
1695 while (__first != __last && __result_real_last != __result_last)
1696 {
1697 *__result_real_last = *__first;
1698 ++__result_real_last;
1699 ++__first;
1700 }
1701
1702 std::__make_heap(__result_first, __result_real_last, __comp);
1703 while (__first != __last)
1704 {
1705 if (__comp(__first, __result_first))
1706 std::__adjust_heap(__result_first, _DistanceType(0),
1707 _DistanceType(__result_real_last
1708 - __result_first),
1709 _InputValueType(*__first), __comp);
1710 ++__first;
1711 }
1712 std::__sort_heap(__result_first, __result_real_last, __comp);
1713 return __result_real_last;
1714 }
1715
1716 /**
1717 * @brief Copy the smallest elements of a sequence.
1718 * @ingroup sorting_algorithms
1719 * @param __first An iterator.
1720 * @param __last Another iterator.
1721 * @param __result_first A random-access iterator.
1722 * @param __result_last Another random-access iterator.
1723 * @return An iterator indicating the end of the resulting sequence.
1724 *
1725 * Copies and sorts the smallest N values from the range @p [__first,__last)
1726 * to the range beginning at @p __result_first, where the number of
1727 * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1728 * @p (__result_last-__result_first).
1729 * After the sort if @e i and @e j are iterators in the range
1730 * @p [__result_first,__result_first+N) such that i precedes j then
1731 * *j<*i is false.
1732 * The value returned is @p __result_first+N.
1733 */
1734 template<typename _InputIterator, typename _RandomAccessIterator>
1735 inline _RandomAccessIterator
1736 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1737 _RandomAccessIterator __result_first,
1738 _RandomAccessIterator __result_last)
1739 {
1740#ifdef _GLIBCXX_CONCEPT_CHECKS
1741 typedef typename iterator_traits<_InputIterator>::value_type
1742 _InputValueType;
1743 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1744 _OutputValueType;
1745#endif
1746
1747 // concept requirements
1748 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1749 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1750 _OutputValueType>)
1751 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1752 _OutputValueType>)
1753 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1754 __glibcxx_requires_valid_range(__first, __last);
1755 __glibcxx_requires_irreflexive(__first, __last);
1756 __glibcxx_requires_valid_range(__result_first, __result_last);
1757
1758 return std::__partial_sort_copy(__first, __last,
1759 __result_first, __result_last,
1760 __gnu_cxx::__ops::__iter_less_iter());
1761 }
1762
1763 /**
1764 * @brief Copy the smallest elements of a sequence using a predicate for
1765 * comparison.
1766 * @ingroup sorting_algorithms
1767 * @param __first An input iterator.
1768 * @param __last Another input iterator.
1769 * @param __result_first A random-access iterator.
1770 * @param __result_last Another random-access iterator.
1771 * @param __comp A comparison functor.
1772 * @return An iterator indicating the end of the resulting sequence.
1773 *
1774 * Copies and sorts the smallest N values from the range @p [__first,__last)
1775 * to the range beginning at @p result_first, where the number of
1776 * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1777 * @p (__result_last-__result_first).
1778 * After the sort if @e i and @e j are iterators in the range
1779 * @p [__result_first,__result_first+N) such that i precedes j then
1780 * @p __comp(*j,*i) is false.
1781 * The value returned is @p __result_first+N.
1782 */
1783 template<typename _InputIterator, typename _RandomAccessIterator,
1784 typename _Compare>
1785 inline _RandomAccessIterator
1786 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1787 _RandomAccessIterator __result_first,
1788 _RandomAccessIterator __result_last,
1789 _Compare __comp)
1790 {
1791#ifdef _GLIBCXX_CONCEPT_CHECKS
1792 typedef typename iterator_traits<_InputIterator>::value_type
1793 _InputValueType;
1794 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1795 _OutputValueType;
1796#endif
1797
1798 // concept requirements
1799 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1800 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1801 _RandomAccessIterator>)
1802 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1803 _OutputValueType>)
1804 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1805 _InputValueType, _OutputValueType>)
1806 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1807 _OutputValueType, _OutputValueType>)
1808 __glibcxx_requires_valid_range(__first, __last);
1809 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
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 // concept requirements
2026 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2027 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2028 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2029 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2030 __val, __comp);
2031
2032 return std::__lower_bound(__first, __last, __val,
2033 __gnu_cxx::__ops::__iter_comp_val(__comp));
2034 }
2035
2036 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2037 _ForwardIterator
2038 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2039 const _Tp& __val, _Compare __comp)
2040 {
2041 typedef typename iterator_traits<_ForwardIterator>::difference_type
2042 _DistanceType;
2043
2044 _DistanceType __len = std::distance(__first, __last);
2045
2046 while (__len > 0)
2047 {
2048 _DistanceType __half = __len >> 1;
2049 _ForwardIterator __middle = __first;
2050 std::advance(__middle, __half);
2051 if (__comp(__val, __middle))
2052 __len = __half;
2053 else
2054 {
2055 __first = __middle;
2056 ++__first;
2057 __len = __len - __half - 1;
2058 }
2059 }
2060 return __first;
2061 }
2062
2063 /**
2064 * @brief Finds the last position in which @p __val could be inserted
2065 * without changing the ordering.
2066 * @ingroup binary_search_algorithms
2067 * @param __first An iterator.
2068 * @param __last Another iterator.
2069 * @param __val The search term.
2070 * @return An iterator pointing to the first element greater than @p __val,
2071 * or end() if no elements are greater than @p __val.
2072 * @ingroup binary_search_algorithms
2073 */
2074 template<typename _ForwardIterator, typename _Tp>
2075 inline _ForwardIterator
2076 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2077 const _Tp& __val)
2078 {
2079 // concept requirements
2080 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2081 __glibcxx_function_requires(_LessThanOpConcept<
2082 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2083 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2084
2085 return std::__upper_bound(__first, __last, __val,
2086 __gnu_cxx::__ops::__val_less_iter());
2087 }
2088
2089 /**
2090 * @brief Finds the last position in which @p __val could be inserted
2091 * without changing the ordering.
2092 * @ingroup binary_search_algorithms
2093 * @param __first An iterator.
2094 * @param __last Another iterator.
2095 * @param __val The search term.
2096 * @param __comp A functor to use for comparisons.
2097 * @return An iterator pointing to the first element greater than @p __val,
2098 * or end() if no elements are greater than @p __val.
2099 * @ingroup binary_search_algorithms
2100 *
2101 * The comparison function should have the same effects on ordering as
2102 * the function used for the initial sort.
2103 */
2104 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2105 inline _ForwardIterator
2106 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2107 const _Tp& __val, _Compare __comp)
2108 {
2109 // concept requirements
2110 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2111 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2112 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2113 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2114 __val, __comp);
2115
2116 return std::__upper_bound(__first, __last, __val,
2117 __gnu_cxx::__ops::__val_comp_iter(__comp));
2118 }
2119
2120 template<typename _ForwardIterator, typename _Tp,
2121 typename _CompareItTp, typename _CompareTpIt>
2122 pair<_ForwardIterator, _ForwardIterator>
2123 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2124 const _Tp& __val,
2125 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2126 {
2127 typedef typename iterator_traits<_ForwardIterator>::difference_type
2128 _DistanceType;
2129
2130 _DistanceType __len = std::distance(__first, __last);
2131
2132 while (__len > 0)
2133 {
2134 _DistanceType __half = __len >> 1;
2135 _ForwardIterator __middle = __first;
2136 std::advance(__middle, __half);
2137 if (__comp_it_val(__middle, __val))
2138 {
2139 __first = __middle;
2140 ++__first;
2141 __len = __len - __half - 1;
2142 }
2143 else if (__comp_val_it(__val, __middle))
2144 __len = __half;
2145 else
2146 {
2147 _ForwardIterator __left
2148 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2149 std::advance(__first, __len);
2150 _ForwardIterator __right
2151 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2152 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2153 }
2154 }
2155 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2156 }
2157
2158 /**
2159 * @brief Finds the largest subrange in which @p __val could be inserted
2160 * at any place in it without changing the ordering.
2161 * @ingroup binary_search_algorithms
2162 * @param __first An iterator.
2163 * @param __last Another iterator.
2164 * @param __val The search term.
2165 * @return An pair of iterators defining the subrange.
2166 * @ingroup binary_search_algorithms
2167 *
2168 * This is equivalent to
2169 * @code
2170 * std::make_pair(lower_bound(__first, __last, __val),
2171 * upper_bound(__first, __last, __val))
2172 * @endcode
2173 * but does not actually call those functions.
2174 */
2175 template<typename _ForwardIterator, typename _Tp>
2176 inline pair<_ForwardIterator, _ForwardIterator>
2177 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2178 const _Tp& __val)
2179 {
2180 // concept requirements
2181 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2182 __glibcxx_function_requires(_LessThanOpConcept<
2183 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2184 __glibcxx_function_requires(_LessThanOpConcept<
2185 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2186 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2187 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2188
2189 return std::__equal_range(__first, __last, __val,
2190 __gnu_cxx::__ops::__iter_less_val(),
2191 __gnu_cxx::__ops::__val_less_iter());
2192 }
2193
2194 /**
2195 * @brief Finds the largest subrange in which @p __val could be inserted
2196 * at any place in it without changing the ordering.
2197 * @param __first An iterator.
2198 * @param __last Another iterator.
2199 * @param __val The search term.
2200 * @param __comp A functor to use for comparisons.
2201 * @return An pair of iterators defining the subrange.
2202 * @ingroup binary_search_algorithms
2203 *
2204 * This is equivalent to
2205 * @code
2206 * std::make_pair(lower_bound(__first, __last, __val, __comp),
2207 * upper_bound(__first, __last, __val, __comp))
2208 * @endcode
2209 * but does not actually call those functions.
2210 */
2211 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2212 inline pair<_ForwardIterator, _ForwardIterator>
2213 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2214 const _Tp& __val, _Compare __comp)
2215 {
2216 // concept requirements
2217 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2218 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2219 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2220 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2221 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2222 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2223 __val, __comp);
2224 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2225 __val, __comp);
2226
2227 return std::__equal_range(__first, __last, __val,
2228 __gnu_cxx::__ops::__iter_comp_val(__comp),
2229 __gnu_cxx::__ops::__val_comp_iter(__comp));
2230 }
2231
2232 /**
2233 * @brief Determines whether an element exists in a range.
2234 * @ingroup binary_search_algorithms
2235 * @param __first An iterator.
2236 * @param __last Another iterator.
2237 * @param __val The search term.
2238 * @return True if @p __val (or its equivalent) is in [@p
2239 * __first,@p __last ].
2240 *
2241 * Note that this does not actually return an iterator to @p __val. For
2242 * that, use std::find or a container's specialized find member functions.
2243 */
2244 template<typename _ForwardIterator, typename _Tp>
2245 bool
2246 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2247 const _Tp& __val)
2248 {
2249 // concept requirements
2250 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2251 __glibcxx_function_requires(_LessThanOpConcept<
2252 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2253 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2254 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2255
2256 _ForwardIterator __i
2257 = std::__lower_bound(__first, __last, __val,
2258 __gnu_cxx::__ops::__iter_less_val());
2259 return __i != __last && !(__val < *__i);
2260 }
2261
2262 /**
2263 * @brief Determines whether an element exists in a range.
2264 * @ingroup binary_search_algorithms
2265 * @param __first An iterator.
2266 * @param __last Another iterator.
2267 * @param __val The search term.
2268 * @param __comp A functor to use for comparisons.
2269 * @return True if @p __val (or its equivalent) is in @p [__first,__last].
2270 *
2271 * Note that this does not actually return an iterator to @p __val. For
2272 * that, use std::find or a container's specialized find member functions.
2273 *
2274 * The comparison function should have the same effects on ordering as
2275 * the function used for the initial sort.
2276 */
2277 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2278 bool
2279 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2280 const _Tp& __val, _Compare __comp)
2281 {
2282 // concept requirements
2283 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2284 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2285 _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2286 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2287 __val, __comp);
2288 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2289 __val, __comp);
2290
2291 _ForwardIterator __i
2292 = std::__lower_bound(__first, __last, __val,
2293 __gnu_cxx::__ops::__iter_comp_val(__comp));
2294 return __i != __last && !bool(__comp(__val, *__i));
2295 }
2296
2297 // merge
2298
2299 /// This is a helper function for the __merge_adaptive routines.
2300 template<typename _InputIterator1, typename _InputIterator2,
2301 typename _OutputIterator, typename _Compare>
2302 void
2303 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2304 _InputIterator2 __first2, _InputIterator2 __last2,
2305 _OutputIterator __result, _Compare __comp)
2306 {
2307 while (__first1 != __last1 && __first2 != __last2)
2308 {
2309 if (__comp(__first2, __first1))
2310 {
2311 *__result = _GLIBCXX_MOVE(*__first2);
2312 ++__first2;
2313 }
2314 else
2315 {
2316 *__result = _GLIBCXX_MOVE(*__first1);
2317 ++__first1;
2318 }
2319 ++__result;
2320 }
2321 if (__first1 != __last1)
2322 _GLIBCXX_MOVE3(__first1, __last1, __result);
2323 }
2324
2325 /// This is a helper function for the __merge_adaptive routines.
2326 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2327 typename _BidirectionalIterator3, typename _Compare>
2328 void
2329 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2330 _BidirectionalIterator1 __last1,
2331 _BidirectionalIterator2 __first2,
2332 _BidirectionalIterator2 __last2,
2333 _BidirectionalIterator3 __result,
2334 _Compare __comp)
2335 {
2336 if (__first1 == __last1)
2337 {
2338 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2339 return;
2340 }
2341 else if (__first2 == __last2)
2342 return;
2343
2344 --__last1;
2345 --__last2;
2346 while (true)
2347 {
2348 if (__comp(__last2, __last1))
2349 {
2350 *--__result = _GLIBCXX_MOVE(*__last1);
2351 if (__first1 == __last1)
2352 {
2353 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2354 return;
2355 }
2356 --__last1;
2357 }
2358 else
2359 {
2360 *--__result = _GLIBCXX_MOVE(*__last2);
2361 if (__first2 == __last2)
2362 return;
2363 --__last2;
2364 }
2365 }
2366 }
2367
2368 /// This is a helper function for the merge routines.
2369 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2370 typename _Distance>
2371 _BidirectionalIterator1
2372 __rotate_adaptive(_BidirectionalIterator1 __first,
2373 _BidirectionalIterator1 __middle,
2374 _BidirectionalIterator1 __last,
2375 _Distance __len1, _Distance __len2,
2376 _BidirectionalIterator2 __buffer,
2377 _Distance __buffer_size)
2378 {
2379 _BidirectionalIterator2 __buffer_end;
2380 if (__len1 > __len2 && __len2 <= __buffer_size)
2381 {
2382 if (__len2)
2383 {
2384 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2385 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2386 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2387 }
2388 else
2389 return __first;
2390 }
2391 else if (__len1 <= __buffer_size)
2392 {
2393 if (__len1)
2394 {
2395 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2396 _GLIBCXX_MOVE3(__middle, __last, __first);
2397 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2398 }
2399 else
2400 return __last;
2401 }
2402 else
2403 return std::rotate(__first, __middle, __last);
2404 }
2405
2406 /// This is a helper function for the merge routines.
2407 template<typename _BidirectionalIterator, typename _Distance,
2408 typename _Pointer, typename _Compare>
2409 void
2410 __merge_adaptive(_BidirectionalIterator __first,
2411 _BidirectionalIterator __middle,
2412 _BidirectionalIterator __last,
2413 _Distance __len1, _Distance __len2,
2414 _Pointer __buffer, _Distance __buffer_size,
2415 _Compare __comp)
2416 {
2417 if (__len1 <= __len2 && __len1 <= __buffer_size)
2418 {
2419 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2420 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2421 __first, __comp);
2422 }
2423 else if (__len2 <= __buffer_size)
2424 {
2425 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2426 std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2427 __buffer_end, __last, __comp);
2428 }
2429 else
2430 {
2431 _BidirectionalIterator __first_cut = __first;
2432 _BidirectionalIterator __second_cut = __middle;
2433 _Distance __len11 = 0;
2434 _Distance __len22 = 0;
2435 if (__len1 > __len2)
2436 {
2437 __len11 = __len1 / 2;
2438 std::advance(__first_cut, __len11);
2439 __second_cut
2440 = std::__lower_bound(__middle, __last, *__first_cut,
2441 __gnu_cxx::__ops::__iter_comp_val(__comp));
2442 __len22 = std::distance(__middle, __second_cut);
2443 }
2444 else
2445 {
2446 __len22 = __len2 / 2;
2447 std::advance(__second_cut, __len22);
2448 __first_cut
2449 = std::__upper_bound(__first, __middle, *__second_cut,
2450 __gnu_cxx::__ops::__val_comp_iter(__comp));
2451 __len11 = std::distance(__first, __first_cut);
2452 }
2453
2454 _BidirectionalIterator __new_middle
2455 = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2456 __len1 - __len11, __len22, __buffer,
2457 __buffer_size);
2458 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2459 __len22, __buffer, __buffer_size, __comp);
2460 std::__merge_adaptive(__new_middle, __second_cut, __last,
2461 __len1 - __len11,
2462 __len2 - __len22, __buffer,
2463 __buffer_size, __comp);
2464 }
2465 }
2466
2467 /// This is a helper function for the merge routines.
2468 template<typename _BidirectionalIterator, typename _Distance,
2469 typename _Compare>
2470 void
2471 __merge_without_buffer(_BidirectionalIterator __first,
2472 _BidirectionalIterator __middle,
2473 _BidirectionalIterator __last,
2474 _Distance __len1, _Distance __len2,
2475 _Compare __comp)
2476 {
2477 if (__len1 == 0 || __len2 == 0)
2478 return;
2479
2480 if (__len1 + __len2 == 2)
2481 {
2482 if (__comp(__middle, __first))
2483 std::iter_swap(__first, __middle);
2484 return;
2485 }
2486
2487 _BidirectionalIterator __first_cut = __first;
2488 _BidirectionalIterator __second_cut = __middle;
2489 _Distance __len11 = 0;
2490 _Distance __len22 = 0;
2491 if (__len1 > __len2)
2492 {
2493 __len11 = __len1 / 2;
2494 std::advance(__first_cut, __len11);
2495 __second_cut
2496 = std::__lower_bound(__middle, __last, *__first_cut,
2497 __gnu_cxx::__ops::__iter_comp_val(__comp));
2498 __len22 = std::distance(__middle, __second_cut);
2499 }
2500 else
2501 {
2502 __len22 = __len2 / 2;
2503 std::advance(__second_cut, __len22);
2504 __first_cut
2505 = std::__upper_bound(__first, __middle, *__second_cut,
2506 __gnu_cxx::__ops::__val_comp_iter(__comp));
2507 __len11 = std::distance(__first, __first_cut);
2508 }
2509
2510 _BidirectionalIterator __new_middle
2511 = std::rotate(__first_cut, __middle, __second_cut);
2512 std::__merge_without_buffer(__first, __first_cut, __new_middle,
2513 __len11, __len22, __comp);
2514 std::__merge_without_buffer(__new_middle, __second_cut, __last,
2515 __len1 - __len11, __len2 - __len22, __comp);
2516 }
2517
2518 template<typename _BidirectionalIterator, typename _Compare>
2519 void
2520 __inplace_merge(_BidirectionalIterator __first,
2521 _BidirectionalIterator __middle,
2522 _BidirectionalIterator __last,
2523 _Compare __comp)
2524 {
2525 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2526 _ValueType;
2527 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2528 _DistanceType;
2529
2530 if (__first == __middle || __middle == __last)
2531 return;
2532
2533 const _DistanceType __len1 = std::distance(__first, __middle);
2534 const _DistanceType __len2 = std::distance(__middle, __last);
2535
2536 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2537 _TmpBuf __buf(__first, __len1 + __len2);
2538
2539 if (__buf.begin() == 0)
2540 std::__merge_without_buffer
2541 (__first, __middle, __last, __len1, __len2, __comp);
2542 else
2543 std::__merge_adaptive
2544 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2545 _DistanceType(__buf.size()), __comp);
2546 }
2547
2548 /**
2549 * @brief Merges two sorted ranges in place.
2550 * @ingroup sorting_algorithms
2551 * @param __first An iterator.
2552 * @param __middle Another iterator.
2553 * @param __last Another iterator.
2554 * @return Nothing.
2555 *
2556 * Merges two sorted and consecutive ranges, [__first,__middle) and
2557 * [__middle,__last), and puts the result in [__first,__last). The
2558 * output will be sorted. The sort is @e stable, that is, for
2559 * equivalent elements in the two ranges, elements from the first
2560 * range will always come before elements from the second.
2561 *
2562 * If enough additional memory is available, this takes (__last-__first)-1
2563 * comparisons. Otherwise an NlogN algorithm is used, where N is
2564 * distance(__first,__last).
2565 */
2566 template<typename _BidirectionalIterator>
2567 inline void
2568 inplace_merge(_BidirectionalIterator __first,
2569 _BidirectionalIterator __middle,
2570 _BidirectionalIterator __last)
2571 {
2572 // concept requirements
2573 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2574 _BidirectionalIterator>)
2575 __glibcxx_function_requires(_LessThanComparableConcept<
2576 typename iterator_traits<_BidirectionalIterator>::value_type>)
2577 __glibcxx_requires_sorted(__first, __middle);
2578 __glibcxx_requires_sorted(__middle, __last);
2579 __glibcxx_requires_irreflexive(__first, __last);
2580
2581 std::__inplace_merge(__first, __middle, __last,
2582 __gnu_cxx::__ops::__iter_less_iter());
2583 }
2584
2585 /**
2586 * @brief Merges two sorted ranges in place.
2587 * @ingroup sorting_algorithms
2588 * @param __first An iterator.
2589 * @param __middle Another iterator.
2590 * @param __last Another iterator.
2591 * @param __comp A functor to use for comparisons.
2592 * @return Nothing.
2593 *
2594 * Merges two sorted and consecutive ranges, [__first,__middle) and
2595 * [middle,last), and puts the result in [__first,__last). The output will
2596 * be sorted. The sort is @e stable, that is, for equivalent
2597 * elements in the two ranges, elements from the first range will always
2598 * come before elements from the second.
2599 *
2600 * If enough additional memory is available, this takes (__last-__first)-1
2601 * comparisons. Otherwise an NlogN algorithm is used, where N is
2602 * distance(__first,__last).
2603 *
2604 * The comparison function should have the same effects on ordering as
2605 * the function used for the initial sort.
2606 */
2607 template<typename _BidirectionalIterator, typename _Compare>
2608 inline void
2609 inplace_merge(_BidirectionalIterator __first,
2610 _BidirectionalIterator __middle,
2611 _BidirectionalIterator __last,
2612 _Compare __comp)
2613 {
2614 // concept requirements
2615 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2616 _BidirectionalIterator>)
2617 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2618 typename iterator_traits<_BidirectionalIterator>::value_type,
2619 typename iterator_traits<_BidirectionalIterator>::value_type>)
2620 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2621 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2622 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2623
2624 std::__inplace_merge(__first, __middle, __last,
2625 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2626 }
2627
2628
2629 /// This is a helper function for the __merge_sort_loop routines.
2630 template<typename _InputIterator, typename _OutputIterator,
2631 typename _Compare>
2632 _OutputIterator
2633 __move_merge(_InputIterator __first1, _InputIterator __last1,
2634 _InputIterator __first2, _InputIterator __last2,
2635 _OutputIterator __result, _Compare __comp)
2636 {
2637 while (__first1 != __last1 && __first2 != __last2)
2638 {
2639 if (__comp(__first2, __first1))
2640 {
2641 *__result = _GLIBCXX_MOVE(*__first2);
2642 ++__first2;
2643 }
2644 else
2645 {
2646 *__result = _GLIBCXX_MOVE(*__first1);
2647 ++__first1;
2648 }
2649 ++__result;
2650 }
2651 return _GLIBCXX_MOVE3(__first2, __last2,
2652 _GLIBCXX_MOVE3(__first1, __last1,
2653 __result));
2654 }
2655
2656 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
2657 typename _Distance, typename _Compare>
2658 void
2659 __merge_sort_loop(_RandomAccessIterator1 __first,
2660 _RandomAccessIterator1 __last,
2661 _RandomAccessIterator2 __result, _Distance __step_size,
2662 _Compare __comp)
2663 {
2664 const _Distance __two_step = 2 * __step_size;
2665
2666 while (__last - __first >= __two_step)
2667 {
2668 __result = std::__move_merge(__first, __first + __step_size,
2669 __first + __step_size,
2670 __first + __two_step,
2671 __result, __comp);
2672 __first += __two_step;
2673 }
2674 __step_size = std::min(_Distance(__last - __first), __step_size);
2675
2676 std::__move_merge(__first, __first + __step_size,
2677 __first + __step_size, __last, __result, __comp);
2678 }
2679
2680 template<typename _RandomAccessIterator, typename _Distance,
2681 typename _Compare>
2682 void
2683 __chunk_insertion_sort(_RandomAccessIterator __first,
2684 _RandomAccessIterator __last,
2685 _Distance __chunk_size, _Compare __comp)
2686 {
2687 while (__last - __first >= __chunk_size)
2688 {
2689 std::__insertion_sort(__first, __first + __chunk_size, __comp);
2690 __first += __chunk_size;
2691 }
2692 std::__insertion_sort(__first, __last, __comp);
2693 }
2694
2695 enum { _S_chunk_size = 7 };
2696
2697 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
2698 void
2699 __merge_sort_with_buffer(_RandomAccessIterator __first,
2700 _RandomAccessIterator __last,
2701 _Pointer __buffer, _Compare __comp)
2702 {
2703 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2704 _Distance;
2705
2706 const _Distance __len = __last - __first;
2707 const _Pointer __buffer_last = __buffer + __len;
2708
2709 _Distance __step_size = _S_chunk_size;
2710 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2711
2712 while (__step_size < __len)
2713 {
2714 std::__merge_sort_loop(__first, __last, __buffer,
2715 __step_size, __comp);
2716 __step_size *= 2;
2717 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2718 __step_size, __comp);
2719 __step_size *= 2;
2720 }
2721 }
2722
2723 template<typename _RandomAccessIterator, typename _Pointer,
2724 typename _Distance, typename _Compare>
2725 void
2726 __stable_sort_adaptive(_RandomAccessIterator __first,
2727 _RandomAccessIterator __last,
2728 _Pointer __buffer, _Distance __buffer_size,
2729 _Compare __comp)
2730 {
2731 const _Distance __len = (__last - __first + 1) / 2;
2732 const _RandomAccessIterator __middle = __first + __len;
2733 if (__len > __buffer_size)
2734 {
2735 std::__stable_sort_adaptive(__first, __middle, __buffer,
2736 __buffer_size, __comp);
2737 std::__stable_sort_adaptive(__middle, __last, __buffer,
2738 __buffer_size, __comp);
2739 }
2740 else
2741 {
2742 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2743 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2744 }
2745 std::__merge_adaptive(__first, __middle, __last,
2746 _Distance(__middle - __first),
2747 _Distance(__last - __middle),
2748 __buffer, __buffer_size,
2749 __comp);
2750 }
2751
2752 /// This is a helper function for the stable sorting routines.
2753 template<typename _RandomAccessIterator, typename _Compare>
2754 void
2755 __inplace_stable_sort(_RandomAccessIterator __first,
2756 _RandomAccessIterator __last, _Compare __comp)
2757 {
2758 if (__last - __first < 15)
2759 {
2760 std::__insertion_sort(__first, __last, __comp);
2761 return;
2762 }
2763 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2764 std::__inplace_stable_sort(__first, __middle, __comp);
2765 std::__inplace_stable_sort(__middle, __last, __comp);
2766 std::__merge_without_buffer(__first, __middle, __last,
2767 __middle - __first,
2768 __last - __middle,
2769 __comp);
2770 }
2771
2772 // stable_sort
2773
2774 // Set algorithms: includes, set_union, set_intersection, set_difference,
2775 // set_symmetric_difference. All of these algorithms have the precondition
2776 // that their input ranges are sorted and the postcondition that their output
2777 // ranges are sorted.
2778
2779 template<typename _InputIterator1, typename _InputIterator2,
2780 typename _Compare>
2781 bool
2782 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2783 _InputIterator2 __first2, _InputIterator2 __last2,
2784 _Compare __comp)
2785 {
2786 while (__first1 != __last1 && __first2 != __last2)
2787 if (__comp(__first2, __first1))
2788 return false;
2789 else if (__comp(__first1, __first2))
2790 ++__first1;
2791 else
2792 {
2793 ++__first1;
2794 ++__first2;
2795 }
2796
2797 return __first2 == __last2;
2798 }
2799
2800 /**
2801 * @brief Determines whether all elements of a sequence exists in a range.
2802 * @param __first1 Start of search range.
2803 * @param __last1 End of search range.
2804 * @param __first2 Start of sequence
2805 * @param __last2 End of sequence.
2806 * @return True if each element in [__first2,__last2) is contained in order
2807 * within [__first1,__last1). False otherwise.
2808 * @ingroup set_algorithms
2809 *
2810 * This operation expects both [__first1,__last1) and
2811 * [__first2,__last2) to be sorted. Searches for the presence of
2812 * each element in [__first2,__last2) within [__first1,__last1).
2813 * The iterators over each range only move forward, so this is a
2814 * linear algorithm. If an element in [__first2,__last2) is not
2815 * found before the search iterator reaches @p __last2, false is
2816 * returned.
2817 */
2818 template<typename _InputIterator1, typename _InputIterator2>
2819 inline bool
2820 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2821 _InputIterator2 __first2, _InputIterator2 __last2)
2822 {
2823 // concept requirements
2824 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2825 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2826 __glibcxx_function_requires(_LessThanOpConcept<
2827 typename iterator_traits<_InputIterator1>::value_type,
2828 typename iterator_traits<_InputIterator2>::value_type>)
2829 __glibcxx_function_requires(_LessThanOpConcept<
2830 typename iterator_traits<_InputIterator2>::value_type,
2831 typename iterator_traits<_InputIterator1>::value_type>)
2832 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2833 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2834 __glibcxx_requires_irreflexive2(__first1, __last1);
2835 __glibcxx_requires_irreflexive2(__first2, __last2);
2836
2837 return std::__includes(__first1, __last1, __first2, __last2,
2838 __gnu_cxx::__ops::__iter_less_iter());
2839 }
2840
2841 /**
2842 * @brief Determines whether all elements of a sequence exists in a range
2843 * using comparison.
2844 * @ingroup set_algorithms
2845 * @param __first1 Start of search range.
2846 * @param __last1 End of search range.
2847 * @param __first2 Start of sequence
2848 * @param __last2 End of sequence.
2849 * @param __comp Comparison function to use.
2850 * @return True if each element in [__first2,__last2) is contained
2851 * in order within [__first1,__last1) according to comp. False
2852 * otherwise. @ingroup set_algorithms
2853 *
2854 * This operation expects both [__first1,__last1) and
2855 * [__first2,__last2) to be sorted. Searches for the presence of
2856 * each element in [__first2,__last2) within [__first1,__last1),
2857 * using comp to decide. The iterators over each range only move
2858 * forward, so this is a linear algorithm. If an element in
2859 * [__first2,__last2) is not found before the search iterator
2860 * reaches @p __last2, false is returned.
2861 */
2862 template<typename _InputIterator1, typename _InputIterator2,
2863 typename _Compare>
2864 inline bool
2865 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2866 _InputIterator2 __first2, _InputIterator2 __last2,
2867 _Compare __comp)
2868 {
2869 // concept requirements
2870 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2871 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2872 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2873 typename iterator_traits<_InputIterator1>::value_type,
2874 typename iterator_traits<_InputIterator2>::value_type>)
2875 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2876 typename iterator_traits<_InputIterator2>::value_type,
2877 typename iterator_traits<_InputIterator1>::value_type>)
2878 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2879 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2880 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2881 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2882
2883 return std::__includes(__first1, __last1, __first2, __last2,
2884 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2885 }
2886
2887 // nth_element
2888 // merge
2889 // set_difference
2890 // set_intersection
2891 // set_union
2892 // stable_sort
2893 // set_symmetric_difference
2894 // min_element
2895 // max_element
2896
2897 template<typename _BidirectionalIterator, typename _Compare>
2898 bool
2899 __next_permutation(_BidirectionalIterator __first,
2900 _BidirectionalIterator __last, _Compare __comp)
2901 {
2902 if (__first == __last)
2903 return false;
2904 _BidirectionalIterator __i = __first;
2905 ++__i;
2906 if (__i == __last)
2907 return false;
2908 __i = __last;
2909 --__i;
2910
2911 for(;;)
2912 {
2913 _BidirectionalIterator __ii = __i;
2914 --__i;
2915 if (__comp(__i, __ii))
2916 {
2917 _BidirectionalIterator __j = __last;
2918 while (!__comp(__i, --__j))
2919 {}
2920 std::iter_swap(__i, __j);
2921 std::__reverse(__ii, __last,
2922 std::__iterator_category(__first));
2923 return true;
2924 }
2925 if (__i == __first)
2926 {
2927 std::__reverse(__first, __last,
2928 std::__iterator_category(__first));
2929 return false;
2930 }
2931 }
2932 }
2933
2934 /**
2935 * @brief Permute range into the next @e dictionary ordering.
2936 * @ingroup sorting_algorithms
2937 * @param __first Start of range.
2938 * @param __last End of range.
2939 * @return False if wrapped to first permutation, true otherwise.
2940 *
2941 * Treats all permutations of the range as a set of @e dictionary sorted
2942 * sequences. Permutes the current sequence into the next one of this set.
2943 * Returns true if there are more sequences to generate. If the sequence
2944 * is the largest of the set, the smallest is generated and false returned.
2945 */
2946 template<typename _BidirectionalIterator>
2947 inline bool
2948 next_permutation(_BidirectionalIterator __first,
2949 _BidirectionalIterator __last)
2950 {
2951 // concept requirements
2952 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2953 _BidirectionalIterator>)
2954 __glibcxx_function_requires(_LessThanComparableConcept<
2955 typename iterator_traits<_BidirectionalIterator>::value_type>)
2956 __glibcxx_requires_valid_range(__first, __last);
2957 __glibcxx_requires_irreflexive(__first, __last);
2958
2959 return std::__next_permutation
2960 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2961 }
2962
2963 /**
2964 * @brief Permute range into the next @e dictionary ordering using
2965 * comparison functor.
2966 * @ingroup sorting_algorithms
2967 * @param __first Start of range.
2968 * @param __last End of range.
2969 * @param __comp A comparison functor.
2970 * @return False if wrapped to first permutation, true otherwise.
2971 *
2972 * Treats all permutations of the range [__first,__last) as a set of
2973 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
2974 * sequence into the next one of this set. Returns true if there are more
2975 * sequences to generate. If the sequence is the largest of the set, the
2976 * smallest is generated and false returned.
2977 */
2978 template<typename _BidirectionalIterator, typename _Compare>
2979 inline bool
2980 next_permutation(_BidirectionalIterator __first,
2981 _BidirectionalIterator __last, _Compare __comp)
2982 {
2983 // concept requirements
2984 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2985 _BidirectionalIterator>)
2986 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2987 typename iterator_traits<_BidirectionalIterator>::value_type,
2988 typename iterator_traits<_BidirectionalIterator>::value_type>)
2989 __glibcxx_requires_valid_range(__first, __last);
2990 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2991
2992 return std::__next_permutation
2993 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
2994 }
2995
2996 template<typename _BidirectionalIterator, typename _Compare>
2997 bool
2998 __prev_permutation(_BidirectionalIterator __first,
2999 _BidirectionalIterator __last, _Compare __comp)
3000 {
3001 if (__first == __last)
3002 return false;
3003 _BidirectionalIterator __i = __first;
3004 ++__i;
3005 if (__i == __last)
3006 return false;
3007 __i = __last;
3008 --__i;
3009
3010 for(;;)
3011 {
3012 _BidirectionalIterator __ii = __i;
3013 --__i;
3014 if (__comp(__ii, __i))
3015 {
3016 _BidirectionalIterator __j = __last;
3017 while (!__comp(--__j, __i))
3018 {}
3019 std::iter_swap(__i, __j);
3020 std::__reverse(__ii, __last,
3021 std::__iterator_category(__first));
3022 return true;
3023 }
3024 if (__i == __first)
3025 {
3026 std::__reverse(__first, __last,
3027 std::__iterator_category(__first));
3028 return false;
3029 }
3030 }
3031 }
3032
3033 /**
3034 * @brief Permute range into the previous @e dictionary ordering.
3035 * @ingroup sorting_algorithms
3036 * @param __first Start of range.
3037 * @param __last End of range.
3038 * @return False if wrapped to last permutation, true otherwise.
3039 *
3040 * Treats all permutations of the range as a set of @e dictionary sorted
3041 * sequences. Permutes the current sequence into the previous one of this
3042 * set. Returns true if there are more sequences to generate. If the
3043 * sequence is the smallest of the set, the largest is generated and false
3044 * returned.
3045 */
3046 template<typename _BidirectionalIterator>
3047 inline bool
3048 prev_permutation(_BidirectionalIterator __first,
3049 _BidirectionalIterator __last)
3050 {
3051 // concept requirements
3052 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3053 _BidirectionalIterator>)
3054 __glibcxx_function_requires(_LessThanComparableConcept<
3055 typename iterator_traits<_BidirectionalIterator>::value_type>)
3056 __glibcxx_requires_valid_range(__first, __last);
3057 __glibcxx_requires_irreflexive(__first, __last);
3058
3059 return std::__prev_permutation(__first, __last,
3060 __gnu_cxx::__ops::__iter_less_iter());
3061 }
3062
3063 /**
3064 * @brief Permute range into the previous @e dictionary ordering using
3065 * comparison functor.
3066 * @ingroup sorting_algorithms
3067 * @param __first Start of range.
3068 * @param __last End of range.
3069 * @param __comp A comparison functor.
3070 * @return False if wrapped to last permutation, true otherwise.
3071 *
3072 * Treats all permutations of the range [__first,__last) as a set of
3073 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
3074 * sequence into the previous one of this set. Returns true if there are
3075 * more sequences to generate. If the sequence is the smallest of the set,
3076 * the largest is generated and false returned.
3077 */
3078 template<typename _BidirectionalIterator, typename _Compare>
3079 inline bool
3080 prev_permutation(_BidirectionalIterator __first,
3081 _BidirectionalIterator __last, _Compare __comp)
3082 {
3083 // concept requirements
3084 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3085 _BidirectionalIterator>)
3086 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3087 typename iterator_traits<_BidirectionalIterator>::value_type,
3088 typename iterator_traits<_BidirectionalIterator>::value_type>)
3089 __glibcxx_requires_valid_range(__first, __last);
3090 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3091
3092 return std::__prev_permutation(__first, __last,
3093 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3094 }
3095
3096 // replace
3097 // replace_if
3098
3099 template<typename _InputIterator, typename _OutputIterator,
3100 typename _Predicate, typename _Tp>
3101 _OutputIterator
3102 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3103 _OutputIterator __result,
3104 _Predicate __pred, const _Tp& __new_value)
3105 {
3106 for (; __first != __last; ++__first, (void)++__result)
3107 if (__pred(__first))
3108 *__result = __new_value;
3109 else
3110 *__result = *__first;
3111 return __result;
3112 }
3113
3114 /**
3115 * @brief Copy a sequence, replacing each element of one value with another
3116 * value.
3117 * @param __first An input iterator.
3118 * @param __last An input iterator.
3119 * @param __result An output iterator.
3120 * @param __old_value The value to be replaced.
3121 * @param __new_value The replacement value.
3122 * @return The end of the output sequence, @p result+(last-first).
3123 *
3124 * Copies each element in the input range @p [__first,__last) to the
3125 * output range @p [__result,__result+(__last-__first)) replacing elements
3126 * equal to @p __old_value with @p __new_value.
3127 */
3128 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
3129 inline _OutputIterator
3130 replace_copy(_InputIterator __first, _InputIterator __last,
3131 _OutputIterator __result,
3132 const _Tp& __old_value, const _Tp& __new_value)
3133 {
3134 // concept requirements
3135 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3136 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3137 typename iterator_traits<_InputIterator>::value_type>)
3138 __glibcxx_function_requires(_EqualOpConcept<
3139 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3140 __glibcxx_requires_valid_range(__first, __last);
3141
3142 return std::__replace_copy_if(__first, __last, __result,
3143 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3144 __new_value);
3145 }
3146
3147 /**
3148 * @brief Copy a sequence, replacing each value for which a predicate
3149 * returns true with another value.
3150 * @ingroup mutating_algorithms
3151 * @param __first An input iterator.
3152 * @param __last An input iterator.
3153 * @param __result An output iterator.
3154 * @param __pred A predicate.
3155 * @param __new_value The replacement value.
3156 * @return The end of the output sequence, @p __result+(__last-__first).
3157 *
3158 * Copies each element in the range @p [__first,__last) to the range
3159 * @p [__result,__result+(__last-__first)) replacing elements for which
3160 * @p __pred returns true with @p __new_value.
3161 */
3162 template<typename _InputIterator, typename _OutputIterator,
3163 typename _Predicate, typename _Tp>
3164 inline _OutputIterator
3165 replace_copy_if(_InputIterator __first, _InputIterator __last,
3166 _OutputIterator __result,
3167 _Predicate __pred, const _Tp& __new_value)
3168 {
3169 // concept requirements
3170 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3171 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3172 typename iterator_traits<_InputIterator>::value_type>)
3173 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3174 typename iterator_traits<_InputIterator>::value_type>)
3175 __glibcxx_requires_valid_range(__first, __last);
3176
3177 return std::__replace_copy_if(__first, __last, __result,
3178 __gnu_cxx::__ops::__pred_iter(__pred),
3179 __new_value);
3180 }
3181
3182 template<typename _InputIterator, typename _Predicate>
3183 typename iterator_traits<_InputIterator>::difference_type
3184 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3185 {
3186 typename iterator_traits<_InputIterator>::difference_type __n = 0;
3187 for (; __first != __last; ++__first)
3188 if (__pred(__first))
3189 ++__n;
3190 return __n;
3191 }
3192
3193#if __cplusplus >= 201103L
3194 /**
3195 * @brief Determines whether the elements of a sequence are sorted.
3196 * @ingroup sorting_algorithms
3197 * @param __first An iterator.
3198 * @param __last Another iterator.
3199 * @return True if the elements are sorted, false otherwise.
3200 */
3201 template<typename _ForwardIterator>
3202 inline bool
3203 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3204 { return std::is_sorted_until(__first, __last) == __last; }
3205
3206 /**
3207 * @brief Determines whether the elements of a sequence are sorted
3208 * according to a comparison functor.
3209 * @ingroup sorting_algorithms
3210 * @param __first An iterator.
3211 * @param __last Another iterator.
3212 * @param __comp A comparison functor.
3213 * @return True if the elements are sorted, false otherwise.
3214 */
3215 template<typename _ForwardIterator, typename _Compare>
3216 inline bool
3217 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3218 _Compare __comp)
3219 { return std::is_sorted_until(__first, __last, __comp) == __last; }
3220
3221 template<typename _ForwardIterator, typename _Compare>
3222 _ForwardIterator
3223 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3224 _Compare __comp)
3225 {
3226 if (__first == __last)
3227 return __last;
3228
3229 _ForwardIterator __next = __first;
3230 for (++__next; __next != __last; __first = __next, (void)++__next)
3231 if (__comp(__next, __first))
3232 return __next;
3233 return __next;
3234 }
3235
3236 /**
3237 * @brief Determines the end of a sorted sequence.
3238 * @ingroup sorting_algorithms
3239 * @param __first An iterator.
3240 * @param __last Another iterator.
3241 * @return An iterator pointing to the last iterator i in [__first, __last)
3242 * for which the range [__first, i) is sorted.
3243 */
3244 template<typename _ForwardIterator>
3245 inline _ForwardIterator
3246 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3247 {
3248 // concept requirements
3249 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3250 __glibcxx_function_requires(_LessThanComparableConcept<
3251 typename iterator_traits<_ForwardIterator>::value_type>)
3252 __glibcxx_requires_valid_range(__first, __last);
3253 __glibcxx_requires_irreflexive(__first, __last);
3254
3255 return std::__is_sorted_until(__first, __last,
3256 __gnu_cxx::__ops::__iter_less_iter());
3257 }
3258
3259 /**
3260 * @brief Determines the end of a sorted sequence using comparison functor.
3261 * @ingroup sorting_algorithms
3262 * @param __first An iterator.
3263 * @param __last Another iterator.
3264 * @param __comp A comparison functor.
3265 * @return An iterator pointing to the last iterator i in [__first, __last)
3266 * for which the range [__first, i) is sorted.
3267 */
3268 template<typename _ForwardIterator, typename _Compare>
3269 inline _ForwardIterator
3270 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3271 _Compare __comp)
3272 {
3273 // concept requirements
3274 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3275 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3276 typename iterator_traits<_ForwardIterator>::value_type,
3277 typename iterator_traits<_ForwardIterator>::value_type>)
3278 __glibcxx_requires_valid_range(__first, __last);
3279 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3280
3281 return std::__is_sorted_until(__first, __last,
3282 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3283 }
3284
3285 /**
3286 * @brief Determines min and max at once as an ordered pair.
3287 * @ingroup sorting_algorithms
3288 * @param __a A thing of arbitrary type.
3289 * @param __b Another thing of arbitrary type.
3290 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
3291 * __b) otherwise.
3292 */
3293 template<typename _Tp>
3294 _GLIBCXX14_CONSTEXPR
3295 inline pair<const _Tp&, const _Tp&>
3296 minmax(const _Tp& __a, const _Tp& __b)
3297 {
3298 // concept requirements
3299 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3300
3301 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3302 : pair<const _Tp&, const _Tp&>(__a, __b);
3303 }
3304
3305 /**
3306 * @brief Determines min and max at once as an ordered pair.
3307 * @ingroup sorting_algorithms
3308 * @param __a A thing of arbitrary type.
3309 * @param __b Another thing of arbitrary type.
3310 * @param __comp A @link comparison_functors comparison functor @endlink.
3311 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
3312 * __b) otherwise.
3313 */
3314 template<typename _Tp, typename _Compare>
3315 _GLIBCXX14_CONSTEXPR
3316 inline pair<const _Tp&, const _Tp&>
3317 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
3318 {
3319 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
3320 : pair<const _Tp&, const _Tp&>(__a, __b);
3321 }
3322
3323 template<typename _ForwardIterator, typename _Compare>
3324 _GLIBCXX14_CONSTEXPR
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 _GLIBCXX14_CONSTEXPR
3396 inline pair<_ForwardIterator, _ForwardIterator>
3397 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3398 {
3399 // concept requirements
3400 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3401 __glibcxx_function_requires(_LessThanComparableConcept<
3402 typename iterator_traits<_ForwardIterator>::value_type>)
3403 __glibcxx_requires_valid_range(__first, __last);
3404 __glibcxx_requires_irreflexive(__first, __last);
3405
3406 return std::__minmax_element(__first, __last,
3407 __gnu_cxx::__ops::__iter_less_iter());
3408 }
3409
3410 /**
3411 * @brief Return a pair of iterators pointing to the minimum and maximum
3412 * elements in a range.
3413 * @ingroup sorting_algorithms
3414 * @param __first Start of range.
3415 * @param __last End of range.
3416 * @param __comp Comparison functor.
3417 * @return make_pair(m, M), where m is the first iterator i in
3418 * [__first, __last) such that no other element in the range is
3419 * smaller, and where M is the last iterator i in [__first, __last)
3420 * such that no other element in the range is larger.
3421 */
3422 template<typename _ForwardIterator, typename _Compare>
3423 _GLIBCXX14_CONSTEXPR
3424 inline pair<_ForwardIterator, _ForwardIterator>
3425 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3426 _Compare __comp)
3427 {
3428 // concept requirements
3429 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3430 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3431 typename iterator_traits<_ForwardIterator>::value_type,
3432 typename iterator_traits<_ForwardIterator>::value_type>)
3433 __glibcxx_requires_valid_range(__first, __last);
3434 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3435
3436 return std::__minmax_element(__first, __last,
3437 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3438 }
3439
3440 // N2722 + DR 915.
3441 template<typename _Tp>
3442 _GLIBCXX14_CONSTEXPR
3443 inline _Tp
3444 min(initializer_list<_Tp> __l)
3445 { return *std::min_element(__l.begin(), __l.end()); }
3446
3447 template<typename _Tp, typename _Compare>
3448 _GLIBCXX14_CONSTEXPR
3449 inline _Tp
3450 min(initializer_list<_Tp> __l, _Compare __comp)
3451 { return *std::min_element(__l.begin(), __l.end(), __comp); }
3452
3453 template<typename _Tp>
3454 _GLIBCXX14_CONSTEXPR
3455 inline _Tp
3456 max(initializer_list<_Tp> __l)
3457 { return *std::max_element(__l.begin(), __l.end()); }
3458
3459 template<typename _Tp, typename _Compare>
3460 _GLIBCXX14_CONSTEXPR
3461 inline _Tp
3462 max(initializer_list<_Tp> __l, _Compare __comp)
3463 { return *std::max_element(__l.begin(), __l.end(), __comp); }
3464
3465 template<typename _Tp>
3466 _GLIBCXX14_CONSTEXPR
3467 inline pair<_Tp, _Tp>
3468 minmax(initializer_list<_Tp> __l)
3469 {
3470 pair<const _Tp*, const _Tp*> __p =
3471 std::minmax_element(__l.begin(), __l.end());
3472 return std::make_pair(*__p.first, *__p.second);
3473 }
3474
3475 template<typename _Tp, typename _Compare>
3476 _GLIBCXX14_CONSTEXPR
3477 inline pair<_Tp, _Tp>
3478 minmax(initializer_list<_Tp> __l, _Compare __comp)
3479 {
3480 pair<const _Tp*, const _Tp*> __p =
3481 std::minmax_element(__l.begin(), __l.end(), __comp);
3482 return std::make_pair(*__p.first, *__p.second);
3483 }
3484
3485 template<typename _ForwardIterator1, typename _ForwardIterator2,
3486 typename _BinaryPredicate>
3487 bool
3488 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3489 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3490 {
3491 // Efficiently compare identical prefixes: O(N) if sequences
3492 // have the same elements in the same order.
3493 for (; __first1 != __last1; ++__first1, (void)++__first2)
3494 if (!__pred(__first1, __first2))
3495 break;
3496
3497 if (__first1 == __last1)
3498 return true;
3499
3500 // Establish __last2 assuming equal ranges by iterating over the
3501 // rest of the list.
3502 _ForwardIterator2 __last2 = __first2;
3503 std::advance(__last2, std::distance(__first1, __last1));
3504 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3505 {
3506 if (__scan != std::__find_if(__first1, __scan,
3507 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3508 continue; // We've seen this one before.
3509
3510 auto __matches
3511 = std::__count_if(__first2, __last2,
3512 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3513 if (0 == __matches ||
3514 std::__count_if(__scan, __last1,
3515 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3516 != __matches)
3517 return false;
3518 }
3519 return true;
3520 }
3521
3522 /**
3523 * @brief Checks whether a permutation of the second sequence is equal
3524 * to the first sequence.
3525 * @ingroup non_mutating_algorithms
3526 * @param __first1 Start of first range.
3527 * @param __last1 End of first range.
3528 * @param __first2 Start of second range.
3529 * @return true if there exists a permutation of the elements in the range
3530 * [__first2, __first2 + (__last1 - __first1)), beginning with
3531 * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
3532 * returns true; otherwise, returns false.
3533 */
3534 template<typename _ForwardIterator1, typename _ForwardIterator2>
3535 inline bool
3536 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3537 _ForwardIterator2 __first2)
3538 {
3539 // concept requirements
3540 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3541 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3542 __glibcxx_function_requires(_EqualOpConcept<
3543 typename iterator_traits<_ForwardIterator1>::value_type,
3544 typename iterator_traits<_ForwardIterator2>::value_type>)
3545 __glibcxx_requires_valid_range(__first1, __last1);
3546
3547 return std::__is_permutation(__first1, __last1, __first2,
3548 __gnu_cxx::__ops::__iter_equal_to_iter());
3549 }
3550
3551 /**
3552 * @brief Checks whether a permutation of the second sequence is equal
3553 * to the first sequence.
3554 * @ingroup non_mutating_algorithms
3555 * @param __first1 Start of first range.
3556 * @param __last1 End of first range.
3557 * @param __first2 Start of second range.
3558 * @param __pred A binary predicate.
3559 * @return true if there exists a permutation of the elements in
3560 * the range [__first2, __first2 + (__last1 - __first1)),
3561 * beginning with ForwardIterator2 begin, such that
3562 * equal(__first1, __last1, __begin, __pred) returns true;
3563 * otherwise, returns false.
3564 */
3565 template<typename _ForwardIterator1, typename _ForwardIterator2,
3566 typename _BinaryPredicate>
3567 inline bool
3568 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3569 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3570 {
3571 // concept requirements
3572 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3573 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3574 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3575 typename iterator_traits<_ForwardIterator1>::value_type,
3576 typename iterator_traits<_ForwardIterator2>::value_type>)
3577 __glibcxx_requires_valid_range(__first1, __last1);
3578
3579 return std::__is_permutation(__first1, __last1, __first2,
3580 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3581 }
3582
3583#if __cplusplus > 201103L
3584 template<typename _ForwardIterator1, typename _ForwardIterator2,
3585 typename _BinaryPredicate>
3586 bool
3587 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3588 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3589 _BinaryPredicate __pred)
3590 {
3591 using _Cat1
3592 = typename iterator_traits<_ForwardIterator1>::iterator_category;
3593 using _Cat2
3594 = typename iterator_traits<_ForwardIterator2>::iterator_category;
3595 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3596 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3597 constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3598 if (__ra_iters)
3599 {
3600 auto __d1 = std::distance(__first1, __last1);
3601 auto __d2 = std::distance(__first2, __last2);
3602 if (__d1 != __d2)
3603 return false;
3604 }
3605
3606 // Efficiently compare identical prefixes: O(N) if sequences
3607 // have the same elements in the same order.
3608 for (; __first1 != __last1 && __first2 != __last2;
3609 ++__first1, (void)++__first2)
3610 if (!__pred(__first1, __first2))
3611 break;
3612
3613 if (__ra_iters)
3614 {
3615 if (__first1 == __last1)
3616 return true;
3617 }
3618 else
3619 {
3620 auto __d1 = std::distance(__first1, __last1);
3621 auto __d2 = std::distance(__first2, __last2);
3622 if (__d1 == 0 && __d2 == 0)
3623 return true;
3624 if (__d1 != __d2)
3625 return false;
3626 }
3627
3628 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3629 {
3630 if (__scan != std::__find_if(__first1, __scan,
3631 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3632 continue; // We've seen this one before.
3633
3634 auto __matches = std::__count_if(__first2, __last2,
3635 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3636 if (0 == __matches
3637 || std::__count_if(__scan, __last1,
3638 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3639 != __matches)
3640 return false;
3641 }
3642 return true;
3643 }
3644
3645 /**
3646 * @brief Checks whether a permutaion of the second sequence is equal
3647 * to the first sequence.
3648 * @ingroup non_mutating_algorithms
3649 * @param __first1 Start of first range.
3650 * @param __last1 End of first range.
3651 * @param __first2 Start of second range.
3652 * @param __last2 End of first range.
3653 * @return true if there exists a permutation of the elements in the range
3654 * [__first2, __last2), beginning with ForwardIterator2 begin,
3655 * such that equal(__first1, __last1, begin) returns true;
3656 * otherwise, returns false.
3657 */
3658 template<typename _ForwardIterator1, typename _ForwardIterator2>
3659 inline bool
3660 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3661 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3662 {
3663 __glibcxx_requires_valid_range(__first1, __last1);
3664 __glibcxx_requires_valid_range(__first2, __last2);
3665
3666 return
3667 std::__is_permutation(__first1, __last1, __first2, __last2,
3668 __gnu_cxx::__ops::__iter_equal_to_iter());
3669 }
3670
3671 /**
3672 * @brief Checks whether a permutation of the second sequence is equal
3673 * to the first sequence.
3674 * @ingroup non_mutating_algorithms
3675 * @param __first1 Start of first range.
3676 * @param __last1 End of first range.
3677 * @param __first2 Start of second range.
3678 * @param __last2 End of first range.
3679 * @param __pred A binary predicate.
3680 * @return true if there exists a permutation of the elements in the range
3681 * [__first2, __last2), beginning with ForwardIterator2 begin,
3682 * such that equal(__first1, __last1, __begin, __pred) returns true;
3683 * otherwise, returns false.
3684 */
3685 template<typename _ForwardIterator1, typename _ForwardIterator2,
3686 typename _BinaryPredicate>
3687 inline bool
3688 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3689 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3690 _BinaryPredicate __pred)
3691 {
3692 __glibcxx_requires_valid_range(__first1, __last1);
3693 __glibcxx_requires_valid_range(__first2, __last2);
3694
3695 return std::__is_permutation(__first1, __last1, __first2, __last2,
3696 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3697 }
3698
3699#if __cplusplus > 201402L
3700
3701#define __cpp_lib_clamp 201603
3702
3703 /**
3704 * @brief Returns the value clamped between lo and hi.
3705 * @ingroup sorting_algorithms
3706 * @param __val A value of arbitrary type.
3707 * @param __lo A lower limit of arbitrary type.
3708 * @param __hi An upper limit of arbitrary type.
3709 * @return max(__val, __lo) if __val < __hi or min(__val, __hi) otherwise.
3710 */
3711 template<typename _Tp>
3712 constexpr const _Tp&
3713 clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi)
3714 {
3715 __glibcxx_assert(!(__hi < __lo));
3716 return (__val < __lo) ? __lo : (__hi < __val) ? __hi : __val;
3717 }
3718
3719 /**
3720 * @brief Returns the value clamped between lo and hi.
3721 * @ingroup sorting_algorithms
3722 * @param __val A value of arbitrary type.
3723 * @param __lo A lower limit of arbitrary type.
3724 * @param __hi An upper limit of arbitrary type.
3725 * @param __comp A comparison functor.
3726 * @return max(__val, __lo, __comp) if __comp(__val, __hi)
3727 * or min(__val, __hi, __comp) otherwise.
3728 */
3729 template<typename _Tp, typename _Compare>
3730 constexpr const _Tp&
3731 clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
3732 {
3733 __glibcxx_assert(!__comp(__hi, __lo));
3734 return __comp(__val, __lo) ? __lo : __comp(__hi, __val) ? __hi : __val;
3735 }
3736#endif // C++17
3737#endif // C++14
3738
3739#ifdef _GLIBCXX_USE_C99_STDINT_TR1
3740 /**
3741 * @brief Generate two uniformly distributed integers using a
3742 * single distribution invocation.
3743 * @param __b0 The upper bound for the first integer.
3744 * @param __b1 The upper bound for the second integer.
3745 * @param __g A UniformRandomBitGenerator.
3746 * @return A pair (i, j) with i and j uniformly distributed
3747 * over [0, __b0) and [0, __b1), respectively.
3748 *
3749 * Requires: __b0 * __b1 <= __g.max() - __g.min().
3750 *
3751 * Using uniform_int_distribution with a range that is very
3752 * small relative to the range of the generator ends up wasting
3753 * potentially expensively generated randomness, since
3754 * uniform_int_distribution does not store leftover randomness
3755 * between invocations.
3756 *
3757 * If we know we want two integers in ranges that are sufficiently
3758 * small, we can compose the ranges, use a single distribution
3759 * invocation, and significantly reduce the waste.
3760 */
3761 template<typename _IntType, typename _UniformRandomBitGenerator>
3762 pair<_IntType, _IntType>
3763 __gen_two_uniform_ints(_IntType __b0, _IntType __b1,
3764 _UniformRandomBitGenerator&& __g)
3765 {
3766 _IntType __x
3767 = uniform_int_distribution<_IntType>{0, (__b0 * __b1) - 1}(__g);
3768 return std::make_pair(__x / __b1, __x % __b1);
3769 }
3770
3771 /**
3772 * @brief Shuffle the elements of a sequence using a uniform random
3773 * number generator.
3774 * @ingroup mutating_algorithms
3775 * @param __first A forward iterator.
3776 * @param __last A forward iterator.
3777 * @param __g A UniformRandomNumberGenerator (26.5.1.3).
3778 * @return Nothing.
3779 *
3780 * Reorders the elements in the range @p [__first,__last) using @p __g to
3781 * provide random numbers.
3782 */
3783 template<typename _RandomAccessIterator,
3784 typename _UniformRandomNumberGenerator>
3785 void
3786 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3787 _UniformRandomNumberGenerator&& __g)
3788 {
3789 // concept requirements
3790 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3791 _RandomAccessIterator>)
3792 __glibcxx_requires_valid_range(__first, __last);
3793
3794 if (__first == __last)
3795 return;
3796
3797 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3798 _DistanceType;
3799
3800 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3801 typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
3802 typedef typename __distr_type::param_type __p_type;
3803
3804 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3805 _Gen;
3806 typedef typename common_type<typename _Gen::result_type, __ud_type>::type
3807 __uc_type;
3808
3809 const __uc_type __urngrange = __g.max() - __g.min();
3810 const __uc_type __urange = __uc_type(__last - __first);
3811
3812 if (__urngrange / __urange >= __urange)
3813 // I.e. (__urngrange >= __urange * __urange) but without wrap issues.
3814 {
3815 _RandomAccessIterator __i = __first + 1;
3816
3817 // Since we know the range isn't empty, an even number of elements
3818 // means an uneven number of elements /to swap/, in which case we
3819 // do the first one up front:
3820
3821 if ((__urange % 2) == 0)
3822 {
3823 __distr_type __d{0, 1};
3824 std::iter_swap(__i++, __first + __d(__g));
3825 }
3826
3827 // Now we know that __last - __i is even, so we do the rest in pairs,
3828 // using a single distribution invocation to produce swap positions
3829 // for two successive elements at a time:
3830
3831 while (__i != __last)
3832 {
3833 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3834
3835 const pair<__uc_type, __uc_type> __pospos =
3836 __gen_two_uniform_ints(__swap_range, __swap_range + 1, __g);
3837
3838 std::iter_swap(__i++, __first + __pospos.first);
3839 std::iter_swap(__i++, __first + __pospos.second);
3840 }
3841
3842 return;
3843 }
3844
3845 __distr_type __d;
3846
3847 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3848 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3849 }
3850#endif
3851
3852#endif // C++11
3853
3854_GLIBCXX_BEGIN_NAMESPACE_ALGO
3855
3856 /**
3857 * @brief Apply a function to every element of a sequence.
3858 * @ingroup non_mutating_algorithms
3859 * @param __first An input iterator.
3860 * @param __last An input iterator.
3861 * @param __f A unary function object.
3862 * @return @p __f
3863 *
3864 * Applies the function object @p __f to each element in the range
3865 * @p [first,last). @p __f must not modify the order of the sequence.
3866 * If @p __f has a return value it is ignored.
3867 */
3868 template<typename _InputIterator, typename _Function>
3869 _Function
3870 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3871 {
3872 // concept requirements
3873 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3874 __glibcxx_requires_valid_range(__first, __last);
3875 for (; __first != __last; ++__first)
3876 __f(*__first);
3877 return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant.
3878 }
3879
3880#if __cplusplus >= 201703L
3881 /**
3882 * @brief Apply a function to every element of a sequence.
3883 * @ingroup non_mutating_algorithms
3884 * @param __first An input iterator.
3885 * @param __n A value convertible to an integer.
3886 * @param __f A unary function object.
3887 * @return `__first+__n`
3888 *
3889 * Applies the function object `__f` to each element in the range
3890 * `[first, first+n)`. `__f` must not modify the order of the sequence.
3891 * If `__f` has a return value it is ignored.
3892 */
3893 template<typename _InputIterator, typename _Size, typename _Function>
3894 _InputIterator
3895 for_each_n(_InputIterator __first, _Size __n, _Function __f)
3896 {
3897 typename iterator_traits<_InputIterator>::difference_type __n2 = __n;
3898 using _Cat = typename iterator_traits<_InputIterator>::iterator_category;
3899 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3900 {
3901 auto __last = __first + __n2;
3902 std::for_each(__first, __last, std::move(__f));
3903 return __last;
3904 }
3905 else
3906 {
3907 while (__n2-->0)
3908 {
3909 __f(*__first);
3910 ++__first;
3911 }
3912 return __first;
3913 }
3914 }
3915#endif // C++17
3916
3917 /**
3918 * @brief Find the first occurrence of a value in a sequence.
3919 * @ingroup non_mutating_algorithms
3920 * @param __first An input iterator.
3921 * @param __last An input iterator.
3922 * @param __val The value to find.
3923 * @return The first iterator @c i in the range @p [__first,__last)
3924 * such that @c *i == @p __val, or @p __last if no such iterator exists.
3925 */
3926 template<typename _InputIterator, typename _Tp>
3927 inline _InputIterator
3928 find(_InputIterator __first, _InputIterator __last,
3929 const _Tp& __val)
3930 {
3931 // concept requirements
3932 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3933 __glibcxx_function_requires(_EqualOpConcept<
3934 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3935 __glibcxx_requires_valid_range(__first, __last);
3936 return std::__find_if(__first, __last,
3937 __gnu_cxx::__ops::__iter_equals_val(__val));
3938 }
3939
3940 /**
3941 * @brief Find the first element in a sequence for which a
3942 * predicate is true.
3943 * @ingroup non_mutating_algorithms
3944 * @param __first An input iterator.
3945 * @param __last An input iterator.
3946 * @param __pred A predicate.
3947 * @return The first iterator @c i in the range @p [__first,__last)
3948 * such that @p __pred(*i) is true, or @p __last if no such iterator exists.
3949 */
3950 template<typename _InputIterator, typename _Predicate>
3951 inline _InputIterator
3952 find_if(_InputIterator __first, _InputIterator __last,
3953 _Predicate __pred)
3954 {
3955 // concept requirements
3956 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3957 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3958 typename iterator_traits<_InputIterator>::value_type>)
3959 __glibcxx_requires_valid_range(__first, __last);
3960
3961 return std::__find_if(__first, __last,
3962 __gnu_cxx::__ops::__pred_iter(__pred));
3963 }
3964
3965 /**
3966 * @brief Find element from a set in a sequence.
3967 * @ingroup non_mutating_algorithms
3968 * @param __first1 Start of range to search.
3969 * @param __last1 End of range to search.
3970 * @param __first2 Start of match candidates.
3971 * @param __last2 End of match candidates.
3972 * @return The first iterator @c i in the range
3973 * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
3974 * iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
3975 *
3976 * Searches the range @p [__first1,__last1) for an element that is
3977 * equal to some element in the range [__first2,__last2). If
3978 * found, returns an iterator in the range [__first1,__last1),
3979 * otherwise returns @p __last1.
3980 */
3981 template<typename _InputIterator, typename _ForwardIterator>
3982 _InputIterator
3983 find_first_of(_InputIterator __first1, _InputIterator __last1,
3984 _ForwardIterator __first2, _ForwardIterator __last2)
3985 {
3986 // concept requirements
3987 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3988 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3989 __glibcxx_function_requires(_EqualOpConcept<
3990 typename iterator_traits<_InputIterator>::value_type,
3991 typename iterator_traits<_ForwardIterator>::value_type>)
3992 __glibcxx_requires_valid_range(__first1, __last1);
3993 __glibcxx_requires_valid_range(__first2, __last2);
3994
3995 for (; __first1 != __last1; ++__first1)
3996 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3997 if (*__first1 == *__iter)
3998 return __first1;
3999 return __last1;
4000 }
4001
4002 /**
4003 * @brief Find element from a set in a sequence using a predicate.
4004 * @ingroup non_mutating_algorithms
4005 * @param __first1 Start of range to search.
4006 * @param __last1 End of range to search.
4007 * @param __first2 Start of match candidates.
4008 * @param __last2 End of match candidates.
4009 * @param __comp Predicate to use.
4010 * @return The first iterator @c i in the range
4011 * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
4012 * and i2 is an iterator in [__first2,__last2), or @p __last1 if no
4013 * such iterator exists.
4014 *
4015
4016 * Searches the range @p [__first1,__last1) for an element that is
4017 * equal to some element in the range [__first2,__last2). If
4018 * found, returns an iterator in the range [__first1,__last1),
4019 * otherwise returns @p __last1.
4020 */
4021 template<typename _InputIterator, typename _ForwardIterator,
4022 typename _BinaryPredicate>
4023 _InputIterator
4024 find_first_of(_InputIterator __first1, _InputIterator __last1,
4025 _ForwardIterator __first2, _ForwardIterator __last2,
4026 _BinaryPredicate __comp)
4027 {
4028 // concept requirements
4029 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4030 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4031 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4032 typename iterator_traits<_InputIterator>::value_type,
4033 typename iterator_traits<_ForwardIterator>::value_type>)
4034 __glibcxx_requires_valid_range(__first1, __last1);
4035 __glibcxx_requires_valid_range(__first2, __last2);
4036
4037 for (; __first1 != __last1; ++__first1)
4038 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4039 if (__comp(*__first1, *__iter))
4040 return __first1;
4041 return __last1;
4042 }
4043
4044 /**
4045 * @brief Find two adjacent values in a sequence that are equal.
4046 * @ingroup non_mutating_algorithms
4047 * @param __first A forward iterator.
4048 * @param __last A forward iterator.
4049 * @return The first iterator @c i such that @c i and @c i+1 are both
4050 * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
4051 * or @p __last if no such iterator exists.
4052 */
4053 template<typename _ForwardIterator>
4054 inline _ForwardIterator
4055 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4056 {
4057 // concept requirements
4058 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4059 __glibcxx_function_requires(_EqualityComparableConcept<
4060 typename iterator_traits<_ForwardIterator>::value_type>)
4061 __glibcxx_requires_valid_range(__first, __last);
4062
4063 return std::__adjacent_find(__first, __last,
4064 __gnu_cxx::__ops::__iter_equal_to_iter());
4065 }
4066
4067 /**
4068 * @brief Find two adjacent values in a sequence using a predicate.
4069 * @ingroup non_mutating_algorithms
4070 * @param __first A forward iterator.
4071 * @param __last A forward iterator.
4072 * @param __binary_pred A binary predicate.
4073 * @return The first iterator @c i such that @c i and @c i+1 are both
4074 * valid iterators in @p [__first,__last) and such that
4075 * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
4076 * exists.
4077 */
4078 template<typename _ForwardIterator, typename _BinaryPredicate>
4079 inline _ForwardIterator
4080 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4081 _BinaryPredicate __binary_pred)
4082 {
4083 // concept requirements
4084 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4085 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4086 typename iterator_traits<_ForwardIterator>::value_type,
4087 typename iterator_traits<_ForwardIterator>::value_type>)
4088 __glibcxx_requires_valid_range(__first, __last);
4089
4090 return std::__adjacent_find(__first, __last,
4091 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4092 }
4093
4094 /**
4095 * @brief Count the number of copies of a value in a sequence.
4096 * @ingroup non_mutating_algorithms
4097 * @param __first An input iterator.
4098 * @param __last An input iterator.
4099 * @param __value The value to be counted.
4100 * @return The number of iterators @c i in the range @p [__first,__last)
4101 * for which @c *i == @p __value
4102 */
4103 template<typename _InputIterator, typename _Tp>
4104 inline typename iterator_traits<_InputIterator>::difference_type
4105 count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4106 {
4107 // concept requirements
4108 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4109 __glibcxx_function_requires(_EqualOpConcept<
4110 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4111 __glibcxx_requires_valid_range(__first, __last);
4112
4113 return std::__count_if(__first, __last,
4114 __gnu_cxx::__ops::__iter_equals_val(__value));
4115 }
4116
4117 /**
4118 * @brief Count the elements of a sequence for which a predicate is true.
4119 * @ingroup non_mutating_algorithms
4120 * @param __first An input iterator.
4121 * @param __last An input iterator.
4122 * @param __pred A predicate.
4123 * @return The number of iterators @c i in the range @p [__first,__last)
4124 * for which @p __pred(*i) is true.
4125 */
4126 template<typename _InputIterator, typename _Predicate>
4127 inline typename iterator_traits<_InputIterator>::difference_type
4128 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4129 {
4130 // concept requirements
4131 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4132 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4133 typename iterator_traits<_InputIterator>::value_type>)
4134 __glibcxx_requires_valid_range(__first, __last);
4135
4136 return std::__count_if(__first, __last,
4137 __gnu_cxx::__ops::__pred_iter(__pred));
4138 }
4139
4140 /**
4141 * @brief Search a sequence for a matching sub-sequence.
4142 * @ingroup non_mutating_algorithms
4143 * @param __first1 A forward iterator.
4144 * @param __last1 A forward iterator.
4145 * @param __first2 A forward iterator.
4146 * @param __last2 A forward iterator.
4147 * @return The first iterator @c i in the range @p
4148 * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
4149 * *(__first2+N) for each @c N in the range @p
4150 * [0,__last2-__first2), or @p __last1 if no such iterator exists.
4151 *
4152 * Searches the range @p [__first1,__last1) for a sub-sequence that
4153 * compares equal value-by-value with the sequence given by @p
4154 * [__first2,__last2) and returns an iterator to the first element
4155 * of the sub-sequence, or @p __last1 if the sub-sequence is not
4156 * found.
4157 *
4158 * Because the sub-sequence must lie completely within the range @p
4159 * [__first1,__last1) it must start at a position less than @p
4160 * __last1-(__last2-__first2) where @p __last2-__first2 is the
4161 * length of the sub-sequence.
4162 *
4163 * This means that the returned iterator @c i will be in the range
4164 * @p [__first1,__last1-(__last2-__first2))
4165 */
4166 template<typename _ForwardIterator1, typename _ForwardIterator2>
4167 inline _ForwardIterator1
4168 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4169 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4170 {
4171 // concept requirements
4172 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4173 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4174 __glibcxx_function_requires(_EqualOpConcept<
4175 typename iterator_traits<_ForwardIterator1>::value_type,
4176 typename iterator_traits<_ForwardIterator2>::value_type>)
4177 __glibcxx_requires_valid_range(__first1, __last1);
4178 __glibcxx_requires_valid_range(__first2, __last2);
4179
4180 return std::__search(__first1, __last1, __first2, __last2,
4181 __gnu_cxx::__ops::__iter_equal_to_iter());
4182 }
4183
4184 /**
4185 * @brief Search a sequence for a matching sub-sequence using a predicate.
4186 * @ingroup non_mutating_algorithms
4187 * @param __first1 A forward iterator.
4188 * @param __last1 A forward iterator.
4189 * @param __first2 A forward iterator.
4190 * @param __last2 A forward iterator.
4191 * @param __predicate A binary predicate.
4192 * @return The first iterator @c i in the range
4193 * @p [__first1,__last1-(__last2-__first2)) such that
4194 * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
4195 * @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
4196 *
4197 * Searches the range @p [__first1,__last1) for a sub-sequence that
4198 * compares equal value-by-value with the sequence given by @p
4199 * [__first2,__last2), using @p __predicate to determine equality,
4200 * and returns an iterator to the first element of the
4201 * sub-sequence, or @p __last1 if no such iterator exists.
4202 *
4203 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4204 */
4205 template<typename _ForwardIterator1, typename _ForwardIterator2,
4206 typename _BinaryPredicate>
4207 inline _ForwardIterator1
4208 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4209 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4210 _BinaryPredicate __predicate)
4211 {
4212 // concept requirements
4213 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4214 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4215 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4216 typename iterator_traits<_ForwardIterator1>::value_type,
4217 typename iterator_traits<_ForwardIterator2>::value_type>)
4218 __glibcxx_requires_valid_range(__first1, __last1);
4219 __glibcxx_requires_valid_range(__first2, __last2);
4220
4221 return std::__search(__first1, __last1, __first2, __last2,
4222 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4223 }
4224
4225 /**
4226 * @brief Search a sequence for a number of consecutive values.
4227 * @ingroup non_mutating_algorithms
4228 * @param __first A forward iterator.
4229 * @param __last A forward iterator.
4230 * @param __count The number of consecutive values.
4231 * @param __val The value to find.
4232 * @return The first iterator @c i in the range @p
4233 * [__first,__last-__count) such that @c *(i+N) == @p __val for
4234 * each @c N in the range @p [0,__count), or @p __last if no such
4235 * iterator exists.
4236 *
4237 * Searches the range @p [__first,__last) for @p count consecutive elements
4238 * equal to @p __val.
4239 */
4240 template<typename _ForwardIterator, typename _Integer, typename _Tp>
4241 inline _ForwardIterator
4242 search_n(_ForwardIterator __first, _ForwardIterator __last,
4243 _Integer __count, const _Tp& __val)
4244 {
4245 // concept requirements
4246 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4247 __glibcxx_function_requires(_EqualOpConcept<
4248 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4249 __glibcxx_requires_valid_range(__first, __last);
4250
4251 return std::__search_n(__first, __last, __count,
4252 __gnu_cxx::__ops::__iter_equals_val(__val));
4253 }
4254
4255
4256 /**
4257 * @brief Search a sequence for a number of consecutive values using a
4258 * predicate.
4259 * @ingroup non_mutating_algorithms
4260 * @param __first A forward iterator.
4261 * @param __last A forward iterator.
4262 * @param __count The number of consecutive values.
4263 * @param __val The value to find.
4264 * @param __binary_pred A binary predicate.
4265 * @return The first iterator @c i in the range @p
4266 * [__first,__last-__count) such that @p
4267 * __binary_pred(*(i+N),__val) is true for each @c N in the range
4268 * @p [0,__count), or @p __last if no such iterator exists.
4269 *
4270 * Searches the range @p [__first,__last) for @p __count
4271 * consecutive elements for which the predicate returns true.
4272 */
4273 template<typename _ForwardIterator, typename _Integer, typename _Tp,
4274 typename _BinaryPredicate>
4275 inline _ForwardIterator
4276 search_n(_ForwardIterator __first, _ForwardIterator __last,
4277 _Integer __count, const _Tp& __val,
4278 _BinaryPredicate __binary_pred)
4279 {
4280 // concept requirements
4281 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4282 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4283 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4284 __glibcxx_requires_valid_range(__first, __last);
4285
4286 return std::__search_n(__first, __last, __count,
4287 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4288 }
4289
4290#if __cplusplus > 201402L
4291 /** @brief Search a sequence using a Searcher object.
4292 *
4293 * @param __first A forward iterator.
4294 * @param __last A forward iterator.
4295 * @param __searcher A callable object.
4296 * @return @p __searcher(__first,__last).first
4297 */
4298 template<typename _ForwardIterator, typename _Searcher>
4299 inline _ForwardIterator
4300 search(_ForwardIterator __first, _ForwardIterator __last,
4301 const _Searcher& __searcher)
4302 { return __searcher(__first, __last).first; }
4303#endif
4304
4305 /**
4306 * @brief Perform an operation on a sequence.
4307 * @ingroup mutating_algorithms
4308 * @param __first An input iterator.
4309 * @param __last An input iterator.
4310 * @param __result An output iterator.
4311 * @param __unary_op A unary operator.
4312 * @return An output iterator equal to @p __result+(__last-__first).
4313 *
4314 * Applies the operator to each element in the input range and assigns
4315 * the results to successive elements of the output sequence.
4316 * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
4317 * range @p [0,__last-__first).
4318 *
4319 * @p unary_op must not alter its argument.
4320 */
4321 template<typename _InputIterator, typename _OutputIterator,
4322 typename _UnaryOperation>
4323 _OutputIterator
4324 transform(_InputIterator __first, _InputIterator __last,
4325 _OutputIterator __result, _UnaryOperation __unary_op)
4326 {
4327 // concept requirements
4328 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4329 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4330 // "the type returned by a _UnaryOperation"
4331 __typeof__(__unary_op(*__first))>)
4332 __glibcxx_requires_valid_range(__first, __last);
4333
4334 for (; __first != __last; ++__first, (void)++__result)
4335 *__result = __unary_op(*__first);
4336 return __result;
4337 }
4338
4339 /**
4340 * @brief Perform an operation on corresponding elements of two sequences.
4341 * @ingroup mutating_algorithms
4342 * @param __first1 An input iterator.
4343 * @param __last1 An input iterator.
4344 * @param __first2 An input iterator.
4345 * @param __result An output iterator.
4346 * @param __binary_op A binary operator.
4347 * @return An output iterator equal to @p result+(last-first).
4348 *
4349 * Applies the operator to the corresponding elements in the two
4350 * input ranges and assigns the results to successive elements of the
4351 * output sequence.
4352 * Evaluates @p
4353 * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
4354 * @c N in the range @p [0,__last1-__first1).
4355 *
4356 * @p binary_op must not alter either of its arguments.
4357 */
4358 template<typename _InputIterator1, typename _InputIterator2,
4359 typename _OutputIterator, typename _BinaryOperation>
4360 _OutputIterator
4361 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4362 _InputIterator2 __first2, _OutputIterator __result,
4363 _BinaryOperation __binary_op)
4364 {
4365 // concept requirements
4366 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4367 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4368 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4369 // "the type returned by a _BinaryOperation"
4370 __typeof__(__binary_op(*__first1,*__first2))>)
4371 __glibcxx_requires_valid_range(__first1, __last1);
4372
4373 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4374 *__result = __binary_op(*__first1, *__first2);
4375 return __result;
4376 }
4377
4378 /**
4379 * @brief Replace each occurrence of one value in a sequence with another
4380 * value.
4381 * @ingroup mutating_algorithms
4382 * @param __first A forward iterator.
4383 * @param __last A forward iterator.
4384 * @param __old_value The value to be replaced.
4385 * @param __new_value The replacement value.
4386 * @return replace() returns no value.
4387 *
4388 * For each iterator @c i in the range @p [__first,__last) if @c *i ==
4389 * @p __old_value then the assignment @c *i = @p __new_value is performed.
4390 */
4391 template<typename _ForwardIterator, typename _Tp>
4392 void
4393 replace(_ForwardIterator __first, _ForwardIterator __last,
4394 const _Tp& __old_value, const _Tp& __new_value)
4395 {
4396 // concept requirements
4397 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4398 _ForwardIterator>)
4399 __glibcxx_function_requires(_EqualOpConcept<
4400 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4401 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4402 typename iterator_traits<_ForwardIterator>::value_type>)
4403 __glibcxx_requires_valid_range(__first, __last);
4404
4405 for (; __first != __last; ++__first)
4406 if (*__first == __old_value)
4407 *__first = __new_value;
4408 }
4409
4410 /**
4411 * @brief Replace each value in a sequence for which a predicate returns
4412 * true with another value.
4413 * @ingroup mutating_algorithms
4414 * @param __first A forward iterator.
4415 * @param __last A forward iterator.
4416 * @param __pred A predicate.
4417 * @param __new_value The replacement value.
4418 * @return replace_if() returns no value.
4419 *
4420 * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
4421 * is true then the assignment @c *i = @p __new_value is performed.
4422 */
4423 template<typename _ForwardIterator, typename _Predicate, typename _Tp>
4424 void
4425 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4426 _Predicate __pred, const _Tp& __new_value)
4427 {
4428 // concept requirements
4429 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4430 _ForwardIterator>)
4431 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4432 typename iterator_traits<_ForwardIterator>::value_type>)
4433 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4434 typename iterator_traits<_ForwardIterator>::value_type>)
4435 __glibcxx_requires_valid_range(__first, __last);
4436
4437 for (; __first != __last; ++__first)
4438 if (__pred(*__first))
4439 *__first = __new_value;
4440 }
4441
4442 /**
4443 * @brief Assign the result of a function object to each value in a
4444 * sequence.
4445 * @ingroup mutating_algorithms
4446 * @param __first A forward iterator.
4447 * @param __last A forward iterator.
4448 * @param __gen A function object taking no arguments and returning
4449 * std::iterator_traits<_ForwardIterator>::value_type
4450 * @return generate() returns no value.
4451 *
4452 * Performs the assignment @c *i = @p __gen() for each @c i in the range
4453 * @p [__first,__last).
4454 */
4455 template<typename _ForwardIterator, typename _Generator>
4456 void
4457 generate(_ForwardIterator __first, _ForwardIterator __last,
4458 _Generator __gen)
4459 {
4460 // concept requirements
4461 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4462 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4463 typename iterator_traits<_ForwardIterator>::value_type>)
4464 __glibcxx_requires_valid_range(__first, __last);
4465
4466 for (; __first != __last; ++__first)
4467 *__first = __gen();
4468 }
4469
4470 /**
4471 * @brief Assign the result of a function object to each value in a
4472 * sequence.
4473 * @ingroup mutating_algorithms
4474 * @param __first A forward iterator.
4475 * @param __n The length of the sequence.
4476 * @param __gen A function object taking no arguments and returning
4477 * std::iterator_traits<_ForwardIterator>::value_type
4478 * @return The end of the sequence, @p __first+__n
4479 *
4480 * Performs the assignment @c *i = @p __gen() for each @c i in the range
4481 * @p [__first,__first+__n).
4482 *
4483 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4484 * DR 865. More algorithms that throw away information
4485 */
4486 template<typename _OutputIterator, typename _Size, typename _Generator>
4487 _OutputIterator
4488 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4489 {
4490 // concept requirements
4491 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4492 // "the type returned by a _Generator"
4493 __typeof__(__gen())>)
4494
4495 for (__decltype(__n + 0) __niter = __n;
4496 __niter > 0; --__niter, (void) ++__first)
4497 *__first = __gen();
4498 return __first;
4499 }
4500
4501 /**
4502 * @brief Copy a sequence, removing consecutive duplicate values.
4503 * @ingroup mutating_algorithms
4504 * @param __first An input iterator.
4505 * @param __last An input iterator.
4506 * @param __result An output iterator.
4507 * @return An iterator designating the end of the resulting sequence.
4508 *
4509 * Copies each element in the range @p [__first,__last) to the range
4510 * beginning at @p __result, except that only the first element is copied
4511 * from groups of consecutive elements that compare equal.
4512 * unique_copy() is stable, so the relative order of elements that are
4513 * copied is unchanged.
4514 *
4515 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4516 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4517 *
4518 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4519 * DR 538. 241 again: Does unique_copy() require CopyConstructible and
4520 * Assignable?
4521 */
4522 template<typename _InputIterator, typename _OutputIterator>
4523 inline _OutputIterator
4524 unique_copy(_InputIterator __first, _InputIterator __last,
4525 _OutputIterator __result)
4526 {
4527 // concept requirements
4528 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4529 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4530 typename iterator_traits<_InputIterator>::value_type>)
4531 __glibcxx_function_requires(_EqualityComparableConcept<
4532 typename iterator_traits<_InputIterator>::value_type>)
4533 __glibcxx_requires_valid_range(__first, __last);
4534
4535 if (__first == __last)
4536 return __result;
4537 return std::__unique_copy(__first, __last, __result,
4538 __gnu_cxx::__ops::__iter_equal_to_iter(),
4539 std::__iterator_category(__first),
4540 std::__iterator_category(__result));
4541 }
4542
4543 /**
4544 * @brief Copy a sequence, removing consecutive values using a predicate.
4545 * @ingroup mutating_algorithms
4546 * @param __first An input iterator.
4547 * @param __last An input iterator.
4548 * @param __result An output iterator.
4549 * @param __binary_pred A binary predicate.
4550 * @return An iterator designating the end of the resulting sequence.
4551 *
4552 * Copies each element in the range @p [__first,__last) to the range
4553 * beginning at @p __result, except that only the first element is copied
4554 * from groups of consecutive elements for which @p __binary_pred returns
4555 * true.
4556 * unique_copy() is stable, so the relative order of elements that are
4557 * copied is unchanged.
4558 *
4559 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4560 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4561 */
4562 template<typename _InputIterator, typename _OutputIterator,
4563 typename _BinaryPredicate>
4564 inline _OutputIterator
4565 unique_copy(_InputIterator __first, _InputIterator __last,
4566 _OutputIterator __result,
4567 _BinaryPredicate __binary_pred)
4568 {
4569 // concept requirements -- predicates checked later
4570 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4571 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4572 typename iterator_traits<_InputIterator>::value_type>)
4573 __glibcxx_requires_valid_range(__first, __last);
4574
4575 if (__first == __last)
4576 return __result;
4577 return std::__unique_copy(__first, __last, __result,
4578 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4579 std::__iterator_category(__first),
4580 std::__iterator_category(__result));
4581 }
4582
4583#if _GLIBCXX_HOSTED
4584 /**
4585 * @brief Randomly shuffle the elements of a sequence.
4586 * @ingroup mutating_algorithms
4587 * @param __first A forward iterator.
4588 * @param __last A forward iterator.
4589 * @return Nothing.
4590 *
4591 * Reorder the elements in the range @p [__first,__last) using a random
4592 * distribution, so that every possible ordering of the sequence is
4593 * equally likely.
4594 */
4595 template<typename _RandomAccessIterator>
4596 inline void
4597 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4598 {
4599 // concept requirements
4600 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4601 _RandomAccessIterator>)
4602 __glibcxx_requires_valid_range(__first, __last);
4603
4604 if (__first != __last)
4605 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4606 {
4607 // XXX rand() % N is not uniformly distributed
4608 _RandomAccessIterator __j = __first
4609 + std::rand() % ((__i - __first) + 1);
4610 if (__i != __j)
4611 std::iter_swap(__i, __j);
4612 }
4613 }
4614#endif
4615
4616 /**
4617 * @brief Shuffle the elements of a sequence using a random number
4618 * generator.
4619 * @ingroup mutating_algorithms
4620 * @param __first A forward iterator.
4621 * @param __last A forward iterator.
4622 * @param __rand The RNG functor or function.
4623 * @return Nothing.
4624 *
4625 * Reorders the elements in the range @p [__first,__last) using @p __rand to
4626 * provide a random distribution. Calling @p __rand(N) for a positive
4627 * integer @p N should return a randomly chosen integer from the
4628 * range [0,N).
4629 */
4630 template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
4631 void
4632 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4633#if __cplusplus >= 201103L
4634 _RandomNumberGenerator&& __rand)
4635#else
4636 _RandomNumberGenerator& __rand)
4637#endif
4638 {
4639 // concept requirements
4640 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4641 _RandomAccessIterator>)
4642 __glibcxx_requires_valid_range(__first, __last);
4643
4644 if (__first == __last)
4645 return;
4646 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4647 {
4648 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4649 if (__i != __j)
4650 std::iter_swap(__i, __j);
4651 }
4652 }
4653
4654
4655 /**
4656 * @brief Move elements for which a predicate is true to the beginning
4657 * of a sequence.
4658 * @ingroup mutating_algorithms
4659 * @param __first A forward iterator.
4660 * @param __last A forward iterator.
4661 * @param __pred A predicate functor.
4662 * @return An iterator @p middle such that @p __pred(i) is true for each
4663 * iterator @p i in the range @p [__first,middle) and false for each @p i
4664 * in the range @p [middle,__last).
4665 *
4666 * @p __pred must not modify its operand. @p partition() does not preserve
4667 * the relative ordering of elements in each group, use
4668 * @p stable_partition() if this is needed.
4669 */
4670 template<typename _ForwardIterator, typename _Predicate>
4671 inline _ForwardIterator
4672 partition(_ForwardIterator __first, _ForwardIterator __last,
4673 _Predicate __pred)
4674 {
4675 // concept requirements
4676 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4677 _ForwardIterator>)
4678 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4679 typename iterator_traits<_ForwardIterator>::value_type>)
4680 __glibcxx_requires_valid_range(__first, __last);
4681
4682 return std::__partition(__first, __last, __pred,
4683 std::__iterator_category(__first));
4684 }
4685
4686
4687 /**
4688 * @brief Sort the smallest elements of a sequence.
4689 * @ingroup sorting_algorithms
4690 * @param __first An iterator.
4691 * @param __middle Another iterator.
4692 * @param __last Another iterator.
4693 * @return Nothing.
4694 *
4695 * Sorts the smallest @p (__middle-__first) elements in the range
4696 * @p [first,last) and moves them to the range @p [__first,__middle). The
4697 * order of the remaining elements in the range @p [__middle,__last) is
4698 * undefined.
4699 * After the sort if @e i and @e j are iterators in the range
4700 * @p [__first,__middle) such that i precedes j and @e k is an iterator in
4701 * the range @p [__middle,__last) then *j<*i and *k<*i are both false.
4702 */
4703 template<typename _RandomAccessIterator>
4704 inline void
4705 partial_sort(_RandomAccessIterator __first,
4706 _RandomAccessIterator __middle,
4707 _RandomAccessIterator __last)
4708 {
4709 // concept requirements
4710 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4711 _RandomAccessIterator>)
4712 __glibcxx_function_requires(_LessThanComparableConcept<
4713 typename iterator_traits<_RandomAccessIterator>::value_type>)
4714 __glibcxx_requires_valid_range(__first, __middle);
4715 __glibcxx_requires_valid_range(__middle, __last);
4716 __glibcxx_requires_irreflexive(__first, __last);
4717
4718 std::__partial_sort(__first, __middle, __last,
4719 __gnu_cxx::__ops::__iter_less_iter());
4720 }
4721
4722 /**
4723 * @brief Sort the smallest elements of a sequence using a predicate
4724 * for comparison.
4725 * @ingroup sorting_algorithms
4726 * @param __first An iterator.
4727 * @param __middle Another iterator.
4728 * @param __last Another iterator.
4729 * @param __comp A comparison functor.
4730 * @return Nothing.
4731 *
4732 * Sorts the smallest @p (__middle-__first) elements in the range
4733 * @p [__first,__last) and moves them to the range @p [__first,__middle). The
4734 * order of the remaining elements in the range @p [__middle,__last) is
4735 * undefined.
4736 * After the sort if @e i and @e j are iterators in the range
4737 * @p [__first,__middle) such that i precedes j and @e k is an iterator in
4738 * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
4739 * are both false.
4740 */
4741 template<typename _RandomAccessIterator, typename _Compare>
4742 inline void
4743 partial_sort(_RandomAccessIterator __first,
4744 _RandomAccessIterator __middle,
4745 _RandomAccessIterator __last,
4746 _Compare __comp)
4747 {
4748 // concept requirements
4749 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4750 _RandomAccessIterator>)
4751 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4752 typename iterator_traits<_RandomAccessIterator>::value_type,
4753 typename iterator_traits<_RandomAccessIterator>::value_type>)
4754 __glibcxx_requires_valid_range(__first, __middle);
4755 __glibcxx_requires_valid_range(__middle, __last);
4756 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4757
4758 std::__partial_sort(__first, __middle, __last,
4759 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4760 }
4761
4762 /**
4763 * @brief Sort a sequence just enough to find a particular position.
4764 * @ingroup sorting_algorithms
4765 * @param __first An iterator.
4766 * @param __nth Another iterator.
4767 * @param __last Another iterator.
4768 * @return Nothing.
4769 *
4770 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
4771 * is the same element that would have been in that position had the
4772 * whole sequence been sorted. The elements either side of @p *__nth are
4773 * not completely sorted, but for any iterator @e i in the range
4774 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
4775 * holds that *j < *i is false.
4776 */
4777 template<typename _RandomAccessIterator>
4778 inline void
4779 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4780 _RandomAccessIterator __last)
4781 {
4782 // concept requirements
4783 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4784 _RandomAccessIterator>)
4785 __glibcxx_function_requires(_LessThanComparableConcept<
4786 typename iterator_traits<_RandomAccessIterator>::value_type>)
4787 __glibcxx_requires_valid_range(__first, __nth);
4788 __glibcxx_requires_valid_range(__nth, __last);
4789 __glibcxx_requires_irreflexive(__first, __last);
4790
4791 if (__first == __last || __nth == __last)
4792 return;
4793
4794 std::__introselect(__first, __nth, __last,
4795 std::__lg(__last - __first) * 2,
4796 __gnu_cxx::__ops::__iter_less_iter());
4797 }
4798
4799 /**
4800 * @brief Sort a sequence just enough to find a particular position
4801 * using a predicate for comparison.
4802 * @ingroup sorting_algorithms
4803 * @param __first An iterator.
4804 * @param __nth Another iterator.
4805 * @param __last Another iterator.
4806 * @param __comp A comparison functor.
4807 * @return Nothing.
4808 *
4809 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
4810 * is the same element that would have been in that position had the
4811 * whole sequence been sorted. The elements either side of @p *__nth are
4812 * not completely sorted, but for any iterator @e i in the range
4813 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
4814 * holds that @p __comp(*j,*i) is false.
4815 */
4816 template<typename _RandomAccessIterator, typename _Compare>
4817 inline void
4818 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4819 _RandomAccessIterator __last, _Compare __comp)
4820 {
4821 // concept requirements
4822 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4823 _RandomAccessIterator>)
4824 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4825 typename iterator_traits<_RandomAccessIterator>::value_type,
4826 typename iterator_traits<_RandomAccessIterator>::value_type>)
4827 __glibcxx_requires_valid_range(__first, __nth);
4828 __glibcxx_requires_valid_range(__nth, __last);
4829 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4830
4831 if (__first == __last || __nth == __last)
4832 return;
4833
4834 std::__introselect(__first, __nth, __last,
4835 std::__lg(__last - __first) * 2,
4836 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4837 }
4838
4839 /**
4840 * @brief Sort the elements of a sequence.
4841 * @ingroup sorting_algorithms
4842 * @param __first An iterator.
4843 * @param __last Another iterator.
4844 * @return Nothing.
4845 *
4846 * Sorts the elements in the range @p [__first,__last) in ascending order,
4847 * such that for each iterator @e i in the range @p [__first,__last-1),
4848 * *(i+1)<*i is false.
4849 *
4850 * The relative ordering of equivalent elements is not preserved, use
4851 * @p stable_sort() if this is needed.
4852 */
4853 template<typename _RandomAccessIterator>
4854 inline void
4855 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4856 {
4857 // concept requirements
4858 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4859 _RandomAccessIterator>)
4860 __glibcxx_function_requires(_LessThanComparableConcept<
4861 typename iterator_traits<_RandomAccessIterator>::value_type>)
4862 __glibcxx_requires_valid_range(__first, __last);
4863 __glibcxx_requires_irreflexive(__first, __last);
4864
4865 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4866 }
4867
4868 /**
4869 * @brief Sort the elements of a sequence using a predicate for comparison.
4870 * @ingroup sorting_algorithms
4871 * @param __first An iterator.
4872 * @param __last Another iterator.
4873 * @param __comp A comparison functor.
4874 * @return Nothing.
4875 *
4876 * Sorts the elements in the range @p [__first,__last) in ascending order,
4877 * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
4878 * range @p [__first,__last-1).
4879 *
4880 * The relative ordering of equivalent elements is not preserved, use
4881 * @p stable_sort() if this is needed.
4882 */
4883 template<typename _RandomAccessIterator, typename _Compare>
4884 inline void
4885 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4886 _Compare __comp)
4887 {
4888 // concept requirements
4889 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4890 _RandomAccessIterator>)
4891 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4892 typename iterator_traits<_RandomAccessIterator>::value_type,
4893 typename iterator_traits<_RandomAccessIterator>::value_type>)
4894 __glibcxx_requires_valid_range(__first, __last);
4895 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4896
4897 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4898 }
4899
4900 template<typename _InputIterator1, typename _InputIterator2,
4901 typename _OutputIterator, typename _Compare>
4902 _OutputIterator
4903 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4904 _InputIterator2 __first2, _InputIterator2 __last2,
4905 _OutputIterator __result, _Compare __comp)
4906 {
4907 while (__first1 != __last1 && __first2 != __last2)
4908 {
4909 if (__comp(__first2, __first1))
4910 {
4911 *__result = *__first2;
4912 ++__first2;
4913 }
4914 else
4915 {
4916 *__result = *__first1;
4917 ++__first1;
4918 }
4919 ++__result;
4920 }
4921 return std::copy(__first2, __last2,
4922 std::copy(__first1, __last1, __result));
4923 }
4924
4925 /**
4926 * @brief Merges two sorted ranges.
4927 * @ingroup sorting_algorithms
4928 * @param __first1 An iterator.
4929 * @param __first2 Another iterator.
4930 * @param __last1 Another iterator.
4931 * @param __last2 Another iterator.
4932 * @param __result An iterator pointing to the end of the merged range.
4933 * @return An iterator pointing to the first element <em>not less
4934 * than</em> @e val.
4935 *
4936 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4937 * the sorted range @p [__result, __result + (__last1-__first1) +
4938 * (__last2-__first2)). Both input ranges must be sorted, and the
4939 * output range must not overlap with either of the input ranges.
4940 * The sort is @e stable, that is, for equivalent elements in the
4941 * two ranges, elements from the first range will always come
4942 * before elements from the second.
4943 */
4944 template<typename _InputIterator1, typename _InputIterator2,
4945 typename _OutputIterator>
4946 inline _OutputIterator
4947 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4948 _InputIterator2 __first2, _InputIterator2 __last2,
4949 _OutputIterator __result)
4950 {
4951 // concept requirements
4952 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4953 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4954 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4955 typename iterator_traits<_InputIterator1>::value_type>)
4956 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4957 typename iterator_traits<_InputIterator2>::value_type>)
4958 __glibcxx_function_requires(_LessThanOpConcept<
4959 typename iterator_traits<_InputIterator2>::value_type,
4960 typename iterator_traits<_InputIterator1>::value_type>)
4961 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4962 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4963 __glibcxx_requires_irreflexive2(__first1, __last1);
4964 __glibcxx_requires_irreflexive2(__first2, __last2);
4965
4966 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4967 __first2, __last2, __result,
4968 __gnu_cxx::__ops::__iter_less_iter());
4969 }
4970
4971 /**
4972 * @brief Merges two sorted ranges.
4973 * @ingroup sorting_algorithms
4974 * @param __first1 An iterator.
4975 * @param __first2 Another iterator.
4976 * @param __last1 Another iterator.
4977 * @param __last2 Another iterator.
4978 * @param __result An iterator pointing to the end of the merged range.
4979 * @param __comp A functor to use for comparisons.
4980 * @return An iterator pointing to the first element "not less
4981 * than" @e val.
4982 *
4983 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4984 * the sorted range @p [__result, __result + (__last1-__first1) +
4985 * (__last2-__first2)). Both input ranges must be sorted, and the
4986 * output range must not overlap with either of the input ranges.
4987 * The sort is @e stable, that is, for equivalent elements in the
4988 * two ranges, elements from the first range will always come
4989 * before elements from the second.
4990 *
4991 * The comparison function should have the same effects on ordering as
4992 * the function used for the initial sort.
4993 */
4994 template<typename _InputIterator1, typename _InputIterator2,
4995 typename _OutputIterator, typename _Compare>
4996 inline _OutputIterator
4997 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4998 _InputIterator2 __first2, _InputIterator2 __last2,
4999 _OutputIterator __result, _Compare __comp)
5000 {
5001 // concept requirements
5002 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5003 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5004 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5005 typename iterator_traits<_InputIterator1>::value_type>)
5006 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5007 typename iterator_traits<_InputIterator2>::value_type>)
5008 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5009 typename iterator_traits<_InputIterator2>::value_type,
5010 typename iterator_traits<_InputIterator1>::value_type>)
5011 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5012 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5013 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5014 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5015
5016 return _GLIBCXX_STD_A::__merge(__first1, __last1,
5017 __first2, __last2, __result,
5018 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5019 }
5020
5021 template<typename _RandomAccessIterator, typename _Compare>
5022 inline void
5023 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5024 _Compare __comp)
5025 {
5026 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5027 _ValueType;
5028 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5029 _DistanceType;
5030
5031 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
5032 _TmpBuf __buf(__first, std::distance(__first, __last));
5033
5034 if (__buf.begin() == 0)
5035 std::__inplace_stable_sort(__first, __last, __comp);
5036 else
5037 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5038 _DistanceType(__buf.size()), __comp);
5039 }
5040
5041 /**
5042 * @brief Sort the elements of a sequence, preserving the relative order
5043 * of equivalent elements.
5044 * @ingroup sorting_algorithms
5045 * @param __first An iterator.
5046 * @param __last Another iterator.
5047 * @return Nothing.
5048 *
5049 * Sorts the elements in the range @p [__first,__last) in ascending order,
5050 * such that for each iterator @p i in the range @p [__first,__last-1),
5051 * @p *(i+1)<*i is false.
5052 *
5053 * The relative ordering of equivalent elements is preserved, so any two
5054 * elements @p x and @p y in the range @p [__first,__last) such that
5055 * @p x<y is false and @p y<x is false will have the same relative
5056 * ordering after calling @p stable_sort().
5057 */
5058 template<typename _RandomAccessIterator>
5059 inline void
5060 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5061 {
5062 // concept requirements
5063 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5064 _RandomAccessIterator>)
5065 __glibcxx_function_requires(_LessThanComparableConcept<
5066 typename iterator_traits<_RandomAccessIterator>::value_type>)
5067 __glibcxx_requires_valid_range(__first, __last);
5068 __glibcxx_requires_irreflexive(__first, __last);
5069
5070 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5071 __gnu_cxx::__ops::__iter_less_iter());
5072 }
5073
5074 /**
5075 * @brief Sort the elements of a sequence using a predicate for comparison,
5076 * preserving the relative order of equivalent elements.
5077 * @ingroup sorting_algorithms
5078 * @param __first An iterator.
5079 * @param __last Another iterator.
5080 * @param __comp A comparison functor.
5081 * @return Nothing.
5082 *
5083 * Sorts the elements in the range @p [__first,__last) in ascending order,
5084 * such that for each iterator @p i in the range @p [__first,__last-1),
5085 * @p __comp(*(i+1),*i) is false.
5086 *
5087 * The relative ordering of equivalent elements is preserved, so any two
5088 * elements @p x and @p y in the range @p [__first,__last) such that
5089 * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
5090 * relative ordering after calling @p stable_sort().
5091 */
5092 template<typename _RandomAccessIterator, typename _Compare>
5093 inline void
5094 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5095 _Compare __comp)
5096 {
5097 // concept requirements
5098 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5099 _RandomAccessIterator>)
5100 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5101 typename iterator_traits<_RandomAccessIterator>::value_type,
5102 typename iterator_traits<_RandomAccessIterator>::value_type>)
5103 __glibcxx_requires_valid_range(__first, __last);
5104 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5105
5106 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5107 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5108 }
5109
5110 template<typename _InputIterator1, typename _InputIterator2,
5111 typename _OutputIterator,
5112 typename _Compare>
5113 _OutputIterator
5114 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5115 _InputIterator2 __first2, _InputIterator2 __last2,
5116 _OutputIterator __result, _Compare __comp)
5117 {
5118 while (__first1 != __last1 && __first2 != __last2)
5119 {
5120 if (__comp(__first1, __first2))
5121 {
5122 *__result = *__first1;
5123 ++__first1;
5124 }
5125 else if (__comp(__first2, __first1))
5126 {
5127 *__result = *__first2;
5128 ++__first2;
5129 }
5130 else
5131 {
5132 *__result = *__first1;
5133 ++__first1;
5134 ++__first2;
5135 }
5136 ++__result;
5137 }
5138 return std::copy(__first2, __last2,
5139 std::copy(__first1, __last1, __result));
5140 }
5141
5142 /**
5143 * @brief Return the union of two sorted ranges.
5144 * @ingroup set_algorithms
5145 * @param __first1 Start of first range.
5146 * @param __last1 End of first range.
5147 * @param __first2 Start of second range.
5148 * @param __last2 End of second range.
5149 * @param __result Start of output range.
5150 * @return End of the output range.
5151 * @ingroup set_algorithms
5152 *
5153 * This operation iterates over both ranges, copying elements present in
5154 * each range in order to the output range. Iterators increment for each
5155 * range. When the current element of one range is less than the other,
5156 * that element is copied and the iterator advanced. If an element is
5157 * contained in both ranges, the element from the first range is copied and
5158 * both ranges advance. The output range may not overlap either input
5159 * range.
5160 */
5161 template<typename _InputIterator1, typename _InputIterator2,
5162 typename _OutputIterator>
5163 inline _OutputIterator
5164 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5165 _InputIterator2 __first2, _InputIterator2 __last2,
5166 _OutputIterator __result)
5167 {
5168 // concept requirements
5169 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5170 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5171 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5172 typename iterator_traits<_InputIterator1>::value_type>)
5173 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5174 typename iterator_traits<_InputIterator2>::value_type>)
5175 __glibcxx_function_requires(_LessThanOpConcept<
5176 typename iterator_traits<_InputIterator1>::value_type,
5177 typename iterator_traits<_InputIterator2>::value_type>)
5178 __glibcxx_function_requires(_LessThanOpConcept<
5179 typename iterator_traits<_InputIterator2>::value_type,
5180 typename iterator_traits<_InputIterator1>::value_type>)
5181 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5182 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5183 __glibcxx_requires_irreflexive2(__first1, __last1);
5184 __glibcxx_requires_irreflexive2(__first2, __last2);
5185
5186 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5187 __first2, __last2, __result,
5188 __gnu_cxx::__ops::__iter_less_iter());
5189 }
5190
5191 /**
5192 * @brief Return the union of two sorted ranges using a comparison functor.
5193 * @ingroup set_algorithms
5194 * @param __first1 Start of first range.
5195 * @param __last1 End of first range.
5196 * @param __first2 Start of second range.
5197 * @param __last2 End of second range.
5198 * @param __result Start of output range.
5199 * @param __comp The comparison functor.
5200 * @return End of the output range.
5201 * @ingroup set_algorithms
5202 *
5203 * This operation iterates over both ranges, copying elements present in
5204 * each range in order to the output range. Iterators increment for each
5205 * range. When the current element of one range is less than the other
5206 * according to @p __comp, that element is copied and the iterator advanced.
5207 * If an equivalent element according to @p __comp is contained in both
5208 * ranges, the element from the first range is copied and both ranges
5209 * advance. The output range may not overlap either input range.
5210 */
5211 template<typename _InputIterator1, typename _InputIterator2,
5212 typename _OutputIterator, typename _Compare>
5213 inline _OutputIterator
5214 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5215 _InputIterator2 __first2, _InputIterator2 __last2,
5216 _OutputIterator __result, _Compare __comp)
5217 {
5218 // concept requirements
5219 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5220 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5221 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5222 typename iterator_traits<_InputIterator1>::value_type>)
5223 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5224 typename iterator_traits<_InputIterator2>::value_type>)
5225 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5226 typename iterator_traits<_InputIterator1>::value_type,
5227 typename iterator_traits<_InputIterator2>::value_type>)
5228 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5229 typename iterator_traits<_InputIterator2>::value_type,
5230 typename iterator_traits<_InputIterator1>::value_type>)
5231 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5232 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5233 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5234 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5235
5236 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5237 __first2, __last2, __result,
5238 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5239 }
5240
5241 template<typename _InputIterator1, typename _InputIterator2,
5242 typename _OutputIterator,
5243 typename _Compare>
5244 _OutputIterator
5245 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5246 _InputIterator2 __first2, _InputIterator2 __last2,
5247 _OutputIterator __result, _Compare __comp)
5248 {
5249 while (__first1 != __last1 && __first2 != __last2)
5250 if (__comp(__first1, __first2))
5251 ++__first1;
5252 else if (__comp(__first2, __first1))
5253 ++__first2;
5254 else
5255 {
5256 *__result = *__first1;
5257 ++__first1;
5258 ++__first2;
5259 ++__result;
5260 }
5261 return __result;
5262 }
5263
5264 /**
5265 * @brief Return the intersection of two sorted ranges.
5266 * @ingroup set_algorithms
5267 * @param __first1 Start of first range.
5268 * @param __last1 End of first range.
5269 * @param __first2 Start of second range.
5270 * @param __last2 End of second range.
5271 * @param __result Start of output range.
5272 * @return End of the output range.
5273 * @ingroup set_algorithms
5274 *
5275 * This operation iterates over both ranges, copying elements present in
5276 * both ranges in order to the output range. Iterators increment for each
5277 * range. When the current element of one range is less than the other,
5278 * that iterator advances. If an element is contained in both ranges, the
5279 * element from the first range is copied and both ranges advance. The
5280 * output range may not overlap either input range.
5281 */
5282 template<typename _InputIterator1, typename _InputIterator2,
5283 typename _OutputIterator>
5284 inline _OutputIterator
5285 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5286 _InputIterator2 __first2, _InputIterator2 __last2,
5287 _OutputIterator __result)
5288 {
5289 // concept requirements
5290 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5291 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5292 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5293 typename iterator_traits<_InputIterator1>::value_type>)
5294 __glibcxx_function_requires(_LessThanOpConcept<
5295 typename iterator_traits<_InputIterator1>::value_type,
5296 typename iterator_traits<_InputIterator2>::value_type>)
5297 __glibcxx_function_requires(_LessThanOpConcept<
5298 typename iterator_traits<_InputIterator2>::value_type,
5299 typename iterator_traits<_InputIterator1>::value_type>)
5300 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5301 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5302 __glibcxx_requires_irreflexive2(__first1, __last1);
5303 __glibcxx_requires_irreflexive2(__first2, __last2);
5304
5305 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5306 __first2, __last2, __result,
5307 __gnu_cxx::__ops::__iter_less_iter());
5308 }
5309
5310 /**
5311 * @brief Return the intersection of two sorted ranges using comparison
5312 * functor.
5313 * @ingroup set_algorithms
5314 * @param __first1 Start of first range.
5315 * @param __last1 End of first range.
5316 * @param __first2 Start of second range.
5317 * @param __last2 End of second range.
5318 * @param __result Start of output range.
5319 * @param __comp The comparison functor.
5320 * @return End of the output range.
5321 * @ingroup set_algorithms
5322 *
5323 * This operation iterates over both ranges, copying elements present in
5324 * both ranges in order to the output range. Iterators increment for each
5325 * range. When the current element of one range is less than the other
5326 * according to @p __comp, that iterator advances. If an element is
5327 * contained in both ranges according to @p __comp, the element from the
5328 * first range is copied and both ranges advance. The output range may not
5329 * overlap either input range.
5330 */
5331 template<typename _InputIterator1, typename _InputIterator2,
5332 typename _OutputIterator, typename _Compare>
5333 inline _OutputIterator
5334 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5335 _InputIterator2 __first2, _InputIterator2 __last2,
5336 _OutputIterator __result, _Compare __comp)
5337 {
5338 // concept requirements
5339 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5340 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5341 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5342 typename iterator_traits<_InputIterator1>::value_type>)
5343 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5344 typename iterator_traits<_InputIterator1>::value_type,
5345 typename iterator_traits<_InputIterator2>::value_type>)
5346 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5347 typename iterator_traits<_InputIterator2>::value_type,
5348 typename iterator_traits<_InputIterator1>::value_type>)
5349 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5350 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5351 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5352 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5353
5354 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5355 __first2, __last2, __result,
5356 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5357 }
5358
5359 template<typename _InputIterator1, typename _InputIterator2,
5360 typename _OutputIterator,
5361 typename _Compare>
5362 _OutputIterator
5363 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5364 _InputIterator2 __first2, _InputIterator2 __last2,
5365 _OutputIterator __result, _Compare __comp)
5366 {
5367 while (__first1 != __last1 && __first2 != __last2)
5368 if (__comp(__first1, __first2))
5369 {
5370 *__result = *__first1;
5371 ++__first1;
5372 ++__result;
5373 }
5374 else if (__comp(__first2, __first1))
5375 ++__first2;
5376 else
5377 {
5378 ++__first1;
5379 ++__first2;
5380 }
5381 return std::copy(__first1, __last1, __result);
5382 }
5383
5384 /**
5385 * @brief Return the difference of two sorted ranges.
5386 * @ingroup set_algorithms
5387 * @param __first1 Start of first range.
5388 * @param __last1 End of first range.
5389 * @param __first2 Start of second range.
5390 * @param __last2 End of second range.
5391 * @param __result Start of output range.
5392 * @return End of the output range.
5393 * @ingroup set_algorithms
5394 *
5395 * This operation iterates over both ranges, copying elements present in
5396 * the first range but not the second in order to the output range.
5397 * Iterators increment for each range. When the current element of the
5398 * first range is less than the second, that element is copied and the
5399 * iterator advances. If the current element of the second range is less,
5400 * the iterator advances, but no element is copied. If an element is
5401 * contained in both ranges, no elements are copied and both ranges
5402 * advance. The output range may not overlap either input range.
5403 */
5404 template<typename _InputIterator1, typename _InputIterator2,
5405 typename _OutputIterator>
5406 inline _OutputIterator
5407 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5408 _InputIterator2 __first2, _InputIterator2 __last2,
5409 _OutputIterator __result)
5410 {
5411 // concept requirements
5412 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5413 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5414 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5415 typename iterator_traits<_InputIterator1>::value_type>)
5416 __glibcxx_function_requires(_LessThanOpConcept<
5417 typename iterator_traits<_InputIterator1>::value_type,
5418 typename iterator_traits<_InputIterator2>::value_type>)
5419 __glibcxx_function_requires(_LessThanOpConcept<
5420 typename iterator_traits<_InputIterator2>::value_type,
5421 typename iterator_traits<_InputIterator1>::value_type>)
5422 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5423 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5424 __glibcxx_requires_irreflexive2(__first1, __last1);
5425 __glibcxx_requires_irreflexive2(__first2, __last2);
5426
5427 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5428 __first2, __last2, __result,
5429 __gnu_cxx::__ops::__iter_less_iter());
5430 }
5431
5432 /**
5433 * @brief Return the difference of two sorted ranges using comparison
5434 * functor.
5435 * @ingroup set_algorithms
5436 * @param __first1 Start of first range.
5437 * @param __last1 End of first range.
5438 * @param __first2 Start of second range.
5439 * @param __last2 End of second range.
5440 * @param __result Start of output range.
5441 * @param __comp The comparison functor.
5442 * @return End of the output range.
5443 * @ingroup set_algorithms
5444 *
5445 * This operation iterates over both ranges, copying elements present in
5446 * the first range but not the second in order to the output range.
5447 * Iterators increment for each range. When the current element of the
5448 * first range is less than the second according to @p __comp, that element
5449 * is copied and the iterator advances. If the current element of the
5450 * second range is less, no element is copied and the iterator advances.
5451 * If an element is contained in both ranges according to @p __comp, no
5452 * elements are copied and both ranges advance. The output range may not
5453 * overlap either input range.
5454 */
5455 template<typename _InputIterator1, typename _InputIterator2,
5456 typename _OutputIterator, typename _Compare>
5457 inline _OutputIterator
5458 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5459 _InputIterator2 __first2, _InputIterator2 __last2,
5460 _OutputIterator __result, _Compare __comp)
5461 {
5462 // concept requirements
5463 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5464 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5465 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5466 typename iterator_traits<_InputIterator1>::value_type>)
5467 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5468 typename iterator_traits<_InputIterator1>::value_type,
5469 typename iterator_traits<_InputIterator2>::value_type>)
5470 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5471 typename iterator_traits<_InputIterator2>::value_type,
5472 typename iterator_traits<_InputIterator1>::value_type>)
5473 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5474 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5475 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5476 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5477
5478 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5479 __first2, __last2, __result,
5480 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5481 }
5482
5483 template<typename _InputIterator1, typename _InputIterator2,
5484 typename _OutputIterator,
5485 typename _Compare>
5486 _OutputIterator
5487 __set_symmetric_difference(_InputIterator1 __first1,
5488 _InputIterator1 __last1,
5489 _InputIterator2 __first2,
5490 _InputIterator2 __last2,
5491 _OutputIterator __result,
5492 _Compare __comp)
5493 {
5494 while (__first1 != __last1 && __first2 != __last2)
5495 if (__comp(__first1, __first2))
5496 {
5497 *__result = *__first1;
5498 ++__first1;
5499 ++__result;
5500 }
5501 else if (__comp(__first2, __first1))
5502 {
5503 *__result = *__first2;
5504 ++__first2;
5505 ++__result;
5506 }
5507 else
5508 {
5509 ++__first1;
5510 ++__first2;
5511 }
5512 return std::copy(__first2, __last2,
5513 std::copy(__first1, __last1, __result));
5514 }
5515
5516 /**
5517 * @brief Return the symmetric difference of two sorted ranges.
5518 * @ingroup set_algorithms
5519 * @param __first1 Start of first range.
5520 * @param __last1 End of first range.
5521 * @param __first2 Start of second range.
5522 * @param __last2 End of second range.
5523 * @param __result Start of output range.
5524 * @return End of the output range.
5525 * @ingroup set_algorithms
5526 *
5527 * This operation iterates over both ranges, copying elements present in
5528 * one range but not the other in order to the output range. Iterators
5529 * increment for each range. When the current element of one range is less
5530 * than the other, that element is copied and the iterator advances. If an
5531 * element is contained in both ranges, no elements are copied and both
5532 * ranges advance. The output range may not overlap either input range.
5533 */
5534 template<typename _InputIterator1, typename _InputIterator2,
5535 typename _OutputIterator>
5536 inline _OutputIterator
5537 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5538 _InputIterator2 __first2, _InputIterator2 __last2,
5539 _OutputIterator __result)
5540 {
5541 // concept requirements
5542 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5543 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5544 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5545 typename iterator_traits<_InputIterator1>::value_type>)
5546 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5547 typename iterator_traits<_InputIterator2>::value_type>)
5548 __glibcxx_function_requires(_LessThanOpConcept<
5549 typename iterator_traits<_InputIterator1>::value_type,
5550 typename iterator_traits<_InputIterator2>::value_type>)
5551 __glibcxx_function_requires(_LessThanOpConcept<
5552 typename iterator_traits<_InputIterator2>::value_type,
5553 typename iterator_traits<_InputIterator1>::value_type>)
5554 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5555 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5556 __glibcxx_requires_irreflexive2(__first1, __last1);
5557 __glibcxx_requires_irreflexive2(__first2, __last2);
5558
5559 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5560 __first2, __last2, __result,
5561 __gnu_cxx::__ops::__iter_less_iter());
5562 }
5563
5564 /**
5565 * @brief Return the symmetric difference of two sorted ranges using
5566 * comparison functor.
5567 * @ingroup set_algorithms
5568 * @param __first1 Start of first range.
5569 * @param __last1 End of first range.
5570 * @param __first2 Start of second range.
5571 * @param __last2 End of second range.
5572 * @param __result Start of output range.
5573 * @param __comp The comparison functor.
5574 * @return End of the output range.
5575 * @ingroup set_algorithms
5576 *
5577 * This operation iterates over both ranges, copying elements present in
5578 * one range but not the other in order to the output range. Iterators
5579 * increment for each range. When the current element of one range is less
5580 * than the other according to @p comp, that element is copied and the
5581 * iterator advances. If an element is contained in both ranges according
5582 * to @p __comp, no elements are copied and both ranges advance. The output
5583 * range may not overlap either input range.
5584 */
5585 template<typename _InputIterator1, typename _InputIterator2,
5586 typename _OutputIterator, typename _Compare>
5587 inline _OutputIterator
5588 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5589 _InputIterator2 __first2, _InputIterator2 __last2,
5590 _OutputIterator __result,
5591 _Compare __comp)
5592 {
5593 // concept requirements
5594 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5595 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5596 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5597 typename iterator_traits<_InputIterator1>::value_type>)
5598 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5599 typename iterator_traits<_InputIterator2>::value_type>)
5600 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5601 typename iterator_traits<_InputIterator1>::value_type,
5602 typename iterator_traits<_InputIterator2>::value_type>)
5603 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5604 typename iterator_traits<_InputIterator2>::value_type,
5605 typename iterator_traits<_InputIterator1>::value_type>)
5606 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5607 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5608 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5609 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5610
5611 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5612 __first2, __last2, __result,
5613 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5614 }
5615
5616 template<typename _ForwardIterator, typename _Compare>
5617 _GLIBCXX14_CONSTEXPR
5618 _ForwardIterator
5619 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5620 _Compare __comp)
5621 {
5622 if (__first == __last)
5623 return __first;
5624 _ForwardIterator __result = __first;
5625 while (++__first != __last)
5626 if (__comp(__first, __result))
5627 __result = __first;
5628 return __result;
5629 }
5630
5631 /**
5632 * @brief Return the minimum element in a range.
5633 * @ingroup sorting_algorithms
5634 * @param __first Start of range.
5635 * @param __last End of range.
5636 * @return Iterator referencing the first instance of the smallest value.
5637 */
5638 template<typename _ForwardIterator>
5639 _GLIBCXX14_CONSTEXPR
5640 _ForwardIterator
5641 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5642 {
5643 // concept requirements
5644 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5645 __glibcxx_function_requires(_LessThanComparableConcept<
5646 typename iterator_traits<_ForwardIterator>::value_type>)
5647 __glibcxx_requires_valid_range(__first, __last);
5648 __glibcxx_requires_irreflexive(__first, __last);
5649
5650 return _GLIBCXX_STD_A::__min_element(__first, __last,
5651 __gnu_cxx::__ops::__iter_less_iter());
5652 }
5653
5654 /**
5655 * @brief Return the minimum element in a range using comparison functor.
5656 * @ingroup sorting_algorithms
5657 * @param __first Start of range.
5658 * @param __last End of range.
5659 * @param __comp Comparison functor.
5660 * @return Iterator referencing the first instance of the smallest value
5661 * according to __comp.
5662 */
5663 template<typename _ForwardIterator, typename _Compare>
5664 _GLIBCXX14_CONSTEXPR
5665 inline _ForwardIterator
5666 min_element(_ForwardIterator __first, _ForwardIterator __last,
5667 _Compare __comp)
5668 {
5669 // concept requirements
5670 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5671 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5672 typename iterator_traits<_ForwardIterator>::value_type,
5673 typename iterator_traits<_ForwardIterator>::value_type>)
5674 __glibcxx_requires_valid_range(__first, __last);
5675 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5676
5677 return _GLIBCXX_STD_A::__min_element(__first, __last,
5678 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5679 }
5680
5681 template<typename _ForwardIterator, typename _Compare>
5682 _GLIBCXX14_CONSTEXPR
5683 _ForwardIterator
5684 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5685 _Compare __comp)
5686 {
5687 if (__first == __last) return __first;
5688 _ForwardIterator __result = __first;
5689 while (++__first != __last)
5690 if (__comp(__result, __first))
5691 __result = __first;
5692 return __result;
5693 }
5694
5695 /**
5696 * @brief Return the maximum element in a range.
5697 * @ingroup sorting_algorithms
5698 * @param __first Start of range.
5699 * @param __last End of range.
5700 * @return Iterator referencing the first instance of the largest value.
5701 */
5702 template<typename _ForwardIterator>
5703 _GLIBCXX14_CONSTEXPR
5704 inline _ForwardIterator
5705 max_element(_ForwardIterator __first, _ForwardIterator __last)
5706 {
5707 // concept requirements
5708 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5709 __glibcxx_function_requires(_LessThanComparableConcept<
5710 typename iterator_traits<_ForwardIterator>::value_type>)
5711 __glibcxx_requires_valid_range(__first, __last);
5712 __glibcxx_requires_irreflexive(__first, __last);
5713
5714 return _GLIBCXX_STD_A::__max_element(__first, __last,
5715 __gnu_cxx::__ops::__iter_less_iter());
5716 }
5717
5718 /**
5719 * @brief Return the maximum element in a range using comparison functor.
5720 * @ingroup sorting_algorithms
5721 * @param __first Start of range.
5722 * @param __last End of range.
5723 * @param __comp Comparison functor.
5724 * @return Iterator referencing the first instance of the largest value
5725 * according to __comp.
5726 */
5727 template<typename _ForwardIterator, typename _Compare>
5728 _GLIBCXX14_CONSTEXPR
5729 inline _ForwardIterator
5730 max_element(_ForwardIterator __first, _ForwardIterator __last,
5731 _Compare __comp)
5732 {
5733 // concept requirements
5734 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5735 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5736 typename iterator_traits<_ForwardIterator>::value_type,
5737 typename iterator_traits<_ForwardIterator>::value_type>)
5738 __glibcxx_requires_valid_range(__first, __last);
5739 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5740
5741 return _GLIBCXX_STD_A::__max_element(__first, __last,
5742 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5743 }
5744
5745#if __cplusplus >= 201402L
5746 /// Reservoir sampling algorithm.
5747 template<typename _InputIterator, typename _RandomAccessIterator,
5748 typename _Size, typename _UniformRandomBitGenerator>
5749 _RandomAccessIterator
5750 __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag,
5751 _RandomAccessIterator __out, random_access_iterator_tag,
5752 _Size __n, _UniformRandomBitGenerator&& __g)
5753 {
5754 using __distrib_type = uniform_int_distribution<_Size>;
5755 using __param_type = typename __distrib_type::param_type;
5756 __distrib_type __d{};
5757 _Size __sample_sz = 0;
5758 while (__first != __last && __sample_sz != __n)
5759 {
5760 __out[__sample_sz++] = *__first;
5761 ++__first;
5762 }
5763 for (auto __pop_sz = __sample_sz; __first != __last;
5764 ++__first, (void) ++__pop_sz)
5765 {
5766 const auto __k = __d(__g, __param_type{0, __pop_sz});
5767 if (__k < __n)
5768 __out[__k] = *__first;
5769 }
5770 return __out + __sample_sz;
5771 }
5772
5773 /// Selection sampling algorithm.
5774 template<typename _ForwardIterator, typename _OutputIterator, typename _Cat,
5775 typename _Size, typename _UniformRandomBitGenerator>
5776 _OutputIterator
5777 __sample(_ForwardIterator __first, _ForwardIterator __last,
5778 forward_iterator_tag,
5779 _OutputIterator __out, _Cat,
5780 _Size __n, _UniformRandomBitGenerator&& __g)
5781 {
5782 using __distrib_type = uniform_int_distribution<_Size>;
5783 using __param_type = typename __distrib_type::param_type;
5784 using _USize = make_unsigned_t<_Size>;
5785 using _Gen = remove_reference_t<_UniformRandomBitGenerator>;
5786 using __uc_type = common_type_t<typename _Gen::result_type, _USize>;
5787
5788 __distrib_type __d{};
5789 _Size __unsampled_sz = std::distance(__first, __last);
5790 __n = std::min(__n, __unsampled_sz);
5791
5792 // If possible, we use __gen_two_uniform_ints to efficiently produce
5793 // two random numbers using a single distribution invocation:
5794
5795 const __uc_type __urngrange = __g.max() - __g.min();
5796 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5797 // I.e. (__urngrange >= __unsampled_sz * __unsampled_sz) but without
5798 // wrapping issues.
5799 {
5800 while (__n != 0 && __unsampled_sz >= 2)
5801 {
5802 const pair<_Size, _Size> __p =
5803 __gen_two_uniform_ints(__unsampled_sz, __unsampled_sz - 1, __g);
5804
5805 --__unsampled_sz;
5806 if (__p.first < __n)
5807 {
5808 *__out++ = *__first;
5809 --__n;
5810 }
5811
5812 ++__first;
5813
5814 if (__n == 0) break;
5815
5816 --__unsampled_sz;
5817 if (__p.second < __n)
5818 {
5819 *__out++ = *__first;
5820 --__n;
5821 }
5822
5823 ++__first;
5824 }
5825 }
5826
5827 // The loop above is otherwise equivalent to this one-at-a-time version:
5828
5829 for (; __n != 0; ++__first)
5830 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5831 {
5832 *__out++ = *__first;
5833 --__n;
5834 }
5835 return __out;
5836 }
5837
5838#if __cplusplus > 201402L
5839#define __cpp_lib_sample 201603
5840 /// Take a random sample from a population.
5841 template<typename _PopulationIterator, typename _SampleIterator,
5842 typename _Distance, typename _UniformRandomBitGenerator>
5843 _SampleIterator
5844 sample(_PopulationIterator __first, _PopulationIterator __last,
5845 _SampleIterator __out, _Distance __n,
5846 _UniformRandomBitGenerator&& __g)
5847 {
5848 using __pop_cat = typename
5849 std::iterator_traits<_PopulationIterator>::iterator_category;
5850 using __samp_cat = typename
5851 std::iterator_traits<_SampleIterator>::iterator_category;
5852
5853 static_assert(
5854 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5855 is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5856 "output range must use a RandomAccessIterator when input range"
5857 " does not meet the ForwardIterator requirements");
5858
5859 static_assert(is_integral<_Distance>::value,
5860 "sample size must be an integer type");
5861
5862 typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
5863 return _GLIBCXX_STD_A::
5864 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5865 std::forward<_UniformRandomBitGenerator>(__g));
5866 }
5867#endif // C++17
5868#endif // C++14
5869
5870_GLIBCXX_END_NAMESPACE_ALGO
5871_GLIBCXX_END_NAMESPACE_VERSION
5872} // namespace std
5873
5874#endif /* _STL_ALGO_H */
5875