Functions
Predicate Algorithms

Functions

template<typename InputIterator , typename OutputIterator , typename UnaryFunction >
OutputIterator ustl::transform (InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op)
 
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename BinaryFunction >
OutputIterator ustl::transform (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction op)
 
template<typename ForwardIterator , typename Generator >
void ustl::generate (ForwardIterator first, ForwardIterator last, Generator gen)
 
template<typename OutputIterator , typename Generator >
OutputIterator ustl::generate_n (OutputIterator first, size_t n, Generator gen)
 
template<typename RandomAccessIterator , typename Compare >
void ustl::sort (RandomAccessIterator first, RandomAccessIterator last, Compare)
 
template<typename RandomAccessIterator , typename Compare >
void ustl::stable_sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp)
 
template<typename InputIterator , typename OutputIterator , typename Predicate >
OutputIterator ustl::copy_if (InputIterator first, InputIterator last, OutputIterator result, Predicate pred)
 
template<typename InputIterator , typename Predicate >
InputIterator ustl::find_if (InputIterator first, InputIterator last, Predicate pred)
 
template<typename ForwardIterator , typename BinaryPredicate >
ForwardIterator ustl::adjacent_find (ForwardIterator first, ForwardIterator last, BinaryPredicate p)
 
template<typename InputIterator , typename BinaryPredicate >
pair< InputIterator, InputIterator > ustl::mismatch (InputIterator first1, InputIterator last1, InputIterator first2, BinaryPredicate comp)
 
template<typename InputIterator , typename BinaryPredicate >
bool ustl::equal (InputIterator first1, InputIterator last1, InputIterator first2, BinaryPredicate comp)
 
template<typename InputIterator , typename Predicate >
size_t ustl::count_if (InputIterator first, InputIterator last, Predicate pred)
 
template<typename ForwardIterator , typename Predicate , typename T >
void ustl::replace_if (ForwardIterator first, ForwardIterator last, Predicate pred, const T &new_value)
 
template<typename InputIterator , typename OutputIterator , typename Predicate , typename T >
OutputIterator ustl::replace_copy_if (InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T &new_value)
 
template<typename InputIterator , typename OutputIterator , typename Predicate >
OutputIterator ustl::remove_copy_if (InputIterator first, InputIterator last, OutputIterator result, Predicate pred)
 
template<typename ForwardIterator , typename Predicate >
ForwardIterator ustl::remove_if (ForwardIterator first, ForwardIterator last, Predicate pred)
 
template<typename InputIterator , typename OutputIterator , typename BinaryPredicate >
OutputIterator ustl::unique_copy (InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred)
 
template<typename ForwardIterator , typename BinaryPredicate >
ForwardIterator ustl::unique (ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred)
 
template<typename ForwardIterator , typename T , typename StrictWeakOrdering >
ForwardIterator ustl::lower_bound (ForwardIterator first, ForwardIterator last, const T &value, StrictWeakOrdering comp)
 
template<typename ForwardIterator , typename T , typename StrictWeakOrdering >
bool ustl::binary_search (ForwardIterator first, ForwardIterator last, const T &value, StrictWeakOrdering comp)
 
template<typename ForwardIterator , typename T , typename StrictWeakOrdering >
ForwardIterator ustl::upper_bound (ForwardIterator first, ForwardIterator last, const T &value, StrictWeakOrdering comp)
 
template<typename ForwardIterator , typename T , typename StrictWeakOrdering >
pair< ForwardIterator, ForwardIterator > ustl::equal_range (ForwardIterator first, ForwardIterator last, const T &value, StrictWeakOrdering comp)
 
template<typename RandomAccessIterator , typename Compare >
void ustl::nth_element (RandomAccessIterator first, RandomAccessIterator, RandomAccessIterator last, Compare comp)
 Puts nth element into its sorted position. In this implementation, the entire array is sorted. The performance difference is so small and the function use is so rare, there is no need to have code for it.
 
template<typename ForwardIterator1 , typename ForwardIterator2 , typename BinaryPredicate >
ForwardIterator1 ustl::search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate comp)
 Searches for the first subsequence [first2,last2) in [first1,last1)
 
template<typename ForwardIterator1 , typename ForwardIterator2 , typename BinaryPredicate >
ForwardIterator1 ustl::find_end (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate comp)
 Searches for the last subsequence [first2,last2) in [first1,last1)
 
