Binary Search Operations

Search the elements of a view using binary search. Defined in stapl/algorithms/sorting.hpp. More...

Collaboration diagram for Binary Search Operations:

Classes
class	stapl::algo_details::range_lower_bound< Value, StrictWeakOrdering >
	Work function for lower_bound(), which takes a view over a sorted input, and computes the std::lower_bound on it, or null_reference if the range is all less than the given value. More...
class	stapl::algo_details::upper_bound_map_wf< Value, StrictWeakOrdering >
	Work function for upper_bound(), which takes a view over a sorted input, and computes the std::upper_bound on it, or null_reference if the range is all less than or equal to the given value. More...
class	stapl::algo_details::binary_search_map_wf< Value, StrictWeakOrdering >
	Work function which invokes std::binary_search. More...
class	stapl::algo_details::range_equal_range< Value, StrictWeakOrdering, Return >
	Work function for equal_range() which returns the position of its argument if the argument compares equal to the given value according to the given ordering, or null_reference position otherwise. More...
struct	stapl::algo_details::equal_range_reduce_wf< Return >
	Work function for equal_range() which, given two domains, returns the one which is non-empty, or merges them together. More...

Functions
template<typename View , typename T , typename StrictWeakOrdering >
View::reference	stapl::lower_bound (View const &view, T value, StrictWeakOrdering comparator)
	Finds the first element in the input view which compares greater than or equal to the given value. More...
template<typename View , typename T >
View::reference	stapl::lower_bound (View const &view, T const &value)
	Finds the first element in the input view which compares greater than or equal to the given value. More...
template<typename View , typename T , typename StrictWeakOrdering >
View::reference	stapl::upper_bound (View const &view, T value, StrictWeakOrdering comparator)
	Finds the first element in the input view which compares greater than the given value. More...
template<typename View , typename T >
View::reference	stapl::upper_bound (View const &view, T const &value)
	Finds the first element in the input view which compares greater than the given value. More...
template<typename View , typename StrictWeakOrdering >
bool	stapl::binary_search (View const &view, typename View::value_type value, StrictWeakOrdering comparator)
	Searches the input view for the given value using a binary search, and returns true if that value exists in the input. More...
template<typename View >
bool	stapl::binary_search (View const &view, typename View::value_type const &value)
	Searches the input view for the given value using a binary search, and returns true if that value exists in the input. More...
template<typename View , typename StrictWeakOrdering >
View	stapl::equal_range (View const &view, typename View::value_type value, StrictWeakOrdering comparator)
	Computes the range of elements which are equal to the given value. More...
template<typename View >
View	stapl::equal_range (View const &view, typename View::value_type const &value)
	Computes the range of elements which are equal to the given value. More...

Detailed Description

Search the elements of a view using binary search. Defined in stapl/algorithms/sorting.hpp.

Function Documentation

lower_bound() [1/2]

template<typename View , typename T , typename StrictWeakOrdering >

View::reference stapl::lower_bound	(	View const &	view,
		T	value,
		StrictWeakOrdering	comparator
	)

Finds the first element in the input view which compares greater than or equal to the given value.

Parameters

view	One-dimensional view of the input (which is sorted).
value	Value to search for in the input (of same type as inputs).
comparator	Binary functor which implements the less than operation.

Returns

A reference to the first value in the input which is greater than or equal to the given value.

lower_bound() [2/2]

template<typename View , typename T >

View::reference stapl::lower_bound	(	View const &	view,
		T const &	value
	)

Finds the first element in the input view which compares greater than or equal to the given value.

Parameters

view	One-dimensional view of the input (which is sorted).
value	Value to search for in the input (of same type as inputs).

Returns

A reference to the first value in the input which is greater than or equal to the given value.

upper_bound() [1/2]

template<typename View , typename T , typename StrictWeakOrdering >

View::reference stapl::upper_bound	(	View const &	view,
		T	value,
		StrictWeakOrdering	comparator
	)

Finds the first element in the input view which compares greater than the given value.

Parameters

view	One-dimensional view of the input (which is sorted).
value	Value to search for in the input (of same type as inputs).
comparator	Binary functor which implements the less than operation.

Returns

A reference to the first value in the input which is greater than the given value.

upper_bound() [2/2]

template<typename View , typename T >

View::reference stapl::upper_bound	(	View const &	view,
		T const &	value
	)

Finds the first element in the input view which compares greater than the given value.

Parameters

view	One-dimensional view of the input (which is sorted).
value	Value to search for in the input (of same type as inputs).

Returns

A reference to the first value in the input which is greater than the given value.

binary_search() [1/2]

template<typename View , typename StrictWeakOrdering >

bool stapl::binary_search	(	View const &	view,
		typename View::value_type	value,
		StrictWeakOrdering	comparator
	)

Searches the input view for the given value using a binary search, and returns true if that value exists in the input.

Parameters

view	One-dimensional view of the input.
value	Value to search for in the input (of same type as inputs).
comparator	Binary functor used to compare elements.

Returns

True if the value is found in the input, false otherwise.

binary_search() [2/2]

template<typename View >

bool stapl::binary_search	(	View const &	view,
		typename View::value_type const &	value
	)

Searches the input view for the given value using a binary search, and returns true if that value exists in the input.

Parameters

view	One-dimensional view of the input.
value	Value to search for in the input (of same type as inputs).

Returns

True if the value is found in the input, false otherwise.

equal_range() [1/2]

template<typename View , typename StrictWeakOrdering >

View stapl::equal_range	(	View const &	view,
		typename View::value_type	value,
		StrictWeakOrdering	comparator
	)

Computes the range of elements which are equal to the given value.

Parameters

view	One-dimensional view of input (which is sorted).
value	Value to search for in the input (of same type as inputs).
comparator	Functor which provides ordering operation.

Returns

A view over the elements which compare equal to the given value.

equal_range() [2/2]

template<typename View >

View stapl::equal_range	(	View const &	view,
		typename View::value_type const &	value
	)

Computes the range of elements which are equal to the given value.

Parameters

view	One-dimensional view of input (which is sorted).
value	Value to search for in the input (of same type as inputs).

Returns

A view over the elements which compare equal to the given value.