Searching

Groups

• Binary Search

template <typename DerivedPolicy,   typename InputIterator,   typename T> __host__ __device__ InputIterator thrust::find(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator first,   InputIterator last,   const T & value);
template <typename InputIterator,   typename T> InputIterator thrust::find(InputIterator first,   InputIterator last,   const T & value);
template <typename DerivedPolicy,   typename InputIterator,   typename Predicate> __host__ __device__ InputIterator thrust::find_if(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator first,   InputIterator last,   Predicate pred);
template <typename InputIterator,   typename Predicate> InputIterator thrust::find_if(InputIterator first,   InputIterator last,   Predicate pred);
template <typename DerivedPolicy,   typename InputIterator,   typename Predicate> __host__ __device__ InputIterator thrust::find_if_not(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator first,   InputIterator last,   Predicate pred);
template <typename InputIterator,   typename Predicate> InputIterator thrust::find_if_not(InputIterator first,   InputIterator last,   Predicate pred);
template <typename DerivedPolicy,   typename InputIterator1,   typename InputIterator2> __host__ __device__ thrust::pair< InputIterator1, InputIterator2 > thrust::mismatch(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator1 first1,   InputIterator1 last1,   InputIterator2 first2);
template <typename InputIterator1,   typename InputIterator2> thrust::pair< InputIterator1, InputIterator2 > thrust::mismatch(InputIterator1 first1,   InputIterator1 last1,   InputIterator2 first2);
template <typename DerivedPolicy,   typename InputIterator1,   typename InputIterator2,   typename BinaryPredicate> __host__ __device__ thrust::pair< InputIterator1, InputIterator2 > thrust::mismatch(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator1 first1,   InputIterator1 last1,   InputIterator2 first2,   BinaryPredicate pred);
template <typename InputIterator1,   typename InputIterator2,   typename BinaryPredicate> thrust::pair< InputIterator1, InputIterator2 > thrust::mismatch(InputIterator1 first1,   InputIterator1 last1,   InputIterator2 first2,   BinaryPredicate pred);
template <typename DerivedPolicy,   typename ForwardIterator,   typename Predicate> __host__ __device__ ForwardIterator thrust::partition_point(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   Predicate pred);
template <typename ForwardIterator,   typename Predicate> ForwardIterator thrust::partition_point(ForwardIterator first,   ForwardIterator last,   Predicate pred);

Functions

Function thrust::find

template <typename DerivedPolicy,   typename InputIterator,   typename T> __host__ __device__ InputIterator find(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator first,   InputIterator last,   const T & value); find returns the first iterator i in the range [first, last) such that *i == value or last if no such iterator exists.

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

#include <thrust/find.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>
...
thrust::device_vector<int> input(4);

input[0] = 0;
input[1] = 5;
input[2] = 3;
input[3] = 7;

thrust::device_vector<int>::iterator iter;

iter = thrust::find(thrust::device, input.begin(), input.end(), 3); // returns input.first() + 2
iter = thrust::find(thrust::device, input.begin(), input.end(), 5); // returns input.first() + 1
iter = thrust::find(thrust::device, input.begin(), input.end(), 9); // returns input.end()

Template Parameters:

• DerivedPolicy The name of the derived execution policy.
• InputIterator is a model of Input Iterator and InputIterator'svalue_type is equality comparable to type T.
• T is a model of EqualityComparable.

Function Parameters:

• exec The execution policy to use for parallelization.
• first Beginning of the sequence to search.
• last End of the sequence to search.
• value The value to find.

Returns: The first iterator i such that *i == value or last.

See:

• find_if
• mismatch

Function thrust::find

template <typename InputIterator,   typename T> InputIterator find(InputIterator first,   InputIterator last,   const T & value); find returns the first iterator i in the range [first, last) such that *i == value or last if no such iterator exists.

#include <thrust/find.h>
#include <thrust/device_vector.h>
...
thrust::device_vector<int> input(4);

input[0] = 0;
input[1] = 5;
input[2] = 3;
input[3] = 7;

thrust::device_vector<int>::iterator iter;

