Functions
Searching Algorithms

Functions

template<typename InputIterator , typename EqualityComparable >
InputIterator ustl::find (InputIterator first, InputIterator last, const EqualityComparable &value)
 
template<typename ForwardIterator >
ForwardIterator ustl::adjacent_find (ForwardIterator first, ForwardIterator last)
 
template<typename InputIterator >
pair< InputIterator, InputIterator > ustl::mismatch (InputIterator first1, InputIterator last1, InputIterator first2)
 
template<typename InputIterator >
bool ustl::equal (InputIterator first1, InputIterator last1, InputIterator first2)
 Returns true if two ranges are equal. This is an extension, present in uSTL and SGI STL.
 
template<typename InputIterator , typename EqualityComparable >
size_t ustl::count (InputIterator first, InputIterator last, const EqualityComparable &value)
 
template<typename ForwardIterator , typename LessThanComparable >
ForwardIterator ustl::lower_bound (ForwardIterator first, ForwardIterator last, const LessThanComparable &value)
 
template<typename ForwardIterator , typename LessThanComparable >
bool ustl::binary_search (ForwardIterator first, ForwardIterator last, const LessThanComparable &value)
 
template<typename ForwardIterator , typename LessThanComparable >
ForwardIterator ustl::upper_bound (ForwardIterator first, ForwardIterator last, const LessThanComparable &value)
 
template<typename ForwardIterator , typename LessThanComparable >
pair< ForwardIterator, ForwardIterator > ustl::equal_range (ForwardIterator first, ForwardIterator last, const LessThanComparable &value)
 
template<typename ForwardIterator1 , typename ForwardIterator2 >
ForwardIterator1 ustl::search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
 Searches for the first subsequence [first2,last2) in [first1,last1)
 
template<typename ForwardIterator1 , typename ForwardIterator2 >
ForwardIterator1 ustl::find_end (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
 Searches for the last subsequence [first2,last2) in [first1,last1)
 
template<typename Iterator , typename T >
Iterator ustl::search_n (Iterator first, Iterator last, size_t count, const T &value)
 Searches for the first occurence of count values in [first, last)
 
template<typename InputIterator , typename ForwardIterator >
InputIterator ustl::find_first_of (InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2)
 Searches [first1,last1) for the first occurrence of an element from [first2,last2)
 
template<typename ForwardIterator >
ForwardIterator ustl::max_element (ForwardIterator first, ForwardIterator last)
 Returns iterator to the max element in [first,last)
 
template<typename ForwardIterator >
ForwardIterator ustl::min_element (ForwardIterator first, ForwardIterator last)
 Returns iterator to the min element in [first,last)
 
template<typename RandomAccessIterator >
void ustl::nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last)
 Puts nth element into its sorted position. In this implementation, the entire array is sorted. I can't think of any use for it where the time gained would be useful.
 
template<typename Container , typename EqualityComparable >
Container::const_iterator ustl::find (const Container &ctr, const EqualityComparable &value)
 
template<typename Container , typename Predicate >
Container::const_iterator ustl::find_if (const Container &ctr, Predicate pred)
 
template<typename Container , typename LessThanComparable >
Container::const_iterator ustl::lower_bound (const Container &ctr, const LessThanComparable &value)
 
template<typename Container , typename LessThanComparable >
Container::const_iterator ustl::upper_bound (const Container &ctr, const LessThanComparable &value)
 
template<typename Container >
bool ustl::binary_search (const Container &ctr, const typename Container::value_type &value)
 
template<typename Container , typename LessThanComparable >
pair< typename Container::const_iterator, typename Container::const_iterator > ustl::equal_range (const Container &ctr, const LessThanComparable &value)
 

Detailed Description

Algorithms for searching through containers.

Function Documentation

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

Returns the first iterator such that *i == *(i + 1)

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

Performs a binary search inside the sorted range.

References ustl::lower_bound().

Referenced by ustl::binary_search().

template<typename Container >
bool ustl::binary_search ( const Container &  ctr,
const typename Container::value_type &  value 
)
inline

Performs a binary search for value. Assumes the range is sorted.

References ustl::binary_search().

template<typename InputIterator , typename EqualityComparable >
size_t ustl::count ( InputIterator  first,
InputIterator  last,
const EqualityComparable &  value 
)
inline

Count finds the number of elements in [first, last) that are equal to value. More precisely, the first version of count returns the number of iterators i in [first, last) such that *i == value.

Referenced by ustl::copy_n(), ustl::count(), and ustl::fill_n().

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

Returns pair<lower_bound,upper_bound>

References ustl::lower_bound().

Referenced by ustl::equal_range().

template<typename Container , typename LessThanComparable >
pair<typename Container::const_iterator,typename Container::const_iterator> ustl::equal_range ( const Container &  ctr,
const LessThanComparable &  value 
)
inline

Returns pair<lower_bound,upper_bound>

References ustl::equal_range().

template<typename InputIterator , typename EqualityComparable >
InputIterator ustl::find ( InputIterator  first,
InputIterator  last,
const EqualityComparable &  value 
)
inline

Returns the first iterator i in the range [first, last) such that *i == value. Returns last if no such iterator exists.

Referenced by ustl::map< K, V, Comp >::erase(), ustl::find(), ustl::string::find(), and ustl::istream::read_strz().

template<typename Container , typename EqualityComparable >
Container::const_iterator ustl::find ( const Container &  ctr,
const EqualityComparable &  value 
)
inline

Returns the first iterator i in the range [first, last) such that *i == value. Returns last if no such iterator exists.

References ustl::find().

template<typename Container , typename Predicate >
Container::const_iterator ustl::find_if ( const Container &  ctr,
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 LessThanComparable >
ForwardIterator ustl::lower_bound ( ForwardIterator  first,
ForwardIterator  last,
const LessThanComparable &  value 
)

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

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

Referenced by ustl::binary_search(), ustl::equal_range(), ustl::multimap< K, V, Comp >::find(), ustl::map< K, V, Comp >::find(), ustl::set< T, Comp >::insert(), ustl::map< K, V, Comp >::insert(), ustl::lower_bound(), and ustl::map< K, V, Comp >::operator[]().

template<typename Container , typename LessThanComparable >
Container::const_iterator ustl::lower_bound ( const Container &  ctr,
const LessThanComparable &  value 
)
inline

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

References ustl::lower_bound().

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

Returns the pointer to the first pair of unequal elements.

References ustl::make_pair().

Referenced by ustl::equal().

template<typename Container , typename LessThanComparable >
Container::const_iterator ustl::upper_bound ( const Container &  ctr,
const LessThanComparable &  value 
)
inline

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

References ustl::upper_bound().

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

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

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

Referenced by ustl::upper_bound().


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