stl_algo.h File Reference

#include <bits/stl_heap.h>
#include <bits/stl_tempbuf.h>

Include dependency graph for stl_algo.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces

namespace  std

Functions

template<typename Type>
const Type & __median (const Type &a, const Type &__b, const Type &c)
 Find the median of three values.
template<typename Type, typename Compare>
const Type & __median (const Type &a, const Type &__b, const Type &c, Compare comp)
 Find the median of three values using a predicate for comparison.
template<typename InputIter, typename Function>
Function for_each (InputIter first, InputIter last, Function __f)
 Apply a function to every element of a sequence.
template<typename InputIter, typename Type>
InputIter find (InputIter first, InputIter last, const Type &__val)
 Find the first occurrence of a value in a sequence.
template<typename InputIter, typename Predicate>
InputIter find_if (InputIter first, InputIter last, Predicate pred)
 Find the first element in a sequence for which a predicate is true.
template<typename ForwardIter>
ForwardIter adjacent_find (ForwardIter first, ForwardIter last)
 Find two adjacent values in a sequence that are equal.
template<typename ForwardIter, typename BinaryPredicate>
ForwardIter adjacent_find (ForwardIter first, ForwardIter last, BinaryPredicate __binary_pred)
 Find two adjacent values in a sequence using a predicate.
template<typename InputIter, typename Type>
iterator_traits< InputIter
>::difference_type 
count (InputIter first, InputIter last, const Type &value)
 Count the number of copies of a value in a sequence.
template<typename InputIter, typename Predicate>
iterator_traits< InputIter
>::difference_type 
count_if (InputIter first, InputIter last, Predicate pred)
 Count the elements of a sequence for which a predicate is true.
template<typename ForwardIter1, typename ForwardIter2>
ForwardIter1 search (ForwardIter1 first1, ForwardIter1 last1, ForwardIter2 first2, ForwardIter2 last2)
 Search a sequence for a matching sub-sequence.
template<typename ForwardIter1, typename ForwardIter2, typename BinaryPred>
ForwardIter1 search (ForwardIter1 first1, ForwardIter1 last1, ForwardIter2 first2, ForwardIter2 last2, BinaryPred predicate)
 Search a sequence for a matching sub-sequence using a predicate.
template<typename ForwardIter, typename Integer, typename Type>
ForwardIter search_n (ForwardIter first, ForwardIter last, Integer count, const Type &__val)
 Search a sequence for a number of consecutive values.
template<typename ForwardIter, typename Integer, typename Type, typename BinaryPred>
ForwardIter search_n (ForwardIter first, ForwardIter last, Integer count, const Type &__val, BinaryPred __binary_pred)
 Search a sequence for a number of consecutive values using a predicate.
template<typename ForwardIter1, typename ForwardIter2>
ForwardIter2 swap_ranges (ForwardIter1 first1, ForwardIter1 last1, ForwardIter2 first2)
 Swap the elements of two sequences.
template<typename InputIter, typename OutputIter, typename UnaryOperation>
OutputIter transform (InputIter first, InputIter last, OutputIter __result, UnaryOperation __unary_op)
 Perform an operation on a sequence.
template<typename InputIter1, typename InputIter2, typename OutputIter, typename BinaryOperation>
OutputIter transform (InputIter1 first1, InputIter1 last1, InputIter2 first2, OutputIter __result, BinaryOperation __binary_op)
 Perform an operation on corresponding elements of two sequences.
template<typename ForwardIter, typename Type>
void replace (ForwardIter first, ForwardIter last, const Type &__old_value, const Type &new_value)
 Replace each occurrence of one value in a sequence with another value.
template<typename ForwardIter, typename Predicate, typename Type>
void replace_if (ForwardIter first, ForwardIter last, Predicate pred, const Type &new_value)
 Replace each value in a sequence for which a predicate returns true with another value.
template<typename InputIter, typename OutputIter, typename Type>
OutputIter replace_copy (InputIter first, InputIter last, OutputIter __result, const Type &__old_value, const Type &new_value)
 Copy a sequence, replacing each element of one value with another value.
