STLdoc
STLdocumentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Modules | Functions
Sorting
Algorithms

Modules

 Set Operation
 
 Binary Search
 
 Heap
 

Functions

namespace std _GLIBCXX_VISIBILITY (default)
 

Detailed Description

Function Documentation

namespace std _GLIBCXX_VISIBILITY ( default  )

Swaps the median value of *__a, *__b and *__c to *__result

Swaps the median value of *__a, *__b and *__c under __comp to *__result

This is an overload used by find() for the Input Iterator case.

This is an overload used by find_if() for the Input Iterator case.

This is an overload used by find() for the RAI case.

This is an overload used by find_if() for the RAI case.

This is an overload used by find_if_not() for the Input Iterator case.

This is an overload used by find_if_not() for the RAI case.

Provided for stable_partition to use.

Like find_if_not(), but uses and updates a count of the remaining range length instead of comparing against an end iterator.

This is an uglified search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&) overloaded for forward iterators.

This is an uglified search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&) overloaded for random access iterators.

This is an uglified search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&, _BinaryPredicate) overloaded for forward iterators.

This is an uglified search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&, _BinaryPredicate) overloaded for random access iterators.

Find last matching subsequence in a sequence.

Parameters
__first1Start of range to search.
__last1End of range to search.
__first2Start of sequence to match.
__last2End of sequence to match.
Returns
The last iterator i in the range [__first1,__last1-(__last2-__first2)) such that *(i+N) == *(__first2+N) for each N in the range [0,__last2-__first2), or __last1 if no such iterator exists.

Searches the range [__first1,__last1) for a sub-sequence that compares equal value-by-value with the sequence given by [__first2,__last2) and returns an iterator to the __first element of the sub-sequence, or __last1 if the sub-sequence is not found. The sub-sequence will be the last such subsequence contained in [__first,__last1).

Because the sub-sequence must lie completely within the range [__first1,__last1) it must start at a position less than __last1-(__last2-__first2) where __last2-__first2 is the length of the sub-sequence. This means that the returned iterator i will be in the range [__first1,__last1-(__last2-__first2))

Find last matching subsequence in a sequence using a predicate.

Parameters
__first1Start of range to search.
__last1End of range to search.
__first2Start of sequence to match.
__last2End of sequence to match.
__compThe predicate to use.
Returns
The last iterator i in the range [__first1,__last1-(__last2-__first2)) such that predicate(*(i+N), (__first2+N)) is true for each N in the range [0,__last2-__first2), or __last1 if no such iterator exists.

Searches the range [__first1,__last1) for a sub-sequence that compares equal value-by-value with the sequence given by [__first2,__last2) using comp as a predicate and returns an iterator to the first element of the sub-sequence, or __last1 if the sub-sequence is not found. The sub-sequence will be the last such subsequence contained in [__first,__last1).

Because the sub-sequence must lie completely within the range [__first1,__last1) it must start at a position less than __last1-(__last2-__first2) where __last2-__first2 is the length of the sub-sequence. This means that the returned iterator i will be in the range [__first1,__last1-(__last2-__first2))

Copy a sequence, removing elements of a given value.

Parameters
__firstAn input iterator.
__lastAn input iterator.
__resultAn output iterator.
__valueThe value to be removed.
Returns
An iterator designating the end of the resulting sequence.

Copies each element in the range [__first,__last) not equal to __value to the range beginning at __result. remove_copy() is stable, so the relative order of elements that are copied is unchanged.

Copy a sequence, removing elements for which a predicate is true.

Parameters
__firstAn input iterator.
__lastAn input iterator.
__resultAn output iterator.
__predA predicate.
Returns
An iterator designating the end of the resulting sequence.

Copies each element in the range [__first,__last) for which __pred returns false to the range beginning at __result.

remove_copy_if() is stable, so the relative order of elements that are copied is unchanged.

Remove elements from a sequence.

Parameters
__firstAn input iterator.
__lastAn input iterator.
__valueThe value to be removed.
Returns
An iterator designating the end of the resulting sequence.

All elements equal to __value are removed from the range [__first,__last).

remove() is stable, so the relative order of elements that are not removed is unchanged.

Elements between the end of the resulting sequence and __last are still present, but their value is unspecified.

Remove elements from a sequence using a predicate.

Parameters
__firstA forward iterator.
__lastA forward iterator.
__predA predicate.
Returns
An iterator designating the end of the resulting sequence.

All elements for which __pred returns true are removed from the range [__first,__last).

remove_if() is stable, so the relative order of elements that are not removed is unchanged.

Elements between the end of the resulting sequence and __last are still present, but their value is unspecified.

Remove consecutive duplicate values from a sequence.

Parameters
__firstA forward iterator.
__lastA forward iterator.
Returns
An iterator designating the end of the resulting sequence.

Removes all but the first element from each group of consecutive values that compare equal. unique() is stable, so the relative order of elements that are not removed is unchanged. Elements between the end of the resulting sequence and __last are still present, but their value is unspecified.

Remove consecutive values from a sequence using a predicate.

Parameters
__firstA forward iterator.
__lastA forward iterator.
__binary_predA binary predicate.
Returns
An iterator designating the end of the resulting sequence.

Removes all but the first element from each group of consecutive values for which __binary_pred returns true. unique() is stable, so the relative order of elements that are not removed is unchanged. Elements between the end of the resulting sequence and __last are still present, but their value is unspecified.

This is an uglified unique_copy(_InputIterator, _InputIterator, _OutputIterator) overloaded for forward iterators and output iterator as result.

This is an uglified unique_copy(_InputIterator, _InputIterator, _OutputIterator) overloaded for input iterators and output iterator as result.

This is an uglified unique_copy(_InputIterator, _InputIterator, _OutputIterator) overloaded for input iterators and forward iterator as result.

This is an uglified unique_copy(_InputIterator, _InputIterator, _OutputIterator, _BinaryPredicate) overloaded for forward iterators and output iterator as result.

This is an uglified unique_copy(_InputIterator, _InputIterator, _OutputIterator, _BinaryPredicate) overloaded for input iterators and output iterator as result.

This is an uglified unique_copy(_InputIterator, _InputIterator, _OutputIterator, _BinaryPredicate) overloaded for input iterators and forward iterator as result.

This is an uglified reverse(_BidirectionalIterator, _BidirectionalIterator) overloaded for bidirectional iterators.

This is an uglified reverse(_BidirectionalIterator, _BidirectionalIterator) overloaded for random access iterators.

Reverse a sequence.

Parameters
__firstA bidirectional iterator.
__lastA bidirectional iterator.
Returns
reverse() returns no value.

Reverses the order of the elements in the range [__first,__last), so that the first element becomes the last etc. For every i such that 0<=i<=(__last-__first)/2), reverse() swaps *(__first+i) and *(__last-(i+1))

Copy a sequence, reversing its elements.

Parameters
__firstA bidirectional iterator.
__lastA bidirectional iterator.
__resultAn output iterator.
Returns
An iterator designating the end of the resulting sequence.

Copies the elements in the range [__first,__last) to the range [__result,__result+(__last-__first)) such that the order of the elements is reversed. For every i such that 0<=i<=(__last-__first), reverse_copy() performs the assignment *(__result+(__last-__first)-1-i) = *(__first+i). The ranges [__first,__last) and [__result,__result+(__last-__first)) must not overlap.

This is a helper function for the rotate algorithm specialized on RAIs. It returns the greatest common divisor of two integer values.

This is a helper function for the rotate algorithm.

This is a helper function for the rotate algorithm.

This is a helper function for the rotate algorithm.

Rotate the elements of a sequence.

Parameters
__firstA forward iterator.
__middleA forward iterator.
__lastA forward iterator.
Returns
Nothing.

Rotates the elements of the range [__first,__last) by (__middle - __first) positions so that the element at __middle is moved to __first, the element at __middle+1 is moved to __first+1 and so on for each element in the range [__first,__last).

This effectively swaps the ranges [__first,__middle) and [__middle,__last).

Performs *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n) for each n in the range [0,__last-__first).

Copy a sequence, rotating its elements.

Parameters
__firstA forward iterator.
__middleA forward iterator.
__lastA forward iterator.
__resultAn output iterator.
Returns
An iterator designating the end of the resulting sequence.

Copies the elements of the range [__first,__last) to the range beginning at

Returns
, rotating the copied elements by (__middle-__first) positions so that the element at __middle is moved to __result, the element at __middle+1 is moved to __result+1 and so on for each element in the range [__first,__last).

Performs *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n) for each n in the range [0,__last-__first).

This is a helper function...

This is a helper function...

This is a helper function... Requires __len != 0 and !__pred(*__first), same as __stable_partition_adaptive.

This is a helper function... Requires __first != __last and !__pred(*__first) and __len == distance(__first, __last).

!__pred(*__first) allows us to guarantee that we don't move-assign an element onto itself.

Move elements for which a predicate is true to the beginning of a sequence, preserving relative ordering.

Parameters
__firstA forward iterator.
__lastA forward iterator.
__predA predicate functor.
Returns
An iterator middle such that __pred(i) is true for each iterator i in the range [first,middle) and false for each i in the range [middle,last).

Performs the same function as partition() with the additional guarantee that the relative ordering of elements in each group is preserved, so any two elements x and y in the range [__first,__last) such that __pred(x)==__pred(y) will have the same relative ordering after calling stable_partition().

This is a helper function for the sort routines.

This is a helper function for the sort routines.

Copy the smallest elements of a sequence.

Parameters
__firstAn iterator.
__lastAnother iterator.
__result_firstA random-access iterator.
__result_lastAnother random-access iterator.
Returns
An iterator indicating the end of the resulting sequence.

Copies and sorts the smallest N values from the range [__first,__last) to the range beginning at __result_first, where the number of elements to be copied, N, is the smaller of (__last-__first) and (__result_last-__result_first). After the sort if i and j are iterators in the range [__result_first,__result_first+N) such that i precedes j then *j<*i is false. The value returned is __result_first+N.

Copy the smallest elements of a sequence using a predicate for comparison.

Parameters
__firstAn input iterator.
__lastAnother input iterator.
__result_firstA random-access iterator.
__result_lastAnother random-access iterator.
__compA comparison functor.
Returns
An iterator indicating the end of the resulting sequence.

Copies and sorts the smallest N values from the range [__first,__last) to the range beginning at result_first, where the number of elements to be copied, N, is the smaller of (__last-__first) and (__result_last-__result_first). After the sort if i and j are iterators in the range [__result_first,__result_first+N) such that i precedes j then __comp(*j,*i) is false. The value returned is __result_first+N.

This is a helper function for the sort routine.

This is a helper function for the sort routine.

This is a helper function for the sort routine.

This is a helper function for the sort routine.

This is a helper function for the sort routine.

This is a helper function for the sort routine.

This controls some aspect of the sort routines.

This is a helper function for the sort routine.

This is a helper function for the sort routine.

This is a helper function...

This is a helper function...

This is a helper function...

This is a helper function...

This is a helper function for the sort routine.

This is a helper function for the sort routine.

Finds the first position in which __val could be inserted without changing the ordering.

Parameters
__firstAn iterator.
__lastAnother iterator.
__valThe search term.
__compA functor to use for comparisons.
Returns
An iterator pointing to the first element not less than __val, or end() if every element is less than __val.

The comparison function should have the same effects on ordering as the function used for the initial sort.

Finds the last position in which __val could be inserted without changing the ordering.

Parameters
__firstAn iterator.
__lastAnother iterator.
__valThe search term.
Returns
An iterator pointing to the first element greater than __val, or end() if no elements are greater than __val.

Finds the last position in which __val could be inserted without changing the ordering.

Parameters
__firstAn iterator.
__lastAnother iterator.
__valThe search term.
__compA functor to use for comparisons.
Returns
An iterator pointing to the first element greater than __val, or end() if no elements are greater than __val.

The comparison function should have the same effects on ordering as the function used for the initial sort.

Finds the largest subrange in which __val could be inserted at any place in it without changing the ordering.

Parameters
__firstAn iterator.
__lastAnother iterator.
__valThe search term.
Returns
An pair of iterators defining the subrange.

This is equivalent to

std::make_pair(lower_bound(__first, __last, __val),
upper_bound(__first, __last, __val))

but does not actually call those functions.

Finds the largest subrange in which __val could be inserted at any place in it without changing the ordering.

Parameters
__firstAn iterator.
__lastAnother iterator.
__valThe search term.
__compA functor to use for comparisons.
Returns
An pair of iterators defining the subrange.

This is equivalent to

std::make_pair(lower_bound(__first, __last, __val, __comp),
upper_bound(__first, __last, __val, __comp))

but does not actually call those functions.

Determines whether an element exists in a range.

Parameters
__firstAn iterator.
__lastAnother iterator.
__valThe search term.
Returns
True if __val (or its equivalent) is in [__first,__last ].

Note that this does not actually return an iterator to __val. For that, use std::find or a container's specialized find member functions.

Determines whether an element exists in a range.

Parameters
__firstAn iterator.
__lastAnother iterator.
__valThe search term.
__compA functor to use for comparisons.
Returns
True if __val (or its equivalent) is in [__first,__last].

Note that this does not actually return an iterator to __val. For that, use std::find or a container's specialized find member functions.

The comparison function should have the same effects on ordering as the function used for the initial sort.

This is a helper function for the __merge_adaptive routines.

This is a helper function for the __merge_adaptive routines.

This is a helper function for the __merge_adaptive routines.

This is a helper function for the __merge_adaptive routines.

This is a helper function for the merge routines.

This is a helper function for the merge routines.

This is a helper function for the merge routines.

This is a helper function for the merge routines.

This is a helper function for the merge routines.

Merges two sorted ranges in place.

Parameters
__firstAn iterator.
__middleAnother iterator.
__lastAnother iterator.
Returns
Nothing.

Merges two sorted and consecutive ranges, [__first,__middle) and [__middle,__last), and puts the result in [__first,__last). The output will be sorted. The sort is stable, that is, for equivalent elements in the two ranges, elements from the first range will always come before elements from the second.

If enough additional memory is available, this takes (__last-__first)-1 comparisons. Otherwise an NlogN algorithm is used, where N is distance(__first,__last).

Merges two sorted ranges in place.

Parameters
__firstAn iterator.
__middleAnother iterator.
__lastAnother iterator.
__compA functor to use for comparisons.
Returns
Nothing.

Merges two sorted and consecutive ranges, [__first,__middle) and [middle,last), and puts the result in [__first,__last). The output will be sorted. The sort is stable, that is, for equivalent elements in the two ranges, elements from the first range will always come before elements from the second.

If enough additional memory is available, this takes (__last-__first)-1 comparisons. Otherwise an NlogN algorithm is used, where N is distance(__first,__last).

The comparison function should have the same effects on ordering as the function used for the initial sort.

This is a helper function for the __merge_sort_loop routines.

This is a helper function for the __merge_sort_loop routines.

This is a helper function for the stable sorting routines.

This is a helper function for the stable sorting routines.

Determines whether all elements of a sequence exists in a range.

Parameters
__first1Start of search range.
__last1End of search range.
__first2Start of sequence
__last2End of sequence.
Returns
True if each element in [__first2,__last2) is contained in order within [__first1,__last1). False otherwise.

This operation expects both [__first1,__last1) and [__first2,__last2) to be sorted. Searches for the presence of each element in [__first2,__last2) within [__first1,__last1). The iterators over each range only move forward, so this is a linear algorithm. If an element in [__first2,__last2) is not found before the search iterator reaches __last2, false is returned.

Determines whether all elements of a sequence exists in a range using comparison.

Parameters
__first1Start of search range.
__last1End of search range.
__first2Start of sequence
__last2End of sequence.
__compComparison function to use.
Returns
True if each element in [__first2,__last2) is contained in order within [__first1,__last1) according to comp. False otherwise.

This operation expects both [__first1,__last1) and [__first2,__last2) to be sorted. Searches for the presence of each element in [__first2,__last2) within [__first1,__last1), using comp to decide. The iterators over each range only move forward, so this is a linear algorithm. If an element in [__first2,__last2) is not found before the search iterator reaches __last2, false is returned.

Permute range into the next dictionary ordering.

Parameters
__firstStart of range.
__lastEnd of range.
Returns
False if wrapped to first permutation, true otherwise.

Treats all permutations of the range as a set of dictionary sorted sequences. Permutes the current sequence into the next one of this set. Returns true if there are more sequences to generate. If the sequence is the largest of the set, the smallest is generated and false returned.

Permute range into the next dictionary ordering using comparison functor.

Parameters
__firstStart of range.
__lastEnd of range.
__compA comparison functor.
Returns
False if wrapped to first permutation, true otherwise.

Treats all permutations of the range [__first,__last) as a set of dictionary sorted sequences ordered by __comp. Permutes the current sequence into the next one of this set. Returns true if there are more sequences to generate. If the sequence is the largest of the set, the smallest is generated and false returned.

Permute range into the previous dictionary ordering.

Parameters
__firstStart of range.
__lastEnd of range.
Returns
False if wrapped to last permutation, true otherwise.

Treats all permutations of the range as a set of dictionary sorted sequences. Permutes the current sequence into the previous one of this set. Returns true if there are more sequences to generate. If the sequence is the smallest of the set, the largest is generated and false returned.

Permute range into the previous dictionary ordering using comparison functor.

Parameters
__firstStart of range.
__lastEnd of range.
__compA comparison functor.
Returns
False if wrapped to last permutation, true otherwise.

Treats all permutations of the range [__first,__last) as a set of dictionary sorted sequences ordered by __comp. Permutes the current sequence into the previous one of this set. Returns true if there are more sequences to generate. If the sequence is the smallest of the set, the largest is generated and false returned.

Copy a sequence, replacing each element of one value with another value.

Parameters
__firstAn input iterator.
__lastAn input iterator.
__resultAn output iterator.
__old_valueThe value to be replaced.
__new_valueThe replacement value.
Returns
The end of the output sequence, result+(last-first).

Copies each element in the input range [__first,__last) to the output range [__result,__result+(__last-__first)) replacing elements equal to __old_value with __new_value.

Copy a sequence, replacing each value for which a predicate returns true with another value.

Parameters
__firstAn input iterator.
__lastAn input iterator.
__resultAn output iterator.
__predA predicate.
__new_valueThe replacement value.
Returns
The end of the output sequence, __result+(__last-__first).

Copies each element in the range [__first,__last) to the range [__result,__result+(__last-__first)) replacing elements for which __pred returns true with __new_value.

Apply a function to every element of a sequence.

Parameters
__firstAn input iterator.
__lastAn input iterator.
__fA unary function object.
Returns
__f (std::move(__f) in C++0x).

Applies the function object __f to each element in the range [first,last). __f must not modify the order of the sequence. If __f has a return value it is ignored.

Find the first occurrence of a value in a sequence.

Parameters
__firstAn input iterator.
__lastAn input iterator.
__valThe value to find.
Returns
The first iterator i in the range [__first,__last) such that *i == __val, or __last if no such iterator exists.

Find the first element in a sequence for which a predicate is true.

Parameters
__firstAn input iterator.
__lastAn input iterator.
__predA predicate.
Returns
The first iterator i in the range [__first,__last) such that __pred(*i) is true, or __last if no such iterator exists.

Find element from a set in a sequence.

Parameters
__first1Start of range to search.
__last1End of range to search.
__first2Start of match candidates.
__last2End of match candidates.
Returns
The first iterator i in the range [__first1,__last1) such that *i == *(i2) such that i2 is an iterator in [__first2,__last2), or __last1 if no such iterator exists.

Searches the range [__first1,__last1) for an element that is equal to some element in the range [__first2,__last2). If found, returns an iterator in the range [__first1,__last1), otherwise returns __last1.

Find element from a set in a sequence using a predicate.

Parameters
__first1Start of range to search.
__last1End of range to search.
__first2Start of match candidates.
__last2End of match candidates.
__compPredicate to use.
Returns
The first iterator i in the range [__first1,__last1) such that comp(*i, *(i2)) is true and i2 is an iterator in [__first2,__last2), or __last1 if no such iterator exists.

Searches the range [__first1,__last1) for an element that is equal to some element in the range [__first2,__last2). If found, returns an iterator in the range [__first1,__last1), otherwise returns __last1.

Find two adjacent values in a sequence that are equal.

Parameters
__firstA forward iterator.
__lastA forward iterator.
Returns
The first iterator i such that i and i+1 are both valid iterators in [__first,__last) and such that *i == *(i+1), or __last if no such iterator exists.

Find two adjacent values in a sequence using a predicate.

Parameters
__firstA forward iterator.
__lastA forward iterator.
__binary_predA binary predicate.
Returns
The first iterator i such that i and i+1 are both valid iterators in [__first,__last) and such that __binary_pred(i,(i+1)) is true, or __last if no such iterator exists.

Count the number of copies of a value in a sequence.

Parameters
__firstAn input iterator.
__lastAn input iterator.
__valueThe value to be counted.
Returns
The number of iterators i in the range [__first,__last) for which *i == __value

Count the elements of a sequence for which a predicate is true.

Parameters
__firstAn input iterator.
__lastAn input iterator.
__predA predicate.
Returns
The number of iterators i in the range [__first,__last) for which __pred(*i) is true.

Search a sequence for a matching sub-sequence.

Parameters
__first1A forward iterator.
__last1A forward iterator.
__first2A forward iterator.
__last2A forward iterator.
Returns
The first iterator i in the range [__first1,__last1-(__last2-__first2)) such that *(i+N) == *(__first2+N) for each N in the range [0,__last2-__first2), or __last1 if no such iterator exists.

Searches the range [__first1,__last1) for a sub-sequence that compares equal value-by-value with the sequence given by [__first2,__last2) and returns an iterator to the first element of the sub-sequence, or __last1 if the sub-sequence is not found.

Because the sub-sequence must lie completely within the range [__first1,__last1) it must start at a position less than __last1-(__last2-__first2) where __last2-__first2 is the length of the sub-sequence.

This means that the returned iterator i will be in the range [__first1,__last1-(__last2-__first2))

Search a sequence for a matching sub-sequence using a predicate.

Parameters
__first1A forward iterator.
__last1A forward iterator.
__first2A forward iterator.
__last2A forward iterator.
__predicateA binary predicate.
Returns
The first iterator i in the range [__first1,__last1-(__last2-__first2)) such that __predicate(*(i+N),*(__first2+N)) is true for each N in the range [0,__last2-__first2), or __last1 if no such iterator exists.

Searches the range [__first1,__last1) for a sub-sequence that compares equal value-by-value with the sequence given by [__first2,__last2), using __predicate to determine equality, and returns an iterator to the first element of the sub-sequence, or __last1 if no such iterator exists.

