omptl_algorithm.h

omptl使用openmp多核库优化过的STL库

			::std::bind2nd(::std::not_equal_to<Iterator>(), last) );

	if (result != results + P)
		return *result;

	return last;
}

template<class InputIterator, class EqualityComparable>
InputIterator find(InputIterator first, InputIterator last,
                   const EqualityComparable& value, const unsigned P)
{
	return ::omptl::_find(first, last, value, P, typename
		::std::iterator_traits<InputIterator>::iterator_category());

}

template<class InputIterator, class Predicate>
InputIterator _find_if( InputIterator first, InputIterator last,
			Predicate pred, const unsigned P,
			::std::input_iterator_tag)
{
	return ::std::find_if(first, last, pred);
}

template<class Iterator, class Predicate, class IteratorTag>
Iterator _find_if( Iterator first, Iterator last, Predicate pred,
			const unsigned P, IteratorTag)
{
	if (_linear_serial_is_faster(first, last, P))
		return ::std::find_if(first, last, pred);

	::std::pair<Iterator, Iterator> partitions[P];
	::omptl::_partition_range(first, last, partitions, P);

	Iterator results[P];
	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		results[t] = ::std::find_if(partitions[t].first,
					 partitions[t].second, pred);

	Iterator *result = ::std::find_if(results, results + P,
		::std::bind2nd(::std::not_equal_to<Iterator>(), last) );

	if (result != results + P)
		return *result;

	return last;
}

template<class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last,
                      Predicate pred, const unsigned P)
{
	return ::omptl::_find_if(first, last, pred, P,
	typename ::std::iterator_traits<InputIterator>::iterator_category());
}

// TODO
template <class ForwardIterator1, class ForwardIterator2,
          class BinaryPredicate>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
			  ForwardIterator2 first2, ForwardIterator2 last2,
			  BinaryPredicate comp, const unsigned P)
{
	return ::std::find_end(first1, last1, first2, last2, comp);
}

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
			  ForwardIterator2 first2, ForwardIterator2 last2,
			  const unsigned P)
{
	typedef typename ::std::iterator_traits<ForwardIterator1>::value_type VT;
// 	return ::omptl::find_end(first1, last1, first2, last2, ::std::less<VT>());
	return ::std::find_end(first1, last1, first2, last2);
}

template <class InputIterator, class ForwardIterator, class BinaryPredicate>
InputIterator _find_first_of(InputIterator first1, InputIterator last1,
			ForwardIterator first2, ForwardIterator last2,
			BinaryPredicate comp, const unsigned P,
			::std::input_iterator_tag)
{
	return ::std::find_first_of(first1, last1, first2, last2, comp);
}

// find_first_of suffers from a loss of efficiency, and potentially a loss of
// performance when executed in parallel!
/*
template <class Iterator, class ForwardIterator, class BinaryPredicate,
	  class IteratorTag>
Iterator _find_first_of(Iterator first1, Iterator last1,
			ForwardIterator first2, ForwardIterator last2,
			BinaryPredicate comp, const unsigned P,
	)
{
	if (_linear_serial_is_faster(first1, last2, P))
		return ::std::find_first_of(first1, last1,
					    first2, last2, comp);

	::std::pair<Iterator, Iterator> partitions[P];
	::omptl::_partition_range(first1, last2, partitions, P);

	Iterator results[P];
	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		::std::find_first_of(partitions[t].first, partitions[t].second,
					first2, last2, comp);

	Iterator *result = ::std::find_if(results, results + P,
		::std::bind2nd(::std::not_equal_to<Iterator>(), last1) );

	if (result != results + P)
		return *result;

	return last1;
}
*/

template <class InputIterator, class ForwardIterator, class BinaryPredicate>
InputIterator find_first_of(InputIterator first1, InputIterator last1,
			ForwardIterator first2, ForwardIterator last2,
			BinaryPredicate comp, const unsigned P)
{
// 	return ::omptl::find_first_of(first1, last1, first2, last2, comp,
// 	typename ::std::iterator_traits<InputIterator>::iterator_category() );

	return ::std::find_first_of(first1, last1, first2, last2, comp);
}