template<typename InputIter, typename OutputIter, typename Predicate, typename Type>
OutputIter replace_copy_if (InputIter first, InputIter last, OutputIter __result, Predicate pred, const Type &new_value)
 Copy a sequence, replacing each value for which a predicate returns true with another value.
template<typename ForwardIter, typename Generator>
void generate (ForwardIter first, ForwardIter last, Generator __gen)
 Assign the result of a function object to each value in a sequence.
template<typename OutputIter, typename Size, typename Generator>
OutputIter generate_n (OutputIter first, Size n, Generator __gen)
 Assign the result of a function object to each value in a sequence.
template<typename InputIter, typename OutputIter, typename Type>
OutputIter remove_copy (InputIter first, InputIter last, OutputIter __result, const Type &value)
 Copy a sequence, removing elements of a given value.
template<typename InputIter, typename OutputIter, typename Predicate>
OutputIter remove_copy_if (InputIter first, InputIter last, OutputIter __result, Predicate pred)
 Copy a sequence, removing elements for which a predicate is true.
template<typename ForwardIter, typename Type>
ForwardIter remove (ForwardIter first, ForwardIter last, const Type &value)
 Remove elements from a sequence.
template<typename ForwardIter, typename Predicate>
ForwardIter remove_if (ForwardIter first, ForwardIter last, Predicate pred)
 Remove elements from a sequence using a predicate.
template<typename InputIter, typename OutputIter>
OutputIter unique_copy (InputIter first, InputIter last, OutputIter __result)
 Copy a sequence, removing consecutive duplicate values.
template<typename InputIter, typename OutputIter, typename BinaryPredicate>
OutputIter unique_copy (InputIter first, InputIter last, OutputIter __result, BinaryPredicate __binary_pred)
 Copy a sequence, removing consecutive values using a predicate.
template<typename ForwardIter>
ForwardIter unique (ForwardIter first, ForwardIter last)
 Remove consecutive duplicate values from a sequence.
template<typename ForwardIter, typename BinaryPredicate>
ForwardIter unique (ForwardIter first, ForwardIter last, BinaryPredicate __binary_pred)
 Remove consecutive values from a sequence using a predicate.
template<typename BidirectionalIter>
void reverse (BidirectionalIter first, BidirectionalIter last)
 Reverse a sequence.
template<typename BidirectionalIter, typename OutputIter>
OutputIter reverse_copy (BidirectionalIter first, BidirectionalIter last, OutputIter __result)
 Copy a sequence, reversing its elements.
template<typename ForwardIter>
void rotate (ForwardIter first, ForwardIter __middle, ForwardIter last)
 Rotate the elements of a sequence.
template<typename ForwardIter, typename OutputIter>
OutputIter rotate_copy (ForwardIter first, ForwardIter __middle, ForwardIter last, OutputIter __result)
 Copy a sequence, rotating its elements.
template<typename RandomAccessIter>
void random_shuffle (RandomAccessIter first, RandomAccessIter last)
 Randomly shuffle the elements of a sequence.
template<typename RandomAccessIter, typename RandomNumberGenerator>
void random_shuffle (RandomAccessIter first, RandomAccessIter last, RandomNumberGenerator &__rand)
 Shuffle the elements of a sequence using a random number generator.
template<typename ForwardIter, typename Predicate>
ForwardIter partition (ForwardIter first, ForwardIter last, Predicate pred)
 Move elements for which a predicate is true to the beginning of a sequence.
template<typename ForwardIter, typename Predicate>
ForwardIter stable_partition (ForwardIter first, ForwardIter last, Predicate pred)
 Move elements for which a predicate is true to the beginning of a sequence, preserving relative ordering.
template<typename RandomAccessIter>
void sort (RandomAccessIter first, RandomAccessIter last)
 Sort the elements of a sequence.
template<typename RandomAccessIter, typename Compare>
void sort (RandomAccessIter first, RandomAccessIter last, Compare comp)
 Sort the elements of a sequence using a predicate for comparison.