See Also
search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)

Search a sequence for a number of consecutive values.

Parameters
__firstA forward iterator.
__lastA forward iterator.
__countThe number of consecutive values.
__valThe value to find.
Returns
The first iterator i in the range [__first,__last-__count) such that *(i+N) == __val for each N in the range [0,__count), or __last if no such iterator exists.

Searches the range [__first,__last) for count consecutive elements equal to __val.

Search a sequence for a number of consecutive values using a predicate.

Parameters
__firstA forward iterator.
__lastA forward iterator.
__countThe number of consecutive values.
__valThe value to find.
__binary_predA binary predicate.
Returns
The first iterator i in the range [__first,__last-__count) such that __binary_pred(*(i+N),__val) is true for each N in the range [0,__count), or __last if no such iterator exists.

Searches the range [__first,__last) for __count consecutive elements for which the predicate returns true.

Perform an operation on a sequence.

Parameters
__firstAn input iterator.
__lastAn input iterator.
__resultAn output iterator.
__unary_opA unary operator.
Returns
An output iterator equal to __result+(__last-__first).

Applies the operator to each element in the input range and assigns the results to successive elements of the output sequence. Evaluates *(__result+N)=unary_op(*(__first+N)) for each N in the range [0,__last-__first).

unary_op must not alter its argument.

Perform an operation on corresponding elements of two sequences.

Parameters
__first1An input iterator.
__last1An input iterator.
__first2An input iterator.
__resultAn output iterator.
__binary_opA binary operator.
Returns
An output iterator equal to result+(last-first).

Applies the operator to the corresponding elements in the two input ranges and assigns the results to successive elements of the output sequence. Evaluates *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each N in the range [0,__last1-__first1).

binary_op must not alter either of its arguments.

Replace each occurrence of one value in a sequence with another value.

Parameters
__firstA forward iterator.
__lastA forward iterator.
__old_valueThe value to be replaced.
__new_valueThe replacement value.
Returns
replace() returns no value.

For each iterator i in the range [__first,__last) if *i == __old_value then the assignment *i = __new_value is performed.

Replace each value in a sequence for which a predicate returns true with another value.

Parameters
__firstA forward iterator.
__lastA forward iterator.
__predA predicate.
__new_valueThe replacement value.
Returns
replace_if() returns no value.

For each iterator i in the range [__first,__last) if __pred(*i) is true then the assignment *i = __new_value is performed.

Assign the result of a function object to each value in a sequence.

Parameters
__firstA forward iterator.
__lastA forward iterator.
__genA function object taking no arguments and returning std::iterator_traits<_ForwardIterator>::value_type
Returns
generate() returns no value.

Performs the assignment *i = __gen() for each i in the range [__first,__last).

Assign the result of a function object to each value in a sequence.

Parameters
__firstA forward iterator.
__nThe length of the sequence.
__genA function object taking no arguments and returning std::iterator_traits<_ForwardIterator>::value_type
Returns
The end of the sequence, __first+__n

Performs the assignment *i = __gen() for each i in the range [__first,__first+__n).

_GLIBCXX_RESOLVE_LIB_DEFECTS DR 865. More algorithms that throw away information

Copy a sequence, removing consecutive duplicate values.

Parameters
__firstAn input iterator.
__lastAn input iterator.
__resultAn output iterator.
Returns
An iterator designating the end of the resulting sequence.

Copies each element in the range [__first,__last) to the range beginning at __result, except that only the first element is copied from groups of consecutive elements that compare equal. unique_copy() is stable, so the relative order of elements that are copied is unchanged.

_GLIBCXX_RESOLVE_LIB_DEFECTS DR 241. Does unique_copy() require CopyConstructible and Assignable?

_GLIBCXX_RESOLVE_LIB_DEFECTS DR 538. 241 again: Does unique_copy() require CopyConstructible and Assignable?

Copy a sequence, removing consecutive values using a predicate.

Parameters
__firstAn input iterator.
__lastAn input iterator.
__resultAn output iterator.
__binary_predA binary predicate.
Returns
An iterator designating the end of the resulting sequence.

Copies each element in the range [__first,__last) to the range beginning at __result, except that only the first element is copied from groups of consecutive elements for which __binary_pred returns true. unique_copy() is stable, so the relative order of elements that are copied is unchanged.

_GLIBCXX_RESOLVE_LIB_DEFECTS DR 241. Does unique_copy() require CopyConstructible and Assignable?

Randomly shuffle the elements of a sequence.

Parameters
__firstA forward iterator.
__lastA forward iterator.
Returns
Nothing.

Reorder the elements in the range [__first,__last) using a random distribution, so that every possible ordering of the sequence is equally likely.

Shuffle the elements of a sequence using a random number generator.

Parameters
__firstA forward iterator.
__lastA forward iterator.
__randThe RNG functor or function.
Returns
Nothing.

Reorders the elements in the range [__first,__last) using __rand to provide a random distribution. Calling __rand(N) for a positive integer N should return a randomly chosen integer from the range [0,N).

Move elements for which a predicate is true to the beginning of a sequence.

Parameters
__firstA forward iterator.
__lastA forward iterator.
__predA predicate functor.
Returns
An iterator middle such that __pred(i) is true for each iterator i in the range [__first,middle) and false for each i in the range [middle,__last).

__pred must not modify its operand. partition() does not preserve the relative ordering of elements in each group, use stable_partition() if this is needed.

Sort the smallest elements of a sequence.

Parameters
__firstAn iterator.
__middleAnother iterator.
__lastAnother iterator.
Returns
Nothing.

Sorts the smallest (__middle-__first) elements in the range [first,last) and moves them to the range [__first,__middle). The order of the remaining elements in the range [__middle,__last) is undefined. After the sort if i and j are iterators in the range [__first,__middle) such that i precedes j and k is an iterator in the range [__middle,__last) then *j<*i and *k<*i are both false.

Sort the smallest elements of a sequence using a predicate for comparison.

Parameters
__firstAn iterator.
__middleAnother iterator.
__lastAnother iterator.
__compA comparison functor.
Returns
Nothing.

Sorts the smallest (__middle-__first) elements in the range [__first,__last) and moves them to the range [__first,__middle). The order of the remaining elements in the range [__middle,__last) is undefined. After the sort if i and j are iterators in the range [__first,__middle) such that i precedes j and k is an iterator in the range [__middle,__last) then *__comp(j,*i) and __comp(*k,*i) are both false.

Sort a sequence just enough to find a particular position.

Parameters
__firstAn iterator.
__nthAnother iterator.
__lastAnother iterator.
Returns
Nothing.

Rearranges the elements in the range [__first,__last) so that *__nth is the same element that would have been in that position had the whole sequence been sorted. The elements either side of *__nth are not completely sorted, but for any iterator i in the range [__first,__nth) and any iterator j in the range [__nth,__last) it holds that *j < *i is false.

Sort a sequence just enough to find a particular position using a predicate for comparison.

Parameters
__firstAn iterator.
__nthAnother iterator.
__lastAnother iterator.
__compA comparison functor.
Returns
Nothing.

Rearranges the elements in the range [__first,__last) so that *__nth is the same element that would have been in that position had the whole sequence been sorted. The elements either side of *__nth are not completely sorted, but for any iterator i in the range [__first,__nth) and any iterator j in the range [__nth,__last) it holds that __comp(*j,*i) is false.

Sort the elements of a sequence.

Parameters
__firstAn iterator.
__lastAnother iterator.
Returns
Nothing.

Sorts the elements in the range [__first,__last) in ascending order, such that for each iterator i in the range [__first,__last-1), *(i+1)<*i is false.

The relative ordering of equivalent elements is not preserved, use stable_sort() if this is needed.

Sort the elements of a sequence using a predicate for comparison.

Parameters
__firstAn iterator.
__lastAnother iterator.
__compA comparison functor.
Returns
Nothing.

Sorts the elements in the range [__first,__last) in ascending order, such that __comp(*(i+1),*i) is false for every iterator i in the range [__first,__last-1).

The relative ordering of equivalent elements is not preserved, use stable_sort() if this is needed.

Merges two sorted ranges.

Parameters
__first1An iterator.
__first2Another iterator.
__last1Another iterator.
__last2Another iterator.
__resultAn iterator pointing to the end of the merged range.
Returns
An iterator pointing to the first element not less than val.

Merges the ranges [__first1,__last1) and [__first2,__last2) into the sorted range [__result, __result + (__last1-__first1) + (__last2-__first2)). Both input ranges must be sorted, and the output range must not overlap with either of the input ranges. The sort is stable, that is, for equivalent elements in the two ranges, elements from the first range will always come before elements from the second.

Merges two sorted ranges.

Parameters
__first1An iterator.
__first2Another iterator.
__last1Another iterator.
__last2Another iterator.
__resultAn iterator pointing to the end of the merged range.
__compA functor to use for comparisons.
Returns
An iterator pointing to the first element "not less than" val.

Merges the ranges [__first1,__last1) and [__first2,__last2) into the sorted range [__result, __result + (__last1-__first1) + (__last2-__first2)). Both input ranges must be sorted, and the output range must not overlap with either of the input ranges. The sort is stable, that is, for equivalent elements in the two ranges, elements from the first range will always come before elements from the second.

The comparison function should have the same effects on ordering as the function used for the initial sort.

Sort the elements of a sequence, preserving the relative order of equivalent elements.

Parameters
__firstAn iterator.
__lastAnother iterator.
Returns
Nothing.

Sorts the elements in the range [__first,__last) in ascending order, such that for each iterator i in the range [__first,__last-1), *(i+1)<*i is false.

The relative ordering of equivalent elements is preserved, so any two elements x and y in the range [__first,__last) such that x<y is false and y<x is false will have the same relative ordering after calling stable_sort().

Sort the elements of a sequence using a predicate for comparison, preserving the relative order of equivalent elements.

Parameters
__firstAn iterator.
__lastAnother iterator.
__compA comparison functor.
Returns
Nothing.

Sorts the elements in the range [__first,__last) in ascending order, such that for each iterator i in the range [__first,__last-1), __comp(*(i+1),*i) is false.

The relative ordering of equivalent elements is preserved, so any two elements x and y in the range [__first,__last) such that __comp(x,y) is false and __comp(y,x) is false will have the same relative ordering after calling stable_sort().

Return the union of two sorted ranges.

Parameters
__first1Start of first range.
__last1End of first range.
__first2Start of second range.
__last2End of second range.
Returns
End of the output range.

This operation iterates over both ranges, copying elements present in each range in order to the output range. Iterators increment for each range. When the current element of one range is less than the other, that element is copied and the iterator advanced. If an element is contained in both ranges, the element from the first range is copied and both ranges advance. The output range may not overlap either input range.

Return the union of two sorted ranges using a comparison functor.

Parameters
__first1Start of first range.
__last1End of first range.
__first2Start of second range.
__last2End of second range.
__compThe comparison functor.
Returns
End of the output range.

This operation iterates over both ranges, copying elements present in each range in order to the output range. Iterators increment for each range. When the current element of one range is less than the other according to __comp, that element is copied and the iterator advanced. If an equivalent element according to __comp is contained in both ranges, the element from the first range is copied and both ranges advance. The output range may not overlap either input range.

Return the intersection of two sorted ranges.

Parameters
__first1Start of first range.
__last1End of first range.
__first2Start of second range.
__last2End of second range.
Returns
End of the output range.

This operation iterates over both ranges, copying elements present in both ranges in order to the output range. Iterators increment for each range. When the current element of one range is less than the other, that iterator advances. If an element is contained in both ranges, the element from the first range is copied and both ranges advance. The output range may not overlap either input range.

Return the intersection of two sorted ranges using comparison functor.

Parameters
__first1Start of first range.
__last1End of first range.
__first2Start of second range.
__last2End of second range.
__compThe comparison functor.
Returns
End of the output range.

This operation iterates over both ranges, copying elements present in both ranges in order to the output range. Iterators increment for each range. When the current element of one range is less than the other according to __comp, that iterator advances. If an element is contained in both ranges according to __comp, the element from the first range is copied and both ranges advance. The output range may not overlap either input range.

Return the difference of two sorted ranges.

Parameters
__first1Start of first range.
__last1End of first range.
__first2Start of second range.
__last2End of second range.
Returns
End of the output range.

This operation iterates over both ranges, copying elements present in the first range but not the second in order to the output range. Iterators increment for each range. When the current element of the first range is less than the second, that element is copied and the iterator advances. If the current element of the second range is less, the iterator advances, but no element is copied. If an element is contained in both ranges, no elements are copied and both ranges advance. The output range may not overlap either input range.

Return the difference of two sorted ranges using comparison functor.

Parameters
__first1Start of first range.
__last1End of first range.
__first2Start of second range.
__last2End of second range.
__compThe comparison functor.
Returns
End of the output range.

This operation iterates over both ranges, copying elements present in the first range but not the second in order to the output range. Iterators increment for each range. When the current element of the first range is less than the second according to __comp, that element is copied and the iterator advances. If the current element of the second range is less, no element is copied and the iterator advances. If an element is contained in both ranges according to __comp, no elements are copied and both ranges advance. The output range may not overlap either input range.

Return the symmetric difference of two sorted ranges.

Parameters
__first1Start of first range.
__last1End of first range.
__first2Start of second range.
__last2End of second range.
Returns
End of the output range.

This operation iterates over both ranges, copying elements present in one range but not the other in order to the output range. Iterators increment for each range. When the current element of one range is less than the other, that element is copied and the iterator advances. If an element is contained in both ranges, no elements are copied and both ranges advance. The output range may not overlap either input range.

Return the symmetric difference of two sorted ranges using comparison functor.

Parameters
__first1Start of first range.
__last1End of first range.
__first2Start of second range.
__last2End of second range.
__compThe comparison functor.
Returns
End of the output range.

This operation iterates over both ranges, copying elements present in one range but not the other in order to the output range. Iterators increment for each range. When the current element of one range is less than the other according to comp, that element is copied and the iterator advances. If an element is contained in both ranges according to __comp, no elements are copied and both ranges advance. The output range may not overlap either input range.

Return the minimum element in a range.

Parameters
__firstStart of range.
__lastEnd of range.
Returns
Iterator referencing the first instance of the smallest value.

Return the minimum element in a range using comparison functor.

Parameters
__firstStart of range.
__lastEnd of range.
__compComparison functor.
Returns
Iterator referencing the first instance of the smallest value according to __comp.

Return the maximum element in a range.

Parameters
__firstStart of range.
__lastEnd of range.
Returns
Iterator referencing the first instance of the largest value.

Return the maximum element in a range using comparison functor.