template <class InputIterator, class ForwardIterator>
InputIterator find_first_of(InputIterator first1, InputIterator last1,
			ForwardIterator first2, ForwardIterator last2,
			const unsigned P)
{
	typedef typename ::std::iterator_traits<InputIterator>::value_type VT;
	return ::omptl::find_first_of(first1, last1, first2, last2,
					::std::equal_to<VT>());
}

template <class InputIterator, class UnaryFunction>
UnaryFunction _for_each(InputIterator first, InputIterator last,
		   UnaryFunction f, const unsigned P, ::std::input_iterator_tag)
{
	return ::std::for_each(first, last, f);
}

template <class Iterator, class UnaryFunction, class IteratorTag>
UnaryFunction _for_each(Iterator first, Iterator last,
		       UnaryFunction f, const unsigned P, IteratorTag)
{
	if (_linear_serial_is_faster(first, last, P))
		return ::std::for_each(first, last, f);

	::std::pair<Iterator, Iterator> partitions[P];
	::omptl::_partition_range(first, last, partitions, P);

	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		::std::for_each(partitions[t].first, partitions[t].second, f);

	return f;
}

template <class InputIterator, class UnaryFunction>
UnaryFunction for_each(InputIterator first, InputIterator last,
		       UnaryFunction f, const unsigned P)
{
	return ::omptl::_for_each(first, last, f, P,
	typename ::std::iterator_traits<InputIterator>::iterator_category() );
}

template <class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last, Generator gen)
{
	::std::generate(first, last, gen);
}

template <class ForwardIterator, class Generator>
void par_generate(ForwardIterator first, ForwardIterator last,
		  Generator gen, const unsigned P)
{
	if (_linear_serial_is_faster(first, last, P))
	{
		::std::generate(first, last, gen);
		return;
	}

	::std::pair<ForwardIterator, ForwardIterator> partitions[P];
	::omptl::_partition_range(first, last, partitions, P);

	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		::std::generate(partitions[t].first, partitions[t].second, gen);
}

template <class RandomAccessIterator, class StrictWeakOrdering>
void push_heap(RandomAccessIterator first, RandomAccessIterator last,
               StrictWeakOrdering comp, const unsigned P)
{
	return ::std::push_heap(first, last, comp);
}

template <class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last,
               const unsigned P)
{
// 	::std::less<typename
// 	::std::iterator_traits<RandomAccessIterator>::value_type>(),
	return ::std::push_heap(first, last);
}

template <class RandomAccessIterator, class StrictWeakOrdering>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                     StrictWeakOrdering comp, const unsigned P)
{
	return ::std::pop_heap(first, last, comp);
}

template <class RandomAccessIterator>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                     const unsigned P)
{
// 	::std::less<typename
// 	::std::iterator_traits<RandomAccessIterator>::value_type>
	return ::std::pop_heap(first, last);
}

template <class RandomAccessIterator, class StrictWeakOrdering>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,
               StrictWeakOrdering comp, const unsigned P)
{
	return ::std::make_heap(first, last, comp);
}

template <class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,
               const unsigned P)
{
// 	::std::less<typename
// 		::std::iterator_traits<RandomAccessIterator>::value_type>(),
	return ::std::make_heap(first, last);
}

template <class RandomAccessIterator, class StrictWeakOrdering>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
               StrictWeakOrdering comp, const unsigned P)
{
	return ::std::sort_heap(first, last, comp);
}

template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
               const unsigned P)
{
// 	::std::less<typename
// 		::std::iterator_traits<RandomAccessIterator>::value_type>
	return ::std::sort_heap(first, last);
}

template <class InputIterator1, class InputIterator2, class StrictWeakOrdering,
	  class Iterator1Tag>
bool _includes(InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, InputIterator2 last2,
              StrictWeakOrdering comp, const unsigned P,
		Iterator1Tag, ::std::input_iterator_tag)
{
	return ::std::includes(first1, last1, first2, last2, comp);
}

template <class InputIterator1, class InputIterator2, class StrictWeakOrdering,
	  class Iterator2Tag>
bool _includes(InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, InputIterator2 last2,
              StrictWeakOrdering comp, const unsigned P,
		::std::input_iterator_tag, Iterator2Tag)
{
	return ::std::includes(first1, last1, first2, last2, comp);
}