template<typename RandomAccessIter>
void stable_sort (RandomAccessIter first, RandomAccessIter last)
 Sort the elements of a sequence, preserving the relative order of equivalent elements.
template<typename RandomAccessIter, typename Compare>
void stable_sort (RandomAccessIter first, RandomAccessIter last, Compare comp)
 Sort the elements of a sequence using a predicate for comparison, preserving the relative order of equivalent elements.
template<typename RandomAccessIter>
void partial_sort (RandomAccessIter first, RandomAccessIter __middle, RandomAccessIter last)
 Sort the smallest elements of a sequence.
template<typename RandomAccessIter, typename Compare>
void partial_sort (RandomAccessIter first, RandomAccessIter __middle, RandomAccessIter last, Compare comp)
 Sort the smallest elements of a sequence using a predicate for comparison.
template<typename InputIter, typename RandomAccessIter>
RandomAccessIter partial_sort_copy (InputIter first, InputIter last, RandomAccessIter __result_first, RandomAccessIter __result_last)
 Copy the smallest elements of a sequence.
template<typename InputIter, typename RandomAccessIter, typename Compare>
RandomAccessIter partial_sort_copy (InputIter first, InputIter last, RandomAccessIter __result_first, RandomAccessIter __result_last, Compare comp)
 Copy the smallest elements of a sequence using a predicate for comparison.
template<typename RandomAccessIter>
void nth_element (RandomAccessIter first, RandomAccessIter nth, RandomAccessIter last)
 Sort a sequence just enough to find a particular position.
template<typename RandomAccessIter, typename Compare>
void nth_element (RandomAccessIter first, RandomAccessIter nth, RandomAccessIter last, Compare comp)
 Sort a sequence just enough to find a particular position using a predicate for comparison.
template<typename ForwardIter, typename Type>
ForwardIter lower_bound (ForwardIter first, ForwardIter last, const Type &__val)
 Finds the first position in which val could be inserted without changing the ordering.
template<typename ForwardIter, typename Type, typename Compare>
ForwardIter lower_bound (ForwardIter first, ForwardIter last, const Type &__val, Compare comp)
 Finds the first position in which val could be inserted without changing the ordering.
template<typename ForwardIter, typename Type>
ForwardIter upper_bound (ForwardIter first, ForwardIter last, const Type &__val)
 Finds the last position in which val could be inserted without changing the ordering.
template<typename ForwardIter, typename Type, typename Compare>
ForwardIter upper_bound (ForwardIter first, ForwardIter last, const Type &__val, Compare comp)
 Finds the last position in which val could be inserted without changing the ordering.
template<typename ForwardIter, typename Type>
pair< ForwardIter, ForwardIter > equal_range (ForwardIter first, ForwardIter last, const Type &__val)
 Finds the largest subrange in which val could be inserted at any place in it without changing the ordering.
template<typename ForwardIter, typename Type, typename Compare>
pair< ForwardIter, ForwardIter > equal_range (ForwardIter first, ForwardIter last, const Type &__val, Compare comp)
 Finds the largest subrange in which val could be inserted at any place in it without changing the ordering.
template<typename ForwardIter, typename Type>
bool binary_search (ForwardIter first, ForwardIter last, const Type &__val)
 Determines whether an element exists in a range.
template<typename ForwardIter, typename Type, typename Compare>
bool binary_search (ForwardIter first, ForwardIter last, const Type &__val, Compare comp)
 Determines whether an element exists in a range.
template<typename InputIter1, typename InputIter2, typename OutputIter>
OutputIter merge (InputIter1 first1, InputIter1 last1, InputIter2 first2, InputIter2 last2, OutputIter __result)
 Merges two sorted ranges.
template<typename InputIter1, typename InputIter2, typename OutputIter, typename Compare>
OutputIter merge (InputIter1 first1, InputIter1 last1, InputIter2 first2, InputIter2 last2, OutputIter __result, Compare comp)
 Merges two sorted ranges.
template<typename BidirectionalIter>
void inplace_merge (BidirectionalIter first, BidirectionalIter __middle, BidirectionalIter last)
 Merges two sorted ranges in place.