iter = thrust::find(input.begin(), input.end(), 3); // returns input.first() + 2
iter = thrust::find(input.begin(), input.end(), 5); // returns input.first() + 1
iter = thrust::find(input.begin(), input.end(), 9); // returns input.end()

Template Parameters:

• InputIterator is a model of Input Iterator and InputIterator'svalue_type is equality comparable to type T.
• T is a model of EqualityComparable.

Function Parameters:

• first Beginning of the sequence to search.
• last End of the sequence to search.
• value The value to find.

Returns: The first iterator i such that *i == value or last.

See:

• find_if
• mismatch

Function thrust::find_if

template <typename DerivedPolicy,   typename InputIterator,   typename Predicate> __host__ __device__ InputIterator find_if(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator first,   InputIterator last,   Predicate pred); find_if returns the first iterator i in the range [first, last) such that pred(*i) is true or last if no such iterator exists.

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

#include <thrust/find.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>
...

struct greater_than_four
{
  __host__ __device__
  bool operator()(int x)
  {
    return x > 4;
  }
};

struct greater_than_ten
{
  __host__ __device__
  bool operator()(int x)
  {
    return x > 10;
  }
};

...
thrust::device_vector<int> input(4);

input[0] = 0;
input[1] = 5;
input[2] = 3;
input[3] = 7;

thrust::device_vector<int>::iterator iter;

iter = thrust::find_if(thrust::device, input.begin(), input.end(), greater_than_four()); // returns input.first() + 1

iter = thrust::find_if(thrust::device, input.begin(), input.end(), greater_than_ten());  // returns input.end()

Template Parameters:

• DerivedPolicy The name of the derived execution policy.
• InputIterator is a model of Input Iterator.
• Predicate is a model of Predicate.

Function Parameters:

• exec The execution policy to use for parallelization.
• first Beginning of the sequence to search.
• last End of the sequence to search.
• pred A predicate used to test range elements.

Returns: The first iterator i such that pred(*i) is true, or last.

See:

• find
• find_if_not
• mismatch

Function thrust::find_if

template <typename InputIterator,   typename Predicate> InputIterator find_if(InputIterator first,   InputIterator last,   Predicate pred); find_if returns the first iterator i in the range [first, last) such that pred(*i) is true or last if no such iterator exists.

#include <thrust/find.h>
#include <thrust/device_vector.h>

struct greater_than_four
{
  __host__ __device__
  bool operator()(int x)
  {
    return x > 4;
  }
};

struct greater_than_ten
{
  __host__ __device__
  bool operator()(int x)
  {
    return x > 10;
  }
};

...
thrust::device_vector<int> input(4);

input[0] = 0;
input[1] = 5;
input[2] = 3;
input[3] = 7;

thrust::device_vector<int>::iterator iter;

iter = thrust::find_if(input.begin(), input.end(), greater_than_four()); // returns input.first() + 1

iter = thrust::find_if(input.begin(), input.end(), greater_than_ten());  // returns input.end()

Template Parameters:

• InputIterator is a model of Input Iterator.
• Predicate is a model of Predicate.

Function Parameters:

• first Beginning of the sequence to search.
• last End of the sequence to search.
• pred A predicate used to test range elements.

Returns: The first iterator i such that pred(*i) is true, or last.

See:

• find
• find_if_not
• mismatch

Function thrust::find_if_not

template <typename DerivedPolicy,   typename InputIterator,   typename Predicate> __host__ __device__ InputIterator find_if_not(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator first,   InputIterator last,   Predicate pred); find_if_not returns the first iterator i in the range [first, last) such that pred(*i) is false or last if no such iterator exists.

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

#include <thrust/find.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>
...

struct greater_than_four
{
  __host__ __device__
  bool operator()(int x)
  {
    return x > 4;
  }
};

struct greater_than_ten
{
  __host__ __device__
  bool operator()(int x)
  {
    return x > 10;
  }
};

...
thrust::device_vector<int> input(4);

input[0] = 0;
input[1] = 5;
input[2] = 3;
input[3] = 7;

thrust::device_vector<int>::iterator iter;

iter = thrust::find_if_not(thrust::device, input.begin(), input.end(), greater_than_four()); // returns input.first()

