thrust

◆ equal_range() [3/4]

template<typename DerivedPolicy , typename ForwardIterator , typename T , typename StrictWeakOrdering >
__host__ __device__ thrust::pair<ForwardIterator, ForwardIterator> thrust::equal_range ( const thrust::detail::execution_policy_base< DerivedPolicy > &  exec,
ForwardIterator  first,
ForwardIterator  last,
const T &  value,
StrictWeakOrdering  comp 
)

equal_range is a version of binary search: it attempts to find the element value in an ordered range [first, last). The value returned by equal_range is essentially a combination of the values returned by lower_bound and upper_bound: it returns a pair of iterators i and j such that i is the first position where value could be inserted without violating the ordering and j is the last position where value could be inserted without violating the ordering. It follows that every element in the range [i, j) is equivalent to value, and that [i, j) is the largest subrange of [first, last) that has this property.

This version of equal_range returns a pair of iterators [i, j). i is the furthermost iterator in [first, last) such that, for every iterator k in [first, i), comp(*k, value) is true. j is the furthermost iterator in [first, last) such that, for every iterator k in [first, last), comp(value, *k) is false. For every iterator k in [i, j), neither comp(value, *k) nor comp(*k, value) is true.

The algorithm's execution is parallelized as determined by exec.

Parameters
execThe execution policy to use for parallelization.
firstThe beginning of the ordered sequence.
lastThe end of the ordered sequence.
valueThe value to be searched.
compThe comparison operator.
Returns
A pair of iterators [i, j) that define the range of equivalent elements.
Template Parameters
DerivedPolicyThe name of the derived execution policy.
ForwardIteratoris a model of Forward Iterator.
Tis comparable to ForwardIterator's value_type.
StrictWeakOrderingis a model of Strict Weak Ordering.

The following code snippet demonstrates how to use equal_range to search for values in a ordered range using the thrust::device execution policy for parallelization:

...
thrust::device_vector<int> input(5);
input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;
thrust::equal_range(thrust::device, input.begin(), input.end(), 0, thrust::less<int>()); // returns [input.begin(), input.begin() + 1)
thrust::equal_range(thrust::device, input.begin(), input.end(), 1, thrust::less<int>()); // returns [input.begin() + 1, input.begin() + 1)
thrust::equal_range(thrust::device, input.begin(), input.end(), 2, thrust::less<int>()); // returns [input.begin() + 1, input.begin() + 2)
thrust::equal_range(thrust::device, input.begin(), input.end(), 3, thrust::less<int>()); // returns [input.begin() + 2, input.begin() + 2)
thrust::equal_range(thrust::device, input.begin(), input.end(), 8, thrust::less<int>()); // returns [input.begin() + 4, input.end)
thrust::equal_range(thrust::device, input.begin(), input.end(), 9, thrust::less<int>()); // returns [input.end(), input.end)
See also
http://www.sgi.com/tech/stl/equal_range.html
lower_bound
upper_bound
binary_search