Tested x86_64-linux.
-- >8 --
There doesn't seem to be a lot of benefit in reusing __find_if with
__gnu_cxx::__ops predicates, since they aren't going to actually
instantiate any less code if we use different predicates every time
(e.g. __ops::__negate, or __ops::__iter_equals_val, or
__ops::__pred_iter).
And now that std::find no longer calls __find_if (because it just does a
loop directly), we can make the _Iter_equals_val case of __find_if call
std::find, to take advantage of its memchr optimization. This benefits
other algos like search_n which use __find_if with _Iter_equals_val.
libstdc++-v3/ChangeLog:
* include/bits/stl_algo.h (__find_if_not): Do loop here instead
of using __find_if with __gnu_cxx::__ops predicate.
(find_if): Likewise.
(find): Move to ...
* include/bits/stl_algobase.h (find): ... here.
(__find_if): Overload for _Iter_equals_val predicate.
---
libstdc++-v3/include/bits/stl_algo.h | 63 +++---------------------
libstdc++-v3/include/bits/stl_algobase.h | 61 +++++++++++++++++++++++
2 files changed, 68 insertions(+), 56 deletions(-)
diff --git a/libstdc++-v3/include/bits/stl_algo.h
b/libstdc++-v3/include/bits/stl_algo.h
index 489ce7e14d2..05c1dbd07b6 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -105,15 +105,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
std::iter_swap(__result, __b);
}
- /// Provided for stable_partition to use.
+ // Used by std::find_if_not and __stable_partition.
template<typename _InputIterator, typename _Predicate>
_GLIBCXX20_CONSTEXPR
inline _InputIterator
__find_if_not(_InputIterator __first, _InputIterator __last,
_Predicate __pred)
{
- return std::__find_if(__first, __last,
- __gnu_cxx::__ops::__negate(__pred));
+ while (__first != __last && __pred(__first))
+ ++__first;
+ return __first;
}
/// Like find_if_not(), but uses and updates a count of the
@@ -3810,57 +3811,6 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
}
#endif // C++17
- /**
- * @brief Find the first occurrence of a value in a sequence.
- * @ingroup non_mutating_algorithms
- * @param __first An input iterator.
- * @param __last An input iterator.
- * @param __val The value to find.
- * @return The first iterator @c i in the range @p [__first,__last)
- * such that @c *i == @p __val, or @p __last if no such iterator exists.
- */
- template<typename _InputIterator, typename _Tp>
- _GLIBCXX20_CONSTEXPR
- inline _InputIterator
- find(_InputIterator __first, _InputIterator __last, const _Tp& __val)
- {
- // concept requirements
- __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
- __glibcxx_function_requires(_EqualOpConcept<
- typename iterator_traits<_InputIterator>::value_type, _Tp>)
- __glibcxx_requires_valid_range(__first, __last);
-
-#if __cpp_if_constexpr && __glibcxx_type_trait_variable_templates
- using _ValT = typename iterator_traits<_InputIterator>::value_type;
- if constexpr (__can_use_memchr_for_find<_ValT, _Tp>)
- if constexpr (is_pointer_v<decltype(std::__niter_base(__first))>
-#if __cpp_lib_concepts
- || contiguous_iterator<_InputIterator>
-#endif
- )
- {
- // If conversion to the 1-byte value_type alters the value,
- // it would not be found by std::find using equality comparison.
- // We need to check this here, because otherwise something like
- // memchr("a", 'a'+256, 1) would give a false positive match.
- if (!(static_cast<_ValT>(__val) == __val))
- return __last;
- else if (!__is_constant_evaluated())
- {
- const void* __p0 = std::__to_address(__first);
- const int __ival = static_cast<int>(__val);
- if (auto __n = std::distance(__first, __last); __n > 0)
- if (auto __p1 = __builtin_memchr(__p0, __ival, __n))
- return __first + ((const char*)__p1 - (const char*)__p0);
- return __last;
- }
- }
-#endif
-
- return std::__find_if(__first, __last,
- __gnu_cxx::__ops::__iter_equals_val(__val));
- }
-
/**
* @brief Find the first element in a sequence for which a
* predicate is true.
@@ -3883,8 +3833,9 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
typename iterator_traits<_InputIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- return std::__find_if(__first, __last,
- __gnu_cxx::__ops::__pred_iter(__pred));
+ while (__first != __last && !__pred(*__first))
+ ++__first;
+ return __first;
}
/**
diff --git a/libstdc++-v3/include/bits/stl_algobase.h
b/libstdc++-v3/include/bits/stl_algobase.h
index 5f77b00be9b..34e1cf7322f 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -2077,6 +2077,58 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
}
#endif
+ /**
+ * @brief Find the first occurrence of a value in a sequence.
+ * @ingroup non_mutating_algorithms
+ * @param __first An input iterator.
+ * @param __last An input iterator.
+ * @param __val The value to find.
+ * @return The first iterator @c i in the range @p [__first,__last)
+ * such that @c *i == @p __val, or @p __last if no such iterator exists.
+ */
+ template<typename _InputIterator, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
+ inline _InputIterator
+ find(_InputIterator __first, _InputIterator __last, const _Tp& __val)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
+ __glibcxx_function_requires(_EqualOpConcept<
+ typename iterator_traits<_InputIterator>::value_type, _Tp>)
+ __glibcxx_requires_valid_range(__first, __last);
+
+#if __cpp_if_constexpr && __glibcxx_type_trait_variable_templates
+ using _ValT = typename iterator_traits<_InputIterator>::value_type;
+ if constexpr (__can_use_memchr_for_find<_ValT, _Tp>)
+ if constexpr (is_pointer_v<decltype(std::__niter_base(__first))>
+#if __cpp_lib_concepts
+ || contiguous_iterator<_InputIterator>
+#endif
+ )
+ {
+ // If conversion to the 1-byte value_type alters the value,
+ // it would not be found by std::find using equality comparison.
+ // We need to check this here, because otherwise something like
+ // memchr("a", 'a'+256, 1) would give a false positive match.
+ if (!(static_cast<_ValT>(__val) == __val))
+ return __last;
+ else if (!__is_constant_evaluated())
+ {
+ const void* __p0 = std::__to_address(__first);
+ const int __ival = static_cast<int>(__val);
+ if (auto __n = std::distance(__first, __last); __n > 0)
+ if (auto __p1 = __builtin_memchr(__p0, __ival, __n))
+ return __first + ((const char*)__p1 - (const char*)__p0);
+ return __last;
+ }
+ }
+#endif
+
+ while (__first != __last && !(*__first == __val))
+ ++__first;
+ return __first;
+ }
+
_GLIBCXX_END_NAMESPACE_ALGO
// Implementation of std::find_if, also used in std::remove_if and others.
@@ -2091,6 +2143,15 @@ _GLIBCXX_END_NAMESPACE_ALGO
return __first;
}
+ // When the predicate is just comparing to a value we can use std::find,
+ // which is optimized to memchr for some types.
+ template<typename _Iterator, typename _Value>
+ _GLIBCXX20_CONSTEXPR
+ inline _Iterator
+ __find_if(_Iterator __first, _Iterator __last,
+ __gnu_cxx::__ops::_Iter_equals_val<_Value> __pred)
+ { return _GLIBCXX_STD_A::find(__first, __last, __pred._M_value); }
+
template<typename _InputIterator, typename _Predicate>
_GLIBCXX20_CONSTEXPR
typename iterator_traits<_InputIterator>::difference_type
--
2.46.2