iter = thrust::find_if_not(thrust::device, input.begin(), input.end(), greater_than_ten());  // returns input.first()

Template Parameters:

• DerivedPolicy The name of the derived execution policy.
• InputIterator is a model of Input Iterator.
• Predicate is a model of Predicate.

Function Parameters:

• exec The execution policy to use for parallelization.
• first Beginning of the sequence to search.
• last End of the sequence to search.
• pred A predicate used to test range elements.

Returns: The first iterator i such that pred(*i) is false, or last.

See:

• find
• find_if
• mismatch

Function thrust::find_if_not

template <typename InputIterator,   typename Predicate> InputIterator find_if_not(InputIterator first,   InputIterator last,   Predicate pred); find_if_not returns the first iterator i in the range [first, last) such that pred(*i) is false or last if no such iterator exists.

#include <thrust/find.h>
#include <thrust/device_vector.h>

struct greater_than_four
{
  __host__ __device__
  bool operator()(int x)
  {
    return x > 4;
  }
};

struct greater_than_ten
{
  __host__ __device__
  bool operator()(int x)
  {
    return x > 10;
  }
};

...
thrust::device_vector<int> input(4);

input[0] = 0;
input[1] = 5;
input[2] = 3;
input[3] = 7;

thrust::device_vector<int>::iterator iter;

iter = thrust::find_if_not(input.begin(), input.end(), greater_than_four()); // returns input.first()

iter = thrust::find_if_not(input.begin(), input.end(), greater_than_ten());  // returns input.first()

Template Parameters:

• InputIterator is a model of Input Iterator.
• Predicate is a model of Predicate.

Function Parameters:

• first Beginning of the sequence to search.
• last End of the sequence to search.
• pred A predicate used to test range elements.

Returns: The first iterator i such that pred(*i) is false, or last.

See:

• find
• find_if
• mismatch

Function thrust::mismatch

template <typename DerivedPolicy,   typename InputIterator1,   typename InputIterator2> __host__ __device__ thrust::pair< InputIterator1, InputIterator2 > mismatch(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator1 first1,   InputIterator1 last1,   InputIterator2 first2); mismatch finds the first position where the two ranges [first1, last1) and [first2, first2 + (last1 - first1)) differ. The two versions of mismatch use different tests for whether elements differ.

This version of mismatch finds the first iterator i in [first1, last1) such that *i == *(first2 + (i - first1)) is false. The return value is a pair whose first element is i and whose second element is *(first2 + (i - first1)). If no such iterator i exists, the return value is a pair whose first element is last1 and whose second element is *(first2 + (last1 - first1)).

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

#include <thrust/mismatch.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>
...
thrust::device_vector<int> vec1(4);
thrust::device_vector<int> vec2(4);

vec1[0] = 0;  vec2[0] = 0; 
vec1[1] = 5;  vec2[1] = 5;
vec1[2] = 3;  vec2[2] = 8;
vec1[3] = 7;  vec2[3] = 7;

typedef thrust::device_vector<int>::iterator Iterator;
thrust::pair<Iterator,Iterator> result;

result = thrust::mismatch(thrust::device, vec1.begin(), vec1.end(), vec2.begin());

// result.first  is vec1.begin() + 2
// result.second is vec2.begin() + 2

Template Parameters:

• DerivedPolicy The name of the derived execution policy.
• InputIterator1 is a model of Input Iterator and InputIterator1'svalue_type is equality comparable to InputIterator2'svalue_type.
• InputIterator2 is a model of Input Iterator.

Function Parameters:

• exec The execution policy to use for parallelization.
• first1 The beginning of the first sequence.
• last1 The end of the first sequence.
• first2 The beginning of the second sequence.

Returns: The first position where the sequences differ.

See:

• find
• find_if

Function thrust::mismatch

template <typename InputIterator1,   typename InputIterator2> thrust::pair< InputIterator1, InputIterator2 > mismatch(InputIterator1 first1,   InputIterator1 last1,   InputIterator2 first2); mismatch finds the first position where the two ranges [first1, last1) and [first2, first2 + (last1 - first1)) differ. The two versions of mismatch use different tests for whether elements differ.

