Thrust v1.2 CUDA并行算法库

/* * Copyright 2008-2010 NVIDIA Corporation * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ /*! \file binary_search.h * \brief Search for values in sorted ranges. */ #pragma once #include <thrust/detail/config.h> #include <thrust/pair.h> namespace thrust { /*! \addtogroup algorithms */ /*! \addtogroup searching * \ingroup algorithms * \{ */ /*! \addtogroup binary_search Binary Search * \ingroup searching * \{ */ ////////////////////// // Scalar Functions // ////////////////////// /*! \p lower_bound is a version of binary search: it attempts to find * the element value in an ordered range <tt>[first, last)</tt>. * Specifically, it returns the first position where value could be * inserted without violating the ordering. This version of * \p lower_bound uses <tt>operator<</tt> for comparison and returns * the furthermost iterator \c i in <tt>[first, last)</tt> such that, * for every iterator \c j in <tt>[first, i)</tt>, <tt>*j < value</tt>. * * \param first The beginning of the ordered sequence. * \param last The end of the ordered sequence. * \param value The value to be searched. * \return The furthermost iterator \c i, such that <tt>*i < value</tt>. * * \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>. * \tparam LessThanComparable is a model of <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>. * * The following code snippet demonstrates how to use \p lower_bound * to search for values in a ordered range. * * \code * #include <thrust/binary_search.h> * #include <thrust/device_vector.h> * ... * thrust::device_vector<int> input(5); * * input[0] = 0; * input[1] = 2; * input[2] = 5; * input[3] = 7; * input[4] = 8; * * thrust::lower_bound(input.begin(), input.end(), 0); // returns input.begin() * thrust::lower_bound(input.begin(), input.end(), 1); // returns input.begin() + 1 * thrust::lower_bound(input.begin(), input.end(), 2); // returns input.begin() + 1 * thrust::lower_bound(input.begin(), input.end(), 3); // returns input.begin() + 2 * thrust::lower_bound(input.begin(), input.end(), 8); // returns input.begin() + 4 * thrust::lower_bound(input.begin(), input.end(), 9); // returns input.end() * \endcode * * \see http://www.sgi.com/tech/stl/lower_bound.html * \see \p upper_bound * \see \p equal_range * \see \p binary_search */ template <class ForwardIterator, class LessThanComparable> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const LessThanComparable& value); /*! \p lower_bound is a version of binary search: it attempts to find * the element value in an ordered range <tt>[first, last)</tt>. * Specifically, it returns the first position where value could be * inserted without violating the ordering. This version of * \p lower_bound uses function object \c comp for comparison * and returns the furthermost iterator \c i in <tt>[first, last)</tt> * such that, for every iterator \c j in <tt>[first, i)</tt>, * <tt>comp(*j, value)</tt> is \c true. * * \param first The beginning of the ordered sequence. * \param last The end of the ordered sequence. * \param value The value to be searched. * \param comp The comparison operator. * \return The furthermost iterator \c i, such that <tt>comp(*i, value)</tt> is \c true. * * \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>. * \tparam T is comparable to \p ForwardIterator's \c value_type. * \tparam StrictWeakOrdering is a model of <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">Strict Weak Ordering</a>. * * The following code snippet demonstrates how to use \p lower_bound * to search for values in a ordered range. * * \code * #include <thrust/binary_search.h> * #include <thrust/device_vector.h> * #include <thrust/functional.h> * ... * thrust::device_vector<int> input(5); * * input[0] = 0; * input[1] = 2; * input[2] = 5; * input[3] = 7; * input[4] = 8; * * thrust::lower_bound(input.begin(), input.end(), 0, thrust::less<int>()); // returns input.begin() * thrust::lower_bound(input.begin(), input.end(), 1, thrust::less<int>()); // returns input.begin() + 1 * thrust::lower_bound(input.begin(), input.end(), 2, thrust::less<int>()); // returns input.begin() + 1 * thrust::lower_bound(input.begin(), input.end(), 3, thrust::less<int>()); // returns input.begin() + 2 * thrust::lower_bound(input.begin(), input.end(), 8, thrust::less<int>()); // returns input.begin() + 4 * thrust::lower_bound(input.begin(), input.end(), 9, thrust::less<int>()); // returns input.end() * \endcode * * \see http://www.sgi.com/tech/stl/lower_bound.html * \see \p upper_bound * \see \p equal_range * \see \p binary_search */ template <class ForwardIterator, class T, class StrictWeakOrdering> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp); /*! \p upper_bound is a version of binary search: it attempts to find * the element value in an ordered range <tt>[first, last)</tt>. * Specifically, it returns the last position where value could be * inserted without violating the ordering. This version of * \p upper_bound uses <tt>operator<</tt> for comparison and returns * the furthermost iterator \c i in <tt>[first, last)</tt> such that, * for every iterator \c j in <tt>[first, i)</tt>, <tt>value < *j</tt> * is \c false. * * \param first The beginning of the ordered sequence. * \param last The end of the ordered sequence. * \param value The value to be searched. * \return The furthermost iterator \c i, such that <tt>value < *i</tt> is \c false. * * \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>. * \tparam LessThanComparable is a model of <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>. * * The following code snippet demonstrates how to use \p upper_bound * to search for values in a ordered range. * * \code * #include <thrust/binary_search.h> * #include <thrust/device_vector.h> * ... * thrust::device_vector<int> input(5); * * input[0] = 0; * input[1] = 2; * input[2] = 5; * input[3] = 7; * input[4] = 8; * * thrust::upper_bound(input.begin(), input.end(), 0); // returns input.begin() + 1 * thrust::upper_bound(input.begin(), input.end(), 1); // returns input.begin() + 1 * thrust::upper_bound(input.begin(), input.end(), 2); // returns input.begin() + 2 * thrust::upper_bound(input.begin(), input.end(), 3); // returns input.begin() + 2 * thrust::upper_bound(input.begin(), input.end(), 8); // returns input.end() * thrust::upper_bound(input.begin(), input.end(), 9); // returns input.end() * \endcode * * \see http://www.sgi.com/tech/stl/upper_bound.html * \see \p lower_bound * \see \p equal_range * \see \p binary_search */ template <class ForwardIterator, class LessThanComparable> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const LessThanComparable& value); /*! \p upper_bound is a version of b