template<typename Iterator , typename T , typename BinaryPredicate >
Iterator ustl::search_n (Iterator first, Iterator last, size_t count, const T &value, BinaryPredicate comp)
 Searches for the first occurence of count values in [first, last)
 
template<typename InputIterator , typename ForwardIterator , typename BinaryPredicate >
InputIterator ustl::find_first_of (InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPredicate comp)
 Searches [first1,last1) for the first occurrence of an element from [first2,last2)
 
template<typename InputIterator1 , typename InputIterator2 , typename StrictWeakOrdering >
bool ustl::includes (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, StrictWeakOrdering comp)
 Returns true if [first2,last2) is a subset of [first1,last1)
 
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename StrictWeakOrdering >
OutputIterator ustl::set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp)
 Merges [first1,last1) with [first2,last2) More...
 
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename StrictWeakOrdering >
OutputIterator ustl::set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp)
 Creates a set containing elements shared by the given ranges.
 
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename StrictWeakOrdering >
OutputIterator ustl::set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp)
 Removes from [first1,last1) elements present in [first2,last2)
 
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename StrictWeakOrdering >
OutputIterator ustl::set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp)
 Performs union of sets A-B and B-A.
 
template<typename ForwardIterator , typename StrictWeakOrdering >
bool ustl::is_sorted (ForwardIterator first, ForwardIterator last, StrictWeakOrdering comp)
 Returns true if the given range is sorted.
 
template<typename InputIterator1 , typename InputIterator2 , typename BinaryPredicate >
bool ustl::lexicographical_compare (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate comp)
 Compares two given containers like strcmp compares strings.
 
template<typename BidirectionalIterator , typename StrictWeakOrdering >
bool ustl::next_permutation (BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp)
 Creates the next lexicographical permutation of [first,last). Returns false if no further permutations can be created.
 
template<typename BidirectionalIterator , typename StrictWeakOrdering >
bool ustl::prev_permutation (BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp)
 Creates the previous lexicographical permutation of [first,last). Returns false if no further permutations can be created.
 
template<typename ForwardIterator , typename BinaryPredicate >
ForwardIterator ustl::max_element (ForwardIterator first, ForwardIterator last, BinaryPredicate comp)
 Returns iterator to the max element in [first,last)
 
template<typename ForwardIterator , typename BinaryPredicate >
ForwardIterator ustl::min_element (ForwardIterator first, ForwardIterator last, BinaryPredicate comp)
 Returns iterator to the min element in [first,last)
 
template<typename RandomAccessIterator , typename StrictWeakOrdering >
void ustl::partial_sort (RandomAccessIterator first, RandomAccessIterator, RandomAccessIterator last, StrictWeakOrdering comp)
 Makes [first,middle) a part of the sorted array. Contents of [middle,last) is undefined. This implementation just calls stable_sort.
 
template<typename InputIterator , typename RandomAccessIterator , typename StrictWeakOrdering >
RandomAccessIterator ustl::partial_sort_copy (InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, StrictWeakOrdering comp)
 Like partial_sort, but outputs to [result_first,result_last)
 
template<typename ForwardIterator , typename Predicate >
ForwardIterator ustl::stable_partition (ForwardIterator first, ForwardIterator last, Predicate pred)
 Like partition, but preserves equal element order.
 
template<typename ForwardIterator , typename Predicate >
ForwardIterator ustl::partition (ForwardIterator first, ForwardIterator last, Predicate pred)
 Splits [first,last) in two by pred. More...
 

Detailed Description

Algorithms that take a functor object. Avoid these if you can, and carefully check the generated assembly if you can't. These algorithms can and will generate prodigious amounts of bloat if you are not very very careful about writing your functors.

Function Documentation

template<typename ForwardIterator , typename BinaryPredicate >
ForwardIterator ustl::adjacent_find ( ForwardIterator  first,
ForwardIterator  last,
BinaryPredicate  p 
)
inline

Returns the first iterator such that p(*i, *(i + 1)) == true.

template<typename ForwardIterator , typename T , typename StrictWeakOrdering >
bool ustl::binary_search ( ForwardIterator  first,
ForwardIterator  last,
const T &  value,
StrictWeakOrdering  comp 
)
inline

Performs a binary search inside the sorted range.

References ustl::lower_bound().

template<typename InputIterator , typename OutputIterator , typename Predicate >
OutputIterator ustl::copy_if ( InputIterator  first,
InputIterator  last,
OutputIterator  result,
Predicate  pred 
)
inline