This version of mismatch finds the first iterator i in [first1, last1) such that *i == *(first2 + (i - first1)) is false. The return value is a pair whose first element is i and whose second element is *(first2 + (i - first1)). If no such iterator i exists, the return value is a pair whose first element is last1 and whose second element is *(first2 + (last1 - first1)).

#include <thrust/mismatch.h>
#include <thrust/device_vector.h>
...
thrust::device_vector<int> vec1(4);
thrust::device_vector<int> vec2(4);

vec1[0] = 0;  vec2[0] = 0; 
vec1[1] = 5;  vec2[1] = 5;
vec1[2] = 3;  vec2[2] = 8;
vec1[3] = 7;  vec2[3] = 7;

typedef thrust::device_vector<int>::iterator Iterator;
thrust::pair<Iterator,Iterator> result;

result = thrust::mismatch(vec1.begin(), vec1.end(), vec2.begin());

// result.first  is vec1.begin() + 2
// result.second is vec2.begin() + 2

Template Parameters:

• InputIterator1 is a model of Input Iterator and InputIterator1'svalue_type is equality comparable to InputIterator2'svalue_type.
• InputIterator2 is a model of Input Iterator.

Function Parameters:

• first1 The beginning of the first sequence.
• last1 The end of the first sequence.
• first2 The beginning of the second sequence.

Returns: The first position where the sequences differ.

See:

• find
• find_if

Function thrust::mismatch

template <typename DerivedPolicy,   typename InputIterator1,   typename InputIterator2,   typename BinaryPredicate> __host__ __device__ thrust::pair< InputIterator1, InputIterator2 > mismatch(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator1 first1,   InputIterator1 last1,   InputIterator2 first2,   BinaryPredicate pred); mismatch finds the first position where the two ranges [first1, last1) and [first2, first2 + (last1 - first1)) differ. The two versions of mismatch use different tests for whether elements differ.

