[v3 PATCH] Implement C++17 string searchers.

[Jonathan Wakely]

On 12/09/16 02:48 +0300, Ville Voutilainen wrote:
>The first patch just transforms the TS version into an std one, the second
>patch makes it conform by implementing P0253R1. I haven't added
>any tests for the pair-seconds of the new api, and I noticed that we
>might want to go through our make_pairs and make_tuples and qualify
>them throughout the library, where applicable. Such things can be
>added with subsequent patches.
>
>2016-09-12  Ville Voutilainen  <ville.voutilainen@gmail.com>
>
>    Implement C++17 string searchers.
>    * include/std/functional: (unordered_map, vector): New includes
>    in C++17 mode.
>    (array, bits/stl_algo.h): Likewise.
>    (default_searcher, __boyer_moore_map_base): New.
>    (__boyer_moore_array_base, __is_std_equal_to): Likewise.
>    (__boyer_moore_base_t, boyer_moore_searcher): Likewise.
>    (boyer_moore_horspool_searcher, make_default_searcher): Likewise.
>    (make_boyer_moore_searcher): Likewise.
>    (make_boyer_moore_horspool_searcher): Likewise.
>    * testsuite/20_util/function_objects/searchers.cc: New.

I wrote this code, so obviously I think it's totally awesome ;-)


>2016-09-12  Ville Voutilainen  <ville.voutilainen@gmail.com>
>
>    Implement P0253R1, Fixing a design mistake in the searchers
>    interface in Library Fundamentals.
>    * include/std/functional: (utility): New include in C++17 mode.
>    (default_searcher): Use a pair as return type, adjust the definition.
>    (boyer_moore_searcher): Likewise.
>    (boyer_moore_horspool_searcher): Likewise.
>    * testsuite/20_util/function_objects/searchers.cc: Adjust.

This looks good too. One question below.


>+  template<typename _Pred>
>+    struct __is_std_equal_to : std::false_type { };
>+
>+  template<>
>+    struct __is_std_equal_to<std::equal_to<void>> : std::true_type { };

Is there a reason I didn't use an alias template or variable template here?

  template<typename _Pred>
    using __is_std_equal_to = is_same<equal_to<void>, _Pred>;

That avoids defining a new class template.

>+  // Use __boyer_moore_array_base when pattern consists of narrow characters
>+  // and uses std::equal_to as the predicate.
>+  template<typename _RAIter, typename _Hash, typename _Pred,
>+           typename _Val = typename iterator_traits<_RAIter>::value_type,
>+	   typename _Diff = typename iterator_traits<_RAIter>::difference_type>
>+    using __boyer_moore_base_t
>+      = std::conditional_t<sizeof(_Val) == 1 && is_integral<_Val>::value
>+			   && __is_std_equal_to<_Pred>::value,

Could be __and_<is_integral<_Val>, __is_std_equal_to<_Pred>>::value
but it doesn't make a lot of difference.


>@@ -2217,12 +2218,17 @@ _GLIBCXX_MEM_FN_TRAITS(&&, false_type, true_type)
>       { }
>
>       template<typename _ForwardIterator2>
>-	_ForwardIterator2
>+        pair<_ForwardIterator2, _ForwardIterator2>
> 	operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const
> 	{
>-	  return std::search(__first, __last,
>-			     std::get<0>(_M_m), std::get<1>(_M_m),
>-			     std::get<2>(_M_m));
>+	  _ForwardIterator2 __first_ret =
>+	    std::search(__first, __last,
>+			std::get<0>(_M_m), std::get<1>(_M_m),
>+			std::get<2>(_M_m));
>+	  _ForwardIterator2 __second_ret = __first_ret == __last ?
>+	    __last :  std::next(__first_ret, std::distance(std::get<0>(_M_m),
>+							   std::get<1>(_M_m)));
>+	  return std::make_pair(__first_ret, __second_ret);

This could be simply return { __first_ret, __second_ret };

Does using make_pair have any advantage? (I don't think we need to
worry about iterators with explicit copy constructors.)