Parameters
__firstStart of range.
__lastEnd of range.
__compComparison functor.
Returns
Iterator referencing the first instance of the largest value according to __comp.
72 {
73 _GLIBCXX_BEGIN_NAMESPACE_VERSION
74 
76  template<typename _Iterator>
77  void
78  __move_median_to_first(_Iterator __result, _Iterator __a,
79  _Iterator __b, _Iterator __c)
80  {
81  // concept requirements
82  __glibcxx_function_requires(_LessThanComparableConcept<
83  typename iterator_traits<_Iterator>::value_type>)
84 
85  if (*__a < *__b)
86  {
87  if (*__b < *__c)
88  std::iter_swap(__result, __b);
89  else if (*__a < *__c)
90  std::iter_swap(__result, __c);
91  else
92  std::iter_swap(__result, __a);
93  }
94  else if (*__a < *__c)
95  std::iter_swap(__result, __a);
96  else if (*__b < *__c)
97  std::iter_swap(__result, __c);
98  else
99  std::iter_swap(__result, __b);
100  }
101 
103  template<typename _Iterator, typename _Compare>
104  void
105  __move_median_to_first(_Iterator __result, _Iterator __a,
106  _Iterator __b, _Iterator __c,
107  _Compare __comp)
108  {
109  // concept requirements
110  __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
111  typename iterator_traits<_Iterator>::value_type,
112  typename iterator_traits<_Iterator>::value_type>)
113 
114  if (__comp(*__a, *__b))
115  {
116  if (__comp(*__b, *__c))
117  std::iter_swap(__result, __b);
118  else if (__comp(*__a, *__c))
119  std::iter_swap(__result, __c);
120  else
121  std::iter_swap(__result, __a);
122  }
123  else if (__comp(*__a, *__c))
124  std::iter_swap(__result, __a);
125  else if (__comp(*__b, *__c))
126  std::iter_swap(__result, __c);
127  else
128  std::iter_swap(__result, __b);
129  }
130 
131  // for_each
132 
134  template<typename _InputIterator, typename _Tp>
135  inline _InputIterator
136  __find(_InputIterator __first, _InputIterator __last,
137  const _Tp& __val, input_iterator_tag)
138  {
139  while (__first != __last && !(*__first == __val))
140  ++__first;
141  return __first;
142  }
143 
145  template<typename _InputIterator, typename _Predicate>
146  inline _InputIterator
147  __find_if(_InputIterator __first, _InputIterator __last,
148  _Predicate __pred, input_iterator_tag)
149  {
150  while (__first != __last && !bool(__pred(*__first)))
151  ++__first;
152  return __first;
153  }
154 
156  template<typename _RandomAccessIterator, typename _Tp>
157  _RandomAccessIterator
158  __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
159  const _Tp& __val, random_access_iterator_tag)
160  {
161  typename iterator_traits<_RandomAccessIterator>::difference_type
162  __trip_count = (__last - __first) >> 2;
163 
164  for (; __trip_count > 0; --__trip_count)
165  {
166  if (*__first == __val)
167  return __first;
168  ++__first;
169 
170  if (*__first == __val)
171  return __first;
172  ++__first;
173 
174  if (*__first == __val)
175  return __first;
176  ++__first;
177 
178  if (*__first == __val)
179  return __first;
180  ++__first;
181  }
182 
183  switch (__last - __first)
184  {
185  case 3:
186  if (*__first == __val)
187  return __first;
188  ++__first;
189  case 2:
190  if (*__first == __val)
191  return __first;
192  ++__first;
193  case 1:
194  if (*__first == __val)
195  return __first;
196  ++__first;
197  case 0:
198  default:
199  return __last;
200  }
201  }
202 
204  template<typename _RandomAccessIterator, typename _Predicate>
205  _RandomAccessIterator
206  __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
207  _Predicate __pred, random_access_iterator_tag)
208  {
209  typename iterator_traits<_RandomAccessIterator>::difference_type
210  __trip_count = (__last - __first) >> 2;
211 
212  for (; __trip_count > 0; --__trip_count)
213  {
214  if (__pred(*__first))
215  return __first;
216  ++__first;
217 
218  if (__pred(*__first))
219  return __first;
220  ++__first;
221 
222  if (__pred(*__first))
223  return __first;
224  ++__first;
225 
226  if (__pred(*__first))
227  return __first;
228  ++__first;
229  }
230 
231  switch (__last - __first)
232  {
233  case 3:
234  if (__pred(*__first))
235  return __first;
236  ++__first;
237  case 2:
238  if (__pred(*__first))
239  return __first;
240  ++__first;
241  case 1:
242  if (__pred(*__first))
243  return __first;
244  ++__first;
245  case 0:
246  default:
247  return __last;
248  }
249  }
250 
252  template<typename _InputIterator, typename _Predicate>
253  inline _InputIterator
254  __find_if_not(_InputIterator __first, _InputIterator __last,
255  _Predicate __pred, input_iterator_tag)
256  {
257  while (__first != __last && bool(__pred(*__first)))
258  ++__first;
259  return __first;
260  }
261 
263  template<typename _RandomAccessIterator, typename _Predicate>
264  _RandomAccessIterator
265  __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last,
266  _Predicate __pred, random_access_iterator_tag)
267  {
268  typename iterator_traits<_RandomAccessIterator>::difference_type
269  __trip_count = (__last - __first) >> 2;
270 
271  for (; __trip_count > 0; --__trip_count)
272  {
273  if (!bool(__pred(*__first)))
274  return __first;
275  ++__first;
276 
277  if (!bool(__pred(*__first)))
278  return __first;
279  ++__first;
280 
281  if (!bool(__pred(*__first)))
282  return __first;
283  ++__first;
284 
285  if (!bool(__pred(*__first)))
286  return __first;
287  ++__first;
288  }
289 
290  switch (__last - __first)
291  {
292  case 3:
293  if (!bool(__pred(*__first)))
294  return __first;
295  ++__first;
296  case 2:
297  if (!bool(__pred(*__first)))
298  return __first;
299  ++__first;
300  case 1:
301  if (!bool(__pred(*__first)))
302  return __first;
303  ++__first;
304  case 0:
305  default:
306  return __last;
307  }
308  }
309 
311  template<typename _InputIterator, typename _Predicate>
312  inline _InputIterator
313  __find_if_not(_InputIterator __first, _InputIterator __last,
314  _Predicate __pred)
315  {
316  return std::__find_if_not(__first, __last, __pred,
317  std::__iterator_category(__first));
318  }
319 
323  template<typename _InputIterator, typename _Predicate, typename _Distance>
324  _InputIterator
325  __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
326  {
327  for (; __len; --__len, ++__first)
328  if (!bool(__pred(*__first)))
329  break;
330  return __first;
331  }
332 
333  // set_difference
334  // set_intersection
335  // set_symmetric_difference
336  // set_union
337  // for_each
338  // find
339  // find_if
340  // find_first_of
341  // adjacent_find
342  // count
343  // count_if
344  // search
345 
351  template<typename _ForwardIterator, typename _Integer, typename _Tp>
352  _ForwardIterator
353  __search_n(_ForwardIterator __first, _ForwardIterator __last,
354  _Integer __count, const _Tp& __val,
355  std::forward_iterator_tag)
356  {
357  __first = _GLIBCXX_STD_A::find(__first, __last, __val);
358  while (__first != __last)
359  {
360  typename iterator_traits<_ForwardIterator>::difference_type
361  __n = __count;
362  _ForwardIterator __i = __first;
363  ++__i;
364  while (__i != __last && __n != 1 && *__i == __val)
365  {
366  ++__i;
367  --__n;
368  }
369  if (__n == 1)
370  return __first;
371  if (__i == __last)
372  return __last;
373  __first = _GLIBCXX_STD_A::find(++__i, __last, __val);
374  }
375  return __last;
376  }
377 
383  template<typename _RandomAccessIter, typename _Integer, typename _Tp>
384  _RandomAccessIter
385  __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
386  _Integer __count, const _Tp& __val,
387  std::random_access_iterator_tag)
388  {
389 
390  typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
391  _DistanceType;
392 
393  _DistanceType __tailSize = __last - __first;
394  _DistanceType __remainder = __count;
395 
396  while (__remainder <= __tailSize) // the main loop...
397  {
398  __first += __remainder;
399  __tailSize -= __remainder;
400  // __first here is always pointing to one past the last element of
401  // next possible match.
402  _RandomAccessIter __backTrack = __first;
403  while (*--__backTrack == __val)
404  {
405  if (--__remainder == 0)
406  return (__first - __count); // Success
407  }
408  __remainder = __count + 1 - (__first - __backTrack);
409  }
410  return __last; // Failure
411  }
412 
413  // search_n
414 
421  template<typename _ForwardIterator, typename _Integer, typename _Tp,
422  typename _BinaryPredicate>
423  _ForwardIterator
424  __search_n(_ForwardIterator __first, _ForwardIterator __last,
425  _Integer __count, const _Tp& __val,
426  _BinaryPredicate __binary_pred, std::forward_iterator_tag)
427  {
428  while (__first != __last && !bool(__binary_pred(*__first, __val)))
429  ++__first;
430 
431  while (__first != __last)
432  {
433  typename iterator_traits<_ForwardIterator>::difference_type
434  __n = __count;
435  _ForwardIterator __i = __first;
436  ++__i;
437  while (__i != __last && __n != 1 && bool(__binary_pred(*__i, __val)))
438  {
439  ++__i;
440  --__n;
441  }
442  if (__n == 1)
443  return __first;
444  if (__i == __last)
445  return __last;
446  __first = ++__i;
447  while (__first != __last
448  && !bool(__binary_pred(*__first, __val)))
449  ++__first;
450  }
451  return __last;
452  }
453 
460  template<typename _RandomAccessIter, typename _Integer, typename _Tp,
461  typename _BinaryPredicate>
462  _RandomAccessIter
463  __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
464  _Integer __count, const _Tp& __val,
465  _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
466  {
467 
468  typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
469  _DistanceType;
470 
471  _DistanceType __tailSize = __last - __first;
472  _DistanceType __remainder = __count;
473 
474  while (__remainder <= __tailSize) // the main loop...
475  {
476  __first += __remainder;
477  __tailSize -= __remainder;
478  // __first here is always pointing to one past the last element of
479  // next possible match.
480  _RandomAccessIter __backTrack = __first;
481  while (__binary_pred(*--__backTrack, __val))
482  {
483  if (--__remainder == 0)
484  return (__first - __count); // Success
485  }
486  __remainder = __count + 1 - (__first - __backTrack);
487  }
488  return __last; // Failure
489  }
490 
491  // find_end for forward iterators.
492  template<typename _ForwardIterator1, typename _ForwardIterator2>
493  _ForwardIterator1
494  __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
495  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
496  forward_iterator_tag, forward_iterator_tag)
497  {
498  if (__first2 == __last2)
499  return __last1;
500  else
501  {
502  _ForwardIterator1 __result = __last1;
503  while (1)
504  {
505  _ForwardIterator1 __new_result
506  = _GLIBCXX_STD_A::search(__first1, __last1, __first2, __last2);
507  if (__new_result == __last1)
508  return __result;
509  else
510  {
511  __result = __new_result;
512  __first1 = __new_result;
513  ++__first1;
514  }
515  }
516  }
517  }
518 
519  template<typename _ForwardIterator1, typename _ForwardIterator2,
520  typename _BinaryPredicate>
521  _ForwardIterator1
522  __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
523  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
524  forward_iterator_tag, forward_iterator_tag,
525  _BinaryPredicate __comp)
526  {
527  if (__first2 == __last2)
528  return __last1;
529  else
530  {
531  _ForwardIterator1 __result = __last1;
532  while (1)
533  {
534  _ForwardIterator1 __new_result
535  = _GLIBCXX_STD_A::search(__first1, __last1, __first2,
536  __last2, __comp);
537  if (__new_result == __last1)
538  return __result;
539  else
540  {
541  __result = __new_result;
542  __first1 = __new_result;
543  ++__first1;
544  }
545  }
546  }
547  }
548 
549  // find_end for bidirectional iterators (much faster).
550  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
551  _BidirectionalIterator1
552  __find_end(_BidirectionalIterator1 __first1,
553  _BidirectionalIterator1 __last1,
554  _BidirectionalIterator2 __first2,
555  _BidirectionalIterator2 __last2,
556  bidirectional_iterator_tag, bidirectional_iterator_tag)
557  {
558  // concept requirements
559  __glibcxx_function_requires(_BidirectionalIteratorConcept<
560  _BidirectionalIterator1>)
561  __glibcxx_function_requires(_BidirectionalIteratorConcept<
562  _BidirectionalIterator2>)
563 
564  typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
565  typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
566 
567  _RevIterator1 __rlast1(__first1);
568  _RevIterator2 __rlast2(__first2);
569  _RevIterator1 __rresult = _GLIBCXX_STD_A::search(_RevIterator1(__last1),
570  __rlast1,
571  _RevIterator2(__last2),
572  __rlast2);
573 
574  if (__rresult == __rlast1)
575  return __last1;
576  else
577  {
578  _BidirectionalIterator1 __result = __rresult.base();
579  std::advance(__result, -std::distance(__first2, __last2));
580  return __result;
581  }
582  }
583 
584  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
585  typename _BinaryPredicate>
586  _BidirectionalIterator1
587  __find_end(_BidirectionalIterator1 __first1,
588  _BidirectionalIterator1 __last1,
589  _BidirectionalIterator2 __first2,
590  _BidirectionalIterator2 __last2,
591  bidirectional_iterator_tag, bidirectional_iterator_tag,
592  _BinaryPredicate __comp)
593  {
594  // concept requirements
595  __glibcxx_function_requires(_BidirectionalIteratorConcept<
596  _BidirectionalIterator1>)
597  __glibcxx_function_requires(_BidirectionalIteratorConcept<
598  _BidirectionalIterator2>)
599 
600  typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
601  typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
602 
603  _RevIterator1 __rlast1(__first1);
604  _RevIterator2 __rlast2(__first2);
605  _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
606  _RevIterator2(__last2), __rlast2,
607  __comp);
608 
609  if (__rresult == __rlast1)
610  return __last1;
611  else
612  {
613  _BidirectionalIterator1 __result = __rresult.base();
614  std::advance(__result, -std::distance(__first2, __last2));
615  return __result;
616  }
617  }
618 
645  template<typename _ForwardIterator1, typename _ForwardIterator2>
646  inline _ForwardIterator1
647  find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
648  _ForwardIterator2 __first2, _ForwardIterator2 __last2)
649  {
650  // concept requirements
651  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
652  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
653  __glibcxx_function_requires(_EqualOpConcept<
654  typename iterator_traits<_ForwardIterator1>::value_type,
655  typename iterator_traits<_ForwardIterator2>::value_type>)
656  __glibcxx_requires_valid_range(__first1, __last1);
657  __glibcxx_requires_valid_range(__first2, __last2);
658 
659  return std::__find_end(__first1, __last1, __first2, __last2,
660  std::__iterator_category(__first1),
661  std::__iterator_category(__first2));
662  }
663 
692  template<typename _ForwardIterator1, typename _ForwardIterator2,
693  typename _BinaryPredicate>
694  inline _ForwardIterator1
695  find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
696  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
697  _BinaryPredicate __comp)
698  {
699  // concept requirements
700  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
701  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
702  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
703  typename iterator_traits<_ForwardIterator1>::value_type,
704  typename iterator_traits<_ForwardIterator2>::value_type>)
705  __glibcxx_requires_valid_range(__first1, __last1);
706  __glibcxx_requires_valid_range(__first2, __last2);
707 
708  return std::__find_end(__first1, __last1, __first2, __last2,
709  std::__iterator_category(__first1),
710  std::__iterator_category(__first2),
711  __comp);
712  }
713 
714 #if __cplusplus >= 201103L
715 
727  template<typename _InputIterator, typename _Predicate>
728  inline bool
729  all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
730  { return __last == std::find_if_not(__first, __last, __pred); }
731 
744  template<typename _InputIterator, typename _Predicate>
745  inline bool
746  none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
747  { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
748 
762  template<typename _InputIterator, typename _Predicate>
763  inline bool
764  any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
765  { return !std::none_of(__first, __last, __pred); }
766 
777  template<typename _InputIterator, typename _Predicate>
778  inline _InputIterator
779  find_if_not(_InputIterator __first, _InputIterator __last,
780  _Predicate __pred)
781  {
782  // concept requirements
783  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
784  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
785  typename iterator_traits<_InputIterator>::value_type>)
786  __glibcxx_requires_valid_range(__first, __last);
787  return std::__find_if_not(__first, __last, __pred);
788  }
789 
800  template<typename _InputIterator, typename _Predicate>
801  inline bool
802  is_partitioned(_InputIterator __first, _InputIterator __last,
803  _Predicate __pred)
804  {
805  __first = std::find_if_not(__first, __last, __pred);
806  return std::none_of(__first, __last, __pred);
807  }
808 
818  template<typename _ForwardIterator, typename _Predicate>
819  _ForwardIterator
820  partition_point(_ForwardIterator __first, _ForwardIterator __last,
821  _Predicate __pred)
822  {
823  // concept requirements
824  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
825  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
826  typename iterator_traits<_ForwardIterator>::value_type>)
827 
828  // A specific debug-mode test will be necessary...
829  __glibcxx_requires_valid_range(__first, __last);
830 
831  typedef typename iterator_traits<_ForwardIterator>::difference_type
832  _DistanceType;
833 
834  _DistanceType __len = std::distance(__first, __last);
835  _DistanceType __half;
836  _ForwardIterator __middle;
837 
838  while (__len > 0)
839  {
840  __half = __len >> 1;
841  __middle = __first;
842  std::advance(__middle, __half);
843  if (__pred(*__middle))
844  {
845  __first = __middle;
846  ++__first;
847  __len = __len - __half - 1;
848  }
849  else
850  __len = __half;
851  }
852  return __first;
853  }
854 #endif
855 
856 
871  template<typename _InputIterator, typename _OutputIterator, typename _Tp>
872  _OutputIterator
873  remove_copy(_InputIterator __first, _InputIterator __last,
874  _OutputIterator __result, const _Tp& __value)
875  {
876  // concept requirements
877  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
878  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
879  typename iterator_traits<_InputIterator>::value_type>)
880  __glibcxx_function_requires(_EqualOpConcept<
881  typename iterator_traits<_InputIterator>::value_type, _Tp>)
882  __glibcxx_requires_valid_range(__first, __last);
883 
884  for (; __first != __last; ++__first)
885  if (!(*__first == __value))
886  {
887  *__result = *__first;
888  ++__result;
889  }
890  return __result;
891  }
892 
908  template<typename _InputIterator, typename _OutputIterator,
909  typename _Predicate>
910  _OutputIterator
911  remove_copy_if(_InputIterator __first, _InputIterator __last,
912  _OutputIterator __result, _Predicate __pred)
913  {
914  // concept requirements
915  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
916  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
917  typename iterator_traits<_InputIterator>::value_type>)
918  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
919  typename iterator_traits<_InputIterator>::value_type>)
920  __glibcxx_requires_valid_range(__first, __last);
921 
922  for (; __first != __last; ++__first)
923  if (!bool(__pred(*__first)))
924  {
925  *__result = *__first;
926  ++__result;
927  }
928  return __result;
929  }
930 
931 #if __cplusplus >= 201103L
932 
947  template<typename _InputIterator, typename _OutputIterator,
948  typename _Predicate>
949  _OutputIterator
950  copy_if(_InputIterator __first, _InputIterator __last,
951  _OutputIterator __result, _Predicate __pred)
952  {
953  // concept requirements
954  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
955  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
956  typename iterator_traits<_InputIterator>::value_type>)
957  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
958  typename iterator_traits<_InputIterator>::value_type>)
959  __glibcxx_requires_valid_range(__first, __last);
960 
961  for (; __first != __last; ++__first)
962  if (__pred(*__first))
963  {
964  *__result = *__first;
965  ++__result;
966  }
967  return __result;
968  }
969 
970 
971  template<typename _InputIterator, typename _Size, typename _OutputIterator>
972  _OutputIterator
973  __copy_n(_InputIterator __first, _Size __n,
974  _OutputIterator __result, input_iterator_tag)
975  {
976  if (__n > 0)
977  {
978  while (true)
979  {
980  *__result = *__first;
981  ++__result;
982  if (--__n > 0)
983  ++__first;
984  else
985  break;
986  }
987  }
988  return __result;
989  }
990 
991  template<typename _RandomAccessIterator, typename _Size,
992  typename _OutputIterator>
993  inline _OutputIterator
994  __copy_n(_RandomAccessIterator __first, _Size __n,
995  _OutputIterator __result, random_access_iterator_tag)
996  { return std::copy(__first, __first + __n, __result); }
997 
1011  template<typename _InputIterator, typename _Size, typename _OutputIterator>
1012  inline _OutputIterator
1013  copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1014  {
1015  // concept requirements
1016  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1017  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1018  typename iterator_traits<_InputIterator>::value_type>)
1019 
1020  return std::__copy_n(__first, __n, __result,
1021  std::__iterator_category(__first));
1022  }
1023 
1039  template<typename _InputIterator, typename _OutputIterator1,
1040  typename _OutputIterator2, typename _Predicate>
1041  pair<_OutputIterator1, _OutputIterator2>
1042  partition_copy(_InputIterator __first, _InputIterator __last,
1043  _OutputIterator1 __out_true, _OutputIterator2 __out_false,
1044  _Predicate __pred)
1045  {
1046  // concept requirements
1047  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1048  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
1049  typename iterator_traits<_InputIterator>::value_type>)
1050  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
1051  typename iterator_traits<_InputIterator>::value_type>)
1052  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1053  typename iterator_traits<_InputIterator>::value_type>)
1054  __glibcxx_requires_valid_range(__first, __last);
1055 
1056  for (; __first != __last; ++__first)
1057  if (__pred(*__first))
1058  {
1059  *__out_true = *__first;
1060  ++__out_true;
1061  }
1062  else
1063  {
1064  *__out_false = *__first;
1065  ++__out_false;
1066  }
1067 
1068  return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
1069  }
1070 #endif
1071 
1089  template<typename _ForwardIterator, typename _Tp>
1090  _ForwardIterator
1091  remove(_ForwardIterator __first, _ForwardIterator __last,
1092  const _Tp& __value)
1093  {
1094  // concept requirements
1095  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1096  _ForwardIterator>)
1097  __glibcxx_function_requires(_EqualOpConcept<
1098  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1099  __glibcxx_requires_valid_range(__first, __last);
1100 
1101  __first = _GLIBCXX_STD_A::find(__first, __last, __value);
1102  if(__first == __last)
1103  return __first;
1104  _ForwardIterator __result = __first;
1105  ++__first;
1106  for(; __first != __last; ++__first)
1107  if(!(*__first == __value))
1108  {
1109  *__result = _GLIBCXX_MOVE(*__first);
1110  ++__result;
1111  }
1112  return __result;
1113  }
1114 
1132  template<typename _ForwardIterator, typename _Predicate>
1133  _ForwardIterator
1134  remove_if(_ForwardIterator __first, _ForwardIterator __last,
1135  _Predicate __pred)
1136  {
1137  // concept requirements
1138  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1139  _ForwardIterator>)
1140  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1141  typename iterator_traits<_ForwardIterator>::value_type>)
1142  __glibcxx_requires_valid_range(__first, __last);
1143 
1144  __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
1145  if(__first == __last)
1146  return __first;
1147  _ForwardIterator __result = __first;
1148  ++__first;
1149  for(; __first != __last; ++__first)
1150  if(!bool(__pred(*__first)))
1151  {
1152  *__result = _GLIBCXX_MOVE(*__first);
1153  ++__result;
1154  }
1155  return __result;
1156  }
1157 
1172  template<typename _ForwardIterator>
1173  _ForwardIterator
1174  unique(_ForwardIterator __first, _ForwardIterator __last)
1175  {
1176  // concept requirements
1177  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1178  _ForwardIterator>)
1179  __glibcxx_function_requires(_EqualityComparableConcept<
1180  typename iterator_traits<_ForwardIterator>::value_type>)
1181  __glibcxx_requires_valid_range(__first, __last);
1182 
1183  // Skip the beginning, if already unique.
1184  __first = _GLIBCXX_STD_A::adjacent_find(__first, __last);
1185  if (__first == __last)
1186  return __last;
1187 
1188  // Do the real copy work.
1189  _ForwardIterator __dest = __first;
1190  ++__first;
1191  while (++__first != __last)
1192  if (!(*__dest == *__first))
1193  *++__dest = _GLIBCXX_MOVE(*__first);
1194  return ++__dest;
1195  }
1196 
1212  template<typename _ForwardIterator, typename _BinaryPredicate>
1213  _ForwardIterator
1214  unique(_ForwardIterator __first, _ForwardIterator __last,
1215  _BinaryPredicate __binary_pred)
1216  {
1217  // concept requirements
1218  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1219  _ForwardIterator>)
1220  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1221  typename iterator_traits<_ForwardIterator>::value_type,
1222  typename iterator_traits<_ForwardIterator>::value_type>)
1223  __glibcxx_requires_valid_range(__first, __last);
1224 
1225  // Skip the beginning, if already unique.
1226  __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
1227  if (__first == __last)
1228  return __last;
1229 
1230  // Do the real copy work.
1231  _ForwardIterator __dest = __first;
1232  ++__first;
1233  while (++__first != __last)
1234  if (!bool(__binary_pred(*__dest, *__first)))
1235  *++__dest = _GLIBCXX_MOVE(*__first);
1236  return ++__dest;
1237  }
1238 
1244  template<typename _ForwardIterator, typename _OutputIterator>
1245  _OutputIterator
1246  __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1247  _OutputIterator __result,
1248  forward_iterator_tag, output_iterator_tag)
1249  {
1250  // concept requirements -- taken care of in dispatching function
1251  _ForwardIterator __next = __first;
1252  *__result = *__first;
1253  while (++__next != __last)
1254  if (!(*__first == *__next))
1255  {
1256  __first = __next;
1257  *++__result = *__first;
1258  }
1259  return ++__result;
1260  }
1261 
1267  template<typename _InputIterator, typename _OutputIterator>
1268  _OutputIterator
1269  __unique_copy(_InputIterator __first, _InputIterator __last,
1270  _OutputIterator __result,
1271  input_iterator_tag, output_iterator_tag)
1272  {
1273  // concept requirements -- taken care of in dispatching function
1274  typename iterator_traits<_InputIterator>::value_type __value = *__first;
1275  *__result = __value;
1276  while (++__first != __last)
1277  if (!(__value == *__first))
1278  {
1279  __value = *__first;
1280  *++__result = __value;
1281  }
1282  return ++__result;
1283  }
1284 
1290  template<typename _InputIterator, typename _ForwardIterator>
1291  _ForwardIterator
1292  __unique_copy(_InputIterator __first, _InputIterator __last,
1293  _ForwardIterator __result,
1294  input_iterator_tag, forward_iterator_tag)
1295  {
1296  // concept requirements -- taken care of in dispatching function
1297  *__result = *__first;
1298  while (++__first != __last)
1299  if (!(*__result == *__first))
1300  *++__result = *__first;
1301  return ++__result;
1302  }
1303 
1310  template<typename _ForwardIterator, typename _OutputIterator,
1311  typename _BinaryPredicate>
1312  _OutputIterator
1313  __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1314  _OutputIterator __result, _BinaryPredicate __binary_pred,
1315  forward_iterator_tag, output_iterator_tag)
1316  {
1317  // concept requirements -- iterators already checked
1318  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1319  typename iterator_traits<_ForwardIterator>::value_type,
1320  typename iterator_traits<_ForwardIterator>::value_type>)
1321 
1322  _ForwardIterator __next = __first;
1323  *__result = *__first;
1324  while (++__next != __last)
1325  if (!bool(__binary_pred(*__first, *__next)))
1326  {
1327  __first = __next;
1328  *++__result = *__first;
1329  }
1330  return ++__result;
1331  }
1332 
1339  template<typename _InputIterator, typename _OutputIterator,
1340  typename _BinaryPredicate>
1341  _OutputIterator
1342  __unique_copy(_InputIterator __first, _InputIterator __last,
1343  _OutputIterator __result, _BinaryPredicate __binary_pred,
1344  input_iterator_tag, output_iterator_tag)
1345  {
1346  // concept requirements -- iterators already checked
1347  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1348  typename iterator_traits<_InputIterator>::value_type,
1349  typename iterator_traits<_InputIterator>::value_type>)
1350 
1351  typename iterator_traits<_InputIterator>::value_type __value = *__first;
1352  *__result = __value;
1353  while (++__first != __last)
1354  if (!bool(__binary_pred(__value, *__first)))
1355  {
1356  __value = *__first;
1357  *++__result = __value;
1358  }
1359  return ++__result;
1360  }
1361 
1368  template<typename _InputIterator, typename _ForwardIterator,
1369  typename _BinaryPredicate>
1370  _ForwardIterator
1371  __unique_copy(_InputIterator __first, _InputIterator __last,
1372  _ForwardIterator __result, _BinaryPredicate __binary_pred,
1373  input_iterator_tag, forward_iterator_tag)
1374  {
1375  // concept requirements -- iterators already checked
1376  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1377  typename iterator_traits<_ForwardIterator>::value_type,
1378  typename iterator_traits<_InputIterator>::value_type>)
1379 
1380  *__result = *__first;
1381  while (++__first != __last)
1382  if (!bool(__binary_pred(*__result, *__first)))
1383  *++__result = *__first;
1384  return ++__result;
1385  }
1386 
1392  template<typename _BidirectionalIterator>
1393  void
1394  __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1395  bidirectional_iterator_tag)
1396  {
1397  while (true)
1398  if (__first == __last || __first == --__last)
1399  return;
1400  else
1401  {
1402  std::iter_swap(__first, __last);
1403  ++__first;
1404  }
1405  }
1406 
1412  template<typename _RandomAccessIterator>
1413  void
1414  __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1415  random_access_iterator_tag)
1416  {
1417  if (__first == __last)
1418  return;
1419  --__last;
1420  while (__first < __last)
1421  {
1422  std::iter_swap(__first, __last);
1423  ++__first;
1424  --__last;
1425  }
1426  }
1427 
1440  template<typename _BidirectionalIterator>
1441  inline void
1442  reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1443  {
1444  // concept requirements
1445  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1446  _BidirectionalIterator>)
1447  __glibcxx_requires_valid_range(__first, __last);
1448  std::__reverse(__first, __last, std::__iterator_category(__first));
1449  }
1450 
1467  template<typename _BidirectionalIterator, typename _OutputIterator>
1468  _OutputIterator
1469  reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1470  _OutputIterator __result)
1471  {
1472  // concept requirements
1473  __glibcxx_function_requires(_BidirectionalIteratorConcept<
1474  _BidirectionalIterator>)
1475  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1476  typename iterator_traits<_BidirectionalIterator>::value_type>)
1477  __glibcxx_requires_valid_range(__first, __last);
1478 
1479  while (__first != __last)
1480  {
1481  --__last;
1482  *__result = *__last;
1483  ++__result;
1484  }
1485  return __result;
1486  }
1487 
1492  template<typename _EuclideanRingElement>
1493  _EuclideanRingElement
1494  __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1495  {
1496  while (__n != 0)
1497  {
1498  _EuclideanRingElement __t = __m % __n;
1499  __m = __n;
1500  __n = __t;
1501  }
1502  return __m;
1503  }
1504 
1506  template<typename _ForwardIterator>
1507  void
1508  __rotate(_ForwardIterator __first,
1509  _ForwardIterator __middle,
1510  _ForwardIterator __last,
1511  forward_iterator_tag)
1512  {
1513  if (__first == __middle || __last == __middle)
1514  return;
1515 
1516  _ForwardIterator __first2 = __middle;
1517  do
1518  {
1519  std::iter_swap(__first, __first2);
1520  ++__first;
1521  ++__first2;
1522  if (__first == __middle)
1523  __middle = __first2;
1524  }
1525  while (__first2 != __last);
1526 
1527  __first2 = __middle;
1528 
1529  while (__first2 != __last)
1530  {
1531  std::iter_swap(__first, __first2);
1532  ++__first;
1533  ++__first2;
1534  if (__first == __middle)
1535  __middle = __first2;
1536  else if (__first2 == __last)
1537  __first2 = __middle;
1538  }
1539  }
1540 
1542  template<typename _BidirectionalIterator>
1543  void
1544  __rotate(_BidirectionalIterator __first,
1545  _BidirectionalIterator __middle,
1546  _BidirectionalIterator __last,
1547  bidirectional_iterator_tag)
1548  {
1549  // concept requirements
1550  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1551  _BidirectionalIterator>)
1552 
1553  if (__first == __middle || __last == __middle)
1554  return;
1555 
1556  std::__reverse(__first, __middle, bidirectional_iterator_tag());
1557  std::__reverse(__middle, __last, bidirectional_iterator_tag());
1558 
1559  while (__first != __middle && __middle != __last)
1560  {
1561  std::iter_swap(__first, --__last);
1562  ++__first;
1563  }
1564 
1565  if (__first == __middle)
1566  std::__reverse(__middle, __last, bidirectional_iterator_tag());
1567  else
1568  std::__reverse(__first, __middle, bidirectional_iterator_tag());
1569  }
1570 
1572  template<typename _RandomAccessIterator>
1573  void
1574  __rotate(_RandomAccessIterator __first,
1575  _RandomAccessIterator __middle,
1576  _RandomAccessIterator __last,
1577  random_access_iterator_tag)
1578  {
1579  // concept requirements
1580  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1581  _RandomAccessIterator>)
1582 
1583  if (__first == __middle || __last == __middle)
1584  return;
1585 
1586  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1587  _Distance;
1588  typedef typename iterator_traits<_RandomAccessIterator>::value_type
1589  _ValueType;
1590 
1591  _Distance __n = __last - __first;
1592  _Distance __k = __middle - __first;
1593 
1594  if (__k == __n - __k)
1595  {
1596  std::swap_ranges(__first, __middle, __middle);
1597  return;
1598  }
1599 
1600  _RandomAccessIterator __p = __first;
1601 
1602  for (;;)
1603  {
1604  if (__k < __n - __k)
1605  {
1606  if (__is_pod(_ValueType) && __k == 1)
1607  {
1608  _ValueType __t = _GLIBCXX_MOVE(*__p);
1609  _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1610  *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1611  return;
1612  }
1613  _RandomAccessIterator __q = __p + __k;
1614  for (_Distance __i = 0; __i < __n - __k; ++ __i)
1615  {
1616  std::iter_swap(__p, __q);
1617  ++__p;
1618  ++__q;
1619  }
1620  __n %= __k;
1621  if (__n == 0)
1622  return;
1623  std::swap(__n, __k);
1624  __k = __n - __k;
1625  }
1626  else
1627  {
1628  __k = __n - __k;
1629  if (__is_pod(_ValueType) && __k == 1)
1630  {
1631  _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1632  _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1633  *__p = _GLIBCXX_MOVE(__t);
1634  return;
1635  }
1636  _RandomAccessIterator __q = __p + __n;
1637  __p = __q - __k;
1638  for (_Distance __i = 0; __i < __n - __k; ++ __i)
1639  {
1640  --__p;
1641  --__q;
1642  std::iter_swap(__p, __q);
1643  }
1644  __n %= __k;
1645  if (__n == 0)
1646  return;
1647  std::swap(__n, __k);
1648  }
1649  }
1650  }
1651 
1673  template<typename _ForwardIterator>
1674  inline void
1675  rotate(_ForwardIterator __first, _ForwardIterator __middle,
1676  _ForwardIterator __last)
1677  {
1678  // concept requirements
1679  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1680  _ForwardIterator>)
1681  __glibcxx_requires_valid_range(__first, __middle);
1682  __glibcxx_requires_valid_range(__middle, __last);
1683 
1684  typedef typename iterator_traits<_ForwardIterator>::iterator_category
1685  _IterType;
1686  std::__rotate(__first, __middle, __last, _IterType());
1687  }
1688 
1709  template<typename _ForwardIterator, typename _OutputIterator>
1710  _OutputIterator
1711  rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1712  _ForwardIterator __last, _OutputIterator __result)
1713  {
1714  // concept requirements
1715  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1716  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1717  typename iterator_traits<_ForwardIterator>::value_type>)
1718  __glibcxx_requires_valid_range(__first, __middle);
1719  __glibcxx_requires_valid_range(__middle, __last);
1720 
1721  return std::copy(__first, __middle,
1722  std::copy(__middle, __last, __result));
1723  }
1724 
1726  template<typename _ForwardIterator, typename _Predicate>
1727  _ForwardIterator
1728  __partition(_ForwardIterator __first, _ForwardIterator __last,
1729  _Predicate __pred, forward_iterator_tag)
1730  {
1731  if (__first == __last)
1732  return __first;
1733 
1734  while (__pred(*__first))
1735  if (++__first == __last)
1736  return __first;
1737 
1738  _ForwardIterator __next = __first;
1739 
1740  while (++__next != __last)
1741  if (__pred(*__next))
1742  {
1743  std::iter_swap(__first, __next);
1744  ++__first;
1745  }
1746 
1747  return __first;
1748  }
1749 
1751  template<typename _BidirectionalIterator, typename _Predicate>
1752  _BidirectionalIterator
1753  __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1754  _Predicate __pred, bidirectional_iterator_tag)
1755  {
1756  while (true)
1757  {
1758  while (true)
1759  if (__first == __last)
1760  return __first;
1761  else if (__pred(*__first))
1762  ++__first;
1763  else
1764  break;
1765  --__last;
1766  while (true)
1767  if (__first == __last)
1768  return __first;
1769  else if (!bool(__pred(*__last)))
1770  --__last;
1771  else
1772  break;
1773  std::iter_swap(__first, __last);
1774  ++__first;
1775  }
1776  }
1777 
1778  // partition
1779 
1783  template<typename _ForwardIterator, typename _Predicate, typename _Distance>
1784  _ForwardIterator
1785  __inplace_stable_partition(_ForwardIterator __first,
1786  _Predicate __pred, _Distance __len)
1787  {
1788  if (__len == 1)
1789  return __first;
1790  _ForwardIterator __middle = __first;
1791  std::advance(__middle, __len / 2);
1792  _ForwardIterator __left_split =
1793  std::__inplace_stable_partition(__first, __pred, __len / 2);
1794  // Advance past true-predicate values to satisfy this
1795  // function's preconditions.
1796  _Distance __right_len = __len - __len / 2;
1797  _ForwardIterator __right_split =
1798  std::__find_if_not_n(__middle, __right_len, __pred);
1799  if (__right_len)
1800  __right_split = std::__inplace_stable_partition(__middle,
1801  __pred,
1802  __right_len);
1803  std::rotate(__left_split, __middle, __right_split);
1804  std::advance(__left_split, std::distance(__middle, __right_split));
1805  return __left_split;
1806  }
1807 
1814  template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1815  typename _Distance>
1816  _ForwardIterator
1817  __stable_partition_adaptive(_ForwardIterator __first,
1818  _ForwardIterator __last,
1819  _Predicate __pred, _Distance __len,
1820  _Pointer __buffer,
1821  _Distance __buffer_size)
1822  {
1823  if (__len <= __buffer_size)
1824  {
1825  _ForwardIterator __result1 = __first;
1826  _Pointer __result2 = __buffer;
1827  // The precondition guarantees that !__pred(*__first), so
1828  // move that element to the buffer before starting the loop.
1829  // This ensures that we only call __pred once per element.
1830  *__result2 = _GLIBCXX_MOVE(*__first);
1831  ++__result2;
1832  ++__first;
1833  for (; __first != __last; ++__first)
1834  if (__pred(*__first))
1835  {
1836  *__result1 = _GLIBCXX_MOVE(*__first);
1837  ++__result1;
1838  }
1839  else
1840  {
1841  *__result2 = _GLIBCXX_MOVE(*__first);
1842  ++__result2;
1843  }
1844  _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1845  return __result1;
1846  }
1847  else
1848  {
1849  _ForwardIterator __middle = __first;
1850  std::advance(__middle, __len / 2);
1851  _ForwardIterator __left_split =
1852  std::__stable_partition_adaptive(__first, __middle, __pred,
1853  __len / 2, __buffer,
1854  __buffer_size);
1855  // Advance past true-predicate values to satisfy this
1856  // function's preconditions.
1857  _Distance __right_len = __len - __len / 2;
1858  _ForwardIterator __right_split =
1859  std::__find_if_not_n(__middle, __right_len, __pred);
1860  if (__right_len)
1861  __right_split =
1862  std::__stable_partition_adaptive(__right_split, __last, __pred,
1863  __right_len,
1864  __buffer, __buffer_size);
1865  std::rotate(__left_split, __middle, __right_split);
1866  std::advance(__left_split, std::distance(__middle, __right_split));
1867  return __left_split;
1868  }
1869  }
1870 
1888  template<typename _ForwardIterator, typename _Predicate>
1889  _ForwardIterator
1890  stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1891  _Predicate __pred)
1892  {
1893  // concept requirements
1894  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1895  _ForwardIterator>)
1896  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1897  typename iterator_traits<_ForwardIterator>::value_type>)
1898  __glibcxx_requires_valid_range(__first, __last);
1899 
1900  __first = std::__find_if_not(__first, __last, __pred);
1901 
1902  if (__first == __last)
1903  return __first;
1904  else
1905  {
1906  typedef typename iterator_traits<_ForwardIterator>::value_type
1907  _ValueType;
1908  typedef typename iterator_traits<_ForwardIterator>::difference_type
1909  _DistanceType;
1910 
1911  _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
1912  __last);
1913  if (__buf.size() > 0)
1914  return
1915  std::__stable_partition_adaptive(__first, __last, __pred,
1916  _DistanceType(__buf.requested_size()),
1917  __buf.begin(),
1918  _DistanceType(__buf.size()));
1919  else
1920  return
1921  std::__inplace_stable_partition(__first, __pred,
1922  _DistanceType(__buf.requested_size()));
1923  }
1924  }
1925 
1927  template<typename _RandomAccessIterator>
1928  void
1929  __heap_select(_RandomAccessIterator __first,
1930  _RandomAccessIterator __middle,
1931  _RandomAccessIterator __last)
1932  {
1933  std::make_heap(__first, __middle);
1934  for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1935  if (*__i < *__first)
1936  std::__pop_heap(__first, __middle, __i);
1937  }
1938 
1940  template<typename _RandomAccessIterator, typename _Compare>
1941  void
1942  __heap_select(_RandomAccessIterator __first,
1943  _RandomAccessIterator __middle,
1944  _RandomAccessIterator __last, _Compare __comp)
1945  {
1946  std::make_heap(__first, __middle, __comp);
1947  for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1948  if (__comp(*__i, *__first))
1949  std::__pop_heap(__first, __middle, __i, __comp);
1950  }
1951 
1952  // partial_sort
1953 
1972  template<typename _InputIterator, typename _RandomAccessIterator>
1973  _RandomAccessIterator
1974  partial_sort_copy(_InputIterator __first, _InputIterator __last,
1975  _RandomAccessIterator __result_first,
1976  _RandomAccessIterator __result_last)
1977  {
1978  typedef typename iterator_traits<_InputIterator>::value_type
1979  _InputValueType;
1980  typedef typename iterator_traits<_RandomAccessIterator>::value_type
1981  _OutputValueType;
1982  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1983  _DistanceType;
1984 
1985  // concept requirements
1986  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1987  __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1988  _OutputValueType>)
1989  __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1990  _OutputValueType>)
1991  __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1992  __glibcxx_requires_valid_range(__first, __last);
1993  __glibcxx_requires_valid_range(__result_first, __result_last);
1994 
1995  if (__result_first == __result_last)
1996  return __result_last;
1997  _RandomAccessIterator __result_real_last = __result_first;
1998  while(__first != __last && __result_real_last != __result_last)
1999  {
2000  *__result_real_last = *__first;
2001  ++__result_real_last;
2002  ++__first;
2003  }
2004  std::make_heap(__result_first, __result_real_last);
2005  while (__first != __last)
2006  {
2007  if (*__first < *__result_first)
2008  std::__adjust_heap(__result_first, _DistanceType(0),
2009  _DistanceType(__result_real_last
2010  - __result_first),
2011  _InputValueType(*__first));
2012  ++__first;
2013  }
2014  std::sort_heap(__result_first, __result_real_last);
2015  return __result_real_last;
2016  }
2017 
2038  template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
2039  _RandomAccessIterator
2040  partial_sort_copy(_InputIterator __first, _InputIterator __last,
2041  _RandomAccessIterator __result_first,
2042  _RandomAccessIterator __result_last,
2043  _Compare __comp)
2044  {
2045  typedef typename iterator_traits<_InputIterator>::value_type
2046  _InputValueType;
2047  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2048  _OutputValueType;
2049  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2050  _DistanceType;
2051 
2052  // concept requirements
2053  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2054  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2055  _RandomAccessIterator>)
2056  __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2057  _OutputValueType>)
2058  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2059  _InputValueType, _OutputValueType>)
2060  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2061  _OutputValueType, _OutputValueType>)
2062  __glibcxx_requires_valid_range(__first, __last);
2063  __glibcxx_requires_valid_range(__result_first, __result_last);
2064 
2065  if (__result_first == __result_last)
2066  return __result_last;
2067  _RandomAccessIterator __result_real_last = __result_first;
2068  while(__first != __last && __result_real_last != __result_last)
2069  {
2070  *__result_real_last = *__first;
2071  ++__result_real_last;
2072  ++__first;
2073  }
2074  std::make_heap(__result_first, __result_real_last, __comp);
2075  while (__first != __last)
2076  {
2077  if (__comp(*__first, *__result_first))
2078  std::__adjust_heap(__result_first, _DistanceType(0),
2079  _DistanceType(__result_real_last
2080  - __result_first),
2081  _InputValueType(*__first),
2082  __comp);
2083  ++__first;
2084  }
2085  std::sort_heap(__result_first, __result_real_last, __comp);
2086  return __result_real_last;
2087  }
2088 
2090  template<typename _RandomAccessIterator>
2091  void
2092  __unguarded_linear_insert(_RandomAccessIterator __last)
2093  {
2094  typename iterator_traits<_RandomAccessIterator>::value_type
2095  __val = _GLIBCXX_MOVE(*__last);
2096  _RandomAccessIterator __next = __last;
2097  --__next;
2098  while (__val < *__next)
2099  {
2100  *__last = _GLIBCXX_MOVE(*__next);
2101  __last = __next;
2102  --__next;
2103  }
2104  *__last = _GLIBCXX_MOVE(__val);
2105  }
2106 
2108  template<typename _RandomAccessIterator, typename _Compare>
2109  void
2110  __unguarded_linear_insert(_RandomAccessIterator __last,
2111  _Compare __comp)
2112  {
2113  typename iterator_traits<_RandomAccessIterator>::value_type
2114  __val = _GLIBCXX_MOVE(*__last);
2115  _RandomAccessIterator __next = __last;
2116  --__next;
2117  while (__comp(__val, *__next))
2118  {
2119  *__last = _GLIBCXX_MOVE(*__next);
2120  __last = __next;
2121  --__next;
2122  }
2123  *__last = _GLIBCXX_MOVE(__val);
2124  }
2125 
2127  template<typename _RandomAccessIterator>
2128  void
2129  __insertion_sort(_RandomAccessIterator __first,
2130  _RandomAccessIterator __last)
2131  {
2132  if (__first == __last)
2133  return;
2134 
2135  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2136  {
2137  if (*__i < *__first)
2138  {
2139  typename iterator_traits<_RandomAccessIterator>::value_type
2140  __val = _GLIBCXX_MOVE(*__i);
2141  _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2142  *__first = _GLIBCXX_MOVE(__val);
2143  }
2144  else
2145  std::__unguarded_linear_insert(__i);
2146  }
2147  }
2148 
2150  template<typename _RandomAccessIterator, typename _Compare>
2151  void
2152  __insertion_sort(_RandomAccessIterator __first,
2153  _RandomAccessIterator __last, _Compare __comp)
2154  {
2155  if (__first == __last) return;
2156 
2157  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2158  {
2159  if (__comp(*__i, *__first))
2160  {
2161  typename iterator_traits<_RandomAccessIterator>::value_type
2162  __val = _GLIBCXX_MOVE(*__i);
2163  _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2164  *__first = _GLIBCXX_MOVE(__val);
2165  }
2166  else
2167  std::__unguarded_linear_insert(__i, __comp);
2168  }
2169  }
2170 
2172  template<typename _RandomAccessIterator>
2173  inline void
2174  __unguarded_insertion_sort(_RandomAccessIterator __first,
2175  _RandomAccessIterator __last)
2176  {
2177  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2178  _ValueType;
2179 
2180  for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2181  std::__unguarded_linear_insert(__i);
2182  }
2183 
2185  template<typename _RandomAccessIterator, typename _Compare>
2186  inline void
2187  __unguarded_insertion_sort(_RandomAccessIterator __first,
2188  _RandomAccessIterator __last, _Compare __comp)
2189  {
2190  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2191  _ValueType;
2192 
2193  for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2194  std::__unguarded_linear_insert(__i, __comp);
2195  }
2196 
2201  enum { _S_threshold = 16 };
2202 
2204  template<typename _RandomAccessIterator>
2205  void
2206  __final_insertion_sort(_RandomAccessIterator __first,
2207  _RandomAccessIterator __last)
2208  {
2209  if (__last - __first > int(_S_threshold))
2210  {
2211  std::__insertion_sort(__first, __first + int(_S_threshold));
2212  std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
2213  }
2214  else
2215  std::__insertion_sort(__first, __last);
2216  }
2217 
2219  template<typename _RandomAccessIterator, typename _Compare>
2220  void
2221  __final_insertion_sort(_RandomAccessIterator __first,
2222  _RandomAccessIterator __last, _Compare __comp)
2223  {
2224  if (__last - __first > int(_S_threshold))
2225  {
2226  std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
2227  std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
2228  __comp);
2229  }
2230  else
2231  std::__insertion_sort(__first, __last, __comp);
2232  }
2233 
2235  template<typename _RandomAccessIterator, typename _Tp>
2236  _RandomAccessIterator
2237  __unguarded_partition(_RandomAccessIterator __first,
2238  _RandomAccessIterator __last, const _Tp& __pivot)
2239  {
2240  while (true)
2241  {
2242  while (*__first < __pivot)
2243  ++__first;
2244  --__last;
2245  while (__pivot < *__last)
2246  --__last;
2247  if (!(__first < __last))
2248  return __first;
2249  std::iter_swap(__first, __last);
2250  ++__first;
2251  }
2252  }
2253 
2255  template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
2256  _RandomAccessIterator
2257  __unguarded_partition(_RandomAccessIterator __first,
2258  _RandomAccessIterator __last,
2259  const _Tp& __pivot, _Compare __comp)
2260  {
2261  while (true)
2262  {
2263  while (__comp(*__first, __pivot))
2264  ++__first;
2265  --__last;
2266  while (__comp(__pivot, *__last))
2267  --__last;
2268  if (!(__first < __last))
2269  return __first;
2270  std::iter_swap(__first, __last);
2271  ++__first;
2272  }
2273  }
2274 
2276  template<typename _RandomAccessIterator>
2277  inline _RandomAccessIterator
2278  __unguarded_partition_pivot(_RandomAccessIterator __first,
2279  _RandomAccessIterator __last)
2280  {
2281  _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2282  std::__move_median_to_first(__first, __first + 1, __mid, __last - 1);
2283  return std::__unguarded_partition(__first + 1, __last, *__first);
2284  }
2285 
2286 
2288  template<typename _RandomAccessIterator, typename _Compare>
2289  inline _RandomAccessIterator
2290  __unguarded_partition_pivot(_RandomAccessIterator __first,
2291  _RandomAccessIterator __last, _Compare __comp)
2292  {
2293  _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2294  std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
2295  __comp);
2296  return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
2297  }
2298 
2300  template<typename _RandomAccessIterator, typename _Size>
2301  void
2302  __introsort_loop(_RandomAccessIterator __first,
2303  _RandomAccessIterator __last,
2304  _Size __depth_limit)
2305  {
2306  while (__last - __first > int(_S_threshold))
2307  {
2308  if (__depth_limit == 0)
2309  {
2310  _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
2311  return;
2312  }
2313  --__depth_limit;
2314  _RandomAccessIterator __cut =
2315  std::__unguarded_partition_pivot(__first, __last);
2316  std::__introsort_loop(__cut, __last, __depth_limit);
2317  __last = __cut;
2318  }
2319  }
2320 
2322  template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2323  void
2324  __introsort_loop(_RandomAccessIterator __first,
2325  _RandomAccessIterator __last,
2326  _Size __depth_limit, _Compare __comp)
2327  {
2328  while (__last - __first > int(_S_threshold))
2329  {
2330  if (__depth_limit == 0)
2331  {
2332  _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
2333  return;
2334  }
2335  --__depth_limit;
2336  _RandomAccessIterator __cut =
2337  std::__unguarded_partition_pivot(__first, __last, __comp);
2338  std::__introsort_loop(__cut, __last, __depth_limit, __comp);
2339  __last = __cut;
2340  }
2341  }
2342 
2343  // sort
2344 
2345  template<typename _RandomAccessIterator, typename _Size>
2346  void
2347  __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2348  _RandomAccessIterator __last, _Size __depth_limit)
2349  {
2350  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2351  _ValueType;
2352 
2353  while (__last - __first > 3)
2354  {
2355  if (__depth_limit == 0)
2356  {
2357  std::__heap_select(__first, __nth + 1, __last);
2358 
2359  // Place the nth largest element in its final position.
2360  std::iter_swap(__first, __nth);
2361  return;
2362  }
2363  --__depth_limit;
2364  _RandomAccessIterator __cut =
2365  std::__unguarded_partition_pivot(__first, __last);
2366  if (__cut <= __nth)
2367  __first = __cut;
2368  else
2369  __last = __cut;
2370  }
2371  std::__insertion_sort(__first, __last);
2372  }
2373 
2374  template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2375  void
2376  __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2377  _RandomAccessIterator __last, _Size __depth_limit,
2378  _Compare __comp)
2379  {
2380  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2381  _ValueType;
2382 
2383  while (__last - __first > 3)
2384  {
2385  if (__depth_limit == 0)
2386  {
2387  std::__heap_select(__first, __nth + 1, __last, __comp);
2388  // Place the nth largest element in its final position.
2389  std::iter_swap(__first, __nth);
2390  return;
2391  }
2392  --__depth_limit;
2393  _RandomAccessIterator __cut =
2394  std::__unguarded_partition_pivot(__first, __last, __comp);
2395  if (__cut <= __nth)
2396  __first = __cut;
2397  else
2398  __last = __cut;
2399  }
2400  std::__insertion_sort(__first, __last, __comp);
2401  }
2402 
2403  // nth_element
2404 
2405  // lower_bound moved to stl_algobase.h
2406 
2423  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2424  _ForwardIterator
2425  lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2426  const _Tp& __val, _Compare __comp)
2427  {
2428  typedef typename iterator_traits<_ForwardIterator>::value_type
2429  _ValueType;
2430  typedef typename iterator_traits<_ForwardIterator>::difference_type
2431  _DistanceType;
2432 
2433  // concept requirements
2434  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2435  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2436  _ValueType, _Tp>)
2437  __glibcxx_requires_partitioned_lower_pred(__first, __last,
2438  __val, __comp);
2439 
2440  _DistanceType __len = std::distance(__first, __last);
2441 
2442  while (__len > 0)
2443  {
2444  _DistanceType __half = __len >> 1;
2445  _ForwardIterator __middle = __first;
2446  std::advance(__middle, __half);
2447  if (__comp(*__middle, __val))
2448  {
2449  __first = __middle;
2450  ++__first;
2451  __len = __len - __half - 1;
2452  }
2453  else
2454  __len = __half;
2455  }
2456  return __first;
2457  }
2458 
2470  template<typename _ForwardIterator, typename _Tp>
2471  _ForwardIterator
2472  upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2473  const _Tp& __val)
2474  {
2475  typedef typename iterator_traits<_ForwardIterator>::value_type
2476  _ValueType;
2477  typedef typename iterator_traits<_ForwardIterator>::difference_type
2478  _DistanceType;
2479 
2480  // concept requirements
2481  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2482  __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2483  __glibcxx_requires_partitioned_upper(__first, __last, __val);
2484 
2485  _DistanceType __len = std::distance(__first, __last);
2486 
2487  while (__len > 0)
2488  {
2489  _DistanceType __half = __len >> 1;
2490  _ForwardIterator __middle = __first;
2491  std::advance(__middle, __half);
2492  if (__val < *__middle)
2493  __len = __half;
2494  else
2495  {
2496  __first = __middle;
2497  ++__first;
2498  __len = __len - __half - 1;
2499  }
2500  }
2501  return __first;
2502  }
2503 
2519  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2520  _ForwardIterator
2521  upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2522  const _Tp& __val, _Compare __comp)
2523  {
2524  typedef typename iterator_traits<_ForwardIterator>::value_type
2525  _ValueType;
2526  typedef typename iterator_traits<_ForwardIterator>::difference_type
2527  _DistanceType;
2528 
2529  // concept requirements
2530  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2531  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2532  _Tp, _ValueType>)
2533  __glibcxx_requires_partitioned_upper_pred(__first, __last,
2534  __val, __comp);
2535 
2536  _DistanceType __len = std::distance(__first, __last);
2537 
2538  while (__len > 0)
2539  {
2540  _DistanceType __half = __len >> 1;
2541  _ForwardIterator __middle = __first;
2542  std::advance(__middle, __half);
2543  if (__comp(__val, *__middle))
2544  __len = __half;
2545  else
2546  {
2547  __first = __middle;
2548  ++__first;
2549  __len = __len - __half - 1;
2550  }
2551  }
2552  return __first;
2553  }
2554 
2572  template<typename _ForwardIterator, typename _Tp>
2573  pair<_ForwardIterator, _ForwardIterator>
2574  equal_range(_ForwardIterator __first, _ForwardIterator __last,
2575  const _Tp& __val)
2576  {
2577  typedef typename iterator_traits<_ForwardIterator>::value_type
2578  _ValueType;
2579  typedef typename iterator_traits<_ForwardIterator>::difference_type
2580  _DistanceType;
2581 
2582  // concept requirements
2583  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2584  __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2585  __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2586  __glibcxx_requires_partitioned_lower(__first, __last, __val);
2587  __glibcxx_requires_partitioned_upper(__first, __last, __val);
2588 
2589  _DistanceType __len = std::distance(__first, __last);
2590 
2591  while (__len > 0)
2592  {
2593  _DistanceType __half = __len >> 1;
2594  _ForwardIterator __middle = __first;
2595  std::advance(__middle, __half);
2596  if (*__middle < __val)
2597  {
2598  __first = __middle;
2599  ++__first;
2600  __len = __len - __half - 1;
2601  }
2602  else if (__val < *__middle)
2603  __len = __half;
2604  else
2605  {
2606  _ForwardIterator __left = std::lower_bound(__first, __middle,
2607  __val);
2608  std::advance(__first, __len);
2609  _ForwardIterator __right = std::upper_bound(++__middle, __first,
2610  __val);
2611  return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2612  }
2613  }
2614  return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2615  }
2616 
2634  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2635  pair<_ForwardIterator, _ForwardIterator>
2636  equal_range(_ForwardIterator __first, _ForwardIterator __last,
2637  const _Tp& __val, _Compare __comp)
2638  {
2639  typedef typename iterator_traits<_ForwardIterator>::value_type
2640  _ValueType;
2641  typedef typename iterator_traits<_ForwardIterator>::difference_type
2642  _DistanceType;
2643 
2644  // concept requirements
2645  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2646  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2647  _ValueType, _Tp>)
2648  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2649  _Tp, _ValueType>)
2650  __glibcxx_requires_partitioned_lower_pred(__first, __last,
2651  __val, __comp);
2652  __glibcxx_requires_partitioned_upper_pred(__first, __last,
2653  __val, __comp);
2654 
2655  _DistanceType __len = std::distance(__first, __last);
2656 
2657  while (__len > 0)
2658  {
2659  _DistanceType __half = __len >> 1;
2660  _ForwardIterator __middle = __first;
2661  std::advance(__middle, __half);
2662  if (__comp(*__middle, __val))
2663  {
2664  __first = __middle;
2665  ++__first;
2666  __len = __len - __half - 1;
2667  }
2668  else if (__comp(__val, *__middle))
2669  __len = __half;
2670  else
2671  {
2672  _ForwardIterator __left = std::lower_bound(__first, __middle,
2673  __val, __comp);
2674  std::advance(__first, __len);
2675  _ForwardIterator __right = std::upper_bound(++__middle, __first,
2676  __val, __comp);
2677  return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2678  }
2679  }
2680  return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2681  }
2682 
2695  template<typename _ForwardIterator, typename _Tp>
2696  bool
2697  binary_search(_ForwardIterator __first, _ForwardIterator __last,
2698  const _Tp& __val)
2699  {
2700  typedef typename iterator_traits<_ForwardIterator>::value_type
2701  _ValueType;
2702 
2703  // concept requirements
2704  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2705  __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2706  __glibcxx_requires_partitioned_lower(__first, __last, __val);
2707  __glibcxx_requires_partitioned_upper(__first, __last, __val);
2708 
2709  _ForwardIterator __i = std::lower_bound(__first, __last, __val);
2710  return __i != __last && !(__val < *__i);
2711  }
2712 
2728  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2729  bool
2730  binary_search(_ForwardIterator __first, _ForwardIterator __last,
2731  const _Tp& __val, _Compare __comp)
2732  {
2733  typedef typename iterator_traits<_ForwardIterator>::value_type
2734  _ValueType;
2735 
2736  // concept requirements
2737  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2738  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2739  _Tp, _ValueType>)
2740  __glibcxx_requires_partitioned_lower_pred(__first, __last,
2741  __val, __comp);
2742  __glibcxx_requires_partitioned_upper_pred(__first, __last,
2743  __val, __comp);
2744 
2745  _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
2746  return __i != __last && !bool(__comp(__val, *__i));
2747  }
2748 
2749  // merge
2750 
2752  template<typename _InputIterator1, typename _InputIterator2,
2753  typename _OutputIterator>
2754  void
2755  __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2756  _InputIterator2 __first2, _InputIterator2 __last2,
2757  _OutputIterator __result)
2758  {
2759  while (__first1 != __last1 && __first2 != __last2)
2760  {
2761  if (*__first2 < *__first1)
2762  {
2763  *__result = _GLIBCXX_MOVE(*__first2);
2764  ++__first2;
2765  }
2766  else
2767  {
2768  *__result = _GLIBCXX_MOVE(*__first1);
2769  ++__first1;
2770  }
2771  ++__result;
2772  }
2773  if (__first1 != __last1)
2774  _GLIBCXX_MOVE3(__first1, __last1, __result);
2775  }
2776 
2778  template<typename _InputIterator1, typename _InputIterator2,
2779  typename _OutputIterator, typename _Compare>
2780  void
2781  __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2782  _InputIterator2 __first2, _InputIterator2 __last2,
2783  _OutputIterator __result, _Compare __comp)
2784  {
2785  while (__first1 != __last1 && __first2 != __last2)
2786  {
2787  if (__comp(*__first2, *__first1))
2788  {
2789  *__result = _GLIBCXX_MOVE(*__first2);
2790  ++__first2;
2791  }
2792  else
2793  {
2794  *__result = _GLIBCXX_MOVE(*__first1);
2795  ++__first1;
2796  }
2797  ++__result;
2798  }
2799  if (__first1 != __last1)
2800  _GLIBCXX_MOVE3(__first1, __last1, __result);
2801  }
2802 
2804  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2805  typename _BidirectionalIterator3>
2806  void
2807  __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2808  _BidirectionalIterator1 __last1,
2809  _BidirectionalIterator2 __first2,
2810  _BidirectionalIterator2 __last2,
2811  _BidirectionalIterator3 __result)
2812  {
2813  if (__first1 == __last1)
2814  {
2815  _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2816  return;
2817  }
2818  else if (__first2 == __last2)
2819  return;
2820 
2821  --__last1;
2822  --__last2;
2823  while (true)
2824  {
2825  if (*__last2 < *__last1)
2826  {
2827  *--__result = _GLIBCXX_MOVE(*__last1);
2828  if (__first1 == __last1)
2829  {
2830  _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2831  return;
2832  }
2833  --__last1;
2834  }
2835  else
2836  {
2837  *--__result = _GLIBCXX_MOVE(*__last2);
2838  if (__first2 == __last2)
2839  return;
2840  --__last2;
2841  }
2842  }
2843  }
2844 
2846  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2847  typename _BidirectionalIterator3, typename _Compare>
2848  void
2849  __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2850  _BidirectionalIterator1 __last1,
2851  _BidirectionalIterator2 __first2,
2852  _BidirectionalIterator2 __last2,
2853  _BidirectionalIterator3 __result,
2854  _Compare __comp)
2855  {
2856  if (__first1 == __last1)
2857  {
2858  _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2859  return;
2860  }
2861  else if (__first2 == __last2)
2862  return;
2863 
2864  --__last1;
2865  --__last2;
2866  while (true)
2867  {
2868  if (__comp(*__last2, *__last1))
2869  {
2870  *--__result = _GLIBCXX_MOVE(*__last1);
2871  if (__first1 == __last1)
2872  {
2873  _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2874  return;
2875  }
2876  --__last1;
2877  }
2878  else
2879  {
2880  *--__result = _GLIBCXX_MOVE(*__last2);
2881  if (__first2 == __last2)
2882  return;
2883  --__last2;
2884  }
2885  }
2886  }
2887 
2889  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2890  typename _Distance>
2891  _BidirectionalIterator1
2892  __rotate_adaptive(_BidirectionalIterator1 __first,
2893  _BidirectionalIterator1 __middle,
2894  _BidirectionalIterator1 __last,
2895  _Distance __len1, _Distance __len2,
2896  _BidirectionalIterator2 __buffer,
2897  _Distance __buffer_size)
2898  {
2899  _BidirectionalIterator2 __buffer_end;
2900  if (__len1 > __len2 && __len2 <= __buffer_size)
2901  {
2902  if (__len2)
2903  {
2904  __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2905  _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2906  return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2907  }
2908  else
2909  return __first;
2910  }
2911  else if (__len1 <= __buffer_size)
2912  {
2913  if (__len1)
2914  {
2915  __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2916  _GLIBCXX_MOVE3(__middle, __last, __first);
2917  return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2918  }
2919  else
2920  return __last;
2921  }
2922  else
2923  {
2924  std::rotate(__first, __middle, __last);
2925  std::advance(__first, std::distance(__middle, __last));
2926  return __first;
2927  }
2928  }
2929 
2931  template<typename _BidirectionalIterator, typename _Distance,
2932  typename _Pointer>
2933  void
2934  __merge_adaptive(_BidirectionalIterator __first,
2935  _BidirectionalIterator __middle,
2936  _BidirectionalIterator __last,
2937  _Distance __len1, _Distance __len2,
2938  _Pointer __buffer, _Distance __buffer_size)
2939  {
2940  if (__len1 <= __len2 && __len1 <= __buffer_size)
2941  {
2942  _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2943  std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2944  __first);
2945  }
2946  else if (__len2 <= __buffer_size)
2947  {
2948  _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2949  std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2950  __buffer_end, __last);
2951  }
2952  else
2953  {
2954  _BidirectionalIterator __first_cut = __first;
2955  _BidirectionalIterator __second_cut = __middle;
2956  _Distance __len11 = 0;
2957  _Distance __len22 = 0;
2958  if (__len1 > __len2)
2959  {
2960  __len11 = __len1 / 2;
2961  std::advance(__first_cut, __len11);
2962  __second_cut = std::lower_bound(__middle, __last,
2963  *__first_cut);
2964  __len22 = std::distance(__middle, __second_cut);
2965  }
2966  else
2967  {
2968  __len22 = __len2 / 2;
2969  std::advance(__second_cut, __len22);
2970  __first_cut = std::upper_bound(__first, __middle,
2971  *__second_cut);
2972  __len11 = std::distance(__first, __first_cut);
2973  }
2974  _BidirectionalIterator __new_middle =
2975  std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2976  __len1 - __len11, __len22, __buffer,
2977  __buffer_size);
2978  std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2979  __len22, __buffer, __buffer_size);
2980  std::__merge_adaptive(__new_middle, __second_cut, __last,
2981  __len1 - __len11,
2982  __len2 - __len22, __buffer, __buffer_size);
2983  }
2984  }
2985 
2987  template<typename _BidirectionalIterator, typename _Distance,
2988  typename _Pointer, typename _Compare>
2989  void
2990  __merge_adaptive(_BidirectionalIterator __first,
2991  _BidirectionalIterator __middle,
2992  _BidirectionalIterator __last,
2993  _Distance __len1, _Distance __len2,
2994  _Pointer __buffer, _Distance __buffer_size,
2995  _Compare __comp)
2996  {
2997  if (__len1 <= __len2 && __len1 <= __buffer_size)
2998  {
2999  _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
3000  std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
3001  __first, __comp);
3002  }
3003  else if (__len2 <= __buffer_size)
3004  {
3005  _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
3006  std::__move_merge_adaptive_backward(__first, __middle, __buffer,
3007  __buffer_end, __last, __comp);
3008  }
3009  else
3010  {
3011  _BidirectionalIterator __first_cut = __first;
3012  _BidirectionalIterator __second_cut = __middle;
3013  _Distance __len11 = 0;
3014  _Distance __len22 = 0;
3015  if (__len1 > __len2)
3016  {
3017  __len11 = __len1 / 2;
3018  std::advance(__first_cut, __len11);
3019  __second_cut = std::lower_bound(__middle, __last, *__first_cut,
3020  __comp);
3021  __len22 = std::distance(__middle, __second_cut);
3022  }
3023  else
3024  {
3025  __len22 = __len2 / 2;
3026  std::advance(__second_cut, __len22);
3027  __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3028  __comp);
3029  __len11 = std::distance(__first, __first_cut);
3030  }
3031  _BidirectionalIterator __new_middle =
3032  std::__rotate_adaptive(__first_cut, __middle, __second_cut,
3033  __len1 - __len11, __len22, __buffer,
3034  __buffer_size);
3035  std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3036  __len22, __buffer, __buffer_size, __comp);
3037  std::__merge_adaptive(__new_middle, __second_cut, __last,
3038  __len1 - __len11,
3039  __len2 - __len22, __buffer,
3040  __buffer_size, __comp);
3041  }
3042  }
3043 
3045  template<typename _BidirectionalIterator, typename _Distance>
3046  void
3047  __merge_without_buffer(_BidirectionalIterator __first,
3048  _BidirectionalIterator __middle,
3049  _BidirectionalIterator __last,
3050  _Distance __len1, _Distance __len2)
3051  {
3052  if (__len1 == 0 || __len2 == 0)
3053  return;
3054  if (__len1 + __len2 == 2)
3055  {
3056  if (*__middle < *__first)
3057  std::iter_swap(__first, __middle);
3058  return;
3059  }
3060  _BidirectionalIterator __first_cut = __first;
3061  _BidirectionalIterator __second_cut = __middle;
3062  _Distance __len11 = 0;
3063  _Distance __len22 = 0;
3064  if (__len1 > __len2)
3065  {
3066  __len11 = __len1 / 2;
3067  std::advance(__first_cut, __len11);
3068  __second_cut = std::lower_bound(__middle, __last, *__first_cut);
3069  __len22 = std::distance(__middle, __second_cut);
3070  }
3071  else
3072  {
3073  __len22 = __len2 / 2;
3074  std::advance(__second_cut, __len22);
3075  __first_cut = std::upper_bound(__first, __middle, *__second_cut);
3076  __len11 = std::distance(__first, __first_cut);
3077  }
3078  std::rotate(__first_cut, __middle, __second_cut);
3079  _BidirectionalIterator __new_middle = __first_cut;
3080  std::advance(__new_middle, std::distance(__middle, __second_cut));
3081  std::__merge_without_buffer(__first, __first_cut, __new_middle,
3082  __len11, __len22);
3083  std::__merge_without_buffer(__new_middle, __second_cut, __last,
3084  __len1 - __len11, __len2 - __len22);
3085  }
3086 
3088  template<typename _BidirectionalIterator, typename _Distance,
3089  typename _Compare>
3090  void
3091  __merge_without_buffer(_BidirectionalIterator __first,
3092  _BidirectionalIterator __middle,
3093  _BidirectionalIterator __last,
3094  _Distance __len1, _Distance __len2,
3095  _Compare __comp)
3096  {
3097  if (__len1 == 0 || __len2 == 0)
3098  return;
3099  if (__len1 + __len2 == 2)
3100  {
3101  if (__comp(*__middle, *__first))
3102  std::iter_swap(__first, __middle);
3103  return;
3104  }
3105  _BidirectionalIterator __first_cut = __first;
3106  _BidirectionalIterator __second_cut = __middle;
3107  _Distance __len11 = 0;
3108  _Distance __len22 = 0;
3109  if (__len1 > __len2)
3110  {
3111  __len11 = __len1 / 2;
3112  std::advance(__first_cut, __len11);
3113  __second_cut = std::lower_bound(__middle, __last, *__first_cut,
3114  __comp);
3115  __len22 = std::distance(__middle, __second_cut);
3116  }
3117  else
3118  {
3119  __len22 = __len2 / 2;
3120  std::advance(__second_cut, __len22);
3121  __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3122  __comp);
3123  __len11 = std::distance(__first, __first_cut);
3124  }
3125  std::rotate(__first_cut, __middle, __second_cut);
3126  _BidirectionalIterator __new_middle = __first_cut;
3127  std::advance(__new_middle, std::distance(__middle, __second_cut));
3128  std::__merge_without_buffer(__first, __first_cut, __new_middle,
3129  __len11, __len22, __comp);
3130  std::__merge_without_buffer(__new_middle, __second_cut, __last,
3131  __len1 - __len11, __len2 - __len22, __comp);
3132  }
3133 
3152  template<typename _BidirectionalIterator>
3153  void
3154  inplace_merge(_BidirectionalIterator __first,
3155  _BidirectionalIterator __middle,
3156  _BidirectionalIterator __last)
3157  {
3158  typedef typename iterator_traits<_BidirectionalIterator>::value_type
3159  _ValueType;
3160  typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3161  _DistanceType;
3162 
3163  // concept requirements
3164  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3165  _BidirectionalIterator>)
3166  __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3167  __glibcxx_requires_sorted(__first, __middle);
3168  __glibcxx_requires_sorted(__middle, __last);
3169 
3170  if (__first == __middle || __middle == __last)
3171  return;
3172 
3173  _DistanceType __len1 = std::distance(__first, __middle);
3174  _DistanceType __len2 = std::distance(__middle, __last);
3175 
3176  _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3177  __last);
3178  if (__buf.begin() == 0)
3179  std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
3180  else
3181  std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3182  __buf.begin(), _DistanceType(__buf.size()));
3183  }
3184 
3207  template<typename _BidirectionalIterator, typename _Compare>
3208  void
3209  inplace_merge(_BidirectionalIterator __first,
3210  _BidirectionalIterator __middle,
3211  _BidirectionalIterator __last,
3212  _Compare __comp)
3213  {
3214  typedef typename iterator_traits<_BidirectionalIterator>::value_type
3215  _ValueType;
3216  typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3217  _DistanceType;
3218 
3219  // concept requirements
3220  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3221  _BidirectionalIterator>)
3222  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3223  _ValueType, _ValueType>)
3224  __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3225  __glibcxx_requires_sorted_pred(__middle, __last, __comp);
3226 
3227  if (__first == __middle || __middle == __last)
3228  return;
3229 
3230  const _DistanceType __len1 = std::distance(__first, __middle);
3231  const _DistanceType __len2 = std::distance(__middle, __last);
3232 
3233  _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3234  __last);
3235  if (__buf.begin() == 0)
3236  std::__merge_without_buffer(__first, __middle, __last, __len1,
3237  __len2, __comp);
3238  else
3239  std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3240  __buf.begin(), _DistanceType(__buf.size()),
3241  __comp);
3242  }
3243 
3244 
3246  template<typename _InputIterator1, typename _InputIterator2,
3247  typename _OutputIterator>
3248  _OutputIterator
3249  __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
3250  _InputIterator2 __first2, _InputIterator2 __last2,
3251  _OutputIterator __result)
3252  {
3253  while (__first1 != __last1 && __first2 != __last2)
3254  {
3255  if (*__first2 < *__first1)
3256  {
3257  *__result = _GLIBCXX_MOVE(*__first2);
3258  ++__first2;
3259  }
3260  else
3261  {
3262  *__result = _GLIBCXX_MOVE(*__first1);
3263  ++__first1;
3264  }
3265  ++__result;
3266  }
3267  return _GLIBCXX_MOVE3(__first2, __last2,
3268  _GLIBCXX_MOVE3(__first1, __last1,
3269  __result));
3270  }
3271 
3273  template<typename _InputIterator1, typename _InputIterator2,
3274  typename _OutputIterator, typename _Compare>
3275  _OutputIterator
3276  __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
3277  _InputIterator2 __first2, _InputIterator2 __last2,
3278  _OutputIterator __result, _Compare __comp)
3279  {
3280  while (__first1 != __last1 && __first2 != __last2)
3281  {
3282  if (__comp(*__first2, *__first1))
3283  {
3284  *__result = _GLIBCXX_MOVE(*__first2);
3285  ++__first2;
3286  }
3287  else
3288  {
3289  *__result = _GLIBCXX_MOVE(*__first1);
3290  ++__first1;
3291  }
3292  ++__result;
3293  }
3294  return _GLIBCXX_MOVE3(__first2, __last2,
3295  _GLIBCXX_MOVE3(__first1, __last1,
3296  __result));
3297  }
3298 
3299  template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3300  typename _Distance>
3301  void
3302  __merge_sort_loop(_RandomAccessIterator1 __first,
3303  _RandomAccessIterator1 __last,
3304  _RandomAccessIterator2 __result,
3305  _Distance __step_size)
3306  {
3307  const _Distance __two_step = 2 * __step_size;
3308 
3309  while (__last - __first >= __two_step)
3310  {
3311  __result = std::__move_merge(__first, __first + __step_size,
3312  __first + __step_size,
3313  __first + __two_step, __result);
3314  __first += __two_step;
3315  }
3316 
3317  __step_size = std::min(_Distance(__last - __first), __step_size);
3318  std::__move_merge(__first, __first + __step_size,
3319  __first + __step_size, __last, __result);
3320  }
3321 
3322  template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3323  typename _Distance, typename _Compare>
3324  void
3325  __merge_sort_loop(_RandomAccessIterator1 __first,
3326  _RandomAccessIterator1 __last,
3327  _RandomAccessIterator2 __result, _Distance __step_size,
3328  _Compare __comp)
3329  {
3330  const _Distance __two_step = 2 * __step_size;
3331 
3332  while (__last - __first >= __two_step)
3333  {
3334  __result = std::__move_merge(__first, __first + __step_size,
3335  __first + __step_size,
3336  __first + __two_step,
3337  __result, __comp);
3338  __first += __two_step;
3339  }
3340  __step_size = std::min(_Distance(__last - __first), __step_size);
3341 
3342  std::__move_merge(__first,__first + __step_size,
3343  __first + __step_size, __last, __result, __comp);
3344  }
3345 
3346  template<typename _RandomAccessIterator, typename _Distance>
3347  void
3348  __chunk_insertion_sort(_RandomAccessIterator __first,
3349  _RandomAccessIterator __last,
3350  _Distance __chunk_size)
3351  {
3352  while (__last - __first >= __chunk_size)
3353  {
3354  std::__insertion_sort(__first, __first + __chunk_size);
3355  __first += __chunk_size;
3356  }
3357  std::__insertion_sort(__first, __last);
3358  }
3359 
3360  template<typename _RandomAccessIterator, typename _Distance,
3361  typename _Compare>
3362  void
3363  __chunk_insertion_sort(_RandomAccessIterator __first,
3364  _RandomAccessIterator __last,
3365  _Distance __chunk_size, _Compare __comp)
3366  {
3367  while (__last - __first >= __chunk_size)
3368  {
3369  std::__insertion_sort(__first, __first + __chunk_size, __comp);
3370  __first += __chunk_size;
3371  }
3372  std::__insertion_sort(__first, __last, __comp);
3373  }
3374 
3375  enum { _S_chunk_size = 7 };
3376 
3377  template<typename _RandomAccessIterator, typename _Pointer>
3378  void
3379  __merge_sort_with_buffer(_RandomAccessIterator __first,
3380  _RandomAccessIterator __last,
3381  _Pointer __buffer)
3382  {
3383  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3384  _Distance;
3385 
3386  const _Distance __len = __last - __first;
3387  const _Pointer __buffer_last = __buffer + __len;
3388 
3389  _Distance __step_size = _S_chunk_size;
3390  std::__chunk_insertion_sort(__first, __last, __step_size);
3391 
3392  while (__step_size < __len)
3393  {
3394  std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3395  __step_size *= 2;
3396  std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3397  __step_size *= 2;
3398  }
3399  }
3400 
3401  template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
3402  void
3403  __merge_sort_with_buffer(_RandomAccessIterator __first,
3404  _RandomAccessIterator __last,
3405  _Pointer __buffer, _Compare __comp)
3406  {
3407  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3408  _Distance;
3409 
3410  const _Distance __len = __last - __first;
3411  const _Pointer __buffer_last = __buffer + __len;
3412 
3413  _Distance __step_size = _S_chunk_size;
3414  std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3415 
3416  while (__step_size < __len)
3417  {
3418  std::__merge_sort_loop(__first, __last, __buffer,
3419  __step_size, __comp);
3420  __step_size *= 2;
3421  std::__merge_sort_loop(__buffer, __buffer_last, __first,
3422  __step_size, __comp);
3423  __step_size *= 2;
3424  }
3425  }
3426 
3427  template<typename _RandomAccessIterator, typename _Pointer,
3428  typename _Distance>
3429  void
3430  __stable_sort_adaptive(_RandomAccessIterator __first,
3431  _RandomAccessIterator __last,
3432  _Pointer __buffer, _Distance __buffer_size)
3433  {
3434  const _Distance __len = (__last - __first + 1) / 2;
3435  const _RandomAccessIterator __middle = __first + __len;
3436  if (__len > __buffer_size)
3437  {
3438  std::__stable_sort_adaptive(__first, __middle,
3439  __buffer, __buffer_size);
3440  std::__stable_sort_adaptive(__middle, __last,
3441  __buffer, __buffer_size);
3442  }
3443  else
3444  {
3445  std::__merge_sort_with_buffer(__first, __middle, __buffer);
3446  std::__merge_sort_with_buffer(__middle, __last, __buffer);
3447  }
3448  std::__merge_adaptive(__first, __middle, __last,
3449  _Distance(__middle - __first),
3450  _Distance(__last - __middle),
3451  __buffer, __buffer_size);
3452  }
3453 
3454  template<typename _RandomAccessIterator, typename _Pointer,
3455  typename _Distance, typename _Compare>
3456  void
3457  __stable_sort_adaptive(_RandomAccessIterator __first,
3458  _RandomAccessIterator __last,
3459  _Pointer __buffer, _Distance __buffer_size,
3460  _Compare __comp)
3461  {
3462  const _Distance __len = (__last - __first + 1) / 2;
3463  const _RandomAccessIterator __middle = __first + __len;
3464  if (__len > __buffer_size)
3465  {
3466  std::__stable_sort_adaptive(__first, __middle, __buffer,
3467  __buffer_size, __comp);
3468  std::__stable_sort_adaptive(__middle, __last, __buffer,
3469  __buffer_size, __comp);
3470  }
3471  else
3472  {
3473  std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3474  std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
3475  }
3476  std::__merge_adaptive(__first, __middle, __last,
3477  _Distance(__middle - __first),
3478  _Distance(__last - __middle),
3479  __buffer, __buffer_size,
3480  __comp);
3481  }
3482 
3484  template<typename _RandomAccessIterator>
3485  void
3486  __inplace_stable_sort(_RandomAccessIterator __first,
3487  _RandomAccessIterator __last)
3488  {
3489  if (__last - __first < 15)
3490  {
3491  std::__insertion_sort(__first, __last);
3492  return;
3493  }
3494  _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3495  std::__inplace_stable_sort(__first, __middle);
3496  std::__inplace_stable_sort(__middle, __last);
3497  std::__merge_without_buffer(__first, __middle, __last,
3498  __middle - __first,
3499  __last - __middle);
3500  }
3501 
3503  template<typename _RandomAccessIterator, typename _Compare>
3504  void
3505  __inplace_stable_sort(_RandomAccessIterator __first,
3506  _RandomAccessIterator __last, _Compare __comp)
3507  {
3508  if (__last - __first < 15)
3509  {
3510  std::__insertion_sort(__first, __last, __comp);
3511  return;
3512  }
3513  _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3514  std::__inplace_stable_sort(__first, __middle, __comp);
3515  std::__inplace_stable_sort(__middle, __last, __comp);
3516  std::__merge_without_buffer(__first, __middle, __last,
3517  __middle - __first,
3518  __last - __middle,
3519  __comp);
3520  }
3521 
3522  // stable_sort
3523 
3524  // Set algorithms: includes, set_union, set_intersection, set_difference,
3525  // set_symmetric_difference. All of these algorithms have the precondition
3526  // that their input ranges are sorted and the postcondition that their output
3527  // ranges are sorted.
3528 
3547  template<typename _InputIterator1, typename _InputIterator2>
3548  bool
3549  includes(_InputIterator1 __first1, _InputIterator1 __last1,
3550  _InputIterator2 __first2, _InputIterator2 __last2)
3551  {
3552  typedef typename iterator_traits<_InputIterator1>::value_type
3553  _ValueType1;
3554  typedef typename iterator_traits<_InputIterator2>::value_type
3555  _ValueType2;
3556 
3557  // concept requirements
3558  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3559  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3560  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
3561  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
3562  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
3563  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
3564 
3565  while (__first1 != __last1 && __first2 != __last2)
3566  if (*__first2 < *__first1)
3567  return false;
3568  else if(*__first1 < *__first2)
3569  ++__first1;
3570  else
3571  ++__first1, ++__first2;
3572 
3573  return __first2 == __last2;
3574  }
3575 
3597  template<typename _InputIterator1, typename _InputIterator2,
3598  typename _Compare>
3599  bool
3600  includes(_InputIterator1 __first1, _InputIterator1 __last1,
3601  _InputIterator2 __first2, _InputIterator2 __last2,
3602  _Compare __comp)
3603  {
3604  typedef typename iterator_traits<_InputIterator1>::value_type
3605  _ValueType1;
3606  typedef typename iterator_traits<_InputIterator2>::value_type
3607  _ValueType2;
3608 
3609  // concept requirements
3610  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3611  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3612  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3613  _ValueType1, _ValueType2>)
3614  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3615  _ValueType2, _ValueType1>)
3616  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
3617  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
3618 
3619  while (__first1 != __last1 && __first2 != __last2)
3620  if (__comp(*__first2, *__first1))
3621  return false;
3622  else if(__comp(*__first1, *__first2))
3623  ++__first1;
3624  else
3625  ++__first1, ++__first2;
3626 
3627  return __first2 == __last2;
3628  }
3629 
3630  // nth_element
3631  // merge
3632  // set_difference
3633  // set_intersection
3634  // set_union
3635  // stable_sort
3636  // set_symmetric_difference
3637  // min_element
3638  // max_element
3639 
3652  template<typename _BidirectionalIterator>
3653  bool
3654  next_permutation(_BidirectionalIterator __first,
3655  _BidirectionalIterator __last)
3656  {
3657  // concept requirements
3658  __glibcxx_function_requires(_BidirectionalIteratorConcept<
3659  _BidirectionalIterator>)
3660  __glibcxx_function_requires(_LessThanComparableConcept<
3661  typename iterator_traits<_BidirectionalIterator>::value_type>)
3662  __glibcxx_requires_valid_range(__first, __last);
3663 
3664  if (__first == __last)
3665  return false;
3666  _BidirectionalIterator __i = __first;
3667  ++__i;
3668  if (__i == __last)
3669  return false;
3670  __i = __last;
3671  --__i;
3672 
3673  for(;;)
3674  {
3675  _BidirectionalIterator __ii = __i;
3676  --__i;
3677  if (*__i < *__ii)
3678  {
3679  _BidirectionalIterator __j = __last;
3680  while (!(*__i < *--__j))
3681  {}
3682  std::iter_swap(__i, __j);
3683  std::reverse(__ii, __last);
3684  return true;
3685  }
3686  if (__i == __first)
3687  {
3688  std::reverse(__first, __last);
3689  return false;
3690  }
3691  }
3692  }
3693 
3709  template<typename _BidirectionalIterator, typename _Compare>
3710  bool
3711  next_permutation(_BidirectionalIterator __first,
3712  _BidirectionalIterator __last, _Compare __comp)
3713  {
3714  // concept requirements
3715  __glibcxx_function_requires(_BidirectionalIteratorConcept<
3716  _BidirectionalIterator>)
3717  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3718  typename iterator_traits<_BidirectionalIterator>::value_type,
3719  typename iterator_traits<_BidirectionalIterator>::value_type>)
3720  __glibcxx_requires_valid_range(__first, __last);
3721 
3722  if (__first == __last)
3723  return false;
3724  _BidirectionalIterator __i = __first;
3725  ++__i;
3726  if (__i == __last)
3727  return false;
3728  __i = __last;
3729  --__i;
3730 
3731  for(;;)
3732  {
3733  _BidirectionalIterator __ii = __i;
3734  --__i;
3735  if (__comp(*__i, *__ii))
3736  {
3737  _BidirectionalIterator __j = __last;
3738  while (!bool(__comp(*__i, *--__j)))
3739  {}
3740  std::iter_swap(__i, __j);
3741  std::reverse(__ii, __last);
3742  return true;
3743  }
3744  if (__i == __first)
3745  {
3746  std::reverse(__first, __last);
3747  return false;
3748  }
3749  }
3750  }
3751 
3765  template<typename _BidirectionalIterator>
3766  bool
3767  prev_permutation(_BidirectionalIterator __first,
3768  _BidirectionalIterator __last)
3769  {
3770  // concept requirements
3771  __glibcxx_function_requires(_BidirectionalIteratorConcept<
3772  _BidirectionalIterator>)
3773  __glibcxx_function_requires(_LessThanComparableConcept<
3774  typename iterator_traits<_BidirectionalIterator>::value_type>)
3775  __glibcxx_requires_valid_range(__first, __last);
3776 
3777  if (__first == __last)
3778  return false;
3779  _BidirectionalIterator __i = __first;
3780  ++__i;
3781  if (__i == __last)
3782  return false;
3783  __i = __last;
3784  --__i;
3785 
3786  for(;;)
3787  {
3788  _BidirectionalIterator __ii = __i;
3789  --__i;
3790  if (*__ii < *__i)
3791  {
3792  _BidirectionalIterator __j = __last;
3793  while (!(*--__j < *__i))
3794  {}
3795  std::iter_swap(__i, __j);
3796  std::reverse(__ii, __last);
3797  return true;
3798  }
3799  if (__i == __first)
3800  {
3801  std::reverse(__first, __last);
3802  return false;
3803  }
3804  }
3805  }
3806 
3822  template<typename _BidirectionalIterator, typename _Compare>
3823  bool
3824  prev_permutation(_BidirectionalIterator __first,
3825  _BidirectionalIterator __last, _Compare __comp)
3826  {
3827  // concept requirements
3828  __glibcxx_function_requires(_BidirectionalIteratorConcept<
3829  _BidirectionalIterator>)
3830  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3831  typename iterator_traits<_BidirectionalIterator>::value_type,
3832  typename iterator_traits<_BidirectionalIterator>::value_type>)
3833  __glibcxx_requires_valid_range(__first, __last);
3834 
3835  if (__first == __last)
3836  return false;
3837  _BidirectionalIterator __i = __first;
3838  ++__i;
3839  if (__i == __last)
3840  return false;
3841  __i = __last;
3842  --__i;
3843 
3844  for(;;)
3845  {
3846  _BidirectionalIterator __ii = __i;
3847  --__i;
3848  if (__comp(*__ii, *__i))
3849  {
3850  _BidirectionalIterator __j = __last;
3851  while (!bool(__comp(*--__j, *__i)))
3852  {}
3853  std::iter_swap(__i, __j);
3854  std::reverse(__ii, __last);
3855  return true;
3856  }
3857  if (__i == __first)
3858  {
3859  std::reverse(__first, __last);
3860  return false;
3861  }
3862  }
3863  }
3864 
3865  // replace
3866  // replace_if
3867 
3882  template<typename _InputIterator, typename _OutputIterator, typename _Tp>
3883  _OutputIterator
3884  replace_copy(_InputIterator __first, _InputIterator __last,
3885  _OutputIterator __result,
3886  const _Tp& __old_value, const _Tp& __new_value)
3887  {
3888  // concept requirements
3889  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3890  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3891  typename iterator_traits<_InputIterator>::value_type>)
3892  __glibcxx_function_requires(_EqualOpConcept<
3893  typename iterator_traits<_InputIterator>::value_type, _Tp>)
3894  __glibcxx_requires_valid_range(__first, __last);
3895 
3896  for (; __first != __last; ++__first, ++__result)
3897  if (*__first == __old_value)
3898  *__result = __new_value;
3899  else
3900  *__result = *__first;
3901  return __result;
3902  }
3903 
3919  template<typename _InputIterator, typename _OutputIterator,
3920  typename _Predicate, typename _Tp>
3921  _OutputIterator
3922  replace_copy_if(_InputIterator __first, _InputIterator __last,
3923  _OutputIterator __result,
3924  _Predicate __pred, const _Tp& __new_value)
3925  {
3926  // concept requirements
3927  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3928  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3929  typename iterator_traits<_InputIterator>::value_type>)
3930  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3931  typename iterator_traits<_InputIterator>::value_type>)
3932  __glibcxx_requires_valid_range(__first, __last);
3933 
3934  for (; __first != __last; ++__first, ++__result)
3935  if (__pred(*__first))
3936  *__result = __new_value;
3937  else
3938  *__result = *__first;
3939  return __result;
3940  }
3941 
3942 #if __cplusplus >= 201103L
3943 
3950  template<typename _ForwardIterator>
3951  inline bool
3952  is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3953  { return std::is_sorted_until(__first, __last) == __last; }
3954 
3964  template<typename _ForwardIterator, typename _Compare>
3965  inline bool
3966  is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3967  _Compare __comp)
3968  { return std::is_sorted_until(__first, __last, __comp) == __last; }
3969 
3978  template<typename _ForwardIterator>
3979  _ForwardIterator
3980  is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3981  {
3982  // concept requirements
3983  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3984  __glibcxx_function_requires(_LessThanComparableConcept<
3985  typename iterator_traits<_ForwardIterator>::value_type>)
3986  __glibcxx_requires_valid_range(__first, __last);
3987 
3988  if (__first == __last)
3989  return __last;
3990 
3991  _ForwardIterator __next = __first;
3992  for (++__next; __next != __last; __first = __next, ++__next)
3993  if (*__next < *__first)
3994  return __next;
3995  return __next;
3996  }
3997 
4007  template<typename _ForwardIterator, typename _Compare>
4008  _ForwardIterator
4009  is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
4010  _Compare __comp)
4011  {
4012  // concept requirements
4013  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4014  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4015  typename iterator_traits<_ForwardIterator>::value_type,
4016  typename iterator_traits<_ForwardIterator>::value_type>)
4017  __glibcxx_requires_valid_range(__first, __last);
4018 
4019  if (__first == __last)
4020  return __last;
4021 
4022  _ForwardIterator __next = __first;
4023  for (++__next; __next != __last; __first = __next, ++__next)
4024  if (__comp(*__next, *__first))
4025  return __next;
4026  return __next;
4027  }
4028 
4037  template<typename _Tp>
4038  inline pair<const _Tp&, const _Tp&>
4039  minmax(const _Tp& __a, const _Tp& __b)
4040  {
4041  // concept requirements
4042  __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
4043 
4044  return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
4045  : pair<const _Tp&, const _Tp&>(__a, __b);
4046  }
4047 
4057  template<typename _Tp, typename _Compare>
4058  inline pair<const _Tp&, const _Tp&>
4059  minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
4060  {
4061  return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
4062  : pair<const _Tp&, const _Tp&>(__a, __b);
4063  }
4064 
4076  template<typename _ForwardIterator>
4077  pair<_ForwardIterator, _ForwardIterator>
4078  minmax_element(_ForwardIterator __first, _ForwardIterator __last)
4079  {
4080  // concept requirements
4081  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4082  __glibcxx_function_requires(_LessThanComparableConcept<
4083  typename iterator_traits<_ForwardIterator>::value_type>)
4084  __glibcxx_requires_valid_range(__first, __last);
4085 
4086  _ForwardIterator __next = __first;
4087  if (__first == __last
4088  || ++__next == __last)
4089  return std::make_pair(__first, __first);
4090 
4091  _ForwardIterator __min, __max;
4092  if (*__next < *__first)
4093  {
4094  __min = __next;
4095  __max = __first;
4096  }
4097  else
4098  {
4099  __min = __first;
4100  __max = __next;
4101  }
4102 
4103  __first = __next;
4104  ++__first;
4105 
4106  while (__first != __last)
4107  {
4108  __next = __first;
4109  if (++__next == __last)
4110  {
4111  if (*__first < *__min)
4112  __min = __first;
4113  else if (!(*__first < *__max))
4114  __max = __first;
4115  break;
4116  }
4117 
4118  if (*__next < *__first)
4119  {
4120  if (*__next < *__min)
4121  __min = __next;
4122  if (!(*__first < *__max))
4123  __max = __first;
4124  }
4125  else
4126  {
4127  if (*__first < *__min)
4128  __min = __first;
4129  if (!(*__next < *__max))
4130  __max = __next;
4131  }
4132 
4133  __first = __next;
4134  ++__first;
4135  }
4136 
4137  return std::make_pair(__min, __max);
4138  }
4139 
4152  template<typename _ForwardIterator, typename _Compare>
4153  pair<_ForwardIterator, _ForwardIterator>
4154  minmax_element(_ForwardIterator __first, _ForwardIterator __last,
4155  _Compare __comp)
4156  {
4157  // concept requirements
4158  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4159  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4160  typename iterator_traits<_ForwardIterator>::value_type,
4161  typename iterator_traits<_ForwardIterator>::value_type>)
4162  __glibcxx_requires_valid_range(__first, __last);
4163 
4164  _ForwardIterator __next = __first;
4165  if (__first == __last
4166  || ++__next == __last)
4167  return std::make_pair(__first, __first);
4168 
4169  _ForwardIterator __min, __max;
4170  if (__comp(*__next, *__first))
4171  {
4172  __min = __next;
4173  __max = __first;
4174  }
4175  else
4176  {
4177  __min = __first;
4178  __max = __next;
4179  }
4180 
4181  __first = __next;
4182  ++__first;
4183 
4184  while (__first != __last)
4185  {
4186  __next = __first;
4187  if (++__next == __last)
4188  {
4189  if (__comp(*__first, *__min))
4190  __min = __first;
4191  else if (!__comp(*__first, *__max))
4192  __max = __first;
4193  break;
4194  }
4195 
4196  if (__comp(*__next, *__first))
4197  {
4198  if (__comp(*__next, *__min))
4199  __min = __next;
4200  if (!__comp(*__first, *__max))
4201  __max = __first;
4202  }
4203  else
4204  {
4205  if (__comp(*__first, *__min))
4206  __min = __first;
4207  if (!__comp(*__next, *__max))
4208  __max = __next;
4209  }
4210 
4211  __first = __next;
4212  ++__first;
4213  }
4214 
4215  return std::make_pair(__min, __max);
4216  }
4217 
4218  // N2722 + DR 915.
4219  template<typename _Tp>
4220  inline _Tp
4221  min(initializer_list<_Tp> __l)
4222  { return *std::min_element(__l.begin(), __l.end()); }
4223 
4224  template<typename _Tp, typename _Compare>
4225  inline _Tp
4226  min(initializer_list<_Tp> __l, _Compare __comp)
4227  { return *std::min_element(__l.begin(), __l.end(), __comp); }
4228 
4229  template<typename _Tp>
4230  inline _Tp
4231  max(initializer_list<_Tp> __l)
4232  { return *std::max_element(__l.begin(), __l.end()); }
4233 
4234  template<typename _Tp, typename _Compare>
4235  inline _Tp
4236  max(initializer_list<_Tp> __l, _Compare __comp)
4237  { return *std::max_element(__l.begin(), __l.end(), __comp); }
4238 
4239  template<typename _Tp>
4240  inline pair<_Tp, _Tp>
4241  minmax(initializer_list<_Tp> __l)
4242  {
4243  pair<const _Tp*, const _Tp*> __p =
4244  std::minmax_element(__l.begin(), __l.end());
4245  return std::make_pair(*__p.first, *__p.second);
4246  }
4247 
4248  template<typename _Tp, typename _Compare>
4249  inline pair<_Tp, _Tp>
4250  minmax(initializer_list<_Tp> __l, _Compare __comp)
4251  {
4252  pair<const _Tp*, const _Tp*> __p =
4253  std::minmax_element(__l.begin(), __l.end(), __comp);
4254  return std::make_pair(*__p.first, *__p.second);
4255  }
4256 
4269  template<typename _ForwardIterator1, typename _ForwardIterator2>
4270  bool
4271  is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4272  _ForwardIterator2 __first2)
4273  {
4274  // Efficiently compare identical prefixes: O(N) if sequences
4275  // have the same elements in the same order.
4276  for (; __first1 != __last1; ++__first1, ++__first2)
4277  if (!(*__first1 == *__first2))
4278  break;
4279 
4280  if (__first1 == __last1)
4281  return true;
4282 
4283  // Establish __last2 assuming equal ranges by iterating over the
4284  // rest of the list.
4285  _ForwardIterator2 __last2 = __first2;
4286  std::advance(__last2, std::distance(__first1, __last1));
4287  for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4288  {
4289  if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
4290  continue; // We've seen this one before.
4291 
4292  auto __matches = std::count(__first2, __last2, *__scan);
4293  if (0 == __matches
4294  || std::count(__scan, __last1, *__scan) != __matches)
4295  return false;
4296  }
4297  return true;
4298  }
4299 
4314  template<typename _ForwardIterator1, typename _ForwardIterator2,
4315  typename _BinaryPredicate>
4316  bool
4317  is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4318  _ForwardIterator2 __first2, _BinaryPredicate __pred)
4319  {
4320  // Efficiently compare identical prefixes: O(N) if sequences
4321  // have the same elements in the same order.
4322  for (; __first1 != __last1; ++__first1, ++__first2)
4323  if (!bool(__pred(*__first1, *__first2)))
4324  break;
4325 
4326  if (__first1 == __last1)
4327  return true;
4328 
4329  // Establish __last2 assuming equal ranges by iterating over the
4330  // rest of the list.
4331  _ForwardIterator2 __last2 = __first2;
4332  std::advance(__last2, std::distance(__first1, __last1));
4333  for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4334  {
4335  using std::placeholders::_1;
4336 
4337  if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
4338  std::bind(__pred, _1, *__scan)))
4339  continue; // We've seen this one before.
4340 
4341  auto __matches = std::count_if(__first2, __last2,
4342  std::bind(__pred, _1, *__scan));
4343  if (0 == __matches
4344  || std::count_if(__scan, __last1,
4345  std::bind(__pred, _1, *__scan)) != __matches)
4346  return false;
4347  }
4348  return true;
4349  }
4350 
4351 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
4352 
4364  template<typename _RandomAccessIterator,
4365  typename _UniformRandomNumberGenerator>
4366  void
4367  shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4368  _UniformRandomNumberGenerator&& __g)
4369  {
4370  // concept requirements
4371  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4372  _RandomAccessIterator>)
4373  __glibcxx_requires_valid_range(__first, __last);
4374 
4375  if (__first == __last)
4376  return;
4377 
4378  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4379  _DistanceType;
4380 
4381  typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
4382  typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
4383  typedef typename __distr_type::param_type __p_type;
4384  __distr_type __d;
4385 
4386  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4387  std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
4388  }
4389 #endif
4390 
4391 #endif // C++11
4392 
4393 _GLIBCXX_END_NAMESPACE_VERSION
4394 
4395 _GLIBCXX_BEGIN_NAMESPACE_ALGO
4396 
4409  template<typename _InputIterator, typename _Function>
4410  _Function
4411  for_each(_InputIterator __first, _InputIterator __last, _Function __f)
4412  {
4413  // concept requirements
4414  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4415  __glibcxx_requires_valid_range(__first, __last);
4416  for (; __first != __last; ++__first)
4417  __f(*__first);
4418  return _GLIBCXX_MOVE(__f);
4419  }
4420 
4430  template<typename _InputIterator, typename _Tp>
4431  inline _InputIterator
4432  find(_InputIterator __first, _InputIterator __last,
4433  const _Tp& __val)
4434  {
4435  // concept requirements
4436  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4437  __glibcxx_function_requires(_EqualOpConcept<
4438  typename iterator_traits<_InputIterator>::value_type, _Tp>)
4439  __glibcxx_requires_valid_range(__first, __last);
4440  return std::__find(__first, __last, __val,
4441  std::__iterator_category(__first));
4442  }
4443 
4454  template<typename _InputIterator, typename _Predicate>
4455  inline _InputIterator
4456  find_if(_InputIterator __first, _InputIterator __last,
4457  _Predicate __pred)
4458  {
4459  // concept requirements
4460  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4461  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4462  typename iterator_traits<_InputIterator>::value_type>)
4463  __glibcxx_requires_valid_range(__first, __last);
4464  return std::__find_if(__first, __last, __pred,
4465  std::__iterator_category(__first));
4466  }
4467 
4484  template<typename _InputIterator, typename _ForwardIterator>
4485  _InputIterator
4486  find_first_of(_InputIterator __first1, _InputIterator __last1,
4487  _ForwardIterator __first2, _ForwardIterator __last2)
4488  {
4489  // concept requirements
4490  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4491  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4492  __glibcxx_function_requires(_EqualOpConcept<
4493  typename iterator_traits<_InputIterator>::value_type,
4494  typename iterator_traits<_ForwardIterator>::value_type>)
4495  __glibcxx_requires_valid_range(__first1, __last1);
4496  __glibcxx_requires_valid_range(__first2, __last2);
4497 
4498  for (; __first1 != __last1; ++__first1)
4499  for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4500  if (*__first1 == *__iter)
4501  return __first1;
4502  return __last1;
4503  }
4504 
4524  template<typename _InputIterator, typename _ForwardIterator,
4525  typename _BinaryPredicate>
4526  _InputIterator
4527  find_first_of(_InputIterator __first1, _InputIterator __last1,
4528  _ForwardIterator __first2, _ForwardIterator __last2,
4529  _BinaryPredicate __comp)
4530  {
4531  // concept requirements
4532  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4533  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4534  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4535  typename iterator_traits<_InputIterator>::value_type,
4536  typename iterator_traits<_ForwardIterator>::value_type>)
4537  __glibcxx_requires_valid_range(__first1, __last1);
4538  __glibcxx_requires_valid_range(__first2, __last2);
4539 
4540  for (; __first1 != __last1; ++__first1)
4541  for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4542  if (__comp(*__first1, *__iter))
4543  return __first1;
4544  return __last1;
4545  }
4546 
4556  template<typename _ForwardIterator>
4557  _ForwardIterator
4558  adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4559  {
4560  // concept requirements
4561  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4562  __glibcxx_function_requires(_EqualityComparableConcept<
4563  typename iterator_traits<_ForwardIterator>::value_type>)
4564  __glibcxx_requires_valid_range(__first, __last);
4565  if (__first == __last)
4566  return __last;
4567  _ForwardIterator __next = __first;
4568  while(++__next != __last)
4569  {
4570  if (*__first == *__next)
4571  return __first;
4572  __first = __next;
4573  }
4574  return __last;
4575  }
4576 
4588  template<typename _ForwardIterator, typename _BinaryPredicate>
4589  _ForwardIterator
4590  adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4591  _BinaryPredicate __binary_pred)
4592  {
4593  // concept requirements
4594  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4595  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4596  typename iterator_traits<_ForwardIterator>::value_type,
4597  typename iterator_traits<_ForwardIterator>::value_type>)
4598  __glibcxx_requires_valid_range(__first, __last);
4599  if (__first == __last)
4600  return __last;
4601  _ForwardIterator __next = __first;
4602  while(++__next != __last)
4603  {
4604  if (__binary_pred(*__first, *__next))
4605  return __first;
4606  __first = __next;
4607  }
4608  return __last;
4609  }
4610 
4620  template<typename _InputIterator, typename _Tp>
4621  typename iterator_traits<_InputIterator>::difference_type
4622  count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4623  {
4624  // concept requirements
4625  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4626  __glibcxx_function_requires(_EqualOpConcept<
4627  typename iterator_traits<_InputIterator>::value_type, _Tp>)
4628  __glibcxx_requires_valid_range(__first, __last);
4629  typename iterator_traits<_InputIterator>::difference_type __n = 0;
4630  for (; __first != __last; ++__first)
4631  if (*__first == __value)
4632  ++__n;
4633  return __n;
4634  }
4635 
4645  template<typename _InputIterator, typename _Predicate>
4646  typename iterator_traits<_InputIterator>::difference_type
4647  count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4648  {
4649  // concept requirements
4650  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4651  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4652  typename iterator_traits<_InputIterator>::value_type>)
4653  __glibcxx_requires_valid_range(__first, __last);
4654  typename iterator_traits<_InputIterator>::difference_type __n = 0;
4655  for (; __first != __last; ++__first)
4656  if (__pred(*__first))
4657  ++__n;
4658  return __n;
4659  }
4660 
4687  template<typename _ForwardIterator1, typename _ForwardIterator2>
4688  _ForwardIterator1
4689  search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4690  _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4691  {
4692  // concept requirements
4693  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4694  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4695  __glibcxx_function_requires(_EqualOpConcept<
4696  typename iterator_traits<_ForwardIterator1>::value_type,
4697  typename iterator_traits<_ForwardIterator2>::value_type>)
4698  __glibcxx_requires_valid_range(__first1, __last1);
4699  __glibcxx_requires_valid_range(__first2, __last2);
4700 
4701  // Test for empty ranges
4702  if (__first1 == __last1 || __first2 == __last2)
4703  return __first1;
4704 
4705  // Test for a pattern of length 1.
4706  _ForwardIterator2 __p1(__first2);
4707  if (++__p1 == __last2)
4708  return _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
4709 
4710  // General case.
4711  _ForwardIterator2 __p;
4712  _ForwardIterator1 __current = __first1;
4713 
4714  for (;;)
4715  {
4716  __first1 = _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
4717  if (__first1 == __last1)
4718  return __last1;
4719 
4720  __p = __p1;
4721  __current = __first1;
4722  if (++__current == __last1)
4723  return __last1;
4724 
4725  while (*__current == *__p)
4726  {
4727  if (++__p == __last2)
4728  return __first1;
4729  if (++__current == __last1)
4730  return __last1;
4731  }
4732  ++__first1;
4733  }
4734  return __first1;
4735  }
4736 
4758  template<typename _ForwardIterator1, typename _ForwardIterator2,
4759  typename _BinaryPredicate>
4760  _ForwardIterator1
4761  search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4762  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4763  _BinaryPredicate __predicate)
4764  {
4765  // concept requirements
4766  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4767  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4768  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4769  typename iterator_traits<_ForwardIterator1>::value_type,
4770  typename iterator_traits<_ForwardIterator2>::value_type>)
4771  __glibcxx_requires_valid_range(__first1, __last1);
4772  __glibcxx_requires_valid_range(__first2, __last2);
4773 
4774  // Test for empty ranges
4775  if (__first1 == __last1 || __first2 == __last2)
4776  return __first1;
4777 
4778  // Test for a pattern of length 1.
4779  _ForwardIterator2 __p1(__first2);
4780  if (++__p1 == __last2)
4781  {
4782  while (__first1 != __last1
4783  && !bool(__predicate(*__first1, *__first2)))
4784  ++__first1;
4785  return __first1;
4786  }
4787 
4788  // General case.
4789  _ForwardIterator2 __p;
4790  _ForwardIterator1 __current = __first1;
4791 
4792  for (;;)
4793  {
4794  while (__first1 != __last1
4795  && !bool(__predicate(*__first1, *__first2)))
4796  ++__first1;
4797  if (__first1 == __last1)
4798  return __last1;
4799 
4800  __p = __p1;
4801  __current = __first1;
4802  if (++__current == __last1)
4803  return __last1;
4804 
4805  while (__predicate(*__current, *__p))
4806  {
4807  if (++__p == __last2)
4808  return __first1;
4809  if (++__current == __last1)
4810  return __last1;
4811  }
4812  ++__first1;
4813  }
4814  return __first1;
4815  }
4816 
4817 
4833  template<typename _ForwardIterator, typename _Integer, typename _Tp>
4834  _ForwardIterator
4835  search_n(_ForwardIterator __first, _ForwardIterator __last,
4836  _Integer __count, const _Tp& __val)
4837  {
4838  // concept requirements
4839  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4840  __glibcxx_function_requires(_EqualOpConcept<
4841  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4842  __glibcxx_requires_valid_range(__first, __last);
4843 
4844  if (__count <= 0)
4845  return __first;
4846  if (__count == 1)
4847  return _GLIBCXX_STD_A::find(__first, __last, __val);
4848  return std::__search_n(__first, __last, __count, __val,
4849  std::__iterator_category(__first));
4850  }
4851 
4852 
4870  template<typename _ForwardIterator, typename _Integer, typename _Tp,
4871  typename _BinaryPredicate>
4872  _ForwardIterator
4873  search_n(_ForwardIterator __first, _ForwardIterator __last,
4874  _Integer __count, const _Tp& __val,
4875  _BinaryPredicate __binary_pred)
4876  {
4877  // concept requirements
4878  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4879  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4880  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4881  __glibcxx_requires_valid_range(__first, __last);
4882 
4883  if (__count <= 0)
4884  return __first;
4885  if (__count == 1)
4886  {
4887  while (__first != __last && !bool(__binary_pred(*__first, __val)))
4888  ++__first;
4889  return __first;
4890  }
4891  return std::__search_n(__first, __last, __count, __val, __binary_pred,
4892  std::__iterator_category(__first));
4893  }
4894 
4895 
4912  template<typename _InputIterator, typename _OutputIterator,
4913  typename _UnaryOperation>
4914  _OutputIterator
4915  transform(_InputIterator __first, _InputIterator __last,
4916  _OutputIterator __result, _UnaryOperation __unary_op)
4917  {
4918  // concept requirements
4919  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4920  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4921  // "the type returned by a _UnaryOperation"
4922  __typeof__(__unary_op(*__first))>)
4923  __glibcxx_requires_valid_range(__first, __last);
4924 
4925  for (; __first != __last; ++__first, ++__result)
4926  *__result = __unary_op(*__first);
4927  return __result;
4928  }
4929 
4949  template<typename _InputIterator1, typename _InputIterator2,
4950  typename _OutputIterator, typename _BinaryOperation>
4951  _OutputIterator
4952  transform(_InputIterator1 __first1, _InputIterator1 __last1,
4953  _InputIterator2 __first2, _OutputIterator __result,
4954  _BinaryOperation __binary_op)
4955  {
4956  // concept requirements
4957  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4958  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4959  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4960  // "the type returned by a _BinaryOperation"
4961  __typeof__(__binary_op(*__first1,*__first2))>)
4962  __glibcxx_requires_valid_range(__first1, __last1);
4963 
4964  for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
4965  *__result = __binary_op(*__first1, *__first2);
4966  return __result;
4967  }
4968 
4982  template<typename _ForwardIterator, typename _Tp>
4983  void
4984  replace(_ForwardIterator __first, _ForwardIterator __last,
4985  const _Tp& __old_value, const _Tp& __new_value)
4986  {
4987  // concept requirements
4988  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4989  _ForwardIterator>)
4990  __glibcxx_function_requires(_EqualOpConcept<
4991  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4992  __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4993  typename iterator_traits<_ForwardIterator>::value_type>)
4994  __glibcxx_requires_valid_range(__first, __last);
4995 
4996  for (; __first != __last; ++__first)
4997  if (*__first == __old_value)
4998  *__first = __new_value;
4999  }
5000 
5014  template<typename _ForwardIterator, typename _Predicate, typename _Tp>
5015  void
5016  replace_if(_ForwardIterator __first, _ForwardIterator __last,
5017  _Predicate __pred, const _Tp& __new_value)
5018  {
5019  // concept requirements
5020  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5021  _ForwardIterator>)
5022  __glibcxx_function_requires(_ConvertibleConcept<_Tp,
5023  typename iterator_traits<_ForwardIterator>::value_type>)
5024  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5025  typename iterator_traits<_ForwardIterator>::value_type>)
5026  __glibcxx_requires_valid_range(__first, __last);
5027 
5028  for (; __first != __last; ++__first)
5029  if (__pred(*__first))
5030  *__first = __new_value;
5031  }
5032 
5046  template<typename _ForwardIterator, typename _Generator>
5047  void
5048  generate(_ForwardIterator __first, _ForwardIterator __last,
5049  _Generator __gen)
5050  {
5051  // concept requirements
5052  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5053  __glibcxx_function_requires(_GeneratorConcept<_Generator,
5054  typename iterator_traits<_ForwardIterator>::value_type>)
5055  __glibcxx_requires_valid_range(__first, __last);
5056 
5057  for (; __first != __last; ++__first)
5058  *__first = __gen();
5059  }
5060 
5077  template<typename _OutputIterator, typename _Size, typename _Generator>
5078  _OutputIterator
5079  generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
5080  {
5081  // concept requirements
5082  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5083  // "the type returned by a _Generator"
5084  __typeof__(__gen())>)
5085 
5086  for (__decltype(__n + 0) __niter = __n;
5087  __niter > 0; --__niter, ++__first)
5088  *__first = __gen();
5089  return __first;
5090  }
5091 
5092 
5114  template<typename _InputIterator, typename _OutputIterator>
5115  inline _OutputIterator
5116  unique_copy(_InputIterator __first, _InputIterator __last,
5117  _OutputIterator __result)
5118  {
5119  // concept requirements
5120  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5121  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5122  typename iterator_traits<_InputIterator>::value_type>)
5123  __glibcxx_function_requires(_EqualityComparableConcept<
5124  typename iterator_traits<_InputIterator>::value_type>)
5125  __glibcxx_requires_valid_range(__first, __last);
5126 
5127  if (__first == __last)
5128  return __result;
5129  return std::__unique_copy(__first, __last, __result,
5130  std::__iterator_category(__first),
5131  std::__iterator_category(__result));
5132  }
5133 
5153  template<typename _InputIterator, typename _OutputIterator,
5154  typename _BinaryPredicate>
5155  inline _OutputIterator
5156  unique_copy(_InputIterator __first, _InputIterator __last,
5157  _OutputIterator __result,
5158  _BinaryPredicate __binary_pred)
5159  {
5160  // concept requirements -- predicates checked later
5161  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5162  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5163  typename iterator_traits<_InputIterator>::value_type>)
5164  __glibcxx_requires_valid_range(__first, __last);
5165 
5166  if (__first == __last)
5167  return __result;
5168  return std::__unique_copy(__first, __last, __result, __binary_pred,
5169  std::__iterator_category(__first),
5170  std::__iterator_category(__result));
5171  }
5172 
5173 
5185  template<typename _RandomAccessIterator>
5186  inline void
5187  random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
5188  {
5189  // concept requirements
5190  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5191  _RandomAccessIterator>)
5192  __glibcxx_requires_valid_range(__first, __last);
5193 
5194  if (__first != __last)
5195  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5196  {
5197  _RandomAccessIterator __j = __first
5198  + std::rand() % ((__i - __first) + 1);
5199  if (__i != __j)
5200  std::iter_swap(__i, __j);
5201  }
5202  }
5203 
5218  template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
5219  void
5220  random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
5221 #if __cplusplus >= 201103L
5222  _RandomNumberGenerator&& __rand)
5223 #else
5224  _RandomNumberGenerator& __rand)
5225 #endif
5226  {
5227  // concept requirements
5228  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5229  _RandomAccessIterator>)
5230  __glibcxx_requires_valid_range(__first, __last);
5231 
5232  if (__first == __last)
5233  return;
5234  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5235  {
5236  _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
5237  if (__i != __j)
5238  std::iter_swap(__i, __j);
5239  }
5240  }
5241 
5242 
5258  template<typename _ForwardIterator, typename _Predicate>
5259  inline _ForwardIterator
5260  partition(_ForwardIterator __first, _ForwardIterator __last,
5261  _Predicate __pred)
5262  {
5263  // concept requirements
5264  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5265  _ForwardIterator>)
5266  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5267  typename iterator_traits<_ForwardIterator>::value_type>)
5268  __glibcxx_requires_valid_range(__first, __last);
5269 
5270  return std::__partition(__first, __last, __pred,
5271  std::__iterator_category(__first));
5272  }
5273 
5274 
5275 
5292  template<typename _RandomAccessIterator>
5293  inline void
5294  partial_sort(_RandomAccessIterator __first,
5295  _RandomAccessIterator __middle,
5296  _RandomAccessIterator __last)
5297  {
5298  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5299  _ValueType;
5300 
5301  // concept requirements
5302  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5303  _RandomAccessIterator>)
5304  __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5305  __glibcxx_requires_valid_range(__first, __middle);
5306  __glibcxx_requires_valid_range(__middle, __last);
5307 
5308  std::__heap_select(__first, __middle, __last);
5309  std::sort_heap(__first, __middle);
5310  }
5311 
5331  template<typename _RandomAccessIterator, typename _Compare>
5332  inline void
5333  partial_sort(_RandomAccessIterator __first,
5334  _RandomAccessIterator __middle,
5335  _RandomAccessIterator __last,
5336  _Compare __comp)
5337  {
5338  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5339  _ValueType;
5340 
5341  // concept requirements
5342  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5343  _RandomAccessIterator>)
5344  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5345  _ValueType, _ValueType>)
5346  __glibcxx_requires_valid_range(__first, __middle);
5347  __glibcxx_requires_valid_range(__middle, __last);
5348 
5349  std::__heap_select(__first, __middle, __last, __comp);
5350  std::sort_heap(__first, __middle, __comp);
5351  }
5352 
5368  template<typename _RandomAccessIterator>
5369  inline void
5370  nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5371  _RandomAccessIterator __last)
5372  {
5373  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5374  _ValueType;
5375 
5376  // concept requirements
5377  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5378  _RandomAccessIterator>)
5379  __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5380  __glibcxx_requires_valid_range(__first, __nth);
5381  __glibcxx_requires_valid_range(__nth, __last);
5382 
5383  if (__first == __last || __nth == __last)
5384  return;
5385 
5386  std::__introselect(__first, __nth, __last,
5387  std::__lg(__last - __first) * 2);
5388  }
5389 
5407  template<typename _RandomAccessIterator, typename _Compare>
5408  inline void
5409  nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5410  _RandomAccessIterator __last, _Compare __comp)
5411  {
5412  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5413  _ValueType;
5414 
5415  // concept requirements
5416  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5417  _RandomAccessIterator>)
5418  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5419  _ValueType, _ValueType>)
5420  __glibcxx_requires_valid_range(__first, __nth);
5421  __glibcxx_requires_valid_range(__nth, __last);
5422 
5423  if (__first == __last || __nth == __last)
5424  return;
5425 
5426  std::__introselect(__first, __nth, __last,
5427  std::__lg(__last - __first) * 2, __comp);
5428  }
5429 
5430 
5445  template<typename _RandomAccessIterator>
5446  inline void
5447  sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5448  {
5449  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5450  _ValueType;
5451 
5452  // concept requirements
5453  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5454  _RandomAccessIterator>)
5455  __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5456  __glibcxx_requires_valid_range(__first, __last);
5457 
5458  if (__first != __last)
5459  {
5460  std::__introsort_loop(__first, __last,
5461  std::__lg(__last - __first) * 2);
5462  std::__final_insertion_sort(__first, __last);
5463  }
5464  }
5465 
5481  template<typename _RandomAccessIterator, typename _Compare>
5482  inline void
5483  sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5484  _Compare __comp)
5485  {
5486  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5487  _ValueType;
5488 
5489  // concept requirements
5490  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5491  _RandomAccessIterator>)
5492  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
5493  _ValueType>)
5494  __glibcxx_requires_valid_range(__first, __last);
5495 
5496  if (__first != __last)
5497  {
5498  std::__introsort_loop(__first, __last,
5499  std::__lg(__last - __first) * 2, __comp);
5500  std::__final_insertion_sort(__first, __last, __comp);
5501  }
5502  }
5503 
5523  template<typename _InputIterator1, typename _InputIterator2,
5524  typename _OutputIterator>
5525  _OutputIterator
5526  merge(_InputIterator1 __first1, _InputIterator1 __last1,
5527  _InputIterator2 __first2, _InputIterator2 __last2,
5528  _OutputIterator __result)
5529  {
5530  typedef typename iterator_traits<_InputIterator1>::value_type
5531  _ValueType1;
5532  typedef typename iterator_traits<_InputIterator2>::value_type
5533  _ValueType2;
5534 
5535  // concept requirements
5536  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5537  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5538  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5539  _ValueType1>)
5540  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5541  _ValueType2>)
5542  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5543  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5544  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5545 
5546  while (__first1 != __last1 && __first2 != __last2)
5547  {
5548  if (*__first2 < *__first1)
5549  {
5550  *__result = *__first2;
5551  ++__first2;
5552  }
5553  else
5554  {
5555  *__result = *__first1;
5556  ++__first1;
5557  }
5558  ++__result;
5559  }
5560  return std::copy(__first2, __last2, std::copy(__first1, __last1,
5561  __result));
5562  }
5563 
5587  template<typename _InputIterator1, typename _InputIterator2,
5588  typename _OutputIterator, typename _Compare>
5589  _OutputIterator
5590  merge(_InputIterator1 __first1, _InputIterator1 __last1,
5591  _InputIterator2 __first2, _InputIterator2 __last2,
5592  _OutputIterator __result, _Compare __comp)
5593  {
5594  typedef typename iterator_traits<_InputIterator1>::value_type
5595  _ValueType1;
5596  typedef typename iterator_traits<_InputIterator2>::value_type
5597  _ValueType2;
5598 
5599  // concept requirements
5600  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5601  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5602  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5603  _ValueType1>)
5604  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5605  _ValueType2>)
5606  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5607  _ValueType2, _ValueType1>)
5608  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5609  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5610 
5611  while (__first1 != __last1 && __first2 != __last2)
5612  {
5613  if (__comp(*__first2, *__first1))
5614  {
5615  *__result = *__first2;
5616  ++__first2;
5617  }
5618  else
5619  {
5620  *__result = *__first1;
5621  ++__first1;
5622  }
5623  ++__result;
5624  }
5625  return std::copy(__first2, __last2, std::copy(__first1, __last1,
5626  __result));
5627  }
5628 
5629 
5647  template<typename _RandomAccessIterator>
5648  inline void
5649  stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5650  {
5651  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5652  _ValueType;
5653  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5654  _DistanceType;
5655 
5656  // concept requirements
5657  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5658  _RandomAccessIterator>)
5659  __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5660  __glibcxx_requires_valid_range(__first, __last);
5661 
5662  _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5663  __last);
5664  if (__buf.begin() == 0)
5665  std::__inplace_stable_sort(__first, __last);
5666  else
5667  std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5668  _DistanceType(__buf.size()));
5669  }
5670 
5689  template<typename _RandomAccessIterator, typename _Compare>
5690  inline void
5691  stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5692  _Compare __comp)
5693  {
5694  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5695  _ValueType;
5696  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5697  _DistanceType;
5698 
5699  // concept requirements
5700  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5701  _RandomAccessIterator>)
5702  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5703  _ValueType,
5704  _ValueType>)
5705  __glibcxx_requires_valid_range(__first, __last);
5706 
5707  _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5708  __last);
5709  if (__buf.begin() == 0)
5710  std::__inplace_stable_sort(__first, __last, __comp);
5711  else
5712  std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5713  _DistanceType(__buf.size()), __comp);
5714  }
5715 
5716 
5735  template<typename _InputIterator1, typename _InputIterator2,
5736  typename _OutputIterator>
5737  _OutputIterator
5738  set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5739  _InputIterator2 __first2, _InputIterator2 __last2,
5740  _OutputIterator __result)
5741  {
5742  typedef typename iterator_traits<_InputIterator1>::value_type
5743  _ValueType1;
5744  typedef typename iterator_traits<_InputIterator2>::value_type
5745  _ValueType2;
5746 
5747  // concept requirements
5748  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5749  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5750  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5751  _ValueType1>)
5752  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5753  _ValueType2>)
5754  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5755  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5756  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5757  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5758 
5759  while (__first1 != __last1 && __first2 != __last2)
5760  {
5761  if (*__first1 < *__first2)
5762  {
5763  *__result = *__first1;
5764  ++__first1;
5765  }
5766  else if (*__first2 < *__first1)
5767  {
5768  *__result = *__first2;
5769  ++__first2;
5770  }
5771  else
5772  {
5773  *__result = *__first1;
5774  ++__first1;
5775  ++__first2;
5776  }
5777  ++__result;
5778  }
5779  return std::copy(__first2, __last2, std::copy(__first1, __last1,
5780  __result));
5781  }
5782 
5802  template<typename _InputIterator1, typename _InputIterator2,
5803  typename _OutputIterator, typename _Compare>
5804  _OutputIterator
5805  set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5806  _InputIterator2 __first2, _InputIterator2 __last2,
5807  _OutputIterator __result, _Compare __comp)
5808  {
5809  typedef typename iterator_traits<_InputIterator1>::value_type
5810  _ValueType1;
5811  typedef typename iterator_traits<_InputIterator2>::value_type
5812  _ValueType2;
5813 
5814  // concept requirements
5815  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5816  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5817  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5818  _ValueType1>)
5819  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5820  _ValueType2>)
5821  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5822  _ValueType1, _ValueType2>)
5823  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5824  _ValueType2, _ValueType1>)
5825  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5826  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5827 
5828  while (__first1 != __last1 && __first2 != __last2)
5829  {
5830  if (__comp(*__first1, *__first2))
5831  {
5832  *__result = *__first1;
5833  ++__first1;
5834  }
5835  else if (__comp(*__first2, *__first1))
5836  {
5837  *__result = *__first2;
5838  ++__first2;
5839  }
5840  else
5841  {
5842  *__result = *__first1;
5843  ++__first1;
5844  ++__first2;
5845  }
5846  ++__result;
5847  }
5848  return std::copy(__first2, __last2, std::copy(__first1, __last1,
5849  __result));
5850  }
5851 
5869  template<typename _InputIterator1, typename _InputIterator2,
5870  typename _OutputIterator>
5871  _OutputIterator
5872  set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5873  _InputIterator2 __first2, _InputIterator2 __last2,
5874  _OutputIterator __result)
5875  {
5876  typedef typename iterator_traits<_InputIterator1>::value_type
5877  _ValueType1;
5878  typedef typename iterator_traits<_InputIterator2>::value_type
5879  _ValueType2;
5880 
5881  // concept requirements
5882  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5883  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5884  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5885  _ValueType1>)
5886  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5887  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5888  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5889  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5890 
5891  while (__first1 != __last1 && __first2 != __last2)
5892  if (*__first1 < *__first2)
5893  ++__first1;
5894  else if (*__first2 < *__first1)
5895  ++__first2;
5896  else
5897  {
5898  *__result = *__first1;
5899  ++__first1;
5900  ++__first2;
5901  ++__result;
5902  }
5903  return __result;
5904  }
5905 
5926  template<typename _InputIterator1, typename _InputIterator2,
5927  typename _OutputIterator, typename _Compare>
5928  _OutputIterator
5929  set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5930  _InputIterator2 __first2, _InputIterator2 __last2,
5931  _OutputIterator __result, _Compare __comp)
5932  {
5933  typedef typename iterator_traits<_InputIterator1>::value_type
5934  _ValueType1;
5935  typedef typename iterator_traits<_InputIterator2>::value_type
5936  _ValueType2;
5937 
5938  // concept requirements
5939  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5940  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5941  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5942  _ValueType1>)
5943  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5944  _ValueType1, _ValueType2>)
5945  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5946  _ValueType2, _ValueType1>)
5947  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5948  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5949 
5950  while (__first1 != __last1 && __first2 != __last2)
5951  if (__comp(*__first1, *__first2))
5952  ++__first1;
5953  else if (__comp(*__first2, *__first1))
5954  ++__first2;
5955  else
5956  {
5957  *__result = *__first1;
5958  ++__first1;
5959  ++__first2;
5960  ++__result;
5961  }
5962  return __result;
5963  }
5964 
5984  template<typename _InputIterator1, typename _InputIterator2,
5985  typename _OutputIterator>
5986  _OutputIterator
5987  set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5988  _InputIterator2 __first2, _InputIterator2 __last2,
5989  _OutputIterator __result)
5990  {
5991  typedef typename iterator_traits<_InputIterator1>::value_type
5992  _ValueType1;
5993  typedef typename iterator_traits<_InputIterator2>::value_type
5994  _ValueType2;
5995 
5996  // concept requirements
5997  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5998  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5999  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6000  _ValueType1>)
6001  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6002  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
6003  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6004  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
6005 
6006  while (__first1 != __last1 && __first2 != __last2)
6007  if (*__first1 < *__first2)
6008  {
6009  *__result = *__first1;
6010  ++__first1;
6011  ++__result;
6012  }
6013  else if (*__first2 < *__first1)
6014  ++__first2;
6015  else
6016  {
6017  ++__first1;
6018  ++__first2;
6019  }
6020  return std::copy(__first1, __last1, __result);
6021  }
6022 
6045  template<typename _InputIterator1, typename _InputIterator2,
6046  typename _OutputIterator, typename _Compare>
6047  _OutputIterator
6048  set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6049  _InputIterator2 __first2, _InputIterator2 __last2,
6050  _OutputIterator __result, _Compare __comp)
6051  {
6052  typedef typename iterator_traits<_InputIterator1>::value_type
6053  _ValueType1;
6054  typedef typename iterator_traits<_InputIterator2>::value_type
6055  _ValueType2;
6056 
6057  // concept requirements
6058  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6059  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6060  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6061  _ValueType1>)
6062  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6063  _ValueType1, _ValueType2>)
6064  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6065  _ValueType2, _ValueType1>)
6066  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6067  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
6068 
6069  while (__first1 != __last1 && __first2 != __last2)
6070  if (__comp(*__first1, *__first2))
6071  {
6072  *__result = *__first1;
6073  ++__first1;
6074  ++__result;
6075  }
6076  else if (__comp(*__first2, *__first1))
6077  ++__first2;
6078  else
6079  {
6080  ++__first1;
6081  ++__first2;
6082  }
6083  return std::copy(__first1, __last1, __result);
6084  }
6085 
6103  template<typename _InputIterator1, typename _InputIterator2,
6104  typename _OutputIterator>
6105  _OutputIterator
6106  set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6107  _InputIterator2 __first2, _InputIterator2 __last2,
6108  _OutputIterator __result)
6109  {
6110  typedef typename iterator_traits<_InputIterator1>::value_type
6111  _ValueType1;
6112  typedef typename iterator_traits<_InputIterator2>::value_type
6113  _ValueType2;
6114 
6115  // concept requirements
6116  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6117  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6118  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6119  _ValueType1>)
6120  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6121  _ValueType2>)
6122  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6123  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
6124  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6125  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
6126 
6127  while (__first1 != __last1 && __first2 != __last2)
6128  if (*__first1 < *__first2)
6129  {
6130  *__result = *__first1;
6131  ++__first1;
6132  ++__result;
6133  }
6134  else if (*__first2 < *__first1)
6135  {
6136  *__result = *__first2;
6137  ++__first2;
6138  ++__result;
6139  }
6140  else
6141  {
6142  ++__first1;
6143  ++__first2;
6144  }
6145  return std::copy(__first2, __last2, std::copy(__first1,
6146  __last1, __result));
6147  }
6148 
6169  template<typename _InputIterator1, typename _InputIterator2,
6170  typename _OutputIterator, typename _Compare>
6171  _OutputIterator
6172  set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6173  _InputIterator2 __first2, _InputIterator2 __last2,
6174  _OutputIterator __result,
6175  _Compare __comp)
6176  {
6177  typedef typename iterator_traits<_InputIterator1>::value_type
6178  _ValueType1;
6179  typedef typename iterator_traits<_InputIterator2>::value_type
6180  _ValueType2;
6181 
6182  // concept requirements
6183  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6184  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6185  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6186  _ValueType1>)
6187  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6188  _ValueType2>)
6189  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6190  _ValueType1, _ValueType2>)
6191  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6192  _ValueType2, _ValueType1>)
6193  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6194  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
6195 
6196  while (__first1 != __last1 && __first2 != __last2)
6197  if (__comp(*__first1, *__first2))
6198  {
6199  *__result = *__first1;
6200  ++__first1;
6201  ++__result;
6202  }
6203  else if (__comp(*__first2, *__first1))
6204  {
6205  *__result = *__first2;
6206  ++__first2;
6207  ++__result;
6208  }
6209  else
6210  {
6211  ++__first1;
6212  ++__first2;
6213  }
6214  return std::copy(__first2, __last2,
6215  std::copy(__first1, __last1, __result));
6216  }
6217 
6218 
6226  template<typename _ForwardIterator>
6227  _ForwardIterator
6228  min_element(_ForwardIterator __first, _ForwardIterator __last)
6229  {
6230  // concept requirements
6231  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6232  __glibcxx_function_requires(_LessThanComparableConcept<
6233  typename iterator_traits<_ForwardIterator>::value_type>)
6234  __glibcxx_requires_valid_range(__first, __last);
6235 
6236  if (__first == __last)
6237  return __first;
6238  _ForwardIterator __result = __first;
6239  while (++__first != __last)
6240  if (*__first < *__result)
6241  __result = __first;
6242  return __result;
6243  }
6244 
6254  template<typename _ForwardIterator, typename _Compare>
6255  _ForwardIterator
6256  min_element(_ForwardIterator __first, _ForwardIterator __last,
6257  _Compare __comp)
6258  {
6259  // concept requirements
6260  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6261  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6262  typename iterator_traits<_ForwardIterator>::value_type,
6263  typename iterator_traits<_ForwardIterator>::value_type>)
6264  __glibcxx_requires_valid_range(__first, __last);
6265 
6266  if (__first == __last)
6267  return __first;
6268  _ForwardIterator __result = __first;
6269  while (++__first != __last)
6270  if (__comp(*__first, *__result))
6271  __result = __first;
6272  return __result;
6273  }
6274 
6282  template<typename _ForwardIterator>
6283  _ForwardIterator
6284  max_element(_ForwardIterator __first, _ForwardIterator __last)
6285  {
6286  // concept requirements
6287  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6288  __glibcxx_function_requires(_LessThanComparableConcept<
6289  typename iterator_traits<_ForwardIterator>::value_type>)
6290  __glibcxx_requires_valid_range(__first, __last);
6291 
6292  if (__first == __last)
6293  return __first;
6294  _ForwardIterator __result = __first;
6295  while (++__first != __last)
6296  if (*__result < *__first)
6297  __result = __first;
6298  return __result;
6299  }
6300 
6310  template<typename _ForwardIterator, typename _Compare>
6311  _ForwardIterator
6312  max_element(_ForwardIterator __first, _ForwardIterator __last,
6313  _Compare __comp)
6314  {
6315  // concept requirements
6316  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6317  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6318  typename iterator_traits<_ForwardIterator>::value_type,
6319  typename iterator_traits<_ForwardIterator>::value_type>)
6320  __glibcxx_requires_valid_range(__first, __last);
6321 
6322  if (__first == __last) return __first;
6323  _ForwardIterator __result = __first;
6324  while (++__first != __last)
6325  if (__comp(*__result, *__first))
6326  __result = __first;
6327  return __result;
6328  }
6329 
6330 _GLIBCXX_END_NAMESPACE_ALGO
6331 } // namespace std
__glibcxx_requires_partitioned_lower
#define __glibcxx_requires_partitioned_lower(_First, _Last, _Value)
Definition: debug.h:71
__glibcxx_requires_partitioned_upper_pred
#define __glibcxx_requires_partitioned_upper_pred(_First, _Last, _Value, _Pred)
Definition: debug.h:74
__glibcxx_function_requires
#define __glibcxx_function_requires(...)
Definition: concept_check.h:47
_GLIBCXX_MOVE
#define _GLIBCXX_MOVE(__val)
Definition: move.h:145
__glibcxx_requires_partitioned_upper
#define __glibcxx_requires_partitioned_upper(_First, _Last, _Value)
Definition: debug.h:72
false
#define false
Definition: stdbool.h:35
__glibcxx_requires_sorted_pred
#define __glibcxx_requires_sorted_pred(_First, _Last, _Pred)
Definition: debug.h:68
__gnu_parallel::min
const _Tp & min(const _Tp &__a, const _Tp &__b)
Equivalent to std::min.
Definition: base.h:144
return
return(unsigned int) __res
__glibcxx_requires_partitioned_lower_pred
#define __glibcxx_requires_partitioned_lower_pred(_First, _Last, _Value, _Pred)
Definition: debug.h:73
_GLIBCXX_MOVE_BACKWARD3
#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp)
__glibcxx_requires_sorted_set_pred
#define __glibcxx_requires_sorted_set_pred(_First1, _Last1, _First2, _Pred)
Definition: debug.h:70
__gnu_parallel::max
const _Tp & max(const _Tp &__a, const _Tp &__b)
Equivalent to std::max.
Definition: base.h:150
_GLIBCXX_MOVE3
#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp)
__glibcxx_requires_sorted
#define __glibcxx_requires_sorted(_First, _Last)
Definition: debug.h:67
__glibcxx_requires_valid_range
#define __glibcxx_requires_valid_range(_First, _Last)
Definition: debug.h:65
std::__exception_ptr::swap
void swap(exception_ptr &__lhs, exception_ptr &__rhs)
Definition: exception_ptr.h:160
__glibcxx_requires_sorted_set
#define __glibcxx_requires_sorted_set(_First1, _Last1, _First2)
Definition: debug.h:69
Generated on Sat Jul 22 2017 14:42:46 for STLdoc by   doxygen 1.8.6