template<typename BidirectionalIter, typename Compare>
void inplace_merge (BidirectionalIter first, BidirectionalIter __middle, BidirectionalIter last, Compare comp)
 Merges two sorted ranges in place.


Detailed Description

This is an internal header file, included by other library headers. You should not attempt to use it directly.

Definition in file stl_algo.h.


Function Documentation

template<typename ForwardIter, typename BinaryPredicate>
ForwardIter adjacent_find ForwardIter  first,
ForwardIter  last,
BinaryPredicate  __binary_pred
 

Find two adjacent values in a sequence using a predicate.

Parameters:
first A forward iterator.
last A forward iterator.
binary_pred A 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.

Definition at line 360 of file stl_algo.h.

template<typename ForwardIter>
ForwardIter adjacent_find ForwardIter  first,
ForwardIter  last
 

Find two adjacent values in a sequence that are equal.

Parameters:
first A forward iterator.
last A 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.

Definition at line 331 of file stl_algo.h.

Referenced by std::unique().

template<typename InputIter, typename Type>
iterator_traits<InputIter>::difference_type count InputIter  first,
InputIter  last,
const Type &  value
 

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

Parameters:
first An input iterator.
last An input iterator.
value The value to be counted.
Returns:
The number of iterators i in the range [first,last) for which *i == value

Definition at line 389 of file stl_algo.h.

template<typename InputIter, typename Predicate>
iterator_traits<InputIter>::difference_type count_if InputIter  first,
InputIter  last,
Predicate  pred
 

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

Parameters:
first An input iterator.
last An input iterator.
pred A predicate.
Returns:
The number of iterators i in the range [first,last) for which pred(*i) is true.

Definition at line 413 of file stl_algo.h.

template<typename InputIter, typename Type>
InputIter find InputIter  first,
InputIter  last,
const Type &  __val
[inline]
 

Find the first occurrence of a value in a sequence.

Parameters:
first An input iterator.
last An input iterator.
val The value to find.
Returns:
The first iterator i in the range [first,last) such that *i == val, or last if no such iterator exists.

Definition at line 291 of file stl_algo.h.

Referenced by std::remove(), std::search(), and std::search_n().

template<typename InputIter, typename Predicate>
InputIter find_if InputIter  first,
InputIter  last,
Predicate  pred
[inline]
 

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

Parameters:
first An input iterator.
last An input iterator.
pred A predicate.
Returns:
The first iterator i in the range [first,last) such that pred(*i) is true, or last if no such iterator exists.

Definition at line 311 of file stl_algo.h.

Referenced by std::remove_if().

template<typename InputIter, typename Function>
Function for_each InputIter  first,
InputIter  last,
Function  __f
 

Apply a function to every element of a sequence.

Parameters:
first An input iterator.
last An input iterator.
f A unary function object.
Returns:
f.
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.

Definition at line 152 of file stl_algo.h.

template<typename ForwardIter, typename Generator>
void generate ForwardIter  first,
ForwardIter  last,
Generator  __gen
 

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

Parameters:
first A forward iterator.
last A forward iterator.
gen A function object taking no arguments.
Returns:
generate() returns no value.
Performs the assignment *i = gen() for each i in the range [first,last).

Definition at line 922 of file stl_algo.h.

template<typename OutputIter, typename Size, typename Generator>
OutputIter generate_n OutputIter  first,
Size  n,
Generator  __gen
 

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

Parameters:
first A forward iterator.
n The length of the sequence.
gen A function object taking no arguments.
Returns:
The end of the sequence, first+n
Performs the assignment *i = gen() for each i in the range [first,first+n).

Definition at line 946 of file stl_algo.h.

template<typename BidirectionalIter, typename Compare>
void inplace_merge BidirectionalIter  first,
BidirectionalIter  __middle,
BidirectionalIter  last,
Compare  comp
 

Merges two sorted ranges in place.

Parameters:
first An iterator.
middle Another iterator.
last Another iterator.
comp A 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.

Definition at line 3563 of file stl_algo.h.