This version of mismatch finds the first iterator i in [first1, last1) such that pred(*i, *(first2 + (i - first1)) is false. The return value is a pair whose first element is i and whose second element is *(first2 + (i - first1)). If no such iterator i exists, the return value is a pair whose first element is last1 and whose second element is *(first2 + (last1 - first1)).

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

#include <thrust/mismatch.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>
...
thrust::device_vector<int> vec1(4);
thrust::device_vector<int> vec2(4);

vec1[0] = 0;  vec2[0] = 0; 
vec1[1] = 5;  vec2[1] = 5;
vec1[2] = 3;  vec2[2] = 8;
vec1[3] = 7;  vec2[3] = 7;

typedef thrust::device_vector<int>::iterator Iterator;
thrust::pair<Iterator,Iterator> result;

result = thrust::mismatch(thrust::device, vec1.begin(), vec1.end(), vec2.begin(), thrust::equal_to<int>());

// result.first  is vec1.begin() + 2
// result.second is vec2.begin() + 2

Template Parameters:

• DerivedPolicy The name of the derived execution policy.
• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• Predicate is a model of Input Iterator.

Function Parameters:

• exec The execution policy to use for parallelization.
• first1 The beginning of the first sequence.
• last1 The end of the first sequence.
• first2 The beginning of the second sequence.
• pred The binary predicate to compare elements.

Returns: The first position where the sequences differ.

See:

• find
• find_if

Function thrust::mismatch

template <typename InputIterator1,   typename InputIterator2,   typename BinaryPredicate> thrust::pair< InputIterator1, InputIterator2 > mismatch(InputIterator1 first1,   InputIterator1 last1,   InputIterator2 first2,   BinaryPredicate pred); mismatch finds the first position where the two ranges [first1, last1) and [first2, first2 + (last1 - first1)) differ. The two versions of mismatch use different tests for whether elements differ.

This version of mismatch finds the first iterator i in [first1, last1) such that pred(*i, *(first2 + (i - first1)) is false. The return value is a pair whose first element is i and whose second element is *(first2 + (i - first1)). If no such iterator i exists, the return value is a pair whose first element is last1 and whose second element is *(first2 + (last1 - first1)).

#include <thrust/mismatch.h>
#include <thrust/device_vector.h>
...
thrust::device_vector<int> vec1(4);
thrust::device_vector<int> vec2(4);

vec1[0] = 0;  vec2[0] = 0; 
vec1[1] = 5;  vec2[1] = 5;
vec1[2] = 3;  vec2[2] = 8;
vec1[3] = 7;  vec2[3] = 7;

typedef thrust::device_vector<int>::iterator Iterator;
thrust::pair<Iterator,Iterator> result;

result = thrust::mismatch(vec1.begin(), vec1.end(), vec2.begin(), thrust::equal_to<int>());

// result.first  is vec1.begin() + 2
// result.second is vec2.begin() + 2

Template Parameters:

• InputIterator1 is a model of Input Iterator.
• InputIterator2 is a model of Input Iterator.
• Predicate is a model of Input Iterator.

Function Parameters:

• first1 The beginning of the first sequence.
• last1 The end of the first sequence.
• first2 The beginning of the second sequence.
• pred The binary predicate to compare elements.

Returns: The first position where the sequences differ.

See:

• find
• find_if

Function thrust::partition_point

template <typename DerivedPolicy,   typename ForwardIterator,   typename Predicate> __host__ __device__ ForwardIterator partition_point(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   Predicate pred); partition_point returns an iterator pointing to the end of the true partition of a partitioned range. partition_point requires the input range [first,last) to be a partition; that is, all elements which satisfy pred shall appear before those that do not.

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

#include <thrust/partition.h>
#include <thrust/execution_policy.h>

struct is_even
{
  __host__ __device__
  bool operator()(const int &x)
  {
    return (x % 2) == 0;
  }
};

...

int A[] = {2, 4, 6, 8, 10, 1, 3, 5, 7, 9};
int * B = thrust::partition_point(thrust::host, A, A + 10, is_even());
// B - A is 5
// [A, B) contains only even values

Note: Though similar, partition_point is not redundant with find_if_not. partition_point's precondition provides an opportunity for a faster implemention.

Template Parameters:

• DerivedPolicy The name of the derived execution policy.
• ForwardIterator is a model of Forward Iterator, and ForwardIterator'svalue_type is convertible to Predicate'sargument_type.
• Predicate is a model of Predicate.

Function Parameters:

• exec The execution policy to use for parallelization.
• first The beginning of the range to consider.
• last The end of the range to consider.
• pred A function object which decides to which partition each element of the range [first, last) belongs.

Preconditions: The range [first, last) shall be partitioned by pred.

Returns: An iterator mid such that all_of(first, mid, pred) and none_of(mid, last, pred) are both true.

See:

• partition
• find_if_not

Function thrust::partition_point

template <typename ForwardIterator,   typename Predicate> ForwardIterator partition_point(ForwardIterator first,   ForwardIterator last,   Predicate pred); partition_point returns an iterator pointing to the end of the true partition of a partitioned range. partition_point requires the input range [first,last) to be a partition; that is, all elements which satisfy pred shall appear before those that do not.

#include <thrust/partition.h>

struct is_even
{
  __host__ __device__
  bool operator()(const int &x)
  {
    return (x % 2) == 0;
  }
};

...

int A[] = {2, 4, 6, 8, 10, 1, 3, 5, 7, 9};
int * B = thrust::partition_point(A, A + 10, is_even());
// B - A is 5
// [A, B) contains only even values

Note: Though similar, partition_point is not redundant with find_if_not. partition_point's precondition provides an opportunity for a faster implemention.

Template Parameters:

• ForwardIterator is a model of Forward Iterator, and ForwardIterator'svalue_type is convertible to Predicate'sargument_type.
• Predicate is a model of Predicate.

Function Parameters:

• first The beginning of the range to consider.
• last The end of the range to consider.
• pred A function object which decides to which partition each element of the range [first, last) belongs.

Preconditions: The range [first, last) shall be partitioned by pred.

Returns: An iterator mid such that all_of(first, mid, pred) and none_of(mid, last, pred) are both true.

See:

• partition
• find_if_not