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