Copy_if copies elements from the range [first, last) to the range [result, result + (last - first)) if pred(*i) returns true.

template<typename InputIterator , typename Predicate >
size_t ustl::count_if ( InputIterator  first,
InputIterator  last,
Predicate  pred 
)
inline

Count_if finds the number of elements in [first, last) that satisfy the predicate pred. More precisely, the first version of count_if returns the number of iterators i in [first, last) such that pred(*i) is true.

template<typename InputIterator , typename BinaryPredicate >
bool ustl::equal ( InputIterator  first1,
InputIterator  last1,
InputIterator  first2,
BinaryPredicate  comp 
)
inline

Returns true if two ranges are equal. This is an extension, present in uSTL and SGI STL.

References ustl::mismatch().

template<typename ForwardIterator , typename T , typename StrictWeakOrdering >
pair<ForwardIterator,ForwardIterator> ustl::equal_range ( ForwardIterator  first,
ForwardIterator  last,
const T &  value,
StrictWeakOrdering  comp 
)
inline

Returns pair<lower_bound,upper_bound>

References ustl::lower_bound().

template<typename InputIterator , typename Predicate >
InputIterator ustl::find_if ( InputIterator  first,
InputIterator  last,
Predicate  pred 
)
inline

Returns the first iterator i in the range [first, last) such that pred(*i) is true. Returns last if no such iterator exists.

template<typename ForwardIterator , typename Generator >
void ustl::generate ( ForwardIterator  first,
ForwardIterator  last,
Generator  gen 
)
inline

Generate assigns the result of invoking gen, a function object that takes no arguments, to each element in the range [first, last).

Referenced by ustl::generate().

template<typename OutputIterator , typename Generator >
OutputIterator ustl::generate_n ( OutputIterator  first,
size_t  n,
Generator  gen 
)
inline

Generate_n assigns the result of invoking gen, a function object that takes no arguments, to each element in the range [first, first+n). The return value is first + n.

template<typename ForwardIterator , typename T , typename StrictWeakOrdering >
ForwardIterator ustl::lower_bound ( ForwardIterator  first,
ForwardIterator  last,
const T &  value,
StrictWeakOrdering  comp 
)

Returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), comp(*j, value) is true. Assumes the range is sorted.

References ustl::advance(), and ustl::distance().

template<typename InputIterator , typename BinaryPredicate >
pair<InputIterator,InputIterator> ustl::mismatch ( InputIterator  first1,
InputIterator  last1,
InputIterator  first2,
BinaryPredicate  comp 
)
inline

Returns the pointer to the first pair of unequal elements.

References ustl::make_pair().

template<typename ForwardIterator , typename Predicate >
ForwardIterator ustl::partition ( ForwardIterator  first,
ForwardIterator  last,
Predicate  pred 
)
inline

Splits [first,last) in two by pred.

Creates two ranges [first,middle) and [middle,last), where every element in the former is less than every element in the latter. The return value is middle.

References ustl::stable_partition().

template<typename InputIterator , typename OutputIterator , typename Predicate >
OutputIterator ustl::remove_copy_if ( InputIterator  first,
InputIterator  last,
OutputIterator  result,
Predicate  pred 
)
inline

Remove_copy_if copies elements from the range [first, last) to a range beginning at result, except that elements for which pred is true are not copied. The return value is the end of the resulting range. This operation is stable, meaning that the relative order of the elements that are copied is the same as in the range [first, last).

template<typename ForwardIterator , typename Predicate >
ForwardIterator ustl::remove_if ( ForwardIterator  first,
ForwardIterator  last,
Predicate  pred 
)
inline

Remove_if removes from the range [first, last) every element x such that pred(x) is true. That is, remove_if returns an iterator new_last such that the range [first, new_last) contains no elements for which pred is true. The iterators in the range [new_last, last) are all still dereferenceable, but the elements that they point to are unspecified. Remove_if is stable, meaning that the relative order of elements that are not removed is unchanged.

References ustl::remove_copy_if().

template<typename InputIterator , typename OutputIterator , typename Predicate , typename T >
OutputIterator ustl::replace_copy_if ( InputIterator  first,
InputIterator  last,
OutputIterator  result,
Predicate  pred,
const T &  new_value 
)
inline

Replace_copy_if copies elements from the range [first, last) to the range [result, result + (last-first)), except that any element for which pred is true is not copied; new_value is copied instead. More precisely, for every integer n such that 0 <= n < last-first, replace_copy_if performs the assignment *(result+n) = new_value if pred(*(first+n)), and *(result+n) = *(first+n) otherwise.

