// count
// count_if
// search
-
- template<typename _ForwardIterator1, typename _ForwardIterator2,
- typename _BinaryPredicate>
- _GLIBCXX20_CONSTEXPR
- _ForwardIterator1
- __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
- _ForwardIterator2 __first2, _ForwardIterator2 __last2,
- _BinaryPredicate __predicate)
- {
- // Test for empty ranges
- if (__first1 == __last1 || __first2 == __last2)
- return __first1;
-
- // Test for a pattern of length 1.
- _ForwardIterator2 __p1(__first2);
- if (++__p1 == __last2)
- return std::__find_if(__first1, __last1,
- __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
-
- // General case.
- _ForwardIterator1 __current = __first1;
-
- for (;;)
- {
- __first1 =
- std::__find_if(__first1, __last1,
- __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
-
- if (__first1 == __last1)
- return __last1;
-
- _ForwardIterator2 __p = __p1;
- __current = __first1;
- if (++__current == __last1)
- return __last1;
-
- while (__predicate(__current, __p))
- {
- if (++__p == __last2)
- return __first1;
- if (++__current == __last1)
- return __last1;
- }
- ++__first1;
- }
- return __first1;
- }
-
// search_n
/**
__gnu_cxx::__ops::__iter_equal_to_iter());
}
- /**
- * @brief Search a sequence for a matching sub-sequence using a predicate.
- * @ingroup non_mutating_algorithms
- * @param __first1 A forward iterator.
- * @param __last1 A forward iterator.
- * @param __first2 A forward iterator.
- * @param __last2 A forward iterator.
- * @param __predicate A binary predicate.
- * @return The first iterator @c i in the range
- * @p [__first1,__last1-(__last2-__first2)) such that
- * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
- * @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
- *
- * Searches the range @p [__first1,__last1) for a sub-sequence that
- * compares equal value-by-value with the sequence given by @p
- * [__first2,__last2), using @p __predicate to determine equality,
- * and returns an iterator to the first element of the
- * sub-sequence, or @p __last1 if no such iterator exists.
- *
- * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
- */
- template<typename _ForwardIterator1, typename _ForwardIterator2,
- typename _BinaryPredicate>
- _GLIBCXX20_CONSTEXPR
- inline _ForwardIterator1
- search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
- _ForwardIterator2 __first2, _ForwardIterator2 __last2,
- _BinaryPredicate __predicate)
- {
- // concept requirements
- __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
- __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
- __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
- typename iterator_traits<_ForwardIterator1>::value_type,
- typename iterator_traits<_ForwardIterator2>::value_type>)
- __glibcxx_requires_valid_range(__first1, __last1);
- __glibcxx_requires_valid_range(__first2, __last2);
-
- return std::__search(__first1, __last1, __first2, __last2,
- __gnu_cxx::__ops::__iter_comp_iter(__predicate));
- }
-
/**
* @brief Search a sequence for a number of consecutive values.
* @ingroup non_mutating_algorithms
return __result;
}
+ template<typename _ForwardIterator1, typename _ForwardIterator2,
+ typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
+ _ForwardIterator1
+ __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+ _ForwardIterator2 __first2, _ForwardIterator2 __last2,
+ _BinaryPredicate __predicate)
+ {
+ // Test for empty ranges
+ if (__first1 == __last1 || __first2 == __last2)
+ return __first1;
+
+ // Test for a pattern of length 1.
+ _ForwardIterator2 __p1(__first2);
+ if (++__p1 == __last2)
+ return std::__find_if(__first1, __last1,
+ __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
+
+ // General case.
+ _ForwardIterator1 __current = __first1;
+
+ for (;;)
+ {
+ __first1 =
+ std::__find_if(__first1, __last1,
+ __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
+
+ if (__first1 == __last1)
+ return __last1;
+
+ _ForwardIterator2 __p = __p1;
+ __current = __first1;
+ if (++__current == __last1)
+ return __last1;
+
+ while (__predicate(__current, __p))
+ {
+ if (++__p == __last2)
+ return __first1;
+ if (++__current == __last1)
+ return __last1;
+ }
+ ++__first1;
+ }
+ return __first1;
+ }
+
#if __cplusplus >= 201103L
template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
}
#endif // C++11
+_GLIBCXX_BEGIN_NAMESPACE_ALGO
+
+ /**
+ * @brief Search a sequence for a matching sub-sequence using a predicate.
+ * @ingroup non_mutating_algorithms
+ * @param __first1 A forward iterator.
+ * @param __last1 A forward iterator.
+ * @param __first2 A forward iterator.
+ * @param __last2 A forward iterator.
+ * @param __predicate A binary predicate.
+ * @return The first iterator @c i in the range
+ * @p [__first1,__last1-(__last2-__first2)) such that
+ * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
+ * @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
+ *
+ * Searches the range @p [__first1,__last1) for a sub-sequence that
+ * compares equal value-by-value with the sequence given by @p
+ * [__first2,__last2), using @p __predicate to determine equality,
+ * and returns an iterator to the first element of the
+ * sub-sequence, or @p __last1 if no such iterator exists.
+ *
+ * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
+ */
+ template<typename _ForwardIterator1, typename _ForwardIterator2,
+ typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
+ inline _ForwardIterator1
+ search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+ _ForwardIterator2 __first2, _ForwardIterator2 __last2,
+ _BinaryPredicate __predicate)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
+ __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
+ __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
+ typename iterator_traits<_ForwardIterator1>::value_type,
+ typename iterator_traits<_ForwardIterator2>::value_type>)
+ __glibcxx_requires_valid_range(__first1, __last1);
+ __glibcxx_requires_valid_range(__first2, __last2);
+
+ return std::__search(__first1, __last1, __first2, __last2,
+ __gnu_cxx::__ops::__iter_comp_iter(__predicate));
+ }
+
+_GLIBCXX_END_NAMESPACE_ALGO
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
#include <unordered_map>
#include <vector>
#include <array>
-#include <bits/stl_algo.h>
-#ifdef _GLIBCXX_PARALLEL
-# include <parallel/algorithm> // For std::__parallel::search
-#endif
+#include <bits/stl_algobase.h> // std::max, std::search
#include <experimental/bits/lfts_config.h>
namespace std _GLIBCXX_VISIBILITY(default)
std::__iterator_category(__begin2));
}
- // Public interface.
- template<typename _FIterator1, typename _FIterator2,
- typename _BinaryPredicate>
- inline _FIterator1
- search(_FIterator1 __begin1, _FIterator1 __end1,
- _FIterator2 __begin2, _FIterator2 __end2,
- _BinaryPredicate __pred, __gnu_parallel::sequential_tag)
- { return _GLIBCXX_STD_A::search(
- __begin1, __end1, __begin2, __end2, __pred); }
-
- // Parallel algorithm for random access iterator.
- template<typename _RAIter1, typename _RAIter2,
- typename _BinaryPredicate>
- _RAIter1
- __search_switch(_RAIter1 __begin1, _RAIter1 __end1,
- _RAIter2 __begin2, _RAIter2 __end2,
- _BinaryPredicate __pred,
- random_access_iterator_tag, random_access_iterator_tag)
- {
- if (_GLIBCXX_PARALLEL_CONDITION(
- static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
- >= __gnu_parallel::_Settings::get().search_minimal_n))
- return __gnu_parallel::__search_template(__begin1, __end1,
- __begin2, __end2, __pred);
- else
- return search(__begin1, __end1, __begin2, __end2, __pred,
- __gnu_parallel::sequential_tag());
- }
-
- // Sequential fallback for input iterator case
- template<typename _FIterator1, typename _FIterator2,
- typename _BinaryPredicate, typename _IteratorTag1,
- typename _IteratorTag2>
- inline _FIterator1
- __search_switch(_FIterator1 __begin1, _FIterator1 __end1,
- _FIterator2 __begin2, _FIterator2 __end2,
- _BinaryPredicate __pred, _IteratorTag1, _IteratorTag2)
- { return search(__begin1, __end1, __begin2, __end2, __pred,
- __gnu_parallel::sequential_tag()); }
-
- // Public interface
- template<typename _FIterator1, typename _FIterator2,
- typename _BinaryPredicate>
- inline _FIterator1
- search(_FIterator1 __begin1, _FIterator1 __end1,
- _FIterator2 __begin2, _FIterator2 __end2,
- _BinaryPredicate __pred)
- {
- return __search_switch(__begin1, __end1, __begin2, __end2, __pred,
- std::__iterator_category(__begin1),
- std::__iterator_category(__begin2));
- }
-
#if __cplusplus >= 201703L
/** @brief Search a sequence using a Searcher object.
*
#if __cpp_lib_three_way_comparison
using _GLIBCXX_STD_A::lexicographical_compare_three_way;
#endif
-} // end namespace
-} // end namespace
+
+ // Public interface.
+ template<typename _FIterator1, typename _FIterator2,
+ typename _BinaryPredicate>
+ inline _FIterator1
+ search(_FIterator1 __begin1, _FIterator1 __end1,
+ _FIterator2 __begin2, _FIterator2 __end2,
+ _BinaryPredicate __pred, __gnu_parallel::sequential_tag)
+ { return _GLIBCXX_STD_A::search(
+ __begin1, __end1, __begin2, __end2, __pred); }
+
+ // Parallel algorithm for random access iterator.
+ template<typename _RAIter1, typename _RAIter2,
+ typename _BinaryPredicate>
+ _RAIter1
+ __search_switch(_RAIter1 __begin1, _RAIter1 __end1,
+ _RAIter2 __begin2, _RAIter2 __end2,
+ _BinaryPredicate __pred,
+ random_access_iterator_tag, random_access_iterator_tag)
+ {
+ if (_GLIBCXX_PARALLEL_CONDITION(
+ static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
+ >= __gnu_parallel::_Settings::get().search_minimal_n))
+ return __gnu_parallel::__search_template(__begin1, __end1,
+ __begin2, __end2, __pred);
+ else
+ return search(__begin1, __end1, __begin2, __end2, __pred,
+ __gnu_parallel::sequential_tag());
+ }
+
+ // Sequential fallback for input iterator case
+ template<typename _FIterator1, typename _FIterator2,
+ typename _BinaryPredicate, typename _IteratorTag1,
+ typename _IteratorTag2>
+ inline _FIterator1
+ __search_switch(_FIterator1 __begin1, _FIterator1 __end1,
+ _FIterator2 __begin2, _FIterator2 __end2,
+ _BinaryPredicate __pred, _IteratorTag1, _IteratorTag2)
+ { return search(__begin1, __end1, __begin2, __end2, __pred,
+ __gnu_parallel::sequential_tag()); }
+
+ // Public interface
+ template<typename _FIterator1, typename _FIterator2,
+ typename _BinaryPredicate>
+ inline _FIterator1
+ search(_FIterator1 __begin1, _FIterator1 __end1,
+ _FIterator2 __begin2, _FIterator2 __end2,
+ _BinaryPredicate __pred)
+ {
+ return __search_switch(__begin1, __end1, __begin2, __end2, __pred,
+ std::__iterator_category(__begin1),
+ std::__iterator_category(__begin2));
+ }
+} // end namespace __parallel
+} // end namespace std
#endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */
# include <vector>
# include <array>
# endif
-# include <bits/stl_algo.h> // std::search
+# include <bits/stl_algobase.h> // std::search
#endif
#if __cplusplus >= 202002L
# include <bits/ranges_cmp.h> // std::identity, ranges::equal_to etc.
projects / thirdparty / gcc.git / commitdiff