References std::distance().

template<typename BidirectionalIter>
void inplace_merge BidirectionalIter  first,
BidirectionalIter  __middle,
BidirectionalIter  last
 

Merges two sorted ranges in place.

Parameters:
first An iterator.
middle Another iterator.
last Another 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).

Definition at line 3512 of file stl_algo.h.

References std::distance().

template<typename InputIter1, typename InputIter2, typename OutputIter, typename Compare>
OutputIter merge InputIter1  first1,
InputIter1  last1,
InputIter2  first2,
InputIter2  last2,
OutputIter  __result,
Compare  comp
 

Merges two sorted ranges.

Parameters:
first1 An iterator.
first2 Another iterator.
last1 Another iterator.
last2 Another iterator.
result An iterator pointing to the end of the merged range.
comp A 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.

Definition at line 3171 of file stl_algo.h.

References std::copy().

template<typename InputIter1, typename InputIter2, typename OutputIter>
OutputIter merge InputIter1  first1,
InputIter1  last1,
InputIter2  first2,
InputIter2  last2,
OutputIter  __result
 

Merges two sorted ranges.

Parameters:
first1 An iterator.
first2 Another iterator.
last1 Another iterator.
last2 Another iterator.
result An 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.

Definition at line 3119 of file stl_algo.h.

References std::copy().

template<typename RandomAccessIter, typename Compare>
void nth_element RandomAccessIter  first,
RandomAccessIter  nth,
RandomAccessIter  last,
Compare  comp
 

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

Parameters:
first An iterator.
nth Another iterator.
last Another iterator.
comp A 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 in the range [first,nth) and any iterator in the range [nth,last) it holds that comp(*j,*i) is false.

Definition at line 2732 of file stl_algo.h.

References std::__median().

template<typename RandomAccessIter>
void nth_element RandomAccessIter  first,
RandomAccessIter  nth,
RandomAccessIter  last
 

Sort a sequence just enough to find a particular position.

Parameters:
first An iterator.
nth Another iterator.
last Another 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. whole sequence been sorted. The elements either side of *nth are not completely sorted, but for any iterator in the range [first,nth) and any iterator in the range [nth,last) it holds that *j<*i is false.

Definition at line 2690 of file stl_algo.h.

References std::__median().

template<typename RandomAccessIter, typename Compare>
void partial_sort RandomAccessIter  first,
RandomAccessIter  __middle,
RandomAccessIter  last,
Compare  comp
 

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

Parameters:
first An iterator.
middle Another iterator.
last Another iterator.
comp A 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 are iterators in the range [first,middle) such that precedes and is an iterator in the range [middle,last) then *comp(j,*i) and comp(*k,*i) are both false.

Definition at line 2544 of file stl_algo.h.

template<typename RandomAccessIter>
void partial_sort RandomAccessIter  first,
RandomAccessIter  __middle,
RandomAccessIter  last
 

Sort the smallest elements of a sequence.

Parameters:
first An iterator.
middle Another iterator.
last Another 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 are iterators in the range [first,middle) such that precedes and is an iterator in the range [middle,last) then *j<*i and *k<*i are both false.

Definition at line 2506 of file stl_algo.h.

template<typename InputIter, typename RandomAccessIter, typename Compare>
RandomAccessIter partial_sort_copy InputIter  first,
InputIter  last,
RandomAccessIter  __result_first,
RandomAccessIter  __result_last,
Compare  comp
 

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

Parameters:
first An input iterator.
last Another input iterator.
result_first A random-access iterator.
result_last Another random-access iterator.
comp A 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 are iterators in the range [result_first,result_first+N) such that precedes then comp(*j,*i) is false. The value returned is result_first+N.

Definition at line 2637 of file stl_algo.h.

template<typename InputIter, typename RandomAccessIter>
RandomAccessIter partial_sort_copy InputIter  first,
InputIter  last,
RandomAccessIter  __result_first,
RandomAccessIter  __result_last
 

Copy the smallest elements of a sequence.

