[pstl] Iterator types renaming: ForwardIterator -> RandomAccessIterator; for parallel patterns/bricks
https://reviews.llvm.org/D96266
GitOrigin-RevId: 5856f202057cd375cd9599fe44cfa7e78239c625
diff --git a/include/pstl/internal/algorithm_fwd.h b/include/pstl/internal/algorithm_fwd.h
index d3986de..8d0a3de 100644
--- a/include/pstl/internal/algorithm_fwd.h
+++ b/include/pstl/internal/algorithm_fwd.h
@@ -32,9 +32,9 @@
__brick_any_of(const _ForwardIterator, const _ForwardIterator, _Pred,
/*__is_vector=*/std::false_type) noexcept;
-template <class _ForwardIterator, class _Pred>
+template <class _RandomAccessIterator, class _Pred>
bool
-__brick_any_of(const _ForwardIterator, const _ForwardIterator, _Pred,
+__brick_any_of(const _RandomAccessIterator, const _RandomAccessIterator, _Pred,
/*__is_vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator, class _Pred, class _IsVector>
@@ -42,9 +42,9 @@
__pattern_any_of(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Pred, _IsVector,
/*parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator, class _Pred, class _IsVector>
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Pred, class _IsVector>
bool
-__pattern_any_of(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Pred, _IsVector,
+__pattern_any_of(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Pred, _IsVector,
/*parallel=*/std::true_type);
//------------------------------------------------------------------------
@@ -66,9 +66,9 @@
__pattern_walk1(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Function, _IsVector,
/*parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator, class _Function, class _IsVector>
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Function, class _IsVector>
void
-__pattern_walk1(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Function, _IsVector,
+__pattern_walk1(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Function, _IsVector,
/*parallel=*/std::true_type);
template <class _ExecutionPolicy, class _ForwardIterator, class _Brick>
@@ -76,9 +76,9 @@
__pattern_walk_brick(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Brick,
/*parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator, class _Brick>
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Brick>
void
-__pattern_walk_brick(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Brick,
+__pattern_walk_brick(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Brick,
/*parallel=*/std::true_type);
//------------------------------------------------------------------------
@@ -123,26 +123,28 @@
_ForwardIterator2 __brick_walk2(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _Function,
/*vector=*/std::false_type) noexcept;
-template <class _ForwardIterator1, class _ForwardIterator2, class _Function>
-_ForwardIterator2 __brick_walk2(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _Function,
- /*vector=*/std::true_type) noexcept;
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Function>
+_RandomAccessIterator2 __brick_walk2(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, _Function,
+ /*vector=*/std::true_type) noexcept;
template <class _ForwardIterator1, class _Size, class _ForwardIterator2, class _Function>
_ForwardIterator2 __brick_walk2_n(_ForwardIterator1, _Size, _ForwardIterator2, _Function,
/*vector=*/std::false_type) noexcept;
-template <class _ForwardIterator1, class _Size, class _ForwardIterator2, class _Function>
-_ForwardIterator2 __brick_walk2_n(_ForwardIterator1, _Size, _ForwardIterator2, _Function,
- /*vector=*/std::true_type) noexcept;
+template <class _RandomAccessIterator1, class _Size, class _RandomAccessIterator2, class _Function>
+_RandomAccessIterator2 __brick_walk2_n(_RandomAccessIterator1, _Size, _RandomAccessIterator2, _Function,
+ /*vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Function, class _IsVector>
_ForwardIterator2
__pattern_walk2(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _Function, _IsVector,
/*parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Function, class _IsVector>
-_ForwardIterator2
-__pattern_walk2(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _Function, _IsVector,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _Function,
+ class _IsVector>
+_RandomAccessIterator2
+__pattern_walk2(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, _Function,
+ _IsVector,
/*parallel=*/std::true_type);
template <class _ExecutionPolicy, class _ForwardIterator1, class _Size, class _ForwardIterator2, class _Function,
@@ -267,9 +269,9 @@
__pattern_find_if(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Predicate, _IsVector,
/*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate, class _IsVector>
-_ForwardIterator
-__pattern_find_if(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Predicate, _IsVector,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Predicate, class _IsVector>
+_RandomAccessIterator
+__pattern_find_if(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Predicate, _IsVector,
/*is_parallel=*/std::true_type);
//------------------------------------------------------------------------
@@ -281,10 +283,10 @@
_BinaryPredicate,
/*__is_vector=*/std::false_type) noexcept;
-template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
-_ForwardIterator1 __brick_find_end(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
- _BinaryPredicate,
- /*__is_vector=*/std::true_type) noexcept;
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
+_RandomAccessIterator1 __brick_find_end(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _BinaryPredicate,
+ /*__is_vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate,
class _IsVector>
@@ -293,11 +295,11 @@
_BinaryPredicate, _IsVector,
/*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate,
class _IsVector>
-_ForwardIterator1
-__pattern_find_end(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
- _BinaryPredicate, _IsVector,
+_RandomAccessIterator1
+__pattern_find_end(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _BinaryPredicate, _IsVector,
/*is_parallel=*/std::true_type) noexcept;
//------------------------------------------------------------------------
@@ -309,10 +311,10 @@
_BinaryPredicate,
/*__is_vector=*/std::false_type) noexcept;
-template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
-_ForwardIterator1 __brick_find_first_of(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
- _BinaryPredicate,
- /*__is_vector=*/std::true_type) noexcept;
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
+_RandomAccessIterator1 __brick_find_first_of(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _BinaryPredicate,
+ /*__is_vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate,
class _IsVector>
@@ -320,11 +322,11 @@
__pattern_find_first_of(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
_BinaryPredicate, _IsVector, /*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate,
class _IsVector>
-_ForwardIterator1
-__pattern_find_first_of(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
- _BinaryPredicate, _IsVector, /*is_parallel=*/std::true_type) noexcept;
+_RandomAccessIterator1
+__pattern_find_first_of(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _BinaryPredicate, _IsVector, /*is_parallel=*/std::true_type) noexcept;
//------------------------------------------------------------------------
// search
@@ -335,10 +337,10 @@
_BinaryPredicate,
/*vector=*/std::false_type) noexcept;
-template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
-_ForwardIterator1 __brick_search(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
- _BinaryPredicate,
- /*vector=*/std::true_type) noexcept;
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
+_RandomAccessIterator1 __brick_search(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _BinaryPredicate,
+ /*vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate,
class _IsVector>
@@ -347,11 +349,11 @@
_BinaryPredicate, _IsVector,
/*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate,
class _IsVector>
-_ForwardIterator1
-__pattern_search(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
- _BinaryPredicate, _IsVector,
+_RandomAccessIterator1
+__pattern_search(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _BinaryPredicate, _IsVector,
/*is_parallel=*/std::true_type) noexcept;
//------------------------------------------------------------------------
@@ -363,9 +365,9 @@
__brick_search_n(_ForwardIterator, _ForwardIterator, _Size, const _Tp&, _BinaryPredicate,
/*vector=*/std::false_type) noexcept;
-template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
-_ForwardIterator
-__brick_search_n(_ForwardIterator, _ForwardIterator, _Size, const _Tp&, _BinaryPredicate,
+template <class _RandomAccessIterator, class _Size, class _Tp, class _BinaryPredicate>
+_RandomAccessIterator
+__brick_search_n(_RandomAccessIterator, _RandomAccessIterator, _Size, const _Tp&, _BinaryPredicate,
/*vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate,
@@ -390,8 +392,8 @@
_OutputIterator __brick_copy_n(_ForwardIterator, _Size, _OutputIterator,
/*vector=*/std::false_type) noexcept;
-template <class _ForwardIterator, class _Size, class _OutputIterator>
-_OutputIterator __brick_copy_n(_ForwardIterator, _Size, _OutputIterator,
+template <class _RandomAccessIterator, class _Size, class _OutputIterator>
+_OutputIterator __brick_copy_n(_RandomAccessIterator, _Size, _OutputIterator,
/*vector=*/std::true_type) noexcept;
//------------------------------------------------------------------------
@@ -426,9 +428,9 @@
__brick_swap_ranges(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
/*vector=*/std::false_type) noexcept;
-template <class _ForwardIterator, class _OutputIterator>
+template <class _RandomAccessIterator, class _OutputIterator>
_OutputIterator
-__brick_swap_ranges(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
+__brick_swap_ranges(_RandomAccessIterator __first, _RandomAccessIterator __last, _OutputIterator __result,
/*vector=*/std::true_type) noexcept;
//------------------------------------------------------------------------
@@ -439,8 +441,8 @@
_OutputIterator __brick_copy_if(_ForwardIterator, _ForwardIterator, _OutputIterator, _UnaryPredicate,
/*vector=*/std::false_type) noexcept;
-template <class _ForwardIterator, class _OutputIterator, class _UnaryPredicate>
-_OutputIterator __brick_copy_if(_ForwardIterator, _ForwardIterator, _OutputIterator, _UnaryPredicate,
+template <class _RandomAccessIterator, class _OutputIterator, class _UnaryPredicate>
+_OutputIterator __brick_copy_if(_RandomAccessIterator, _RandomAccessIterator, _OutputIterator, _UnaryPredicate,
/*vector=*/std::true_type) noexcept;
template <class _DifferenceType, class _ForwardIterator, class _UnaryPredicate>
@@ -457,9 +459,9 @@
__brick_copy_by_mask(_ForwardIterator, _ForwardIterator, _OutputIterator, bool*,
/*vector=*/std::false_type) noexcept;
-template <class _ForwardIterator, class _OutputIterator>
+template <class _RandomAccessIterator, class _OutputIterator>
void
-__brick_copy_by_mask(_ForwardIterator, _ForwardIterator, _OutputIterator, bool* __restrict,
+__brick_copy_by_mask(_RandomAccessIterator, _RandomAccessIterator, _OutputIterator, bool* __restrict,
/*vector=*/std::true_type) noexcept;
template <class _ForwardIterator, class _OutputIterator1, class _OutputIterator2>
@@ -487,9 +489,9 @@
// count
//------------------------------------------------------------------------
-template <class _ForwardIterator, class _Predicate>
-typename std::iterator_traits<_ForwardIterator>::difference_type
- __brick_count(_ForwardIterator, _ForwardIterator, _Predicate,
+template <class _RandomAccessIterator, class _Predicate>
+typename std::iterator_traits<_RandomAccessIterator>::difference_type
+ __brick_count(_RandomAccessIterator, _RandomAccessIterator, _Predicate,
/* is_vector = */ std::true_type) noexcept;
template <class _ForwardIterator, class _Predicate>
@@ -502,9 +504,9 @@
__pattern_count(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Predicate,
/* is_parallel */ std::false_type, _IsVector) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate, class _IsVector>
-typename std::iterator_traits<_ForwardIterator>::difference_type
-__pattern_count(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Predicate,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Predicate, class _IsVector>
+typename std::iterator_traits<_RandomAccessIterator>::difference_type
+__pattern_count(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Predicate,
/* is_parallel */ std::true_type, _IsVector);
//------------------------------------------------------------------------
@@ -515,18 +517,18 @@
_ForwardIterator __brick_unique(_ForwardIterator, _ForwardIterator, _BinaryPredicate,
/*is_vector=*/std::false_type) noexcept;
-template <class _ForwardIterator, class _BinaryPredicate>
-_ForwardIterator __brick_unique(_ForwardIterator, _ForwardIterator, _BinaryPredicate,
- /*is_vector=*/std::true_type) noexcept;
+template <class _RandomAccessIterator, class _BinaryPredicate>
+_RandomAccessIterator __brick_unique(_RandomAccessIterator, _RandomAccessIterator, _BinaryPredicate,
+ /*is_vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator, class _BinaryPredicate, class _IsVector>
_ForwardIterator
__pattern_unique(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _BinaryPredicate, _IsVector,
/*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator, class _BinaryPredicate, class _IsVector>
-_ForwardIterator
-__pattern_unique(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _BinaryPredicate, _IsVector,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _BinaryPredicate, class _IsVector>
+_RandomAccessIterator
+__pattern_unique(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _BinaryPredicate, _IsVector,
/*is_parallel=*/std::true_type) noexcept;
//------------------------------------------------------------------------
@@ -571,16 +573,16 @@
void __brick_reverse(_BidirectionalIterator, _BidirectionalIterator,
/*__is_vector=*/std::false_type) noexcept;
-template <class _BidirectionalIterator>
-void __brick_reverse(_BidirectionalIterator, _BidirectionalIterator,
+template <class _RandomAccessIterator>
+void __brick_reverse(_RandomAccessIterator, _RandomAccessIterator,
/*__is_vector=*/std::true_type) noexcept;
template <class _BidirectionalIterator>
void __brick_reverse(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator,
/*is_vector=*/std::false_type) noexcept;
-template <class _BidirectionalIterator>
-void __brick_reverse(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator,
+template <class _RandomAccessIterator>
+void __brick_reverse(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator,
/*is_vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _BidirectionalIterator, class _IsVector>
@@ -588,9 +590,9 @@
__pattern_reverse(_ExecutionPolicy&&, _BidirectionalIterator, _BidirectionalIterator, _IsVector,
/*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _BidirectionalIterator, class _IsVector>
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _IsVector>
void
-__pattern_reverse(_ExecutionPolicy&&, _BidirectionalIterator, _BidirectionalIterator, _IsVector,
+__pattern_reverse(_RandomAccessIterator&&, _RandomAccessIterator, _RandomAccessIterator, _IsVector,
/*is_parallel=*/std::true_type);
//------------------------------------------------------------------------
@@ -601,8 +603,8 @@
_OutputIterator __brick_reverse_copy(_BidirectionalIterator, _BidirectionalIterator, _OutputIterator,
/*is_vector=*/std::false_type) noexcept;
-template <class _BidirectionalIterator, class _OutputIterator>
-_OutputIterator __brick_reverse_copy(_BidirectionalIterator, _BidirectionalIterator, _OutputIterator,
+template <class _RandomAccessIterator, class _OutputIterator>
+_OutputIterator __brick_reverse_copy(_RandomAccessIterator, _RandomAccessIterator, _OutputIterator,
/*is_vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _BidirectionalIterator, class _OutputIterator, class _IsVector>
@@ -610,9 +612,9 @@
__pattern_reverse_copy(_ExecutionPolicy&&, _BidirectionalIterator, _BidirectionalIterator, _OutputIterator, _IsVector,
/*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _BidirectionalIterator, class _OutputIterator, class _IsVector>
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _OutputIterator, class _IsVector>
_OutputIterator
-__pattern_reverse_copy(_ExecutionPolicy&&, _BidirectionalIterator, _BidirectionalIterator, _OutputIterator, _IsVector,
+__pattern_reverse_copy(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _OutputIterator, _IsVector,
/*is_parallel=*/std::true_type);
//------------------------------------------------------------------------
@@ -623,18 +625,18 @@
_ForwardIterator __brick_rotate(_ForwardIterator, _ForwardIterator, _ForwardIterator,
/*is_vector=*/std::false_type) noexcept;
-template <class _ForwardIterator>
-_ForwardIterator __brick_rotate(_ForwardIterator, _ForwardIterator, _ForwardIterator,
- /*is_vector=*/std::true_type) noexcept;
+template <class _RandomAccessIterator>
+_RandomAccessIterator __brick_rotate(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator,
+ /*is_vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator, class _IsVector>
_ForwardIterator
__pattern_rotate(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _ForwardIterator, _IsVector,
/*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator, class _IsVector>
-_ForwardIterator
-__pattern_rotate(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _ForwardIterator, _IsVector,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _IsVector>
+_RandomAccessIterator
+__pattern_rotate(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _IsVector,
/*is_parallel=*/std::true_type);
//------------------------------------------------------------------------
@@ -645,8 +647,9 @@
_OutputIterator __brick_rotate_copy(_ForwardIterator, _ForwardIterator, _ForwardIterator, _OutputIterator,
/*__is_vector=*/std::false_type) noexcept;
-template <class _ForwardIterator, class _OutputIterator>
-_OutputIterator __brick_rotate_copy(_ForwardIterator, _ForwardIterator, _ForwardIterator, _OutputIterator,
+template <class _RandomAccessIterator, class _OutputIterator>
+_OutputIterator __brick_rotate_copy(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator,
+ _OutputIterator,
/*__is_vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator, class _OutputIterator, class _IsVector>
@@ -655,10 +658,10 @@
_IsVector,
/*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator, class _OutputIterator, class _IsVector>
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _OutputIterator, class _IsVector>
_OutputIterator
-__pattern_rotate_copy(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _ForwardIterator, _OutputIterator,
- _IsVector,
+__pattern_rotate_copy(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator,
+ _OutputIterator, _IsVector,
/*is_parallel=*/std::true_type);
//------------------------------------------------------------------------
@@ -669,8 +672,8 @@
bool __brick_is_partitioned(_ForwardIterator, _ForwardIterator, _UnaryPredicate,
/*is_vector=*/std::false_type) noexcept;
-template <class _ForwardIterator, class _UnaryPredicate>
-bool __brick_is_partitioned(_ForwardIterator, _ForwardIterator, _UnaryPredicate,
+template <class _RandomAccessIterator, class _UnaryPredicate>
+bool __brick_is_partitioned(_RandomAccessIterator, _RandomAccessIterator, _UnaryPredicate,
/*is_vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate, class _IsVector>
@@ -678,9 +681,9 @@
__pattern_is_partitioned(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _UnaryPredicate, _IsVector,
/*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate, class _IsVector>
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _UnaryPredicate, class _IsVector>
bool
-__pattern_is_partitioned(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _UnaryPredicate, _IsVector,
+__pattern_is_partitioned(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _UnaryPredicate, _IsVector,
/*is_parallel=*/std::true_type);
//------------------------------------------------------------------------
@@ -691,18 +694,18 @@
_ForwardIterator __brick_partition(_ForwardIterator, _ForwardIterator, _UnaryPredicate,
/*is_vector=*/std::false_type) noexcept;
-template <class _ForwardIterator, class _UnaryPredicate>
-_ForwardIterator __brick_partition(_ForwardIterator, _ForwardIterator, _UnaryPredicate,
- /*is_vector=*/std::true_type) noexcept;
+template <class _RandomAccessIterator, class _UnaryPredicate>
+_RandomAccessIterator __brick_partition(_RandomAccessIterator, _RandomAccessIterator, _UnaryPredicate,
+ /*is_vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate, class _IsVector>
_ForwardIterator
__pattern_partition(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _UnaryPredicate, _IsVector,
/*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate, class _IsVector>
-_ForwardIterator
-__pattern_partition(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _UnaryPredicate, _IsVector,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _UnaryPredicate, class _IsVector>
+_RandomAccessIterator
+__pattern_partition(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _UnaryPredicate, _IsVector,
/*is_parallel=*/std::true_type);
//------------------------------------------------------------------------
@@ -713,9 +716,9 @@
_BidirectionalIterator __brick_stable_partition(_BidirectionalIterator, _BidirectionalIterator, _UnaryPredicate,
/*__is_vector=*/std::false_type) noexcept;
-template <class _BidirectionalIterator, class _UnaryPredicate>
-_BidirectionalIterator __brick_stable_partition(_BidirectionalIterator, _BidirectionalIterator, _UnaryPredicate,
- /*__is_vector=*/std::true_type) noexcept;
+template <class _RandomAccessIterator, class _UnaryPredicate>
+_RandomAccessIterator __brick_stable_partition(_RandomAccessIterator, _RandomAccessIterator, _UnaryPredicate,
+ /*__is_vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _BidirectionalIterator, class _UnaryPredicate, class _IsVector>
_BidirectionalIterator
@@ -723,10 +726,9 @@
_IsVector,
/*is_parallelization=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _BidirectionalIterator, class _UnaryPredicate, class _IsVector>
-_BidirectionalIterator
-__pattern_stable_partition(_ExecutionPolicy&&, _BidirectionalIterator, _BidirectionalIterator, _UnaryPredicate,
- _IsVector,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _UnaryPredicate, class _IsVector>
+_RandomAccessIterator
+__pattern_stable_partition(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _UnaryPredicate, _IsVector,
/*is_parallelization=*/std::true_type) noexcept;
//------------------------------------------------------------------------
@@ -738,10 +740,11 @@
__brick_partition_copy(_ForwardIterator, _ForwardIterator, _OutputIterator1, _OutputIterator2, _UnaryPredicate,
/*is_vector=*/std::false_type) noexcept;
-template <class _ForwardIterator, class _OutputIterator1, class _OutputIterator2, class _UnaryPredicate>
-std::pair<_OutputIterator1, _OutputIterator2>
- __brick_partition_copy(_ForwardIterator, _ForwardIterator, _OutputIterator1, _OutputIterator2, _UnaryPredicate,
- /*is_vector=*/std::true_type) noexcept;
+template <class _RandomAccessIterator, class _OutputIterator1, class _OutputIterator2, class _UnaryPredicate>
+std::pair<_OutputIterator1, _OutputIterator2> __brick_partition_copy(_RandomAccessIterator, _RandomAccessIterator,
+ _OutputIterator1, _OutputIterator2,
+ _UnaryPredicate,
+ /*is_vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator, class _OutputIterator1, class _OutputIterator2,
class _UnaryPredicate, class _IsVector>
@@ -809,25 +812,27 @@
// partial_sort_copy
//------------------------------------------------------------------------
-template <class _ExecutionPolicy, class _ForwardIterator, class _RandomAccessIterator, class _Compare, class _IsVector>
-_RandomAccessIterator
-__pattern_partial_sort_copy(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _RandomAccessIterator,
- _RandomAccessIterator, _Compare, _IsVector,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _Compare,
+ class _IsVector>
+_RandomAccessIterator2
+__pattern_partial_sort_copy(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _Compare, _IsVector,
/*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator, class _RandomAccessIterator, class _Compare, class _IsVector>
-_RandomAccessIterator
-__pattern_partial_sort_copy(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _RandomAccessIterator,
- _RandomAccessIterator, _Compare, _IsVector,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _Compare,
+ class _IsVector>
+_RandomAccessIterator2
+__pattern_partial_sort_copy(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _Compare, _IsVector,
/*is_parallel=*/std::true_type);
//------------------------------------------------------------------------
// adjacent_find
//------------------------------------------------------------------------
-template <class _ForwardIterator, class _BinaryPredicate>
-_ForwardIterator
-__brick_adjacent_find(_ForwardIterator, _ForwardIterator, _BinaryPredicate,
+template <class _RandomAccessIterator, class _BinaryPredicate>
+_RandomAccessIterator
+__brick_adjacent_find(_RandomAccessIterator, _RandomAccessIterator, _BinaryPredicate,
/* IsVector = */ std::true_type, bool) noexcept;
template <class _ForwardIterator, class _BinaryPredicate>
@@ -863,9 +868,9 @@
//------------------------------------------------------------------------
// fill, fill_n
//------------------------------------------------------------------------
-template <class _ForwardIterator, class _Tp>
+template <class _RandomAccessIterator, class _Tp>
void
-__brick_fill(_ForwardIterator, _ForwardIterator, const _Tp&,
+__brick_fill(_RandomAccessIterator, _RandomAccessIterator, const _Tp&,
/* __is_vector = */ std::true_type) noexcept;
template <class _ForwardIterator, class _Tp>
@@ -878,14 +883,14 @@
__pattern_fill(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, const _Tp&,
/*is_parallel=*/std::false_type, _IsVector) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _IsVector>
-_ForwardIterator
-__pattern_fill(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, const _Tp&,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Tp, class _IsVector>
+_RandomAccessIterator
+__pattern_fill(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, const _Tp&,
/*is_parallel=*/std::true_type, _IsVector);
-template <class _OutputIterator, class _Size, class _Tp>
-_OutputIterator
-__brick_fill_n(_OutputIterator, _Size, const _Tp&,
+template <class _RandomAccessIterator, class _Size, class _Tp>
+_RandomAccessIterator
+__brick_fill_n(_RandomAccessIterator, _Size, const _Tp&,
/* __is_vector = */ std::true_type) noexcept;
template <class _OutputIterator, class _Size, class _Tp>
@@ -898,9 +903,9 @@
__pattern_fill_n(_ExecutionPolicy&&, _OutputIterator, _Size, const _Tp&,
/*is_parallel=*/std::false_type, _IsVector) noexcept;
-template <class _ExecutionPolicy, class _OutputIterator, class _Size, class _Tp, class _IsVector>
-_OutputIterator
-__pattern_fill_n(_ExecutionPolicy&&, _OutputIterator, _Size, const _Tp&,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Size, class _Tp, class _IsVector>
+_RandomAccessIterator
+__pattern_fill_n(_ExecutionPolicy&&, _RandomAccessIterator, _Size, const _Tp&,
/*is_parallel=*/std::true_type, _IsVector);
//------------------------------------------------------------------------
@@ -920,14 +925,14 @@
__pattern_generate(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Generator,
/*is_parallel=*/std::false_type, _IsVector) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator, class _Generator, class _IsVector>
-_ForwardIterator
-__pattern_generate(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Generator,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Generator, class _IsVector>
+_RandomAccessIterator
+__pattern_generate(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Generator,
/*is_parallel=*/std::true_type, _IsVector);
-template <class OutputIterator, class Size, class _Generator>
-OutputIterator __brick_generate_n(OutputIterator, Size, _Generator,
- /* is_vector = */ std::true_type) noexcept;
+template <class _RandomAccessIterator, class Size, class _Generator>
+_RandomAccessIterator __brick_generate_n(_RandomAccessIterator, Size, _Generator,
+ /* is_vector = */ std::true_type) noexcept;
template <class OutputIterator, class Size, class _Generator>
OutputIterator __brick_generate_n(OutputIterator, Size, _Generator,
@@ -938,9 +943,9 @@
__pattern_generate_n(_ExecutionPolicy&&, OutputIterator, Size, _Generator,
/*is_parallel=*/std::false_type, _IsVector) noexcept;
-template <class _ExecutionPolicy, class OutputIterator, class Size, class _Generator, class _IsVector>
-OutputIterator
-__pattern_generate_n(_ExecutionPolicy&&, OutputIterator, Size, _Generator,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class Size, class _Generator, class _IsVector>
+_RandomAccessIterator
+__pattern_generate_n(_ExecutionPolicy&&, _RandomAccessIterator, Size, _Generator,
/*is_parallel=*/std::true_type, _IsVector);
//------------------------------------------------------------------------
@@ -959,9 +964,9 @@
__pattern_remove_if(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _UnaryPredicate, _IsVector,
/*is_parallel*/ std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate, class _IsVector>
-_ForwardIterator
-__pattern_remove_if(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _UnaryPredicate, _IsVector,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _UnaryPredicate, class _IsVector>
+_RandomAccessIterator
+__pattern_remove_if(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _UnaryPredicate, _IsVector,
/*is_parallel*/ std::true_type) noexcept;
//------------------------------------------------------------------------
@@ -973,9 +978,9 @@
_OutputIterator, _Compare,
/* __is_vector = */ std::false_type) noexcept;
-template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare>
-_OutputIterator __brick_merge(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
- _OutputIterator, _Compare,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _OutputIterator, class _Compare>
+_OutputIterator __brick_merge(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _OutputIterator, _Compare,
/* __is_vector = */ std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator,
@@ -999,8 +1004,8 @@
void __brick_inplace_merge(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, _Compare,
/* __is_vector = */ std::false_type) noexcept;
-template <class _BidirectionalIterator, class _Compare>
-void __brick_inplace_merge(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, _Compare,
+template <class _RandomAccessIterator, class _Compare>
+void __brick_inplace_merge(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare,
/* __is_vector = */ std::true_type) noexcept;
template <class _ExecutionPolicy, class _BidirectionalIterator, class _Compare, class _IsVector>
@@ -1009,9 +1014,9 @@
_Compare, _IsVector,
/* is_parallel = */ std::false_type) noexcept;
-template <class _ExecutionPolicy, class _BidirectionalIterator, class _Compare, class _IsVector>
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Compare, class _IsVector>
void
-__pattern_inplace_merge(_ExecutionPolicy&&, _BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator,
+__pattern_inplace_merge(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator,
_Compare, _IsVector,
/*is_parallel=*/std::true_type);
@@ -1025,10 +1030,11 @@
_Compare, _IsVector,
/*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Compare, class _IsVector>
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _Compare,
+ class _IsVector>
bool
-__pattern_includes(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
- _Compare, _IsVector,
+__pattern_includes(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _Compare, _IsVector,
/*is_parallel=*/std::true_type);
//------------------------------------------------------------------------
@@ -1040,9 +1046,9 @@
_OutputIterator, _Compare,
/*__is_vector=*/std::false_type) noexcept;
-template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare>
-_OutputIterator __brick_set_union(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
- _OutputIterator, _Compare,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _OutputIterator, class _Compare>
+_OutputIterator __brick_set_union(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _OutputIterator, _Compare,
/*__is_vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator,
@@ -1051,11 +1057,11 @@
__pattern_set_union(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
_OutputIterator, _Compare, _IsVector, /*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _OutputIterator,
class _Compare, class _IsVector>
_OutputIterator
-__pattern_set_union(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
- _OutputIterator, _Compare, _IsVector, /*is_parallel=*/std::true_type);
+__pattern_set_union(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _OutputIterator, _Compare, _IsVector, /*is_parallel=*/std::true_type);
//------------------------------------------------------------------------
// set_intersection
@@ -1066,9 +1072,9 @@
_OutputIterator, _Compare,
/*__is_vector=*/std::false_type) noexcept;
-template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare>
-_OutputIterator __brick_set_intersection(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
- _OutputIterator, _Compare,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _OutputIterator, class _Compare>
+_OutputIterator __brick_set_intersection(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _OutputIterator, _Compare,
/*__is_vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator,
@@ -1078,11 +1084,12 @@
_ForwardIterator2, _OutputIterator, _Compare, _IsVector,
/*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _OutputIterator,
class _Compare, class _IsVector>
_OutputIterator
-__pattern_set_intersection(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2,
- _ForwardIterator2, _OutputIterator, _Compare, _IsVector, /*is_parallel=*/std::true_type);
+__pattern_set_intersection(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _OutputIterator, _Compare, _IsVector,
+ /*is_parallel=*/std::true_type);
//------------------------------------------------------------------------
// set_difference
@@ -1093,9 +1100,9 @@
_OutputIterator, _Compare,
/*__is_vector=*/std::false_type) noexcept;
-template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare>
-_OutputIterator __brick_set_difference(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
- _OutputIterator, _Compare,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _OutputIterator, class _Compare>
+_OutputIterator __brick_set_difference(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _OutputIterator, _Compare,
/*__is_vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator,
@@ -1104,11 +1111,11 @@
__pattern_set_difference(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
_OutputIterator, _Compare, _IsVector, /*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _OutputIterator,
class _Compare, class _IsVector>
_OutputIterator
-__pattern_set_difference(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
- _OutputIterator, _Compare, _IsVector, /*is_parallel=*/std::true_type);
+__pattern_set_difference(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _OutputIterator, _Compare, _IsVector, /*is_parallel=*/std::true_type);
//------------------------------------------------------------------------
// set_symmetric_difference
@@ -1119,9 +1126,9 @@
_ForwardIterator2, _OutputIterator, _Compare,
/*__is_vector=*/std::false_type) noexcept;
-template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare>
-_OutputIterator __brick_set_symmetric_difference(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2,
- _ForwardIterator2, _OutputIterator, _Compare,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _OutputIterator, class _Compare>
+_OutputIterator __brick_set_symmetric_difference(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _OutputIterator, _Compare,
/*__is_vector=*/std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator,
@@ -1131,11 +1138,11 @@
_ForwardIterator2, _OutputIterator, _Compare, _IsVector,
/*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _OutputIterator,
class _Compare, class _IsVector>
_OutputIterator
-__pattern_set_symmetric_difference(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2,
- _ForwardIterator2, _OutputIterator, _Compare, _IsVector,
+__pattern_set_symmetric_difference(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1,
+ _RandomAccessIterator2, _RandomAccessIterator2, _OutputIterator, _Compare, _IsVector,
/*is_parallel=*/std::true_type);
//------------------------------------------------------------------------
@@ -1168,9 +1175,9 @@
_ForwardIterator __brick_min_element(_ForwardIterator, _ForwardIterator, _Compare,
/* __is_vector = */ std::false_type) noexcept;
-template <typename _ForwardIterator, typename _Compare>
-_ForwardIterator __brick_min_element(_ForwardIterator, _ForwardIterator, _Compare,
- /* __is_vector = */ std::true_type) noexcept;
+template <typename _RandomAccessIterator, typename _Compare>
+_RandomAccessIterator __brick_min_element(_RandomAccessIterator, _RandomAccessIterator, _Compare,
+ /* __is_vector = */ std::true_type) noexcept;
template <typename _ExecutionPolicy, typename _ForwardIterator, typename _Compare, typename _IsVector>
_ForwardIterator
@@ -1190,18 +1197,19 @@
std::pair<_ForwardIterator, _ForwardIterator> __brick_minmax_element(_ForwardIterator, _ForwardIterator, _Compare,
/* __is_vector = */ std::false_type) noexcept;
-template <typename _ForwardIterator, typename _Compare>
-std::pair<_ForwardIterator, _ForwardIterator> __brick_minmax_element(_ForwardIterator, _ForwardIterator, _Compare,
- /* __is_vector = */ std::true_type) noexcept;
+template <typename _RandomAccessIterator, typename _Compare>
+std::pair<_RandomAccessIterator, _RandomAccessIterator>
+ __brick_minmax_element(_RandomAccessIterator, _RandomAccessIterator, _Compare,
+ /* __is_vector = */ std::true_type) noexcept;
template <typename _ExecutionPolicy, typename _ForwardIterator, typename _Compare, typename _IsVector>
std::pair<_ForwardIterator, _ForwardIterator>
__pattern_minmax_element(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Compare, _IsVector,
/* is_parallel = */ std::false_type) noexcept;
-template <typename _ExecutionPolicy, typename _ForwardIterator, typename _Compare, typename _IsVector>
-std::pair<_ForwardIterator, _ForwardIterator>
-__pattern_minmax_element(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Compare, _IsVector,
+template <typename _ExecutionPolicy, typename _RandomAccessIterator, typename _Compare, typename _IsVector>
+std::pair<_RandomAccessIterator, _RandomAccessIterator>
+__pattern_minmax_element(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Compare, _IsVector,
/* is_parallel = */ std::true_type);
//------------------------------------------------------------------------
@@ -1213,10 +1221,11 @@
_ForwardIterator2, _ForwardIterator2, _Predicate,
/* __is_vector = */ std::false_type) noexcept;
-template <class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
-std::pair<_ForwardIterator1, _ForwardIterator2> __brick_mismatch(_ForwardIterator1, _ForwardIterator1,
- _ForwardIterator2, _ForwardIterator2, _Predicate,
- /* __is_vector = */ std::true_type) noexcept;
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Predicate>
+std::pair<_RandomAccessIterator1, _RandomAccessIterator2>
+ __brick_mismatch(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, _RandomAccessIterator2,
+ _Predicate,
+ /* __is_vector = */ std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate, class _IsVector>
std::pair<_ForwardIterator1, _ForwardIterator2>
@@ -1239,9 +1248,9 @@
_Compare,
/* __is_vector = */ std::false_type) noexcept;
-template <class _ForwardIterator1, class _ForwardIterator2, class _Compare>
-bool __brick_lexicographical_compare(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2,
- _Compare,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Compare>
+bool __brick_lexicographical_compare(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2,
+ _RandomAccessIterator2, _Compare,
/* __is_vector = */ std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Compare, class _IsVector>
@@ -1249,10 +1258,12 @@
__pattern_lexicographical_compare(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2,
_ForwardIterator2, _Compare, _IsVector, /* is_parallel = */ std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Compare, class _IsVector>
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _Compare,
+ class _IsVector>
bool
-__pattern_lexicographical_compare(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2,
- _ForwardIterator2, _Compare, _IsVector, /* is_parallel = */ std::true_type) noexcept;
+__pattern_lexicographical_compare(_ExecutionPolicy&&, _RandomAccessIterator1, _RandomAccessIterator1,
+ _RandomAccessIterator2, _RandomAccessIterator2, _Compare, _IsVector,
+ /* is_parallel = */ std::true_type) noexcept;
} // namespace __internal
} // namespace __pstl
diff --git a/include/pstl/internal/algorithm_impl.h b/include/pstl/internal/algorithm_impl.h
index 46f4224..d5d9a31 100644
--- a/include/pstl/internal/algorithm_impl.h
+++ b/include/pstl/internal/algorithm_impl.h
@@ -43,9 +43,9 @@
return std::any_of(__first, __last, __pred);
};
-template <class _ForwardIterator, class _Pred>
+template <class _RandomAccessIterator, class _Pred>
bool
-__brick_any_of(const _ForwardIterator __first, const _ForwardIterator __last, _Pred __pred,
+__brick_any_of(const _RandomAccessIterator __first, const _RandomAccessIterator __last, _Pred __pred,
/*__is_vector=*/std::true_type) noexcept
{
return __unseq_backend::__simd_or(__first, __last - __first, __pred);
@@ -59,14 +59,14 @@
return __internal::__brick_any_of(__first, __last, __pred, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator, class _Pred, class _IsVector>
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Pred, class _IsVector>
bool
-__pattern_any_of(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred,
+__pattern_any_of(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _Pred __pred,
_IsVector __is_vector, /*parallel=*/std::true_type)
{
return __internal::__except_handler([&]() {
return __internal::__parallel_or(std::forward<_ExecutionPolicy>(__exec), __first, __last,
- [__pred, __is_vector](_ForwardIterator __i, _ForwardIterator __j) {
+ [__pred, __is_vector](_RandomAccessIterator __i, _RandomAccessIterator __j) {
return __internal::__brick_any_of(__i, __j, __pred, __is_vector);
});
});
@@ -113,15 +113,15 @@
__internal::__brick_walk1(__first, __last, __f, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator, class _Function, class _IsVector>
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Function, class _IsVector>
void
-__pattern_walk1(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Function __f,
+__pattern_walk1(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _Function __f,
_IsVector __is_vector,
/*parallel=*/std::true_type)
{
__internal::__except_handler([&]() {
__par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last,
- [__f, __is_vector](_ForwardIterator __i, _ForwardIterator __j) {
+ [__f, __is_vector](_RandomAccessIterator __i, _RandomAccessIterator __j) {
__internal::__brick_walk1(__i, __j, __f, __is_vector);
});
});
@@ -135,14 +135,16 @@
__brick(__first, __last);
}
-template <class _ExecutionPolicy, class _ForwardIterator, class _Brick>
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Brick>
void
-__pattern_walk_brick(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Brick __brick,
+__pattern_walk_brick(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
+ _Brick __brick,
/*parallel=*/std::true_type)
{
__internal::__except_handler([&]() {
- __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last,
- [__brick](_ForwardIterator __i, _ForwardIterator __j) { __brick(__i, __j); });
+ __par_backend::__parallel_for(
+ std::forward<_ExecutionPolicy>(__exec), __first, __last,
+ [__brick](_RandomAccessIterator __i, _RandomAccessIterator __j) { __brick(__i, __j); });
});
}
@@ -220,9 +222,10 @@
return __first2;
}
-template <class _ForwardIterator1, class _ForwardIterator2, class _Function>
-_ForwardIterator2
-__brick_walk2(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _Function __f,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Function>
+_RandomAccessIterator2
+__brick_walk2(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
+ _Function __f,
/*vector=*/std::true_type) noexcept
{
return __unseq_backend::__simd_walk_2(__first1, __last1 - __first1, __first2, __f);
@@ -238,9 +241,9 @@
return __first2;
}
-template <class _ForwardIterator1, class _Size, class _ForwardIterator2, class _Function>
-_ForwardIterator2
-__brick_walk2_n(_ForwardIterator1 __first1, _Size __n, _ForwardIterator2 __first2, _Function __f,
+template <class _RandomAccessIterator1, class _Size, class _RandomAccessIterator2, class _Function>
+_RandomAccessIterator2
+__brick_walk2_n(_RandomAccessIterator1 __first1, _Size __n, _RandomAccessIterator2 __first2, _Function __f,
/*vector=*/std::true_type) noexcept
{
return __unseq_backend::__simd_walk_2(__first1, __n, __first2, __f);
@@ -254,15 +257,16 @@
return __internal::__brick_walk2(__first1, __last1, __first2, __f, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Function, class _IsVector>
-_ForwardIterator2
-__pattern_walk2(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
- _ForwardIterator2 __first2, _Function __f, _IsVector __is_vector, /*parallel=*/std::true_type)
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _Function,
+ class _IsVector>
+_RandomAccessIterator2
+__pattern_walk2(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
+ _RandomAccessIterator2 __first2, _Function __f, _IsVector __is_vector, /*parallel=*/std::true_type)
{
return __internal::__except_handler([&]() {
__par_backend::__parallel_for(
std::forward<_ExecutionPolicy>(__exec), __first1, __last1,
- [__f, __first1, __first2, __is_vector](_ForwardIterator1 __i, _ForwardIterator1 __j) {
+ [__f, __first1, __first2, __is_vector](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) {
__internal::__brick_walk2(__i, __j, __first2 + (__i - __first1), __f, __is_vector);
});
return __first2 + (__last1 - __first1);
@@ -281,8 +285,8 @@
template <class _ExecutionPolicy, class _RandomAccessIterator1, class _Size, class _RandomAccessIterator2,
class _Function, class _IsVector>
_RandomAccessIterator2
-__pattern_walk2_n(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _Size __n, _RandomAccessIterator2 __first2,
- _Function __f, _IsVector is_vector, /*parallel=*/std::true_type)
+__pattern_walk2_n(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _Size __n,
+ _RandomAccessIterator2 __first2, _Function __f, _IsVector is_vector, /*parallel=*/std::true_type)
{
return __internal::__pattern_walk2(std::forward<_ExecutionPolicy>(__exec), __first1, __first1 + __n, __first2, __f,
is_vector, std::true_type());
@@ -513,19 +517,19 @@
return __internal::__brick_find_if(__first, __last, __pred, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate, class _IsVector>
-_ForwardIterator
-__pattern_find_if(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
- _IsVector __is_vector,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Predicate, class _IsVector>
+_RandomAccessIterator
+__pattern_find_if(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
+ _Predicate __pred, _IsVector __is_vector,
/*is_parallel=*/std::true_type)
{
return __internal::__except_handler([&]() {
return __internal::__parallel_find(
std::forward<_ExecutionPolicy>(__exec), __first, __last,
- [__pred, __is_vector](_ForwardIterator __i, _ForwardIterator __j) {
+ [__pred, __is_vector](_RandomAccessIterator __i, _RandomAccessIterator __j) {
return __internal::__brick_find_if(__i, __j, __pred, __is_vector);
},
- std::less<typename std::iterator_traits<_ForwardIterator>::difference_type>(),
+ std::less<typename std::iterator_traits<_RandomAccessIterator>::difference_type>(),
/*is_first=*/true);
});
}
@@ -634,10 +638,10 @@
return std::find_end(__first, __last, __s_first, __s_last, __pred);
}
-template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
-_ForwardIterator1
-__brick_find_end(_ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first,
- _ForwardIterator2 __s_last, _BinaryPredicate __pred, /*__is_vector=*/std::true_type) noexcept
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
+_RandomAccessIterator1
+__brick_find_end(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __s_first,
+ _RandomAccessIterator2 __s_last, _BinaryPredicate __pred, /*__is_vector=*/std::true_type) noexcept
{
return __find_subrange(__first, __last, __last, __s_first, __s_last, __pred, false, std::true_type());
}
@@ -652,11 +656,11 @@
return __internal::__brick_find_end(__first, __last, __s_first, __s_last, __pred, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate,
class _IsVector>
-_ForwardIterator1
-__pattern_find_end(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
- _ForwardIterator2 __s_first, _ForwardIterator2 __s_last, _BinaryPredicate __pred,
+_RandomAccessIterator1
+__pattern_find_end(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last,
+ _RandomAccessIterator2 __s_first, _RandomAccessIterator2 __s_last, _BinaryPredicate __pred,
_IsVector __is_vector, /*is_parallel=*/std::true_type) noexcept
{
if (__last - __first == __s_last - __s_first)
@@ -670,11 +674,13 @@
return __internal::__except_handler([&]() {
return __internal::__parallel_find(
std::forward<_ExecutionPolicy>(__exec), __first, __last,
- [__last, __s_first, __s_last, __pred, __is_vector](_ForwardIterator1 __i, _ForwardIterator1 __j) {
+ [__last, __s_first, __s_last, __pred, __is_vector](_RandomAccessIterator1 __i,
+ _RandomAccessIterator1 __j) {
return __internal::__find_subrange(__i, __j, __last, __s_first, __s_last, __pred, false,
__is_vector);
},
- std::greater<typename std::iterator_traits<_ForwardIterator1>::difference_type>(), /*is_first=*/false);
+ std::greater<typename std::iterator_traits<_RandomAccessIterator1>::difference_type>(),
+ /*is_first=*/false);
});
}
}
@@ -690,10 +696,10 @@
return std::find_first_of(__first, __last, __s_first, __s_last, __pred);
}
-template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
-_ForwardIterator1
-__brick_find_first_of(_ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first,
- _ForwardIterator2 __s_last, _BinaryPredicate __pred, /*__is_vector=*/std::true_type) noexcept
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
+_RandomAccessIterator1
+__brick_find_first_of(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __s_first,
+ _RandomAccessIterator2 __s_last, _BinaryPredicate __pred, /*__is_vector=*/std::true_type) noexcept
{
return __unseq_backend::__simd_find_first_of(__first, __last, __s_first, __s_last, __pred);
}
@@ -708,38 +714,38 @@
return __internal::__brick_find_first_of(__first, __last, __s_first, __s_last, __pred, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate,
class _IsVector>
-_ForwardIterator1
-__pattern_find_first_of(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
- _ForwardIterator2 __s_first, _ForwardIterator2 __s_last, _BinaryPredicate __pred,
+_RandomAccessIterator1
+__pattern_find_first_of(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last,
+ _RandomAccessIterator2 __s_first, _RandomAccessIterator2 __s_last, _BinaryPredicate __pred,
_IsVector __is_vector, /*is_parallel=*/std::true_type) noexcept
{
return __internal::__except_handler([&]() {
return __internal::__parallel_find(
std::forward<_ExecutionPolicy>(__exec), __first, __last,
- [__s_first, __s_last, __pred, __is_vector](_ForwardIterator1 __i, _ForwardIterator1 __j) {
+ [__s_first, __s_last, __pred, __is_vector](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) {
return __internal::__brick_find_first_of(__i, __j, __s_first, __s_last, __pred, __is_vector);
},
- std::less<typename std::iterator_traits<_ForwardIterator1>::difference_type>(), /*is_first=*/true);
+ std::less<typename std::iterator_traits<_RandomAccessIterator1>::difference_type>(), /*is_first=*/true);
});
}
//------------------------------------------------------------------------
// search
//------------------------------------------------------------------------
-template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
-_ForwardIterator1
-__brick_search(_ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first,
- _ForwardIterator2 __s_last, _BinaryPredicate __pred, /*vector=*/std::false_type) noexcept
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
+_RandomAccessIterator1
+__brick_search(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __s_first,
+ _RandomAccessIterator2 __s_last, _BinaryPredicate __pred, /*vector=*/std::false_type) noexcept
{
return std::search(__first, __last, __s_first, __s_last, __pred);
}
-template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
-_ForwardIterator1
-__brick_search(_ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first,
- _ForwardIterator2 __s_last, _BinaryPredicate __pred, /*vector=*/std::true_type) noexcept
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
+_RandomAccessIterator1
+__brick_search(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __s_first,
+ _RandomAccessIterator2 __s_last, _BinaryPredicate __pred, /*vector=*/std::true_type) noexcept
{
return __internal::__find_subrange(__first, __last, __last, __s_first, __s_last, __pred, true, std::true_type());
}
@@ -754,11 +760,11 @@
return __internal::__brick_search(__first, __last, __s_first, __s_last, __pred, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate,
class _IsVector>
-_ForwardIterator1
-__pattern_search(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
- _ForwardIterator2 __s_first, _ForwardIterator2 __s_last, _BinaryPredicate __pred,
+_RandomAccessIterator1
+__pattern_search(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last,
+ _RandomAccessIterator2 __s_first, _RandomAccessIterator2 __s_last, _BinaryPredicate __pred,
_IsVector __is_vector,
/*is_parallel=*/std::true_type) noexcept
{
@@ -773,11 +779,12 @@
return __internal::__except_handler([&]() {
return __internal::__parallel_find(
std::forward<_ExecutionPolicy>(__exec), __first, __last,
- [__last, __s_first, __s_last, __pred, __is_vector](_ForwardIterator1 __i, _ForwardIterator1 __j) {
+ [__last, __s_first, __s_last, __pred, __is_vector](_RandomAccessIterator1 __i,
+ _RandomAccessIterator1 __j) {
return __internal::__find_subrange(__i, __j, __last, __s_first, __s_last, __pred, true,
__is_vector);
},
- std::less<typename std::iterator_traits<_ForwardIterator1>::difference_type>(), /*is_first=*/true);
+ std::less<typename std::iterator_traits<_RandomAccessIterator1>::difference_type>(), /*is_first=*/true);
});
}
}
@@ -793,9 +800,9 @@
return std::search_n(__first, __last, __count, __value, __pred);
}
-template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
-_ForwardIterator
-__brick_search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value,
+template <class _RandomAccessIterator, class _Size, class _Tp, class _BinaryPredicate>
+_RandomAccessIterator
+__brick_search_n(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __count, const _Tp& __value,
_BinaryPredicate __pred, /*vector=*/std::true_type) noexcept
{
return __internal::__find_subrange(__first, __last, __last, __count, __value, __pred, std::true_type());
@@ -850,12 +857,14 @@
return std::copy_n(__first, __n, __result);
}
-template <class _ForwardIterator, class _Size, class _OutputIterator>
-_OutputIterator
-__brick_copy_n(_ForwardIterator __first, _Size __n, _OutputIterator __result, /*vector=*/std::true_type) noexcept
+template <class _RandomAccessIterator1, class _Size, class _RandomAccessIterator2>
+_RandomAccessIterator2
+__brick_copy_n(_RandomAccessIterator1 __first, _Size __n, _RandomAccessIterator2 __result,
+ /*vector=*/std::true_type) noexcept
{
return __unseq_backend::__simd_assign(
- __first, __n, __result, [](_ForwardIterator __first, _OutputIterator __result) { *__result = *__first; });
+ __first, __n, __result,
+ [](_RandomAccessIterator1 __first, _RandomAccessIterator2 __result) { *__result = *__first; });
}
//------------------------------------------------------------------------
@@ -869,14 +878,14 @@
return std::copy(__first, __last, __result);
}
-template <class _RandomAccessIterator, class _OutputIterator>
-_OutputIterator
-__brick_copy(_RandomAccessIterator __first, _RandomAccessIterator __last, _OutputIterator __result,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2>
+_RandomAccessIterator2
+__brick_copy(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __result,
/*vector=*/std::true_type) noexcept
{
return __unseq_backend::__simd_assign(
__first, __last - __first, __result,
- [](_RandomAccessIterator __first, _OutputIterator __result) { *__result = *__first; });
+ [](_RandomAccessIterator1 __first, _RandomAccessIterator2 __result) { *__result = *__first; });
}
//------------------------------------------------------------------------
@@ -890,36 +899,38 @@
return std::move(__first, __last, __result);
}
-template <class _RandomAccessIterator, class _OutputIterator>
-_OutputIterator
-__brick_move(_RandomAccessIterator __first, _RandomAccessIterator __last, _OutputIterator __result,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2>
+_RandomAccessIterator2
+__brick_move(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __result,
/*vector=*/std::true_type) noexcept
{
return __unseq_backend::__simd_assign(
__first, __last - __first, __result,
- [](_RandomAccessIterator __first, _OutputIterator __result) { *__result = std::move(*__first); });
+ [](_RandomAccessIterator1 __first, _RandomAccessIterator2 __result) { *__result = std::move(*__first); });
}
struct __brick_move_destroy
{
- template <typename _Iterator, typename _OutputIterator>
- _OutputIterator
- operator()(_Iterator __first, _Iterator __last, _OutputIterator __result, /*vec*/ std::true_type) const
+ template <typename _RandomAccessIterator1, typename _RandomAccessIterator2>
+ _RandomAccessIterator2
+ operator()(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __result,
+ /*vec*/ std::true_type) const
{
- using _IteratorValueType = typename std::iterator_traits<_Iterator>::value_type;
+ using _IteratorValueType = typename std::iterator_traits<_RandomAccessIterator1>::value_type;
return __unseq_backend::__simd_assign(__first, __last - __first, __result,
- [](_Iterator __first, _OutputIterator __result) {
+ [](_RandomAccessIterator1 __first, _RandomAccessIterator2 __result) {
*__result = std::move(*__first);
(*__first).~_IteratorValueType();
});
}
- template <typename _Iterator, typename _OutputIterator>
- _OutputIterator
- operator()(_Iterator __first, _Iterator __last, _OutputIterator __result, /*vec*/ std::false_type) const
+ template <typename _RandomAccessIterator1, typename _RandomAccessIterator2>
+ _RandomAccessIterator2
+ operator()(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __result,
+ /*vec*/ std::false_type) const
{
- using _IteratorValueType = typename std::iterator_traits<_Iterator>::value_type;
+ using _IteratorValueType = typename std::iterator_traits<_RandomAccessIterator1>::value_type;
for (; __first != __last; ++__first, ++__result)
{
@@ -941,14 +952,14 @@
return std::swap_ranges(__first, __last, __result);
}
-template <class _ForwardIterator, class _OutputIterator>
-_OutputIterator
-__brick_swap_ranges(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2>
+_RandomAccessIterator2
+__brick_swap_ranges(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __result,
/*vector=*/std::true_type) noexcept
{
using std::iter_swap;
return __unseq_backend::__simd_assign(__first, __last - __first, __result,
- iter_swap<_ForwardIterator, _OutputIterator>);
+ iter_swap<_RandomAccessIterator1, _RandomAccessIterator2>);
}
//------------------------------------------------------------------------
@@ -962,9 +973,10 @@
return std::copy_if(__first, __last, __result, __pred);
}
-template <class _ForwardIterator, class _OutputIterator, class _UnaryPredicate>
-_OutputIterator
-__brick_copy_if(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _UnaryPredicate __pred,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _UnaryPredicate>
+_RandomAccessIterator2
+__brick_copy_if(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __result,
+ _UnaryPredicate __pred,
/*vector=*/std::true_type) noexcept
{
#if (_PSTL_MONOTONIC_PRESENT)
@@ -1021,9 +1033,9 @@
}
}
-template <class _ForwardIterator, class _OutputIterator, class _Assigner>
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Assigner>
void
-__brick_copy_by_mask(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
+__brick_copy_by_mask(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __result,
bool* __restrict __mask, _Assigner __assigner, /*vector=*/std::true_type) noexcept
{
#if (_PSTL_MONOTONIC_PRESENT)
@@ -1053,10 +1065,11 @@
}
}
-template <class _RandomAccessIterator, class _OutputIterator1, class _OutputIterator2>
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3>
void
-__brick_partition_by_mask(_RandomAccessIterator __first, _RandomAccessIterator __last, _OutputIterator1 __out_true,
- _OutputIterator2 __out_false, bool* __mask, /*vector=*/std::true_type) noexcept
+__brick_partition_by_mask(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last,
+ _RandomAccessIterator2 __out_true, _RandomAccessIterator3 __out_false, bool* __mask,
+ /*vector=*/std::true_type) noexcept
{
#if (_PSTL_MONOTONIC_PRESENT)
__unseq_backend::__simd_partition_by_mask(__first, __last - __first, __out_true, __out_false, __mask);
@@ -1073,13 +1086,14 @@
return __internal::__brick_copy_if(__first, __last, __result, __pred, __is_vector);
}
-template <class _ExecutionPolicy, class _RandomAccessIterator, class _OutputIterator, class _UnaryPredicate,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _UnaryPredicate,
class _IsVector>
-_OutputIterator
-__pattern_copy_if(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
- _OutputIterator __result, _UnaryPredicate __pred, _IsVector __is_vector, /*parallel=*/std::true_type)
+_RandomAccessIterator2
+__pattern_copy_if(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last,
+ _RandomAccessIterator2 __result, _UnaryPredicate __pred, _IsVector __is_vector,
+ /*parallel=*/std::true_type)
{
- typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
+ typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType;
const _DifferenceType __n = __last - __first;
if (_DifferenceType(1) < __n)
{
@@ -1098,7 +1112,7 @@
[=](_DifferenceType __i, _DifferenceType __len, _DifferenceType __initial) { // Scan
__internal::__brick_copy_by_mask(
__first + __i, __first + (__i + __len), __result + __initial, __mask + __i,
- [](_RandomAccessIterator __x, _OutputIterator __z) { *__z = *__x; }, __is_vector);
+ [](_RandomAccessIterator1 __x, _RandomAccessIterator2 __z) { *__z = *__x; }, __is_vector);
},
[&__m](_DifferenceType __total) { __m = __total; });
return __result + __m;
@@ -1111,9 +1125,9 @@
//------------------------------------------------------------------------
// count
//------------------------------------------------------------------------
-template <class _ForwardIterator, class _Predicate>
-typename std::iterator_traits<_ForwardIterator>::difference_type
-__brick_count(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
+template <class _RandomAccessIterator, class _Predicate>
+typename std::iterator_traits<_RandomAccessIterator>::difference_type
+__brick_count(_RandomAccessIterator __first, _RandomAccessIterator __last, _Predicate __pred,
/* is_vector = */ std::true_type) noexcept
{
return __unseq_backend::__simd_count(__first, __last - __first, __pred);
@@ -1135,18 +1149,18 @@
return __internal::__brick_count(__first, __last, __pred, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate, class _IsVector>
-typename std::iterator_traits<_ForwardIterator>::difference_type
-__pattern_count(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Predicate, class _IsVector>
+typename std::iterator_traits<_RandomAccessIterator>::difference_type
+__pattern_count(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
+ _Predicate __pred,
/* is_parallel */ std::true_type, _IsVector __is_vector)
{
- typedef typename std::iterator_traits<_ForwardIterator>::difference_type _SizeType;
+ typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _SizeType;
return __internal::__except_handler([&]() {
return __par_backend::__parallel_reduce(
std::forward<_ExecutionPolicy>(__exec), __first, __last, _SizeType(0),
- [__pred, __is_vector](_ForwardIterator __begin, _ForwardIterator __end, _SizeType __value) -> _SizeType {
- return __value + __internal::__brick_count(__begin, __end, __pred, __is_vector);
- },
+ [__pred, __is_vector](_RandomAccessIterator __begin, _RandomAccessIterator __end, _SizeType __value)
+ -> _SizeType { return __value + __internal::__brick_count(__begin, __end, __pred, __is_vector); },
std::plus<_SizeType>());
});
}
@@ -1155,17 +1169,17 @@
// unique
//------------------------------------------------------------------------
-template <class _ForwardIterator, class _BinaryPredicate>
-_ForwardIterator
-__brick_unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred,
+template <class _RandomAccessIterator, class _BinaryPredicate>
+_RandomAccessIterator
+__brick_unique(_RandomAccessIterator __first, _RandomAccessIterator __last, _BinaryPredicate __pred,
/*is_vector=*/std::false_type) noexcept
{
return std::unique(__first, __last, __pred);
}
-template <class _ForwardIterator, class _BinaryPredicate>
-_ForwardIterator
-__brick_unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred,
+template <class _RandomAccessIterator, class _BinaryPredicate>
+_RandomAccessIterator
+__brick_unique(_RandomAccessIterator __first, _RandomAccessIterator __last, _BinaryPredicate __pred,
/*is_vector=*/std::true_type) noexcept
{
_PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial");
@@ -1254,23 +1268,20 @@
__par_backend::__parallel_for(
std::forward<_ExecutionPolicy>(__exec), __result, __result + __m,
[__result, __first, __is_vector](_Tp* __i, _Tp* __j) {
- __invoke_if_else(
- std::is_trivial<_Tp>(),
- [&]() { __brick_move(__i, __j, __first + (__i - __result), __is_vector); },
- [&]() {
- __brick_move_destroy()(__i, __j, __first + (__i - __result), __is_vector);
- });
+ __invoke_if_else(std::is_trivial<_Tp>(),
+ [&]() { __brick_move(__i, __j, __first + (__i - __result), __is_vector); },
+ [&]() { __brick_move_destroy()(__i, __j, __first + (__i - __result), __is_vector); });
});
return __first + __m;
});
}
-template <class _ExecutionPolicy, class _ForwardIterator, class _BinaryPredicate, class _IsVector>
-_ForwardIterator
-__pattern_unique(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred,
- _IsVector __is_vector, /*is_parallel=*/std::true_type) noexcept
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _BinaryPredicate, class _IsVector>
+_RandomAccessIterator
+__pattern_unique(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
+ _BinaryPredicate __pred, _IsVector __is_vector, /*is_parallel=*/std::true_type) noexcept
{
- typedef typename std::iterator_traits<_ForwardIterator>::reference _ReferenceType;
+ typedef typename std::iterator_traits<_RandomAccessIterator>::reference _ReferenceType;
if (__first == __last)
{
@@ -1283,7 +1294,7 @@
}
return __internal::__remove_elements(
std::forward<_ExecutionPolicy>(__exec), ++__first, __last,
- [&__pred, __is_vector](bool* __b, bool* __e, _ForwardIterator __it) {
+ [&__pred, __is_vector](bool* __b, bool* __e, _RandomAccessIterator __it) {
__internal::__brick_walk3(
__b, __e, __it - 1, __it,
[&__pred](bool& __x, _ReferenceType __y, _ReferenceType __z) { __x = !__pred(__y, __z); }, __is_vector);
@@ -1303,9 +1314,9 @@
return std::unique_copy(__first, __last, __result, __pred);
}
-template <class _RandomAccessIterator, class OutputIterator, class _BinaryPredicate>
-OutputIterator
-__brick_unique_copy(_RandomAccessIterator __first, _RandomAccessIterator __last, OutputIterator __result,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate>
+_RandomAccessIterator2
+__brick_unique_copy(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __result,
_BinaryPredicate __pred, /*vector=*/std::true_type) noexcept
{
#if (_PSTL_MONOTONIC_PRESENT)
@@ -1346,14 +1357,14 @@
return __unseq_backend::__simd_calc_mask_2(__first, __last - __first, __mask, __pred);
}
-template <class _ExecutionPolicy, class _RandomAccessIterator, class _OutputIterator, class _BinaryPredicate,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryPredicate,
class _IsVector>
-_OutputIterator
-__pattern_unique_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
- _OutputIterator __result, _BinaryPredicate __pred, _IsVector __is_vector,
+_RandomAccessIterator2
+__pattern_unique_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last,
+ _RandomAccessIterator2 __result, _BinaryPredicate __pred, _IsVector __is_vector,
/*parallel=*/std::true_type)
{
- typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
+ typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType;
const _DifferenceType __n = __last - __first;
if (_DifferenceType(2) < __n)
{
@@ -1385,7 +1396,7 @@
// Phase 2 is same as for __pattern_copy_if
__internal::__brick_copy_by_mask(
__first + __i, __first + (__i + __len), __result + __initial, __mask + __i,
- [](_RandomAccessIterator __x, _OutputIterator __z) { *__z = *__x; }, __is_vector);
+ [](_RandomAccessIterator1 __x, _RandomAccessIterator2 __z) { *__z = *__x; }, __is_vector);
},
[&__m](_DifferenceType __total) { __m = __total; });
return __result + __m;
@@ -1406,14 +1417,14 @@
std::reverse(__first, __last);
}
-template <class _BidirectionalIterator>
+template <class _RandomAccessIterator>
void
-__brick_reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, /*__is_vector=*/std::true_type) noexcept
+__brick_reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, /*__is_vector=*/std::true_type) noexcept
{
- typedef typename std::iterator_traits<_BidirectionalIterator>::reference _ReferenceType;
+ typedef typename std::iterator_traits<_RandomAccessIterator>::reference _ReferenceType;
const auto __n = (__last - __first) / 2;
- __unseq_backend::__simd_walk_2(__first, __n, std::reverse_iterator<_BidirectionalIterator>(__last),
+ __unseq_backend::__simd_walk_2(__first, __n, std::reverse_iterator<_RandomAccessIterator>(__last),
[](_ReferenceType __x, _ReferenceType __y) {
using std::swap;
swap(__x, __y);
@@ -1434,14 +1445,14 @@
}
// this brick is called in parallel version, so we can use iterator arithmetic
-template <class _BidirectionalIterator>
+template <class _RandomAccessIterator>
void
-__brick_reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, _BidirectionalIterator __d_last,
+__brick_reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __d_last,
/*is_vector=*/std::true_type) noexcept
{
- typedef typename std::iterator_traits<_BidirectionalIterator>::reference _ReferenceType;
+ typedef typename std::iterator_traits<_RandomAccessIterator>::reference _ReferenceType;
- __unseq_backend::__simd_walk_2(__first, __last - __first, std::reverse_iterator<_BidirectionalIterator>(__d_last),
+ __unseq_backend::__simd_walk_2(__first, __last - __first, std::reverse_iterator<_RandomAccessIterator>(__d_last),
[](_ReferenceType __x, _ReferenceType __y) {
using std::swap;
swap(__x, __y);
@@ -1457,14 +1468,14 @@
__internal::__brick_reverse(__first, __last, _is_vector);
}
-template <class _ExecutionPolicy, class _BidirectionalIterator, class _IsVector>
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _IsVector>
void
-__pattern_reverse(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __last,
+__pattern_reverse(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
_IsVector __is_vector, /*is_parallel=*/std::true_type)
{
__par_backend::__parallel_for(
std::forward<_ExecutionPolicy>(__exec), __first, __first + (__last - __first) / 2,
- [__is_vector, __first, __last](_BidirectionalIterator __inner_first, _BidirectionalIterator __inner_last) {
+ [__is_vector, __first, __last](_RandomAccessIterator __inner_first, _RandomAccessIterator __inner_last) {
__internal::__brick_reverse(__inner_first, __inner_last, __last - (__inner_first - __first), __is_vector);
});
}
@@ -1481,15 +1492,15 @@
return std::reverse_copy(__first, __last, __d_first);
}
-template <class _BidirectionalIterator, class _OutputIterator>
-_OutputIterator
-__brick_reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __d_first,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2>
+_RandomAccessIterator2
+__brick_reverse_copy(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __d_first,
/*is_vector=*/std::true_type) noexcept
{
- typedef typename std::iterator_traits<_BidirectionalIterator>::reference _ReferenceType1;
- typedef typename std::iterator_traits<_OutputIterator>::reference _ReferenceType2;
+ typedef typename std::iterator_traits<_RandomAccessIterator1>::reference _ReferenceType1;
+ typedef typename std::iterator_traits<_RandomAccessIterator2>::reference _ReferenceType2;
- return __unseq_backend::__simd_walk_2(std::reverse_iterator<_BidirectionalIterator>(__last), __last - __first,
+ return __unseq_backend::__simd_walk_2(std::reverse_iterator<_RandomAccessIterator1>(__last), __last - __first,
__d_first, [](_ReferenceType1 __x, _ReferenceType2 __y) { __y = __x; });
}
@@ -1501,15 +1512,15 @@
return __internal::__brick_reverse_copy(__first, __last, __d_first, __is_vector);
}
-template <class _ExecutionPolicy, class _BidirectionalIterator, class _OutputIterator, class _IsVector>
-_OutputIterator
-__pattern_reverse_copy(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __last,
- _OutputIterator __d_first, _IsVector __is_vector, /*is_parallel=*/std::true_type)
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _IsVector>
+_RandomAccessIterator2
+__pattern_reverse_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last,
+ _RandomAccessIterator2 __d_first, _IsVector __is_vector, /*is_parallel=*/std::true_type)
{
auto __len = __last - __first;
__par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last,
- [__is_vector, __first, __len, __d_first](_BidirectionalIterator __inner_first,
- _BidirectionalIterator __inner_last) {
+ [__is_vector, __first, __len, __d_first](_RandomAccessIterator1 __inner_first,
+ _RandomAccessIterator1 __inner_last) {
__internal::__brick_reverse_copy(__inner_first, __inner_last,
__d_first + (__len - (__inner_last - __first)),
__is_vector);
@@ -1533,14 +1544,14 @@
#endif
}
-template <class _ForwardIterator>
-_ForwardIterator
-__brick_rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
+template <class _RandomAccessIterator>
+_RandomAccessIterator
+__brick_rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
/*is_vector=*/std::true_type) noexcept
{
auto __n = __last - __first;
auto __m = __middle - __first;
- const _ForwardIterator __ret = __first + (__last - __middle);
+ const _RandomAccessIterator __ret = __first + (__last - __middle);
bool __is_left = (__m <= __n / 2);
if (!__is_left)
@@ -1555,7 +1566,7 @@
for (; __last - __first >= __m_2; __first += __m)
{
__unseq_backend::__simd_assign(__first, __m, __first + __m,
- iter_swap<_ForwardIterator, _ForwardIterator>);
+ iter_swap<_RandomAccessIterator, _RandomAccessIterator>);
}
}
else
@@ -1563,7 +1574,7 @@
for (; __last - __first >= __m_2; __last -= __m)
{
__unseq_backend::__simd_assign(__last - __m, __m, __last - __m_2,
- iter_swap<_ForwardIterator, _ForwardIterator>);
+ iter_swap<_RandomAccessIterator, _RandomAccessIterator>);
}
}
__is_left = !__is_left;
@@ -1582,12 +1593,12 @@
return __internal::__brick_rotate(__first, __middle, __last, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator, class _IsVector>
-_ForwardIterator
-__pattern_rotate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __middle,
- _ForwardIterator __last, _IsVector __is_vector, /*is_parallel=*/std::true_type)
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _IsVector>
+_RandomAccessIterator
+__pattern_rotate(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __middle,
+ _RandomAccessIterator __last, _IsVector __is_vector, /*is_parallel=*/std::true_type)
{
- typedef typename std::iterator_traits<_ForwardIterator>::value_type _Tp;
+ typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _Tp;
auto __n = __last - __first;
auto __m = __middle - __first;
if (__m <= __n / 2)
@@ -1597,20 +1608,19 @@
_Tp* __result = __buf.get();
__par_backend::__parallel_for(
std::forward<_ExecutionPolicy>(__exec), __middle, __last,
- [__middle, __result, __is_vector](_ForwardIterator __b, _ForwardIterator __e) {
+ [__middle, __result, __is_vector](_RandomAccessIterator __b, _RandomAccessIterator __e) {
__internal::__brick_uninitialized_move(__b, __e, __result + (__b - __middle), __is_vector);
});
- __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __middle,
- [__last, __middle, __is_vector](_ForwardIterator __b, _ForwardIterator __e) {
- __internal::__brick_move(__b, __e, __b + (__last - __middle),
- __is_vector);
- });
+ __par_backend::__parallel_for(
+ std::forward<_ExecutionPolicy>(__exec), __first, __middle,
+ [__last, __middle, __is_vector](_RandomAccessIterator __b, _RandomAccessIterator __e) {
+ __internal::__brick_move(__b, __e, __b + (__last - __middle), __is_vector);
+ });
__par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __result, __result + (__n - __m),
[__first, __result, __is_vector](_Tp* __b, _Tp* __e) {
- __brick_move_destroy()(
- __b, __e, __first + (__b - __result), __is_vector);
+ __brick_move_destroy()(__b, __e, __first + (__b - __result), __is_vector);
});
return __first + (__last - __middle);
@@ -1621,17 +1631,17 @@
__par_backend::__buffer<_Tp> __buf(__m);
return __internal::__except_handler([&__exec, __n, __m, __first, __middle, __last, __is_vector, &__buf]() {
_Tp* __result = __buf.get();
- __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __middle,
- [__first, __result, __is_vector](_ForwardIterator __b, _ForwardIterator __e) {
- __internal::__brick_uninitialized_move(
- __b, __e, __result + (__b - __first), __is_vector);
- });
+ __par_backend::__parallel_for(
+ std::forward<_ExecutionPolicy>(__exec), __first, __middle,
+ [__first, __result, __is_vector](_RandomAccessIterator __b, _RandomAccessIterator __e) {
+ __internal::__brick_uninitialized_move(__b, __e, __result + (__b - __first), __is_vector);
+ });
- __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __middle, __last,
- [__first, __middle, __is_vector](_ForwardIterator __b, _ForwardIterator __e) {
- __internal::__brick_move(__b, __e, __first + (__b - __middle),
- __is_vector);
- });
+ __par_backend::__parallel_for(
+ std::forward<_ExecutionPolicy>(__exec), __middle, __last,
+ [__first, __middle, __is_vector](_RandomAccessIterator __b, _RandomAccessIterator __e) {
+ __internal::__brick_move(__b, __e, __first + (__b - __middle), __is_vector);
+ });
__par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __result, __result + __m,
[__n, __m, __first, __result, __is_vector](_Tp* __b, _Tp* __e) {
@@ -1656,12 +1666,12 @@
return std::rotate_copy(__first, __middle, __last, __result);
}
-template <class _ForwardIterator, class _OutputIterator>
-_OutputIterator
-__brick_rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
- _OutputIterator __result, /*__is_vector=*/std::true_type) noexcept
+template <class _RandomAccessIterator1, class _RandomAccessIterator2>
+_RandomAccessIterator2
+__brick_rotate_copy(_RandomAccessIterator1 __first, _RandomAccessIterator1 __middle, _RandomAccessIterator1 __last,
+ _RandomAccessIterator2 __result, /*__is_vector=*/std::true_type) noexcept
{
- _OutputIterator __res = __internal::__brick_copy(__middle, __last, __result, std::true_type());
+ _RandomAccessIterator2 __res = __internal::__brick_copy(__middle, __last, __result, std::true_type());
return __internal::__brick_copy(__first, __middle, __res, std::true_type());
}
@@ -1673,22 +1683,22 @@
return __internal::__brick_rotate_copy(__first, __middle, __last, __result, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator, class _OutputIterator, class _IsVector>
-_OutputIterator
-__pattern_rotate_copy(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __middle,
- _ForwardIterator __last, _OutputIterator __result, _IsVector __is_vector,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _IsVector>
+_RandomAccessIterator2
+__pattern_rotate_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __middle,
+ _RandomAccessIterator1 __last, _RandomAccessIterator2 __result, _IsVector __is_vector,
/*is_parallel=*/std::true_type)
{
__par_backend::__parallel_for(
std::forward<_ExecutionPolicy>(__exec), __first, __last,
- [__first, __last, __middle, __result, __is_vector](_ForwardIterator __b, _ForwardIterator __e) {
+ [__first, __last, __middle, __result, __is_vector](_RandomAccessIterator1 __b, _RandomAccessIterator1 __e) {
if (__b > __middle)
{
__internal::__brick_copy(__b, __e, __result + (__b - __middle), __is_vector);
}
else
{
- _OutputIterator __new_result = __result + ((__last - __middle) + (__b - __first));
+ _RandomAccessIterator2 __new_result = __result + ((__last - __middle) + (__b - __first));
if (__e < __middle)
{
__internal::__brick_copy(__b, __e, __new_result, __is_vector);
@@ -1715,21 +1725,21 @@
return std::is_partitioned(__first, __last, __pred);
}
-template <class _ForwardIterator, class _UnaryPredicate>
+template <class _RandomAccessIterator, class _UnaryPredicate>
bool
-__brick_is_partitioned(_ForwardIterator __first, _ForwardIterator __last, _UnaryPredicate __pred,
+__brick_is_partitioned(_RandomAccessIterator __first, _RandomAccessIterator __last, _UnaryPredicate __pred,
/*is_vector=*/std::true_type) noexcept
{
- typedef typename std::iterator_traits<_ForwardIterator>::difference_type _SizeType;
+ typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _SizeType;
if (__first == __last)
{
return true;
}
else
{
- _ForwardIterator __result = __unseq_backend::__simd_first(
+ _RandomAccessIterator __result = __unseq_backend::__simd_first(
__first, _SizeType(0), __last - __first,
- [&__pred](_ForwardIterator __it, _SizeType __i) { return !__pred(__it[__i]); });
+ [&__pred](_RandomAccessIterator __it, _SizeType __i) { return !__pred(__it[__i]); });
if (__result == __last)
{
return true;
@@ -1750,9 +1760,9 @@
return __internal::__brick_is_partitioned(__first, __last, __pred, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate, class _IsVector>
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _UnaryPredicate, class _IsVector>
bool
-__pattern_is_partitioned(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last,
+__pattern_is_partitioned(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
_UnaryPredicate __pred, _IsVector __is_vector, /*is_parallel=*/std::true_type)
{
if (__first == __last)
@@ -1785,7 +1795,7 @@
__init = __par_backend::__parallel_reduce(
std::forward<_ExecutionPolicy>(__exec), __first, __last, __init,
- [&__pred, &__table, __is_vector](_ForwardIterator __i, _ForwardIterator __j,
+ [&__pred, &__table, __is_vector](_RandomAccessIterator __i, _RandomAccessIterator __j,
_ReduceType __value) -> _ReduceType {
if (__value == __broken)
{
@@ -1796,12 +1806,12 @@
if (__pred(*__i))
{
// find first element that don't satisfy pred
- _ForwardIterator __x =
+ _RandomAccessIterator __x =
__internal::__brick_find_if(__i + 1, __j, std::not_fn(__pred), __is_vector);
if (__x != __j)
{
// find first element after "x" that satisfy pred
- _ForwardIterator __y = __internal::__brick_find_if(__x + 1, __j, __pred, __is_vector);
+ _RandomAccessIterator __y = __internal::__brick_find_if(__x + 1, __j, __pred, __is_vector);
// if it was found then range isn't partitioned by pred
if (__y != __j)
{
@@ -1859,9 +1869,9 @@
return std::partition(__first, __last, __pred);
}
-template <class _ForwardIterator, class _UnaryPredicate>
-_ForwardIterator
-__brick_partition(_ForwardIterator __first, _ForwardIterator __last, _UnaryPredicate __pred,
+template <class _RandomAccessIterator, class _UnaryPredicate>
+_RandomAccessIterator
+__brick_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _UnaryPredicate __pred,
/*is_vector=*/std::true_type) noexcept
{
_PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial");
@@ -1876,9 +1886,9 @@
return __internal::__brick_partition(__first, __last, __pred, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate, class _IsVector>
-_ForwardIterator
-__pattern_partition(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _UnaryPredicate, class _IsVector>
+_RandomAccessIterator
+__pattern_partition(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
_UnaryPredicate __pred, _IsVector __is_vector, /*is_parallel=*/std::true_type)
{
@@ -1886,9 +1896,9 @@
// elements after pivot don't satisfy pred (false part)
struct _PartitionRange
{
- _ForwardIterator __begin;
- _ForwardIterator __pivot;
- _ForwardIterator __end;
+ _RandomAccessIterator __begin;
+ _RandomAccessIterator __pivot;
+ _RandomAccessIterator __end;
};
return __internal::__except_handler([&]() {
@@ -1911,7 +1921,7 @@
{
__par_backend::__parallel_for(
std::forward<_ExecutionPolicy>(__exec), __val1.__pivot, __val1.__pivot + __size1,
- [__val1, __val2, __size1, __is_vector](_ForwardIterator __i, _ForwardIterator __j) {
+ [__val1, __val2, __size1, __is_vector](_RandomAccessIterator __i, _RandomAccessIterator __j) {
__internal::__brick_swap_ranges(__i, __j, (__val2.__pivot - __size1) + (__i - __val1.__pivot),
__is_vector);
});
@@ -1922,7 +1932,7 @@
{
__par_backend::__parallel_for(
std::forward<_ExecutionPolicy>(__exec), __val1.__pivot, __val1.__pivot + __size2,
- [__val1, __val2, __is_vector](_ForwardIterator __i, _ForwardIterator __j) {
+ [__val1, __val2, __is_vector](_RandomAccessIterator __i, _RandomAccessIterator __j) {
__internal::__brick_swap_ranges(__i, __j, __val2.__begin + (__i - __val1.__pivot), __is_vector);
});
return {__new_begin, __val1.__pivot + __size2, __val2.__end};
@@ -1931,10 +1941,10 @@
_PartitionRange __result = __par_backend::__parallel_reduce(
std::forward<_ExecutionPolicy>(__exec), __first, __last, __init,
- [__pred, __is_vector, __reductor](_ForwardIterator __i, _ForwardIterator __j,
+ [__pred, __is_vector, __reductor](_RandomAccessIterator __i, _RandomAccessIterator __j,
_PartitionRange __value) -> _PartitionRange {
//1. serial partition
- _ForwardIterator __pivot = __internal::__brick_partition(__i, __j, __pred, __is_vector);
+ _RandomAccessIterator __pivot = __internal::__brick_partition(__i, __j, __pred, __is_vector);
// 2. merging of two ranges (left and right respectively)
return __reductor(__value, {__i, __pivot, __j});
@@ -1956,9 +1966,9 @@
return std::stable_partition(__first, __last, __pred);
}
-template <class _BidirectionalIterator, class _UnaryPredicate>
-_BidirectionalIterator
-__brick_stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _UnaryPredicate __pred,
+template <class _RandomAccessIterator, class _UnaryPredicate>
+_RandomAccessIterator
+__brick_stable_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _UnaryPredicate __pred,
/*__is_vector=*/std::true_type) noexcept
{
_PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial");
@@ -1974,9 +1984,9 @@
return __internal::__brick_stable_partition(__first, __last, __pred, __is_vector);
}
-template <class _ExecutionPolicy, class _BidirectionalIterator, class _UnaryPredicate, class _IsVector>
-_BidirectionalIterator
-__pattern_stable_partition(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __last,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _UnaryPredicate, class _IsVector>
+_RandomAccessIterator
+__pattern_stable_partition(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
_UnaryPredicate __pred, _IsVector __is_vector,
/*is_parallelization=*/std::true_type) noexcept
{
@@ -1984,9 +1994,9 @@
// elements after pivot don't satisfy pred (false part)
struct _PartitionRange
{
- _BidirectionalIterator __begin;
- _BidirectionalIterator __pivot;
- _BidirectionalIterator __end;
+ _RandomAccessIterator __begin;
+ _RandomAccessIterator __pivot;
+ _RandomAccessIterator __end;
};
return __internal::__except_handler([&]() {
@@ -2013,10 +2023,10 @@
_PartitionRange __result = __par_backend::__parallel_reduce(
std::forward<_ExecutionPolicy>(__exec), __first, __last, __init,
- [&__pred, __is_vector, __reductor](_BidirectionalIterator __i, _BidirectionalIterator __j,
+ [&__pred, __is_vector, __reductor](_RandomAccessIterator __i, _RandomAccessIterator __j,
_PartitionRange __value) -> _PartitionRange {
//1. serial stable_partition
- _BidirectionalIterator __pivot = __internal::__brick_stable_partition(__i, __j, __pred, __is_vector);
+ _RandomAccessIterator __pivot = __internal::__brick_stable_partition(__i, __j, __pred, __is_vector);
// 2. merging of two ranges (left and right respectively)
return __reductor(__value, {__i, __pivot, __j});
@@ -2038,10 +2048,12 @@
return std::partition_copy(__first, __last, __out_true, __out_false, __pred);
}
-template <class _ForwardIterator, class _OutputIterator1, class _OutputIterator2, class _UnaryPredicate>
-std::pair<_OutputIterator1, _OutputIterator2>
-__brick_partition_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator1 __out_true,
- _OutputIterator2 __out_false, _UnaryPredicate __pred, /*is_vector=*/std::true_type) noexcept
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3,
+ class _UnaryPredicate>
+std::pair<_RandomAccessIterator2, _RandomAccessIterator3>
+__brick_partition_copy(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __out_true,
+ _RandomAccessIterator3 __out_false, _UnaryPredicate __pred,
+ /*is_vector=*/std::true_type) noexcept
{
#if (_PSTL_MONOTONIC_PRESENT)
return __unseq_backend::__simd_partition_copy(__first, __last - __first, __out_true, __out_false, __pred);
@@ -2060,14 +2072,14 @@
return __internal::__brick_partition_copy(__first, __last, __out_true, __out_false, __pred, __is_vector);
}
-template <class _ExecutionPolicy, class _RandomAccessIterator, class _OutputIterator1, class _OutputIterator2,
- class _UnaryPredicate, class _IsVector>
-std::pair<_OutputIterator1, _OutputIterator2>
-__pattern_partition_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
- _OutputIterator1 __out_true, _OutputIterator2 __out_false, _UnaryPredicate __pred,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2,
+ class _RandomAccessIterator3, class _UnaryPredicate, class _IsVector>
+std::pair<_RandomAccessIterator2, _RandomAccessIterator3>
+__pattern_partition_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last,
+ _RandomAccessIterator2 __out_true, _RandomAccessIterator3 __out_false, _UnaryPredicate __pred,
_IsVector __is_vector, /*is_parallelization=*/std::true_type)
{
- typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
+ typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType;
typedef std::pair<_DifferenceType, _DifferenceType> _ReturnType;
const _DifferenceType __n = __last - __first;
if (_DifferenceType(1) < __n)
@@ -2196,10 +2208,11 @@
return std::partial_sort_copy(__first, __last, __d_first, __d_last, __comp);
}
-template <class _ExecutionPolicy, class _ForwardIterator, class _RandomAccessIterator, class _Compare, class _IsVector>
-_RandomAccessIterator
-__pattern_partial_sort_copy(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last,
- _RandomAccessIterator __d_first, _RandomAccessIterator __d_last, _Compare __comp,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _Compare,
+ class _IsVector>
+_RandomAccessIterator2
+__pattern_partial_sort_copy(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last,
+ _RandomAccessIterator2 __d_first, _RandomAccessIterator2 __d_last, _Compare __comp,
_IsVector __is_vector, /*is_parallel=*/std::true_type)
{
if (__last == __first || __d_last == __d_first)
@@ -2213,10 +2226,10 @@
{
__par_backend::__parallel_stable_sort(
std::forward<_ExecutionPolicy>(__exec), __d_first, __d_first + __n1, __comp,
- [__first, __d_first, __is_vector](_RandomAccessIterator __i, _RandomAccessIterator __j,
+ [__first, __d_first, __is_vector](_RandomAccessIterator2 __i, _RandomAccessIterator2 __j,
_Compare __comp) {
- _ForwardIterator __i1 = __first + (__i - __d_first);
- _ForwardIterator __j1 = __first + (__j - __d_first);
+ _RandomAccessIterator1 __i1 = __first + (__i - __d_first);
+ _RandomAccessIterator1 __j1 = __first + (__j - __d_first);
// 1. Copy elements from input to output
#if !_PSTL_ICC_18_OMP_SIMD_BROKEN
@@ -2232,14 +2245,14 @@
}
else
{
- typedef typename std::iterator_traits<_ForwardIterator>::value_type _T1;
- typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _T2;
+ typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type _T1;
+ typedef typename std::iterator_traits<_RandomAccessIterator2>::value_type _T2;
__par_backend::__buffer<_T1> __buf(__n1);
_T1* __r = __buf.get();
__par_backend::__parallel_stable_sort(std::forward<_ExecutionPolicy>(__exec), __r, __r + __n1, __comp,
[__n2, __first, __r](_T1* __i, _T1* __j, _Compare __comp) {
- _ForwardIterator __it = __first + (__i - __r);
+ _RandomAccessIterator1 __it = __first + (__i - __r);
// 1. Copy elements from input to raw memory
for (_T1* __k = __i; __k != __j; ++__k, ++__it)
@@ -2258,8 +2271,7 @@
// 3. Move elements from temporary __buffer to output
__par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __r, __r + __n2,
[__r, __d_first, __is_vector](_T1* __i, _T1* __j) {
- __brick_move_destroy()(
- __i, __j, __d_first + (__i - __r), __is_vector);
+ __brick_move_destroy()(__i, __j, __d_first + (__i - __r), __is_vector);
});
__par_backend::__parallel_for(
std::forward<_ExecutionPolicy>(__exec), __r + __n2, __r + __n1,
@@ -2273,9 +2285,9 @@
//------------------------------------------------------------------------
// adjacent_find
//------------------------------------------------------------------------
-template <class _ForwardIterator, class _BinaryPredicate>
-_ForwardIterator
-__brick_adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred,
+template <class _RandomAccessIterator, class _BinaryPredicate>
+_RandomAccessIterator
+__brick_adjacent_find(_RandomAccessIterator __first, _RandomAccessIterator __last, _BinaryPredicate __pred,
/* IsVector = */ std::true_type, bool __or_semantic) noexcept
{
return __unseq_backend::__simd_adjacent_find(__first, __last, __pred, __or_semantic);
@@ -2406,9 +2418,9 @@
//------------------------------------------------------------------------
// fill, fill_n
//------------------------------------------------------------------------
-template <class _ForwardIterator, class _Tp>
+template <class _RandomAccessIterator, class _Tp>
void
-__brick_fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value,
+__brick_fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value,
/* __is_vector = */ std::true_type) noexcept
{
__unseq_backend::__simd_fill_n(__first, __last - __first, __value);
@@ -2430,23 +2442,26 @@
__internal::__brick_fill(__first, __last, __value, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _IsVector>
-_ForwardIterator
-__pattern_fill(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Tp, class _IsVector>
+_RandomAccessIterator
+__pattern_fill(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
+ const _Tp& __value,
/*is_parallel=*/std::true_type, _IsVector __is_vector)
{
return __internal::__except_handler([&__exec, __first, __last, &__value, __is_vector]() {
- __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last,
- [&__value, __is_vector](_ForwardIterator __begin, _ForwardIterator __end) {
- __internal::__brick_fill(__begin, __end, __value, __is_vector);
- });
+ __par_backend::__parallel_for(
+ std::forward<_ExecutionPolicy>(__exec), __first, __last,
+ [&__value, __is_vector](_RandomAccessIterator __begin, _RandomAccessIterator __end) {
+ __internal::__brick_fill(__begin, __end, __value, __is_vector);
+ });
return __last;
});
}
-template <class _OutputIterator, class _Size, class _Tp>
-_OutputIterator
-__brick_fill_n(_OutputIterator __first, _Size __count, const _Tp& __value, /* __is_vector = */ std::true_type) noexcept
+template <class _RandomAccessIterator, class _Size, class _Tp>
+_RandomAccessIterator
+__brick_fill_n(_RandomAccessIterator __first, _Size __count, const _Tp& __value,
+ /* __is_vector = */ std::true_type) noexcept
{
return __unseq_backend::__simd_fill_n(__first, __count, __value);
}
@@ -2466,9 +2481,9 @@
return __internal::__brick_fill_n(__first, __count, __value, __is_vector);
}
-template <class _ExecutionPolicy, class _OutputIterator, class _Size, class _Tp, class _IsVector>
-_OutputIterator
-__pattern_fill_n(_ExecutionPolicy&& __exec, _OutputIterator __first, _Size __count, const _Tp& __value,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Size, class _Tp, class _IsVector>
+_RandomAccessIterator
+__pattern_fill_n(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _Size __count, const _Tp& __value,
/*is_parallel=*/std::true_type, _IsVector __is_vector)
{
return __internal::__pattern_fill(std::forward<_ExecutionPolicy>(__exec), __first, __first + __count, __value,
@@ -2502,23 +2517,25 @@
__internal::__brick_generate(__first, __last, __g, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator, class _Generator, class _IsVector>
-_ForwardIterator
-__pattern_generate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Generator __g,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Generator, class _IsVector>
+_RandomAccessIterator
+__pattern_generate(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
+ _Generator __g,
/*is_parallel=*/std::true_type, _IsVector __is_vector)
{
return __internal::__except_handler([&]() {
__par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __first, __last,
- [__g, __is_vector](_ForwardIterator __begin, _ForwardIterator __end) {
+ [__g, __is_vector](_RandomAccessIterator __begin, _RandomAccessIterator __end) {
__internal::__brick_generate(__begin, __end, __g, __is_vector);
});
return __last;
});
}
-template <class OutputIterator, class Size, class _Generator>
-OutputIterator
-__brick_generate_n(OutputIterator __first, Size __count, _Generator __g, /* is_vector = */ std::true_type) noexcept
+template <class _RandomAccessIterator, class Size, class _Generator>
+_RandomAccessIterator
+__brick_generate_n(_RandomAccessIterator __first, Size __count, _Generator __g,
+ /* is_vector = */ std::true_type) noexcept
{
return __unseq_backend::__simd_generate_n(__first, __count, __g);
}
@@ -2538,12 +2555,12 @@
return __internal::__brick_generate_n(__first, __count, __g, __is_vector);
}
-template <class _ExecutionPolicy, class _OutputIterator, class _Size, class _Generator, class _IsVector>
-_OutputIterator
-__pattern_generate_n(_ExecutionPolicy&& __exec, _OutputIterator __first, _Size __count, _Generator __g,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Size, class _Generator, class _IsVector>
+_RandomAccessIterator
+__pattern_generate_n(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _Size __count, _Generator __g,
/*is_parallel=*/std::true_type, _IsVector __is_vector)
{
- static_assert(__is_random_access_iterator<_OutputIterator>::value,
+ static_assert(__is_random_access_iterator<_RandomAccessIterator>::value,
"Pattern-brick error. Should be a random access iterator.");
return __internal::__pattern_generate(std::forward<_ExecutionPolicy>(__exec), __first, __first + __count, __g,
std::true_type(), __is_vector);
@@ -2581,12 +2598,12 @@
return __internal::__brick_remove_if(__first, __last, __pred, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate, class _IsVector>
-_ForwardIterator
-__pattern_remove_if(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _UnaryPredicate, class _IsVector>
+_RandomAccessIterator
+__pattern_remove_if(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
_UnaryPredicate __pred, _IsVector __is_vector, /*is_parallel*/ std::true_type) noexcept
{
- typedef typename std::iterator_traits<_ForwardIterator>::reference _ReferenceType;
+ typedef typename std::iterator_traits<_RandomAccessIterator>::reference _ReferenceType;
if (__first == __last || __first + 1 == __last)
{
@@ -2596,7 +2613,7 @@
return __internal::__remove_elements(
std::forward<_ExecutionPolicy>(__exec), __first, __last,
- [&__pred, __is_vector](bool* __b, bool* __e, _ForwardIterator __it) {
+ [&__pred, __is_vector](bool* __b, bool* __e, _RandomAccessIterator __it) {
__internal::__brick_walk2(__b, __e, __it, [&__pred](bool& __x, _ReferenceType __y) { __x = !__pred(__y); },
__is_vector);
},
@@ -2616,10 +2633,10 @@
return std::merge(__first1, __last1, __first2, __last2, __d_first, __comp);
}
-template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare>
-_OutputIterator
-__brick_merge(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
- _ForwardIterator2 __last2, _OutputIterator __d_first, _Compare __comp,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3, class _Compare>
+_RandomAccessIterator3
+__brick_merge(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
+ _RandomAccessIterator2 __last2, _RandomAccessIterator3 __d_first, _Compare __comp,
/* __is_vector = */ std::true_type) noexcept
{
_PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial");
@@ -2636,17 +2653,17 @@
return __internal::__brick_merge(__first1, __last1, __first2, __last2, __d_first, __comp, __is_vector);
}
-template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _OutputIterator,
- class _Compare, class _IsVector>
-_OutputIterator
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2,
+ class _RandomAccessIterator3, class _Compare, class _IsVector>
+_RandomAccessIterator3
__pattern_merge(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
- _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _OutputIterator __d_first,
+ _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _RandomAccessIterator3 __d_first,
_Compare __comp, _IsVector __is_vector, /* is_parallel = */ std::true_type)
{
__par_backend::__parallel_merge(
std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __d_first, __comp,
[__is_vector](_RandomAccessIterator1 __f1, _RandomAccessIterator1 __l1, _RandomAccessIterator2 __f2,
- _RandomAccessIterator2 __l2, _OutputIterator __f3, _Compare __comp) {
+ _RandomAccessIterator2 __l2, _RandomAccessIterator3 __f3, _Compare __comp) {
return __internal::__brick_merge(__f1, __l1, __f2, __l2, __f3, __comp, __is_vector);
});
return __d_first + (__last1 - __first1) + (__last2 - __first2);
@@ -2663,9 +2680,9 @@
std::inplace_merge(__first, __middle, __last, __comp);
}
-template <class _BidirectionalIterator, class _Compare>
+template <class _RandomAccessIterator, class _Compare>
void
-__brick_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
+__brick_inplace_merge(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
_Compare __comp, /* __is_vector = */ std::true_type) noexcept
{
_PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial")
@@ -2681,43 +2698,43 @@
__internal::__brick_inplace_merge(__first, __middle, __last, __comp, __is_vector);
}
-template <class _ExecutionPolicy, class _BidirectionalIterator, class _Compare, class _IsVector>
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Compare, class _IsVector>
void
-__pattern_inplace_merge(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __middle,
- _BidirectionalIterator __last, _Compare __comp, _IsVector __is_vector,
+__pattern_inplace_merge(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __middle,
+ _RandomAccessIterator __last, _Compare __comp, _IsVector __is_vector,
/*is_parallel=*/std::true_type)
{
if (__first == __last || __first == __middle || __middle == __last)
{
return;
}
- typedef typename std::iterator_traits<_BidirectionalIterator>::value_type _Tp;
+ typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _Tp;
auto __n = __last - __first;
__par_backend::__buffer<_Tp> __buf(__n);
_Tp* __r = __buf.get();
__internal::__except_handler([&]() {
- auto __move_values = [](_BidirectionalIterator __x, _Tp* __z) {
+ auto __move_values = [](_RandomAccessIterator __x, _Tp* __z) {
__internal::__invoke_if_else(std::is_trivial<_Tp>(), [&]() { *__z = std::move(*__x); },
[&]() { ::new (std::addressof(*__z)) _Tp(std::move(*__x)); });
};
- auto __move_sequences = [](_BidirectionalIterator __first1, _BidirectionalIterator __last1, _Tp* __first2) {
+ auto __move_sequences = [](_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Tp* __first2) {
return __internal::__brick_uninitialized_move(__first1, __last1, __first2, _IsVector());
};
__par_backend::__parallel_merge(
std::forward<_ExecutionPolicy>(__exec), __first, __middle, __middle, __last, __r, __comp,
- [__n, __move_values, __move_sequences](_BidirectionalIterator __f1, _BidirectionalIterator __l1,
- _BidirectionalIterator __f2, _BidirectionalIterator __l2, _Tp* __f3,
+ [__n, __move_values, __move_sequences](_RandomAccessIterator __f1, _RandomAccessIterator __l1,
+ _RandomAccessIterator __f2, _RandomAccessIterator __l2, _Tp* __f3,
_Compare __comp) {
(__utils::__serial_move_merge(__n))(__f1, __l1, __f2, __l2, __f3, __comp, __move_values, __move_values,
__move_sequences, __move_sequences);
return __f3 + (__l1 - __f1) + (__l2 - __f2);
});
- __par_backend::__parallel_for(
- std::forward<_ExecutionPolicy>(__exec), __r, __r + __n, [__r, __first, __is_vector](_Tp* __i, _Tp* __j) {
- __brick_move_destroy()(__i, __j, __first + (__i - __r), __is_vector);
- });
+ __par_backend::__parallel_for(std::forward<_ExecutionPolicy>(__exec), __r, __r + __n,
+ [__r, __first, __is_vector](_Tp* __i, _Tp* __j) {
+ __brick_move_destroy()(__i, __j, __first + (__i - __r), __is_vector);
+ });
});
}
@@ -2734,10 +2751,11 @@
return std::includes(__first1, __last1, __first2, __last2, __comp);
}
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Compare, class _IsVector>
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _Compare,
+ class _IsVector>
bool
-__pattern_includes(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
- _ForwardIterator2 __first2, _ForwardIterator2 __last2, _Compare __comp, _IsVector,
+__pattern_includes(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
+ _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _Compare __comp, _IsVector,
/*is_parallel=*/std::true_type)
{
if (__first2 >= __last2)
@@ -2756,12 +2774,12 @@
return __internal::__except_handler([&]() {
return !__internal::__parallel_or(
std::forward<_ExecutionPolicy>(__exec), __first2, __last2,
- [__first1, __last1, __first2, __last2, &__comp](_ForwardIterator2 __i, _ForwardIterator2 __j) {
+ [__first1, __last1, __first2, __last2, &__comp](_RandomAccessIterator2 __i, _RandomAccessIterator2 __j) {
_PSTL_ASSERT(__j > __i);
//_PSTL_ASSERT(__j - __i > 1);
//1. moving boundaries to "consume" subsequence of equal elements
- auto __is_equal = [&__comp](_ForwardIterator2 __a, _ForwardIterator2 __b) -> bool {
+ auto __is_equal = [&__comp](_RandomAccessIterator2 __a, _RandomAccessIterator2 __b) -> bool {
return !__comp(*__a, *__b) && !__comp(*__b, *__a);
};
@@ -2822,9 +2840,8 @@
_DifferenceType __m{};
auto __scan = [=](_DifferenceType, _DifferenceType, const _SetRange& __s) { // Scan
if (!__s.empty())
- __brick_move_destroy()(__buffer + __s.__buf_pos,
- __buffer + (__s.__buf_pos + __s.__len), __result + __s.__pos,
- __is_vector);
+ __brick_move_destroy()(__buffer + __s.__buf_pos, __buffer + (__s.__buf_pos + __s.__len),
+ __result + __s.__pos, __is_vector);
};
__par_backend::__parallel_strict_scan(
std::forward<_ExecutionPolicy>(__exec), __n1, _SetRange{0, 0, 0}, //-1, 0},
@@ -3021,10 +3038,10 @@
}
};
-template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare>
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _OutputIterator, class _Compare>
_OutputIterator
-__brick_set_union(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
- _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
+__brick_set_union(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
+ _RandomAccessIterator2 __last2, _OutputIterator __result, _Compare __comp,
/*__is_vector=*/std::true_type) noexcept
{
_PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial");
@@ -3042,12 +3059,12 @@
return __internal::__brick_set_union(__first1, __last1, __first2, __last2, __result, __comp, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _OutputIterator,
class _Compare, class _IsVector>
_OutputIterator
-__pattern_set_union(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
- _ForwardIterator2 __first2, _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
- _IsVector __is_vector, /*__is_parallel=*/std::true_type)
+__pattern_set_union(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
+ _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _OutputIterator __result,
+ _Compare __comp, _IsVector __is_vector, /*__is_parallel=*/std::true_type)
{
const auto __n1 = __last1 - __first1;
@@ -3060,8 +3077,8 @@
typedef typename std::iterator_traits<_OutputIterator>::value_type _Tp;
return __parallel_set_union_op(
std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp,
- [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2,
- _Tp* __result, _Compare __comp) {
+ [](_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
+ _RandomAccessIterator2 __last2, _Tp* __result, _Compare __comp) {
return __pstl::__utils::__set_union_construct(__first1, __last1, __first2, __last2, __result, __comp,
__BrickCopyConstruct<_IsVector>());
},
@@ -3081,10 +3098,11 @@
return std::set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
}
-template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare>
-_OutputIterator
-__brick_set_intersection(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
- _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3, class _Compare>
+_RandomAccessIterator3
+__brick_set_intersection(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
+ _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2,
+ _RandomAccessIterator3 __result, _Compare __comp,
/*__is_vector=*/std::true_type) noexcept
{
_PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial");
@@ -3101,15 +3119,16 @@
return __internal::__brick_set_intersection(__first1, __last1, __first2, __last2, __result, __comp, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator,
- class _Compare, class _IsVector>
-_OutputIterator
-__pattern_set_intersection(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
- _ForwardIterator2 __first2, _ForwardIterator2 __last2, _OutputIterator __result,
- _Compare __comp, _IsVector __is_vector, /*is_parallel=*/std::true_type)
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2,
+ class _RandomAccessIterator3, class _Compare, class _IsVector>
+_RandomAccessIterator3
+__pattern_set_intersection(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
+ _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2,
+ _RandomAccessIterator3 __result, _Compare __comp, _IsVector __is_vector,
+ /*is_parallel=*/std::true_type)
{
- typedef typename std::iterator_traits<_OutputIterator>::value_type _Tp;
- typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferenceType;
+ typedef typename std::iterator_traits<_RandomAccessIterator3>::value_type _Tp;
+ typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType;
const auto __n1 = __last1 - __first1;
const auto __n2 = __last2 - __first2;
@@ -3119,13 +3138,13 @@
return __result;
// testing whether the sequences are intersected
- _ForwardIterator1 __left_bound_seq_1 = std::lower_bound(__first1, __last1, *__first2, __comp);
+ _RandomAccessIterator1 __left_bound_seq_1 = std::lower_bound(__first1, __last1, *__first2, __comp);
//{1} < {2}: seq 2 is wholly greater than seq 1, so, the intersection is empty
if (__left_bound_seq_1 == __last1)
return __result;
// testing whether the sequences are intersected
- _ForwardIterator2 __left_bound_seq_2 = std::lower_bound(__first2, __last2, *__first1, __comp);
+ _RandomAccessIterator2 __left_bound_seq_2 = std::lower_bound(__first2, __last2, *__first1, __comp);
//{2} < {1}: seq 1 is wholly greater than seq 2, so, the intersection is empty
if (__left_bound_seq_2 == __last2)
return __result;
@@ -3137,8 +3156,8 @@
return __internal::__parallel_set_op(
std::forward<_ExecutionPolicy>(__exec), __left_bound_seq_1, __last1, __first2, __last2, __result, __comp,
[](_DifferenceType __n, _DifferenceType __m) { return std::min(__n, __m); },
- [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
- _ForwardIterator2 __last2, _Tp* __result, _Compare __comp) {
+ [](_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
+ _RandomAccessIterator2 __last2, _Tp* __result, _Compare __comp) {
return __pstl::__utils::__set_intersection_construct(__first1, __last1, __first2, __last2, __result,
__comp);
},
@@ -3152,8 +3171,8 @@
__result = __internal::__parallel_set_op(
std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __left_bound_seq_2, __last2, __result, __comp,
[](_DifferenceType __n, _DifferenceType __m) { return std::min(__n, __m); },
- [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
- _ForwardIterator2 __last2, _Tp* __result, _Compare __comp) {
+ [](_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
+ _RandomAccessIterator2 __last2, _Tp* __result, _Compare __comp) {
return __pstl::__utils::__set_intersection_construct(__first2, __last2, __first1, __last1, __result,
__comp);
},
@@ -3178,10 +3197,10 @@
return std::set_difference(__first1, __last1, __first2, __last2, __result, __comp);
}
-template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare>
-_OutputIterator
-__brick_set_difference(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
- _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3, class _Compare>
+_RandomAccessIterator3
+__brick_set_difference(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
+ _RandomAccessIterator2 __last2, _RandomAccessIterator3 __result, _Compare __comp,
/*__is_vector=*/std::true_type) noexcept
{
_PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial");
@@ -3198,15 +3217,16 @@
return __internal::__brick_set_difference(__first1, __last1, __first2, __last2, __result, __comp, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator,
- class _Compare, class _IsVector>
-_OutputIterator
-__pattern_set_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
- _ForwardIterator2 __first2, _ForwardIterator2 __last2, _OutputIterator __result,
- _Compare __comp, _IsVector __is_vector, /*is_parallel=*/std::true_type)
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2,
+ class _RandomAccessIterator3, class _Compare, class _IsVector>
+_RandomAccessIterator3
+__pattern_set_difference(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
+ _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2,
+ _RandomAccessIterator3 __result, _Compare __comp, _IsVector __is_vector,
+ /*is_parallel=*/std::true_type)
{
- typedef typename std::iterator_traits<_OutputIterator>::value_type _Tp;
- typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferenceType;
+ typedef typename std::iterator_traits<_RandomAccessIterator3>::value_type _Tp;
+ typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType;
const auto __n1 = __last1 - __first1;
const auto __n2 = __last2 - __first2;
@@ -3219,43 +3239,43 @@
if (__n2 == 0)
return __internal::__pattern_walk2_brick(
std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __result,
- [__is_vector](_ForwardIterator1 __begin, _ForwardIterator1 __end, _OutputIterator __res) {
+ [__is_vector](_RandomAccessIterator1 __begin, _RandomAccessIterator1 __end, _RandomAccessIterator3 __res) {
return __internal::__brick_copy(__begin, __end, __res, __is_vector);
},
std::true_type());
// testing whether the sequences are intersected
- _ForwardIterator1 __left_bound_seq_1 = std::lower_bound(__first1, __last1, *__first2, __comp);
+ _RandomAccessIterator1 __left_bound_seq_1 = std::lower_bound(__first1, __last1, *__first2, __comp);
//{1} < {2}: seq 2 is wholly greater than seq 1, so, parallel copying just first sequence
if (__left_bound_seq_1 == __last1)
return __internal::__pattern_walk2_brick(
std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __result,
- [__is_vector](_ForwardIterator1 __begin, _ForwardIterator1 __end, _OutputIterator __res) {
+ [__is_vector](_RandomAccessIterator1 __begin, _RandomAccessIterator1 __end, _RandomAccessIterator3 __res) {
return __internal::__brick_copy(__begin, __end, __res, __is_vector);
},
std::true_type());
// testing whether the sequences are intersected
- _ForwardIterator2 __left_bound_seq_2 = std::lower_bound(__first2, __last2, *__first1, __comp);
+ _RandomAccessIterator2 __left_bound_seq_2 = std::lower_bound(__first2, __last2, *__first1, __comp);
//{2} < {1}: seq 1 is wholly greater than seq 2, so, parallel copying just first sequence
if (__left_bound_seq_2 == __last2)
return __internal::__pattern_walk2_brick(
std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __result,
- [__is_vector](_ForwardIterator1 __begin, _ForwardIterator1 __end, _OutputIterator __res) {
+ [__is_vector](_RandomAccessIterator1 __begin, _RandomAccessIterator1 __end, _RandomAccessIterator3 __res) {
return __internal::__brick_copy(__begin, __end, __res, __is_vector);
},
std::true_type());
if (__n1 + __n2 > __set_algo_cut_off)
- return __parallel_set_op(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result,
- __comp, [](_DifferenceType __n, _DifferenceType) { return __n; },
- [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
- _ForwardIterator2 __last2, _Tp* __result, _Compare __comp) {
- return __pstl::__utils::__set_difference_construct(
- __first1, __last1, __first2, __last2, __result, __comp,
- __BrickCopyConstruct<_IsVector>());
- },
- __is_vector);
+ return __parallel_set_op(
+ std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp,
+ [](_DifferenceType __n, _DifferenceType) { return __n; },
+ [](_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
+ _RandomAccessIterator2 __last2, _Tp* __result, _Compare __comp) {
+ return __pstl::__utils::__set_difference_construct(__first1, __last1, __first2, __last2, __result,
+ __comp, __BrickCopyConstruct<_IsVector>());
+ },
+ __is_vector);
// use serial algorithm
return std::set_difference(__first1, __last1, __first2, __last2, __result, __comp);
@@ -3274,10 +3294,11 @@
return std::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
}
-template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare>
-_OutputIterator
-__brick_set_symmetric_difference(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
- _ForwardIterator2 __last2, _OutputIterator __result, _Compare __comp,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3, class _Compare>
+_RandomAccessIterator3
+__brick_set_symmetric_difference(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
+ _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2,
+ _RandomAccessIterator3 __result, _Compare __comp,
/*__is_vector=*/std::true_type) noexcept
{
_PSTL_PRAGMA_MESSAGE("Vectorized algorithm unimplemented, redirected to serial");
@@ -3295,12 +3316,13 @@
__is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator,
- class _Compare, class _IsVector>
-_OutputIterator
-__pattern_set_symmetric_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
- _ForwardIterator2 __first2, _ForwardIterator2 __last2, _OutputIterator __result,
- _Compare __comp, _IsVector __is_vector, /*is_parallel=*/std::true_type)
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2,
+ class _RandomAccessIterator3, class _Compare, class _IsVector>
+_RandomAccessIterator3
+__pattern_set_symmetric_difference(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1,
+ _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
+ _RandomAccessIterator2 __last2, _RandomAccessIterator3 __result, _Compare __comp,
+ _IsVector __is_vector, /*is_parallel=*/std::true_type)
{
const auto __n1 = __last1 - __first1;
@@ -3310,11 +3332,11 @@
if (__n1 + __n2 <= __set_algo_cut_off)
return std::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
- typedef typename std::iterator_traits<_OutputIterator>::value_type _Tp;
+ typedef typename std::iterator_traits<_RandomAccessIterator3>::value_type _Tp;
return __internal::__parallel_set_union_op(
std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp,
- [](_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2,
- _Tp* __result, _Compare __comp) {
+ [](_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
+ _RandomAccessIterator2 __last2, _Tp* __result, _Compare __comp) {
return __pstl::__utils::__set_symmetric_difference_construct(__first1, __last1, __first2, __last2, __result,
__comp, __BrickCopyConstruct<_IsVector>());
},
@@ -3410,9 +3432,9 @@
return std::min_element(__first, __last, __comp);
}
-template <typename _ForwardIterator, typename _Compare>
-_ForwardIterator
-__brick_min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp,
+template <typename _RandomAccessIterator, typename _Compare>
+_RandomAccessIterator
+__brick_min_element(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
/* __is_vector = */ std::true_type) noexcept
{
#if _PSTL_UDR_PRESENT
@@ -3465,9 +3487,9 @@
return std::minmax_element(__first, __last, __comp);
}
-template <typename _ForwardIterator, typename _Compare>
-std::pair<_ForwardIterator, _ForwardIterator>
-__brick_minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp,
+template <typename _RandomAccessIterator, typename _Compare>
+std::pair<_RandomAccessIterator, _RandomAccessIterator>
+__brick_minmax_element(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
/* __is_vector = */ std::true_type) noexcept
{
#if _PSTL_UDR_PRESENT
@@ -3485,20 +3507,20 @@
return __internal::__brick_minmax_element(__first, __last, __comp, __is_vector);
}
-template <typename _ExecutionPolicy, typename _ForwardIterator, typename _Compare, typename _IsVector>
-std::pair<_ForwardIterator, _ForwardIterator>
-__pattern_minmax_element(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp,
- _IsVector __is_vector, /* is_parallel = */ std::true_type)
+template <typename _ExecutionPolicy, typename _RandomAccessIterator, typename _Compare, typename _IsVector>
+std::pair<_RandomAccessIterator, _RandomAccessIterator>
+__pattern_minmax_element(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
+ _Compare __comp, _IsVector __is_vector, /* is_parallel = */ std::true_type)
{
if (__first == __last)
return std::make_pair(__first, __first);
return __internal::__except_handler([&]() {
- typedef std::pair<_ForwardIterator, _ForwardIterator> _Result;
+ typedef std::pair<_RandomAccessIterator, _RandomAccessIterator> _Result;
return __par_backend::__parallel_reduce(
std::forward<_ExecutionPolicy>(__exec), __first + 1, __last, std::make_pair(__first, __first),
- [=](_ForwardIterator __begin, _ForwardIterator __end, _Result __init) -> _Result {
+ [=](_RandomAccessIterator __begin, _RandomAccessIterator __end, _Result __init) -> _Result {
const _Result __subresult = __internal::__brick_minmax_element(__begin, __end, __comp, __is_vector);
return std::make_pair(
__internal::__cmp_iterators_by_values(__subresult.first, __init.first, __comp),
@@ -3538,10 +3560,10 @@
return __mismatch_serial(__first1, __last1, __first2, __last2, __pred);
}
-template <class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
-std::pair<_ForwardIterator1, _ForwardIterator2>
-__brick_mismatch(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
- _ForwardIterator2 __last2, _Predicate __pred, /* __is_vector = */ std::true_type) noexcept
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Predicate>
+std::pair<_RandomAccessIterator1, _RandomAccessIterator2>
+__brick_mismatch(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
+ _RandomAccessIterator2 __last2, _Predicate __pred, /* __is_vector = */ std::true_type) noexcept
{
auto __n = std::min(__last1 - __first1, __last2 - __first2);
return __unseq_backend::__simd_first(__first1, __n, __first2, std::not_fn(__pred));
@@ -3590,10 +3612,11 @@
return std::lexicographical_compare(__first1, __last1, __first2, __last2, __comp);
}
-template <class _ForwardIterator1, class _ForwardIterator2, class _Compare>
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Compare>
bool
-__brick_lexicographical_compare(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
- _ForwardIterator2 __last2, _Compare __comp, /* __is_vector = */ std::true_type) noexcept
+__brick_lexicographical_compare(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
+ _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _Compare __comp,
+ /* __is_vector = */ std::true_type) noexcept
{
if (__first2 == __last2)
{ // if second sequence is empty
@@ -3605,12 +3628,12 @@
}
else
{
- typedef typename std::iterator_traits<_ForwardIterator1>::reference ref_type1;
- typedef typename std::iterator_traits<_ForwardIterator2>::reference ref_type2;
+ typedef typename std::iterator_traits<_RandomAccessIterator1>::reference ref_type1;
+ typedef typename std::iterator_traits<_RandomAccessIterator2>::reference ref_type2;
--__last1;
--__last2;
auto __n = std::min(__last1 - __first1, __last2 - __first2);
- std::pair<_ForwardIterator1, _ForwardIterator2> __result = __unseq_backend::__simd_first(
+ std::pair<_RandomAccessIterator1, _RandomAccessIterator2> __result = __unseq_backend::__simd_first(
__first1, __n, __first2, [__comp](const ref_type1 __x, const ref_type2 __y) mutable {
return __comp(__x, __y) || __comp(__y, __x);
});
@@ -3635,11 +3658,13 @@
return __internal::__brick_lexicographical_compare(__first1, __last1, __first2, __last2, __comp, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Compare, class _IsVector>
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _Compare,
+ class _IsVector>
bool
-__pattern_lexicographical_compare(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
- _ForwardIterator2 __first2, _ForwardIterator2 __last2, _Compare __comp,
- _IsVector __is_vector, /* is_parallel = */ std::true_type) noexcept
+__pattern_lexicographical_compare(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1,
+ _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
+ _RandomAccessIterator2 __last2, _Compare __comp, _IsVector __is_vector,
+ /* is_parallel = */ std::true_type) noexcept
{
if (__first2 == __last2)
{ // if second sequence is empty
@@ -3651,14 +3676,14 @@
}
else
{
- typedef typename std::iterator_traits<_ForwardIterator1>::reference _RefType1;
- typedef typename std::iterator_traits<_ForwardIterator2>::reference _RefType2;
+ typedef typename std::iterator_traits<_RandomAccessIterator1>::reference _RefType1;
+ typedef typename std::iterator_traits<_RandomAccessIterator2>::reference _RefType2;
--__last1;
--__last2;
auto __n = std::min(__last1 - __first1, __last2 - __first2);
auto __result = __internal::__parallel_find(
std::forward<_ExecutionPolicy>(__exec), __first1, __first1 + __n,
- [__first1, __first2, &__comp, __is_vector](_ForwardIterator1 __i, _ForwardIterator1 __j) {
+ [__first1, __first2, &__comp, __is_vector](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j) {
return __internal::__brick_mismatch(__i, __j, __first2 + (__i - __first1), __first2 + (__j - __first1),
[&__comp](const _RefType1 __x, const _RefType2 __y) {
return !__comp(__x, __y) && !__comp(__y, __x);
@@ -3666,7 +3691,7 @@
__is_vector)
.first;
},
- std::less<typename std::iterator_traits<_ForwardIterator1>::difference_type>(), /*is_first=*/true);
+ std::less<typename std::iterator_traits<_RandomAccessIterator1>::difference_type>(), /*is_first=*/true);
if (__result == __last1 && __first2 + (__result - __first1) != __last2)
{ // if first sequence shorter than second
diff --git a/include/pstl/internal/memory_impl.h b/include/pstl/internal/memory_impl.h
index 1eb2fe4..942a30e 100644
--- a/include/pstl/internal/memory_impl.h
+++ b/include/pstl/internal/memory_impl.h
@@ -39,13 +39,13 @@
return __result;
}
-template <typename _ForwardIterator, typename _OutputIterator>
+template <typename _RandomAccessIterator, typename _OutputIterator>
_OutputIterator
-__brick_uninitialized_move(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
+__brick_uninitialized_move(_RandomAccessIterator __first, _RandomAccessIterator __last, _OutputIterator __result,
/*vector=*/std::true_type) noexcept
{
using __ValueType = typename std::iterator_traits<_OutputIterator>::value_type;
- using _ReferenceType1 = typename std::iterator_traits<_ForwardIterator>::reference;
+ using _ReferenceType1 = typename std::iterator_traits<_RandomAccessIterator>::reference;
using _ReferenceType2 = typename std::iterator_traits<_OutputIterator>::reference;
return __unseq_backend::__simd_walk_2(
@@ -63,12 +63,12 @@
__first->~_ValueType();
}
-template <typename _Iterator>
+template <typename _RandomAccessIterator>
void
-__brick_destroy(_Iterator __first, _Iterator __last, /*vector*/ std::true_type) noexcept
+__brick_destroy(_RandomAccessIterator __first, _RandomAccessIterator __last, /*vector*/ std::true_type) noexcept
{
- using _ValueType = typename std::iterator_traits<_Iterator>::value_type;
- using _ReferenceType = typename std::iterator_traits<_Iterator>::reference;
+ using _ValueType = typename std::iterator_traits<_RandomAccessIterator>::value_type;
+ using _ReferenceType = typename std::iterator_traits<_RandomAccessIterator>::reference;
__unseq_backend::__simd_walk_1(__first, __last - __first, [](_ReferenceType __x) { __x.~_ValueType(); });
}
@@ -90,13 +90,13 @@
return __result;
}
-template <typename _ForwardIterator, typename _OutputIterator>
+template <typename _RandomAccessIterator, typename _OutputIterator>
_OutputIterator
-__brick_uninitialized_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
+__brick_uninitialized_copy(_RandomAccessIterator __first, _RandomAccessIterator __last, _OutputIterator __result,
/*vector=*/std::true_type) noexcept
{
using __ValueType = typename std::iterator_traits<_OutputIterator>::value_type;
- using _ReferenceType1 = typename std::iterator_traits<_ForwardIterator>::reference;
+ using _ReferenceType1 = typename std::iterator_traits<_RandomAccessIterator>::reference;
using _ReferenceType2 = typename std::iterator_traits<_OutputIterator>::reference;
return __unseq_backend::__simd_walk_2(
diff --git a/include/pstl/internal/numeric_fwd.h b/include/pstl/internal/numeric_fwd.h
index 07d7f07..bcb3e2d 100644
--- a/include/pstl/internal/numeric_fwd.h
+++ b/include/pstl/internal/numeric_fwd.h
@@ -26,9 +26,10 @@
// transform_reduce (version with two binary functions, according to draft N4659)
//------------------------------------------------------------------------
-template <class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2>
-_Tp __brick_transform_reduce(_ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _Tp, _BinaryOperation1,
- _BinaryOperation2,
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Tp, class _BinaryOperation1,
+ class _BinaryOperation2>
+_Tp __brick_transform_reduce(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, _Tp,
+ _BinaryOperation1, _BinaryOperation2,
/*__is_vector=*/std::true_type) noexcept;
template <class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2>
@@ -54,8 +55,8 @@
// transform_reduce (version with unary and binary functions)
//------------------------------------------------------------------------
-template <class _ForwardIterator, class _Tp, class _UnaryOperation, class _BinaryOperation>
-_Tp __brick_transform_reduce(_ForwardIterator, _ForwardIterator, _Tp, _BinaryOperation, _UnaryOperation,
+template <class _RandomAccessIterator, class _Tp, class _UnaryOperation, class _BinaryOperation>
+_Tp __brick_transform_reduce(_RandomAccessIterator, _RandomAccessIterator, _Tp, _BinaryOperation, _UnaryOperation,
/*is_vector=*/std::true_type) noexcept;
template <class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
@@ -69,10 +70,10 @@
_UnaryOperation, _IsVector,
/*is_parallel=*/std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Tp, class _BinaryOperation, class _UnaryOperation,
class _IsVector>
_Tp
-__pattern_transform_reduce(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Tp, _BinaryOperation,
+__pattern_transform_reduce(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Tp, _BinaryOperation,
_UnaryOperation, _IsVector,
/*is_parallel=*/std::true_type);
@@ -87,8 +88,8 @@
_UnaryOperation, _Tp, _BinaryOperation,
/*Inclusive*/ std::false_type) noexcept;
-template <class _ForwardIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation>
-std::pair<_OutputIterator, _Tp> __brick_transform_scan(_ForwardIterator, _ForwardIterator, _OutputIterator,
+template <class _RandomAccessIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation>
+std::pair<_OutputIterator, _Tp> __brick_transform_scan(_RandomAccessIterator, _RandomAccessIterator, _OutputIterator,
_UnaryOperation, _Tp, _BinaryOperation,
/*Inclusive*/ std::true_type) noexcept;
@@ -119,8 +120,9 @@
_OutputIterator __brick_adjacent_difference(_ForwardIterator, _ForwardIterator, _OutputIterator, _BinaryOperation,
/*is_vector*/ std::false_type) noexcept;
-template <class _ForwardIterator, class _OutputIterator, class _BinaryOperation>
-_OutputIterator __brick_adjacent_difference(_ForwardIterator, _ForwardIterator, _OutputIterator, _BinaryOperation,
+template <class _RandomAccessIterator, class _OutputIterator, class _BinaryOperation>
+_OutputIterator __brick_adjacent_difference(_RandomAccessIterator, _RandomAccessIterator, _OutputIterator,
+ _BinaryOperation,
/*is_vector*/ std::true_type) noexcept;
template <class _ExecutionPolicy, class _ForwardIterator, class _OutputIterator, class _BinaryOperation,
@@ -129,11 +131,11 @@
__pattern_adjacent_difference(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _OutputIterator, _BinaryOperation,
_IsVector, /*is_parallel*/ std::false_type) noexcept;
-template <class _ExecutionPolicy, class _ForwardIterator, class _OutputIterator, class _BinaryOperation,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _OutputIterator, class _BinaryOperation,
class _IsVector>
_OutputIterator
-__pattern_adjacent_difference(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _OutputIterator, _BinaryOperation,
- _IsVector, /*is_parallel*/ std::true_type);
+__pattern_adjacent_difference(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _OutputIterator,
+ _BinaryOperation, _IsVector, /*is_parallel*/ std::true_type);
} // namespace __internal
} // namespace __pstl
diff --git a/include/pstl/internal/numeric_impl.h b/include/pstl/internal/numeric_impl.h
index 3e653bb..e90d865 100644
--- a/include/pstl/internal/numeric_impl.h
+++ b/include/pstl/internal/numeric_impl.h
@@ -40,13 +40,15 @@
return std::inner_product(__first1, __last1, __first2, __init, __binary_op1, __binary_op2);
}
-template <class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2>
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Tp, class _BinaryOperation1,
+ class _BinaryOperation2>
_Tp
-__brick_transform_reduce(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _Tp __init,
- _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2,
+__brick_transform_reduce(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
+ _RandomAccessIterator2 __first2, _Tp __init, _BinaryOperation1 __binary_op1,
+ _BinaryOperation2 __binary_op2,
/*is_vector=*/std::true_type) noexcept
{
- typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferenceType;
+ typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType;
return __unseq_backend::__simd_transform_reduce(
__last1 - __first1, __init, __binary_op1,
[=, &__binary_op2](_DifferenceType __i) { return __binary_op2(__first1[__i], __first2[__i]); });
@@ -98,12 +100,13 @@
return std::transform_reduce(__first, __last, __init, __binary_op, __unary_op);
}
-template <class _ForwardIterator, class _Tp, class _UnaryOperation, class _BinaryOperation>
+template <class _RandomAccessIterator, class _Tp, class _UnaryOperation, class _BinaryOperation>
_Tp
-__brick_transform_reduce(_ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation __binary_op,
- _UnaryOperation __unary_op, /*is_vector=*/std::true_type) noexcept
+__brick_transform_reduce(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp __init,
+ _BinaryOperation __binary_op, _UnaryOperation __unary_op,
+ /*is_vector=*/std::true_type) noexcept
{
- typedef typename std::iterator_traits<_ForwardIterator>::difference_type _DifferenceType;
+ typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
return __unseq_backend::__simd_transform_reduce(
__last - __first, __init, __binary_op,
[=, &__unary_op](_DifferenceType __i) { return __unary_op(__first[__i]); });
@@ -119,18 +122,18 @@
return __internal::__brick_transform_reduce(__first, __last, __init, __binary_op, __unary_op, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation,
+template <class _ExecutionPolicy, class _RandomAccessIterator, class _Tp, class _BinaryOperation, class _UnaryOperation,
class _IsVector>
_Tp
-__pattern_transform_reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init,
- _BinaryOperation __binary_op, _UnaryOperation __unary_op, _IsVector __is_vector,
+__pattern_transform_reduce(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
+ _Tp __init, _BinaryOperation __binary_op, _UnaryOperation __unary_op, _IsVector __is_vector,
/*is_parallel=*/std::true_type)
{
return __internal::__except_handler([&]() {
return __par_backend::__parallel_transform_reduce(
std::forward<_ExecutionPolicy>(__exec), __first, __last,
- [__unary_op](_ForwardIterator __i) mutable { return __unary_op(*__i); }, __init, __binary_op,
- [__unary_op, __binary_op, __is_vector](_ForwardIterator __i, _ForwardIterator __j, _Tp __init) {
+ [__unary_op](_RandomAccessIterator __i) mutable { return __unary_op(*__i); }, __init, __binary_op,
+ [__unary_op, __binary_op, __is_vector](_RandomAccessIterator __i, _RandomAccessIterator __j, _Tp __init) {
return __internal::__brick_transform_reduce(__i, __j, __init, __binary_op, __unary_op, __is_vector);
});
});
@@ -159,9 +162,9 @@
}
// Inclusive form
-template <class _ForwardIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation>
+template <class _RandomAccessIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation>
std::pair<_OutputIterator, _Tp>
-__brick_transform_scan(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
+__brick_transform_scan(_RandomAccessIterator __first, _RandomAccessIterator __last, _OutputIterator __result,
_UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op,
/*Inclusive*/ std::true_type, /*is_vector=*/std::false_type) noexcept
{
@@ -181,10 +184,10 @@
// [restriction] - T shall be DefaultConstructible.
// [violation] - default ctor of T shall set the identity value for binary_op.
-template <class _ForwardIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation,
+template <class _RandomAccessIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation,
class _Inclusive>
typename std::enable_if<!is_arithmetic_udop<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
-__brick_transform_scan(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
+__brick_transform_scan(_RandomAccessIterator __first, _RandomAccessIterator __last, _OutputIterator __result,
_UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op, _Inclusive,
/*is_vector=*/std::true_type) noexcept
{
@@ -198,10 +201,10 @@
#endif
}
-template <class _ForwardIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation,
+template <class _RandomAccessIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation,
class _Inclusive>
typename std::enable_if<is_arithmetic_udop<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
-__brick_transform_scan(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
+__brick_transform_scan(_RandomAccessIterator __first, _RandomAccessIterator __last, _OutputIterator __result,
_UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op, _Inclusive,
/*is_vector=*/std::true_type) noexcept
{
@@ -299,15 +302,16 @@
return std::adjacent_difference(__first, __last, __d_first, __op);
}
-template <class _ForwardIterator1, class _ForwardIterator2, class BinaryOperation>
-_ForwardIterator2
-__brick_adjacent_difference(_ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __d_first,
- BinaryOperation __op, /*is_vector=*/std::true_type) noexcept
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class BinaryOperation>
+_RandomAccessIterator2
+__brick_adjacent_difference(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last,
+ _RandomAccessIterator2 __d_first, BinaryOperation __op,
+ /*is_vector=*/std::true_type) noexcept
{
_PSTL_ASSERT(__first != __last);
- typedef typename std::iterator_traits<_ForwardIterator1>::reference _ReferenceType1;
- typedef typename std::iterator_traits<_ForwardIterator2>::reference _ReferenceType2;
+ typedef typename std::iterator_traits<_RandomAccessIterator1>::reference _ReferenceType1;
+ typedef typename std::iterator_traits<_RandomAccessIterator2>::reference _ReferenceType2;
auto __n = __last - __first;
*__d_first = *__first;
@@ -326,22 +330,22 @@
return __internal::__brick_adjacent_difference(__first, __last, __d_first, __op, __is_vector);
}
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation,
+template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _BinaryOperation,
class _IsVector>
-_ForwardIterator2
-__pattern_adjacent_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
- _ForwardIterator2 __d_first, _BinaryOperation __op, _IsVector __is_vector,
+_RandomAccessIterator2
+__pattern_adjacent_difference(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first, _RandomAccessIterator1 __last,
+ _RandomAccessIterator2 __d_first, _BinaryOperation __op, _IsVector __is_vector,
/*is_parallel=*/std::true_type)
{
_PSTL_ASSERT(__first != __last);
- typedef typename std::iterator_traits<_ForwardIterator1>::reference _ReferenceType1;
- typedef typename std::iterator_traits<_ForwardIterator2>::reference _ReferenceType2;
+ typedef typename std::iterator_traits<_RandomAccessIterator1>::reference _ReferenceType1;
+ typedef typename std::iterator_traits<_RandomAccessIterator2>::reference _ReferenceType2;
*__d_first = *__first;
__par_backend::__parallel_for(
std::forward<_ExecutionPolicy>(__exec), __first, __last - 1,
- [&__op, __is_vector, __d_first, __first](_ForwardIterator1 __b, _ForwardIterator1 __e) {
- _ForwardIterator2 __d_b = __d_first + (__b - __first);
+ [&__op, __is_vector, __d_first, __first](_RandomAccessIterator1 __b, _RandomAccessIterator1 __e) {
+ _RandomAccessIterator2 __d_b = __d_first + (__b - __first);
__internal::__brick_walk3(
__b, __e, __b + 1, __d_b + 1,
[&__op](_ReferenceType1 __x, _ReferenceType1 __y, _ReferenceType2 __z) { __z = __op(__y, __x); },