template<typename ForwardIterator , typename Predicate , typename T >
void ustl::replace_if ( ForwardIterator  first,
ForwardIterator  last,
Predicate  pred,
const T &  new_value 
)
inline

Replace_if replaces every element in the range [first, last) for which pred returns true with new_value. That is: for every iterator i, if pred(*i) is true then it performs the assignment *i = new_value.

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename StrictWeakOrdering >
OutputIterator ustl::set_union ( InputIterator1  first1,
InputIterator1  last1,
InputIterator2  first2,
InputIterator2  last2,
OutputIterator  result,
StrictWeakOrdering  comp 
)

Merges [first1,last1) with [first2,last2)

Result will contain every element that is in either set. If duplicate elements are present, max(n,m) is placed in the result.

References ustl::copy().

template<typename RandomAccessIterator , typename Compare >
void ustl::sort ( RandomAccessIterator  first,
RandomAccessIterator  last,
Compare   
)

Sorts the container

References ustl::distance().

Referenced by ustl::nth_element(), and ustl::sort().

template<typename RandomAccessIterator , typename Compare >
void ustl::stable_sort ( RandomAccessIterator  first,
RandomAccessIterator  last,
Compare  comp 
)

Sorts the container preserving order of equal elements.

References ustl::rotate().

Referenced by ustl::partial_sort(), and ustl::stable_sort().

template<typename InputIterator , typename OutputIterator , typename UnaryFunction >
OutputIterator ustl::transform ( InputIterator  first,
InputIterator  last,
OutputIterator  result,
UnaryFunction  op 
)
inline

The first version of transform performs the operation op(*i) for each iterator i in the range [first, last), and assigns the result of that operation to *o, where o is the corresponding output iterator. That is, for each n such that 0 <= n < last - first, it performs the assignment *(result + n) = op(*(first + n)). The return value is result + (last - first).

Referenced by ustl::bitset< Size >::flip(), and ustl::transform().

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename BinaryFunction >
OutputIterator ustl::transform ( InputIterator1  first1,
InputIterator1  last1,
InputIterator2  first2,
OutputIterator  result,
BinaryFunction  op 
)
inline

The second version of transform is very similar, except that it uses a Binary Function instead of a Unary Function: it performs the operation op(*i1, *i2) for each iterator i1 in the range [first1, last1) and assigns the result to *o, where i2 is the corresponding iterator in the second input range and where o is the corresponding output iterator. That is, for each n such that 0 <= n < last1 - first1, it performs the assignment *(result + n) = op(*(first1 + n), *(first2 + n). The return value is result + (last1 - first1).

template<typename ForwardIterator , typename BinaryPredicate >
ForwardIterator ustl::unique ( ForwardIterator  first,
ForwardIterator  last,
BinaryPredicate  binary_pred 
)
inline

Every time a consecutive group of duplicate elements appears in the range [first, last), the algorithm unique removes all but the first element. That is, unique returns an iterator new_last such that the range [first, new_last) contains no two consecutive elements that are duplicates. The iterators in the range [new_last, last) are all still dereferenceable, but the elements that they point to are unspecified. Unique is stable, meaning that the relative order of elements that are not removed is unchanged.

References ustl::unique_copy().

template<typename InputIterator , typename OutputIterator , typename BinaryPredicate >
OutputIterator ustl::unique_copy ( InputIterator  first,
InputIterator  last,
OutputIterator  result,
BinaryPredicate  binary_pred 
)

The reason there are two different versions of unique_copy is that there are two different definitions of what it means for a consecutive group of elements to be duplicates. In the first version, the test is simple equality: the elements in a range [f, l) are duplicates if, for every iterator i in the range, either i == f or else *i == *(i-1). In the second, the test is an arbitrary Binary Predicate binary_pred: the elements in [f, l) are duplicates if, for every iterator i in the range, either i == f or else binary_pred(*i, *(i-1)) is true.

template<typename ForwardIterator , typename T , typename StrictWeakOrdering >
ForwardIterator ustl::upper_bound ( ForwardIterator  first,
ForwardIterator  last,
const T &  value,
StrictWeakOrdering  comp 
)

Returns the furthermost iterator i in [first,last) such that for every iterator j in [first,i), comp(value,*j) is false.

References ustl::advance(), and ustl::distance().


Generated on Mon Sep 28 2015 17:58:50 for uSTL by Doxygen 1.8.10