Parameters:
first An iterator.
last Another iterator.
result_first A random-access iterator.
result_last Another 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 are iterators in the range [result_first,result_first+N) such that precedes then *j<*i is false. The value returned is result_first+N.

Definition at line 2583 of file stl_algo.h.

template<typename ForwardIter, typename Predicate>
ForwardIter partition ForwardIter  first,
ForwardIter  last,
Predicate  pred
[inline]
 

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

Parameters:
first A forward iterator.
last A forward iterator.
pred A 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.

Definition at line 1752 of file stl_algo.h.

template<typename RandomAccessIter, typename RandomNumberGenerator>
void random_shuffle RandomAccessIter  first,
RandomAccessIter  last,
RandomNumberGenerator &  __rand
 

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

Parameters:
first A forward iterator.
last A forward iterator.
rand The 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).

Definition at line 1664 of file stl_algo.h.

References std::iter_swap().

template<typename RandomAccessIter>
void random_shuffle RandomAccessIter  first,
RandomAccessIter  last
[inline]
 

Randomly shuffle the elements of a sequence.

Parameters:
first A forward iterator.
last A 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.

Definition at line 1638 of file stl_algo.h.

References std::iter_swap().

template<typename ForwardIter, typename Type>
ForwardIter remove ForwardIter  first,
ForwardIter  last,
const Type &  value
 

Remove elements from a sequence.

Parameters:
first An input iterator.
last An input iterator.
value The 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.

Definition at line 1043 of file stl_algo.h.

References std::find(), and std::remove_copy().

template<typename InputIter, typename OutputIter, typename Type>
OutputIter remove_copy InputIter  first,
InputIter  last,
OutputIter  __result,
const Type &  value
 

Copy a sequence, removing elements of a given value.

Parameters:
first An input iterator.
last An input iterator.
result An output iterator.
value The 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.

Definition at line 973 of file stl_algo.h.

Referenced by std::remove().

template<typename InputIter, typename OutputIter, typename Predicate>
OutputIter remove_copy_if InputIter  first,
InputIter  last,
OutputIter  __result,
Predicate  pred
 

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

Parameters:
first An input iterator.
last An input iterator.
result An output iterator.
pred A predicate.
Returns:
An iterator designating the end of the resulting sequence.
Copies each element in the range [first,last) for which pred returns true to the range beginning at result.

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

Definition at line 1007 of file stl_algo.h.

Referenced by std::remove_if().

template<typename ForwardIter, typename Predicate>
ForwardIter remove_if ForwardIter  first,
ForwardIter  last,
Predicate  pred
 

Remove elements from a sequence using a predicate.

Parameters:
first A forward iterator.
last A forward iterator.
pred A 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.

Definition at line 1077 of file stl_algo.h.

References std::find_if(), and std::remove_copy_if().

template<typename ForwardIter, typename Type>
void replace ForwardIter  first,
ForwardIter  last,
const Type &  __old_value,
const Type &  new_value
 

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

Parameters:
first A forward iterator.
last A forward iterator.
old_value The value to be replaced.
new_value The 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.

Definition at line 800 of file stl_algo.h.

template<typename InputIter, typename OutputIter, typename Type>
OutputIter replace_copy InputIter  first,
InputIter  last,
OutputIter  __result,
const Type &  __old_value,
const Type &  new_value
 

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

Parameters:
first An input iterator.
last An input iterator.
result An output iterator.
old_value The value to be replaced.
new_value The 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.

Definition at line 860 of file stl_algo.h.

template<typename InputIter, typename OutputIter, typename Predicate, typename Type>
OutputIter replace_copy_if InputIter  first,
InputIter  last,
OutputIter  __result,
Predicate  pred,
const Type &  new_value
 

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

Parameters:
first An input iterator.
last An input iterator.
result An output iterator.
pred A predicate.
new_value The 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.

Definition at line 893 of file stl_algo.h.

template<typename ForwardIter, typename Predicate, typename Type>
void replace_if ForwardIter  first,
ForwardIter  last,
Predicate  pred,
const Type &  new_value
 

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

Parameters:
first A forward iterator.
last A forward iterator.
pred A predicate.
new_value The 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.

Definition at line 829 of file stl_algo.h.

template<typename BidirectionalIter>
void reverse BidirectionalIter  first,
BidirectionalIter  last
[inline]
 

Reverse a sequence.

Parameters:
first A bidirectional iterator.
last A 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))

Definition at line 1353 of file stl_algo.h.

template<typename BidirectionalIter, typename OutputIter>
OutputIter reverse_copy BidirectionalIter  first,
BidirectionalIter  last,
OutputIter  __result
 

Copy a sequence, reversing its elements.

Parameters:
first A bidirectional iterator.
last A bidirectional iterator.
result An 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)-i) = *(first+i). The ranges [first,last) and [result,result+(last-first)) must not overlap.

Definition at line 1378 of file stl_algo.h.

template<typename ForwardIter>
void rotate ForwardIter  first,
ForwardIter  __middle,
ForwardIter  last
[inline]
 

Rotate the elements of a sequence.

Parameters:
first A forward iterator.
middle A forward iterator.
last A 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 +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).

Definition at line 1565 of file stl_algo.h.

template<typename ForwardIter, typename OutputIter>
OutputIter rotate_copy ForwardIter  first,
ForwardIter  __middle,
ForwardIter  last,
OutputIter  __result
 

Copy a sequence, rotating its elements.

Parameters:
first A forward iterator.
middle A forward iterator.
last A forward iterator.
result An 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

+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).

Definition at line 1593 of file stl_algo.h.

References std::copy().

template<typename ForwardIter1, typename ForwardIter2, typename BinaryPred>
ForwardIter1 search ForwardIter1  first1,
ForwardIter1  last1,
ForwardIter2  first2,
ForwardIter2  last2,
BinaryPred  predicate
 

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

Parameters:
first1 A forward iterator.
last1 A forward iterator.
first2 A forward iterator.
last2 A forward iterator.
predicate A 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)

Definition at line 524 of file stl_algo.h.

template<typename ForwardIter1, typename ForwardIter2>
ForwardIter1 search ForwardIter1  first1,
ForwardIter1  last1,
ForwardIter2  first2,
ForwardIter2  last2
 

Search a sequence for a matching sub-sequence.

Parameters:
first1 A forward iterator.
last1 A forward iterator.
first2 A forward iterator.
last2 A 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))

Definition at line 452 of file stl_algo.h.

References std::find().

template<typename ForwardIter, typename Integer, typename Type, typename BinaryPred>
ForwardIter search_n ForwardIter  first,
ForwardIter  last,
Integer  count,
const Type &  __val,
BinaryPred  __binary_pred
 

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

Parameters:
first A forward iterator.
last A forward iterator.
count The number of consecutive values.
val The value to find.
binary_pred A 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.

Definition at line 647 of file stl_algo.h.

template<typename ForwardIter, typename Integer, typename Type>
ForwardIter search_n ForwardIter  first,
ForwardIter  last,
Integer  count,
const Type &  __val
 

Search a sequence for a number of consecutive values.

Parameters:
first A forward iterator.
last A forward iterator.
count The number of consecutive values.
val The 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.

Definition at line 598 of file stl_algo.h.

References std::find().

template<typename RandomAccessIter, typename Compare>
void sort RandomAccessIter  first,
RandomAccessIter  last,
Compare  comp
[inline]
 

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

Parameters:
first An iterator.
last Another iterator.
comp A 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.

Definition at line 2201 of file stl_algo.h.

template<typename RandomAccessIter>
void sort RandomAccessIter  first,
RandomAccessIter  last
[inline]
 

Sort the elements of a sequence.

Parameters:
first An iterator.
last Another iterator.
Returns:
Nothing.
Sorts the elements in the range [first,last) in ascending order, such that *(i+1)<*i is false for each iterator i in the range [first,last-1).

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

Definition at line 2170 of file stl_algo.h.

template<typename ForwardIter, typename Predicate>
ForwardIter stable_partition ForwardIter  first,
ForwardIter  last,
Predicate  pred
 

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

