File Coverage

/usr/include/c++/5/bits/stl_algo.h
Criterion Covered Total %
statement 69 180 38.3
branch 46 476 9.6
condition n/a
subroutine n/a
pod n/a
total 115 656 17.5


line stmt bran cond sub pod time code
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             // .
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 // for rand
60             #include
61             #include
62             #include // for _Temporary_buffer
63             #include
64              
65             #if __cplusplus >= 201103L
66             #include // for std::uniform_int_distribution
67             #endif
68              
69             // See concept_check.h for the __glibcxx_*_requires macros.
70              
71             namespace std _GLIBCXX_VISIBILITY(default)
72             {
73             _GLIBCXX_BEGIN_NAMESPACE_VERSION
74              
75             /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
76             template
77             void
78 0           __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
79             _Iterator __c, _Compare __comp)
80             {
81 0 0         if (__comp(__a, __b))
    0          
    0          
    0          
82             {
83 0 0         if (__comp(__b, __c))
    0          
    0          
    0          
84 0           std::iter_swap(__result, __b);
85 0 0         else if (__comp(__a, __c))
    0          
    0          
    0          
86 0           std::iter_swap(__result, __c);
87             else
88 0           std::iter_swap(__result, __a);
89             }
90 0 0         else if (__comp(__a, __c))
    0          
    0          
    0          
91 0           std::iter_swap(__result, __a);
92 0 0         else if (__comp(__b, __c))
    0          
    0          
    0          
93 0           std::iter_swap(__result, __c);
94             else
95 0           std::iter_swap(__result, __b);
96 0           }
97              
98             /// This is an overload used by find algos for the Input Iterator case.
99             template
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
111             _RandomAccessIterator
112 120           __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
113             _Predicate __pred, random_access_iterator_tag)
114             {
115             typename iterator_traits<_RandomAccessIterator>::difference_type
116 120           __trip_count = (__last - __first) >> 2;
117              
118 120 0         for (; __trip_count > 0; --__trip_count)
    0          
    50          
    50          
    0          
    0          
    50          
    50          
119             {
120 0 0         if (__pred(__first))
    0          
    0          
    0          
    0          
    0          
    0          
    0          
121 0           return __first;
122 0           ++__first;
123              
124 0 0         if (__pred(__first))
    0          
    0          
    0          
    0          
    0          
    0          
    0          
125 0           return __first;
126 0           ++__first;
127              
128 0 0         if (__pred(__first))
    0          
    0          
    0          
    0          
    0          
    0          
    0          
129 0           return __first;
130 0           ++__first;
131              
132 0 0         if (__pred(__first))
    0          
    0          
    0          
    0          
    0          
    0          
    0          
133 0           return __first;
134 0           ++__first;
135             }
136              
137 120           switch (__last - __first)
138             {
139             case 3:
140 0 0         if (__pred(__first))
    0          
    0          
    0          
    0          
    0          
    0          
    0          
141 0           return __first;
142 0           ++__first;
143             case 2:
144 48 0         if (__pred(__first))
    0          
    0          
    100          
    0          
    0          
    50          
    100          
145 15           return __first;
146 33           ++__first;
147             case 1:
148 83 0         if (__pred(__first))
    0          
    100          
    100          
    0          
    0          
    100          
    100          
149 49           return __first;
150 34           ++__first;
151             case 0:
152             default:
153 56           return __last;
154             }
155             }
156              
157             template
158             inline _Iterator
159 79           __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
160             {
161 79           return __find_if(__first, __last, __pred,
162 158 0         std::__iterator_category(__first));
    0          
    0          
    0          
    50          
    50          
163             }
164              
165             /// Provided for stable_partition to use.
166             template
167             inline _InputIterator
168 41           __find_if_not(_InputIterator __first, _InputIterator __last,
169             _Predicate __pred)
170             {
171 82 50         return std::__find_if(__first, __last,
    50          
172             __gnu_cxx::__ops::__negate(__pred),
173 123 50         std::__iterator_category(__first));
    50          
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
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
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
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
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
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
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
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
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
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
507             inline bool
508 41           all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
509 41           { 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
524             inline bool
525 0           none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
526 0           { 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
542             inline bool
543 0           any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
544 0           { 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
557             inline _InputIterator
558 41           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 41           return std::__find_if_not(__first, __last,
567 41           __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
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
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
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
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
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
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
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
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
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
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
856             _ForwardIterator
857 0           __remove_if(_ForwardIterator __first, _ForwardIterator __last,
858             _Predicate __pred)
859             {
860 0 0         __first = std::__find_if(__first, __last, __pred);
861 0 0         if (__first == __last)
862 0           return __first;
863 0           _ForwardIterator __result = __first;
864 0           ++__first;
865 0 0         for (; __first != __last; ++__first)
866 0 0         if (!__pred(__first))
    0          
867             {
868 0 0         *__result = _GLIBCXX_MOVE(*__first);
869 0           ++__result;
870             }
871 0           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
892             inline _ForwardIterator
893 0           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 0           return std::__remove_if(__first, __last,
904 0           __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
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
941             _ForwardIterator
942 5           __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
943             _BinaryPredicate __binary_pred)
944             {
945 5 0         if (__first == __last)
    50          
946 0           return __last;
947 5           _ForwardIterator __next = __first;
948 6 0         while (++__next != __last)
    100          
949             {
950 1 0         if (__binary_pred(__first, __next))
    50          
951 0           return __first;
952 1           __first = __next;
953             }
954 5           return __last;
955             }
956              
957             template
958             _ForwardIterator
959 5           __unique(_ForwardIterator __first, _ForwardIterator __last,
960             _BinaryPredicate __binary_pred)
961             {
962             // Skip the beginning, if already unique.
963 5 0         __first = std::__adjacent_find(__first, __last, __binary_pred);
    50          
964 5 0         if (__first == __last)
    50          
965 5           return __last;
966              
967             // Do the real copy work.
968 0           _ForwardIterator __dest = __first;
969 0           ++__first;
970 0 0         while (++__first != __last)
    0          
971 0 0         if (!__binary_pred(__dest, __first))
    0          
972 0 0         *++__dest = _GLIBCXX_MOVE(*__first);
973 5           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
991             inline _ForwardIterator
992 5           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 5           return std::__unique(__first, __last,
1002 10 0         __gnu_cxx::__ops::__iter_equal_to_iter());
    50          
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
1664             void
1665 0           __heap_select(_RandomAccessIterator __first,
1666             _RandomAccessIterator __middle,
1667             _RandomAccessIterator __last, _Compare __comp)
1668             {
1669 0           std::__make_heap(__first, __middle, __comp);
1670 0 0         for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
    0          
    0          
    0          
1671 0 0         if (__comp(__i, __first))
    0          
    0          
    0          
    0          
    0          
    0          
1672 0 0         std::__pop_heap(__first, __middle, __i, __comp);
    0          
    0          
    0          
1673 0           }
1674              
1675             // partial_sort
1676              
1677             template
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
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
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
1815             void
1816 0           __unguarded_linear_insert(_RandomAccessIterator __last,
1817             _Compare __comp)
1818             {
1819             typename iterator_traits<_RandomAccessIterator>::value_type
1820 0           __val = _GLIBCXX_MOVE(*__last);
1821 0           _RandomAccessIterator __next = __last;
1822 0           --__next;
1823 0 0         while (__comp(__val, __next))
    0          
    0          
    0          
    0          
    0          
    0          
1824             {
1825 0 0         *__last = _GLIBCXX_MOVE(*__next);
    0          
1826 0           __last = __next;
1827 0           --__next;
1828             }
1829 0 0         *__last = _GLIBCXX_MOVE(__val);
    0          
1830 0           }
1831              
1832             /// This is a helper function for the sort routine.
1833             template
1834             void
1835 5           __insertion_sort(_RandomAccessIterator __first,
1836             _RandomAccessIterator __last, _Compare __comp)
1837             {
1838 5 0         if (__first == __last) return;
    0          
    0          
    50          
1839              
1840 6 0         for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
    0          
    0          
    100          
1841             {
1842 1 0         if (__comp(__i, __first))
    0          
    0          
    0          
    0          
    50          
    50          
1843             {
1844             typename iterator_traits<_RandomAccessIterator>::value_type
1845 2           __val = _GLIBCXX_MOVE(*__i);
1846 1 0         _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
    0          
    0          
    50          
1847 1 0         *__first = _GLIBCXX_MOVE(__val);
    50          
1848             }
1849             else
1850 0 0         std::__unguarded_linear_insert(__i,
    0          
    0          
    0          
    0          
1851 0           __gnu_cxx::__ops::__val_comp_iter(__comp));
1852             }
1853             }
1854              
1855             /// This is a helper function for the sort routine.
1856             template
1857             inline void
1858 0           __unguarded_insertion_sort(_RandomAccessIterator __first,
1859             _RandomAccessIterator __last, _Compare __comp)
1860             {
1861 0 0         for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
    0          
    0          
    0          
1862 0 0         std::__unguarded_linear_insert(__i,
    0          
    0          
    0          
    0          
1863 0           __gnu_cxx::__ops::__val_comp_iter(__comp));
1864 0           }
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
1874             void
1875 5           __final_insertion_sort(_RandomAccessIterator __first,
1876             _RandomAccessIterator __last, _Compare __comp)
1877             {
1878 5 0         if (__last - __first > int(_S_threshold))
    0          
    0          
    50          
1879             {
1880 0           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
1881 0           std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
1882             __comp);
1883             }
1884             else
1885 5           std::__insertion_sort(__first, __last, __comp);
1886 5           }
1887              
1888             /// This is a helper function...
1889             template
1890             _RandomAccessIterator
1891 0           __unguarded_partition(_RandomAccessIterator __first,
1892             _RandomAccessIterator __last,
1893             _RandomAccessIterator __pivot, _Compare __comp)
1894             {
1895 0           while (true)
1896             {
1897 0 0         while (__comp(__first, __pivot))
    0          
    0          
    0          
1898 0           ++__first;
1899 0           --__last;
1900 0 0         while (__comp(__pivot, __last))
    0          
    0          
    0          
1901 0           --__last;
1902 0 0         if (!(__first < __last))
    0          
    0          
    0          
1903 0           return __first;
1904 0           std::iter_swap(__first, __last);
1905 0           ++__first;
1906             }
1907             }
1908              
1909             /// This is a helper function...
1910             template
1911             inline _RandomAccessIterator
1912 0           __unguarded_partition_pivot(_RandomAccessIterator __first,
1913             _RandomAccessIterator __last, _Compare __comp)
1914             {
1915 0           _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1916 0 0         std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
    0          
    0          
    0          
1917             __comp);
1918 0 0         return std::__unguarded_partition(__first + 1, __last, __first, __comp);
    0          
    0          
    0          
1919             }
1920              
1921             template
1922             inline void
1923 0           __partial_sort(_RandomAccessIterator __first,
1924             _RandomAccessIterator __middle,
1925             _RandomAccessIterator __last,
1926             _Compare __comp)
1927             {
1928 0           std::__heap_select(__first, __middle, __last, __comp);
1929 0           std::__sort_heap(__first, __middle, __comp);
1930 0           }
1931              
1932             /// This is a helper function for the sort routine.
1933             template
1934             void
1935 5           __introsort_loop(_RandomAccessIterator __first,
1936             _RandomAccessIterator __last,
1937             _Size __depth_limit, _Compare __comp)
1938             {
1939 5 0         while (__last - __first > int(_S_threshold))
    0          
    0          
    50          
1940             {
1941 0 0         if (__depth_limit == 0)
    0          
    0          
    0          
1942             {
1943 0 0         std::__partial_sort(__first, __last, __last, __comp);
    0          
    0          
    0          
1944 0           return;
1945             }
1946 0           --__depth_limit;
1947             _RandomAccessIterator __cut =
1948 0 0         std::__unguarded_partition_pivot(__first, __last, __comp);
    0          
    0          
    0          
1949 0 0         std::__introsort_loop(__cut, __last, __depth_limit, __comp);
    0          
    0          
    0          
1950 0           __last = __cut;
1951             }
1952             }
1953              
1954             // sort
1955              
1956             template
1957             inline void
1958 5           __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1959             _Compare __comp)
1960             {
1961 5 0         if (__first != __last)
    0          
    0          
    50          
1962             {
1963 5           std::__introsort_loop(__first, __last,
1964 5           std::__lg(__last - __first) * 2,
1965             __comp);
1966 5           std::__final_insertion_sort(__first, __last, __comp);
1967             }
1968 5           }
1969              
1970             template
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 not less
2009             * than @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
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
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
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
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
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
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
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
2253             bool
2254 0           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 0           = std::__lower_bound(__first, __last, __val,
2268 0 0         __gnu_cxx::__ops::__iter_less_val());
2269 0 0         return __i != __last && !(__val < *__i);
    0          
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
3297             _GLIBCXX14_CONSTEXPR
3298             inline pair
3299             minmax(const _Tp& __a, const _Tp& __b)
3300             {
3301             // concept requirements
3302             __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3303              
3304             return __b < __a ? pair(__b, __a)
3305             : pair(__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
3318             _GLIBCXX14_CONSTEXPR
3319             inline pair
3320             minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
3321             {
3322             return __comp(__b, __a) ? pair(__b, __a)
3323             : pair(__a, __b);
3324             }
3325              
3326             template
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
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
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
3443             _GLIBCXX14_CONSTEXPR
3444             inline _Tp
3445             min(initializer_list<_Tp> __l)
3446             { return *std::min_element(__l.begin(), __l.end()); }
3447              
3448             template
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
3455             _GLIBCXX14_CONSTEXPR
3456             inline _Tp
3457             max(initializer_list<_Tp> __l)
3458             { return *std::max_element(__l.begin(), __l.end()); }
3459              
3460             template
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
3467             _GLIBCXX14_CONSTEXPR
3468             inline pair<_Tp, _Tp>
3469             minmax(initializer_list<_Tp> __l)
3470             {
3471             pair __p =
3472             std::minmax_element(__l.begin(), __l.end());
3473             return std::make_pair(*__p.first, *__p.second);
3474             }
3475              
3476             template
3477             _GLIBCXX14_CONSTEXPR
3478             inline pair<_Tp, _Tp>
3479             minmax(initializer_list<_Tp> __l, _Compare __comp)
3480             {
3481             pair __p =
3482             std::minmax_element(__l.begin(), __l.end(), __comp);
3483             return std::make_pair(*__p.first, *__p.second);
3484             }
3485              
3486             template
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
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
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
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
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
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
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
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
3781             inline _InputIterator
3782 15           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 15           return std::__find_if(__first, __last,
3791 15           __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
3805             inline _InputIterator
3806 64           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 64 0         return std::__find_if(__first, __last,
3816 64 0         __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
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
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
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
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
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
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
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
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
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
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
4162             typename _UnaryOperation>
4163             _OutputIterator
4164 21           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 78 100         for (; __first != __last; ++__first, ++__result)
    100          
    0          
4175 57 50         *__result = __unary_op(*__first);
4176 21           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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
4688             inline void
4689 5           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 5 0         std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
    0          
    50          
4699 5           }
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
4717             inline void
4718 0           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 0           std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4730 0           }
4731              
4732             template
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 not less
4766             * than @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
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
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
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
4884             * ordering after calling @p stable_sort().
4885             */
4886             template
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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 */