/*
template <class Iterator1, class Iterator2, class StrictWeakOrdering,
	  class Iterator1Tag, class Iterator2Tag>
bool _includes(Iterator1 first1, Iterator1 last1,
              Iterator2 first2, Iterator2 last2,
              StrictWeakOrdering comp, const unsigned P,
		Iterator1Tag, Iterator2Tag)
{
	if (_linear_serial_is_faster(first2, last2, P))
		return ::std::includes(first1, last1, first2, last2, comp);

	::std::pair<Iterator2, Iterator2> partitions[P];
	::omptl::_partition_range(first2, last2, partitions, P);

	bool results[P];
	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		results[t] = ::std::includes(first1, last1,
						partitions[t].first,
						partitions[t].second, comp);

	return (::std::count(&results[0], results + P, true) == P);
}
*/

template <class InputIterator1, class InputIterator2, class StrictWeakOrdering>
bool includes(InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, InputIterator2 last2,
              StrictWeakOrdering comp, const unsigned P)
{
	return ::std::includes(first1, last1, first2, last2, comp);

// 	return ::omptl::_includes(first1, last1, first2, last2, comp,
// 	typename ::std::iterator_traits<InputIterator1>::iterator_category(),
// 	typename ::std::iterator_traits<InputIterator2>::iterator_category());
}

template <class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, InputIterator2 last2,
              const unsigned P)
{
	typedef typename ::std::iterator_traits<InputIterator1>::value_type VT;

	return ::omptl::includes(first1, last1, first2, last2, ::std::less<VT>());
}

template <class InputIterator1, class InputIterator2, class BinaryPredicate>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2,
                             BinaryPredicate comp, const unsigned P)
{
	return ::std::lexicographical_compare(first1, last1,
					      first2, last2, comp);
}

template <class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2,
                             const unsigned P)
{
// 	::std::less<typename
// 		::std::iterator_traits<InputIterator1>::value_type>
	return ::std::lexicographical_compare(first1, last1, first2, last2);
}

template <class ForwardIterator, class T, class StrictWeakOrdering>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
                            const T& value, StrictWeakOrdering comp,
			    const unsigned P)
{
	if (_logn_serial_is_faster(first, last, P))
		return ::std::lower_bound(first, last, value, comp);

	::std::pair<ForwardIterator, ForwardIterator> partitions[P];
	::omptl::_partition_range(first, last, partitions, P);

	ForwardIterator results[P];
	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		results[t] = ::std::lower_bound(partitions[t].first,
						partitions[t].second,
						value, comp);

	ForwardIterator *result = ::std::find_if(results, results + P,
		::std::bind2nd(::std::not_equal_to<ForwardIterator>(), last) );

	if (result != results + P)
		return *result;

	return last;
}

template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
                            const T& value, const unsigned P)
{
	return ::omptl::lower_bound(first, last, value, ::std::less<T>(), P);
}

// Not parallelized, dependencies between data.
template <class InputIterator1, class InputIterator2, class OutputIterator,
          class StrictWeakOrdering>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result,
		     StrictWeakOrdering comp, const unsigned P)
{
	return ::std::merge(first1, last1, first2, last2, result, comp);
}

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result, const unsigned P)
{
// 	::std::less<typename
// 		::std::iterator_traits<InputIterator1>::value_type>
	return ::std::merge(first1, last1, first2, last2, result);
}

template <class ForwardIterator, class BinaryPredicate>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
                            BinaryPredicate comp, const unsigned P)
{
	if (_linear_serial_is_faster(first, last, P))
		return ::std::min_element(first, last, comp);

	::std::pair<ForwardIterator, ForwardIterator> partitions[P];
	::omptl::_partition_range(first, last, partitions, P);

	ForwardIterator results[P];
	int t;
	#pragma omp parallel for // default(shared), private(t)
	for (t = 0; t < int(P); ++t)
		results[t] = ::std::min_element(partitions[t].first,
					 	partitions[t].second, comp);

	ForwardIterator result = results[0];
	for (unsigned int i = 1; i < P; ++i)
		if ( (result != last) && (results[i] != last) &&
		      comp(*results[i], *result) )
			result = results[i];

	return result;
}