Parameters:
first A forward iterator.
last A forward iterator.
pred A 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().

Definition at line 1852 of file stl_algo.h.

template<typename RandomAccessIter, typename Compare>
void stable_sort RandomAccessIter  first,
RandomAccessIter  last,
Compare  comp
[inline]
 

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

Parameters:
first An iterator.
last Another iterator.
comp A comparison functor.
Returns:
Nothing.
Sorts the elements in the range [first,last) in ascending order, such that comp(*(i+1),*i) is false for each iterator i in the range [first,last-1).

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().

Definition at line 2470 of file stl_algo.h.

template<typename RandomAccessIter>
void stable_sort RandomAccessIter  first,
RandomAccessIter  last
[inline]
 

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

Parameters:
first An iterator.
last Another iterator.
Returns:
Nothing.
Sorts the elements in the range [first,last) in ascending order, such that *(i+1)<*i is false for each iterator i in the range [first,last-1).

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().

Definition at line 2434 of file stl_algo.h.

template<typename ForwardIter1, typename ForwardIter2>
ForwardIter2 swap_ranges ForwardIter1  first1,
ForwardIter1  last1,
ForwardIter2  first2
 

Swap the elements of two sequences.

Parameters:
first1 A forward iterator.
last1 A forward iterator.
first2 A forward iterator.
Returns:
An iterator equal to first2+(last1-first1).
Swaps each element in the range [first1,last1) with the corresponding element in the range [first2,(last1-first1)). The ranges must not overlap.

Definition at line 701 of file stl_algo.h.

References std::iter_swap().

template<typename InputIter1, typename InputIter2, typename OutputIter, typename BinaryOperation>
OutputIter transform InputIter1  first1,
InputIter1  last1,
InputIter2  first2,
OutputIter  __result,
BinaryOperation  __binary_op
 

Perform an operation on corresponding elements of two sequences.

Parameters:
first1 An input iterator.
last1 An input iterator.
first2 An input iterator.
result An output iterator.
binary_op A 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.

Definition at line 770 of file stl_algo.h.

template<typename InputIter, typename OutputIter, typename UnaryOperation>
OutputIter transform InputIter  first,
InputIter  last,
OutputIter  __result,
UnaryOperation  __unary_op
 

Perform an operation on a sequence.

Parameters:
first An input iterator.
last An input iterator.
result An output iterator.
unary_op A 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.

Definition at line 736 of file stl_algo.h.

template<typename ForwardIter, typename BinaryPredicate>
ForwardIter unique ForwardIter  first,
ForwardIter  last,
BinaryPredicate  __binary_pred
 

Remove consecutive values from a sequence using a predicate.

Parameters:
first A forward iterator.
last A forward iterator.
binary_pred A 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.

Definition at line 1294 of file stl_algo.h.

References std::adjacent_find(), and std::unique_copy().

template<typename ForwardIter>
ForwardIter unique ForwardIter  first,
ForwardIter  last
 

Remove consecutive duplicate values from a sequence.

Parameters:
first A forward iterator.
last A 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.

Definition at line 1267 of file stl_algo.h.

References std::adjacent_find(), and std::unique_copy().

template<typename InputIter, typename OutputIter, typename BinaryPredicate>
OutputIter unique_copy InputIter  first,
InputIter  last,
OutputIter  __result,
BinaryPredicate  __binary_pred
[inline]
 

Copy a sequence, removing consecutive values using a predicate.

Parameters:
first An input iterator.
last An input iterator.
result An output iterator.
binary_pred A 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.

Definition at line 1236 of file stl_algo.h.

template<typename InputIter, typename OutputIter>
OutputIter unique_copy InputIter  first,
InputIter  last,
OutputIter  __result
[inline]
 

Copy a sequence, removing consecutive duplicate values.

Parameters:
first An input iterator.
last An input iterator.
result An 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.

Definition at line 1149 of file stl_algo.h.

Referenced by std::unique().


Generated on Thu Feb 10 23:23:30 2005 for libstdc++-v3 Source by  doxygen 1.4.0