GNU g++  v5.2.1
GNU Standard C++
Sorting
Collaboration diagram for Sorting:

Modules

 Binary Search
 
 Heap
 
 Set Operation
 

Functions

namespace std _GLIBCXX_VISIBILITY (default)
 

Detailed Description

Function Documentation

namespace std _GLIBCXX_VISIBILITY ( default  )

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

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

This is an overload used by find algos 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 helper function for search_n overloaded for forward iterators.

This is an helper function for search_n 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 [__first1,__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, _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
first + (last - middle).

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 __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.

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 controls some aspect of the sort routines.

This is a helper function for the sort routine.

This is a helper function...

This is a helper function...

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

1 std::make_pair(lower_bound(__first, __last, __val),
2  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

1 std::make_pair(lower_bound(__first, __last, __val, __comp),
2  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 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 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.

References __glibcxx_function_requires, __glibcxx_requires_partitioned_lower, __glibcxx_requires_partitioned_lower_pred, __glibcxx_requires_partitioned_upper, __glibcxx_requires_partitioned_upper_pred, __glibcxx_requires_sorted, __glibcxx_requires_sorted_pred, __glibcxx_requires_sorted_set, __glibcxx_requires_sorted_set_pred, __glibcxx_requires_valid_range, __gnu_cxx::__ops::__iter_comp_iter(), __gnu_cxx::__ops::__iter_comp_val(), __gnu_cxx::__ops::__iter_equal_to_iter(), __gnu_cxx::__ops::__iter_equals_val(), __gnu_cxx::__ops::__iter_less_iter(), __gnu_cxx::__ops::__iter_less_val(), __gnu_cxx::__ops::__negate(), __gnu_cxx::__ops::__pred_iter(), __gnu_cxx::__ops::__val_comp_iter(), __gnu_cxx::__ops::__val_less_iter(), _GLIBCXX_MOVE, _GLIBCXX_MOVE3, _GLIBCXX_MOVE_BACKWARD3, __gnu_parallel::max(), __gnu_parallel::min(), and std::__exception_ptr::swap().

Here is the call graph for this function: