Optimize std::sub_match comparisons using string_view-like type

Message ID 20180702203052.GA29634@redhat.com
State New
Headers show
Series
  • Optimize std::sub_match comparisons using string_view-like type
Related show

Commit Message

Jonathan Wakely July 2, 2018, 8:30 p.m.
Avoid creation of unnecessary basic_string objects by using a simplified
string_view type and performing comparisons on that type instead. A
temporary basic_string object is still used when the sub_match's
iterators are not contiguous, in order to get an object that the
__string_view can reference.

	* include/bits/regex.h (sub_match::operator string_type): Call str().
	(sub_match::compare): Use _M_str() instead of str().
	(sub_match::_M_compare): New public function.
	(sub_match::__string_view): New helper type.
	(sub_match::_M_str): New overloaded functions to avoid creating a
	string_type object when not needed.
	(operator==, operator!=, operator<, operator>, operator<=, operator>=):
	Use sub_match::_M_compare instead of creating string_type objects.
	Fix Doxygen comments.
	* include/bits/regex_compiler.h (__has_contiguous_iter): Remove.
	(__is_contiguous_normal_iter): Rename to __is_contiguous_iter and
	simplify.
	(__enable_if_contiguous_iter, __disable_if_contiguous_iter): Use
	__enable_if_t.
	* include/std/type_traits (__enable_if_t): Define for C++11.
	* testsuite/28_regex/sub_match/compare.cc: New.
	* testsuite/util/testsuite_iterators.h (remove_cv): Add transformation
	trait.
	(input_iterator_wrapper): Use remove_cv for value_type argument of
	std::iterator base class.

We could avoid temporary string_type objects even for non-contiguous
iterators by writing a manual "compare" function that uses
char_traits::lt on every element in the iterator ranges. It's not
obvious that would actually be an optimization (and I haven't measured
it). For sub-expression matches that fit in an SSO buffer creating a
string doesn't allocate, and once we have a std::string or
std::wstring we benefit from highly optimized strncmp or wcsncmp
implementations in glibc. Maybe we could use an adaptive approach
where we create a string when value_type is char or wchar_t, and
_BiIter is random-access, and std:distance(first, second) <= SSO size.
Otherwise we'd use a manual loop using char_traits::lt. I don't plan
to work on that, the common cases are all likely to be using pointers
or basic_string::const_iterator and so already optimized by this
patch.

Tested powerpc64le-linux, committed to trunk.
commit b6d43fcbdd4987c3bcb48960dc05a1145deca747
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Mon Jul 2 18:34:09 2018 +0100

    Optimize std::sub_match comparisons using string_view-like type
    
    Avoid creation of unnecessary basic_string objects by using a simplified
    string_view type and performing comparisons on that type instead. A
    temporary basic_string object is still used when the sub_match's
    iterators are not contiguous, in order to get an object that the
    __string_view can reference.
    
            * include/bits/regex.h (sub_match::operator string_type): Call str().
            (sub_match::compare): Use _M_str() instead of str().
            (sub_match::_M_compare): New public function.
            (sub_match::__string_view): New helper type.
            (sub_match::_M_str): New overloaded functions to avoid creating a
            string_type object when not needed.
            (operator==, operator!=, operator<, operator>, operator<=, operator>=):
            Use sub_match::_M_compare instead of creating string_type objects.
            Fix Doxygen comments.
            * include/bits/regex_compiler.h (__has_contiguous_iter): Remove.
            (__is_contiguous_normal_iter): Rename to __is_contiguous_iter and
            simplify.
            (__enable_if_contiguous_iter, __disable_if_contiguous_iter): Use
            __enable_if_t.
            * include/std/type_traits (__enable_if_t): Define for C++11.
            * testsuite/28_regex/sub_match/compare.cc: New.
            * testsuite/util/testsuite_iterators.h (remove_cv): Add transformation
            trait.
            (input_iterator_wrapper): Use remove_cv for value_type argument of
            std::iterator base class.

Patch

diff --git a/libstdc++-v3/include/bits/regex.h b/libstdc++-v3/include/bits/regex.h
index 6b6501e98ae..af6fe3f0d79 100644
--- a/libstdc++-v3/include/bits/regex.h
+++ b/libstdc++-v3/include/bits/regex.h
@@ -42,8 +42,7 @@  _GLIBCXX_END_NAMESPACE_CXX11
 
 namespace __detail
 {
-  enum class _RegexExecutorPolicy : int
-    { _S_auto, _S_alternate };
+  enum class _RegexExecutorPolicy : int { _S_auto, _S_alternate };
 
   template<typename _BiIter, typename _Alloc,
 	   typename _CharT, typename _TraitsT,
@@ -847,7 +846,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { __lhs.swap(__rhs); }
 
 
-  // [7.9] Class template sub_match
+  // C++11 28.9 [re.submatch] Class template sub_match
   /**
    * A sequence of characters matched by a particular marked sub-expression.
    *
@@ -875,9 +874,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
 
       constexpr sub_match() noexcept : matched() { }
 
-      /**
-       * Gets the length of the matching sequence.
-       */
+      /// Gets the length of the matching sequence.
       difference_type
       length() const noexcept
       { return this->matched ? std::distance(this->first, this->second) : 0; }
@@ -893,11 +890,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
        * from the unwary.
        */
       operator string_type() const
-      {
-	return this->matched
-	  ? string_type(this->first, this->second)
-	  : string_type();
-      }
+      { return str(); }
 
       /**
        * @brief Gets the matching sequence as a string.
@@ -923,9 +916,10 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
        */
       int
       compare(const sub_match& __s) const
-      { return this->str().compare(__s.str()); }
+      { return this->_M_str().compare(__s._M_str()); }
 
       /**
+       * @{
        * @brief Compares this sub_match to a string.
        *
        * @param __s A string to compare to this sub_match.
@@ -936,20 +930,72 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
        */
       int
       compare(const string_type& __s) const
-      { return this->str().compare(__s); }
+      { return this->_M_str().compare(__s); }
 
-      /**
-       * @brief Compares this sub_match to a C-style string.
-       *
-       * @param __s A C-style string to compare to this sub_match.
-       *
-       * @retval <0 this matched sequence will collate before @p __s.
-       * @retval =0 this matched sequence is equivalent to @p __s.
-       * @retval <0 this matched sequence will collate after @p __s.
-       */
       int
       compare(const value_type* __s) const
-      { return this->str().compare(__s); }
+      { return this->_M_str().compare(__s); }
+      // @}
+
+      // Non-standard, used by comparison operators
+      int
+      _M_compare(const value_type* __s, size_t __n) const
+      { return this->_M_str().compare({__s, __n}); }
+
+    private:
+      // Simplified basic_string_view for C++11
+      struct __string_view
+      {
+	using traits_type = typename string_type::traits_type;
+
+	__string_view() = default;
+
+	__string_view(const value_type* __s, size_t __n) noexcept
+	: _M_data(__s), _M_len(__n) { }
+
+	__string_view(const value_type* __s) noexcept
+	: _M_data(__s), _M_len(traits_type::length(__s)) { }
+
+	__string_view(const string_type& __s) noexcept
+	: _M_data(__s.data()), _M_len(__s.length()) { }
+
+	int
+	compare(__string_view __s) const noexcept
+	{
+	  if (const size_t __n = std::min(_M_len, __s._M_len))
+	    if (int __ret = traits_type::compare(_M_data, __s._M_data, __n))
+	      return __ret;
+	  const difference_type __diff = _M_len - __s._M_len;
+	  if (__diff > std::numeric_limits<int>::max())
+	    return std::numeric_limits<int>::max();
+	  if (__diff < std::numeric_limits<int>::min())
+	    return std::numeric_limits<int>::min();
+	  return static_cast<int>(__diff);
+	}
+
+      private:
+	const value_type* _M_data = nullptr;
+	size_t _M_len = 0;
+      };
+
+      // Create a __string_view over the iterator range.
+      template<typename _Iter = _BiIter>
+	__enable_if_t<__detail::__is_contiguous_iter<_Iter>::value,
+		      __string_view>
+	_M_str() const noexcept
+	{
+	  if (this->matched)
+	    if (auto __len = this->second - this->first)
+	      return { std::__addressof(*this->first), __len };
+	  return {};
+	}
+
+      // Create a temporary string that can be converted to __string_view.
+      template<typename _Iter = _BiIter>
+	__enable_if_t<!__detail::__is_contiguous_iter<_Iter>::value,
+		      string_type>
+	_M_str() const
+	{ return str(); }
     };
 
 
@@ -1035,7 +1081,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     operator>(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
     { return __lhs.compare(__rhs) > 0; }
 
-  // Alias for sub_match'd string.
+  // Alias for a basic_string that can be compared to a sub_match.
   template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc>
     using __sub_match_string = basic_string<
 			      typename iterator_traits<_Bi_iter>::value_type,
@@ -1052,10 +1098,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     inline bool
     operator==(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
 	       const sub_match<_Bi_iter>& __rhs)
-    {
-      typedef typename sub_match<_Bi_iter>::string_type string_type;
-      return __rhs.compare(string_type(__lhs.data(), __lhs.size())) == 0;
-    }
+    { return __rhs._M_compare(__lhs.data(), __lhs.size()) == 0; }
 
   /**
    * @brief Tests the inequivalence of a string and a regular expression
@@ -1080,10 +1123,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     inline bool
     operator<(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
 	      const sub_match<_Bi_iter>& __rhs)
-    {
-      typedef typename sub_match<_Bi_iter>::string_type string_type;
-      return __rhs.compare(string_type(__lhs.data(), __lhs.size())) > 0;
-    }
+    { return __rhs._M_compare(__lhs.data(), __lhs.size()) > 0; }
 
   /**
    * @brief Tests the ordering of a string and a regular expression submatch.
@@ -1132,10 +1172,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     inline bool
     operator==(const sub_match<_Bi_iter>& __lhs,
 	       const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __rhs)
-    {
-      typedef typename sub_match<_Bi_iter>::string_type string_type;
-      return __lhs.compare(string_type(__rhs.data(), __rhs.size())) == 0;
-    }
+    { return __lhs._M_compare(__rhs.data(), __rhs.size()) == 0; }
 
   /**
    * @brief Tests the inequivalence of a regular expression submatch and a
@@ -1156,14 +1193,11 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
    * @param __rhs A string.
    * @returns true if @a __lhs precedes @a __rhs, false otherwise.
    */
-  template<typename _Bi_iter, class _Ch_traits, class _Ch_alloc>
+  template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc>
     inline bool
     operator<(const sub_match<_Bi_iter>& __lhs,
 	      const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __rhs)
-    {
-      typedef typename sub_match<_Bi_iter>::string_type string_type;
-      return __lhs.compare(string_type(__rhs.data(), __rhs.size())) < 0;
-    }
+    { return __lhs._M_compare(__rhs.data(), __rhs.size()) < 0; }
 
   /**
    * @brief Tests the ordering of a regular expression submatch and a string.
@@ -1171,7 +1205,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
    * @param __rhs A string.
    * @returns true if @a __lhs succeeds @a __rhs, false otherwise.
    */
-  template<typename _Bi_iter, class _Ch_traits, class _Ch_alloc>
+  template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc>
     inline bool
     operator>(const sub_match<_Bi_iter>& __lhs,
 	      const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __rhs)
@@ -1183,7 +1217,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
    * @param __rhs A string.
    * @returns true if @a __lhs does not precede @a __rhs, false otherwise.
    */
-  template<typename _Bi_iter, class _Ch_traits, class _Ch_alloc>
+  template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc>
     inline bool
     operator>=(const sub_match<_Bi_iter>& __lhs,
 	       const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __rhs)
@@ -1195,7 +1229,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
    * @param __rhs A string.
    * @returns true if @a __lhs does not succeed @a __rhs, false otherwise.
    */
-  template<typename _Bi_iter, class _Ch_traits, class _Ch_alloc>
+  template<typename _Bi_iter, typename _Ch_traits, typename _Ch_alloc>
     inline bool
     operator<=(const sub_match<_Bi_iter>& __lhs,
 	       const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __rhs)
@@ -1204,7 +1238,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
   /**
    * @brief Tests the equivalence of a C string and a regular expression
    *        submatch.
-   * @param __lhs A C string.
+   * @param __lhs A null-terminated string.
    * @param __rhs A regular expression submatch.
    * @returns true if @a __lhs  is equivalent to @a __rhs, false otherwise.
    */
@@ -1215,10 +1249,10 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return __rhs.compare(__lhs) == 0; }
 
   /**
-   * @brief Tests the inequivalence of an iterator value and a regular
+   * @brief Tests the inequivalence of a C string and a regular
    *        expression submatch.
-   * @param __lhs A regular expression submatch.
-   * @param __rhs A string.
+   * @param __lhs A null-terminated string.
+   * @param __rhs A regular expression submatch.
    * @returns true if @a __lhs is not equivalent to @a __rhs, false otherwise.
    */
   template<typename _Bi_iter>
@@ -1228,8 +1262,8 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return !(__lhs == __rhs); }
 
   /**
-   * @brief Tests the ordering of a string and a regular expression submatch.
-   * @param __lhs A string.
+   * @brief Tests the ordering of a C string and a regular expression submatch.
+   * @param __lhs A null-terminated string.
    * @param __rhs A regular expression submatch.
    * @returns true if @a __lhs precedes @a __rhs, false otherwise.
    */
@@ -1240,8 +1274,8 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return __rhs.compare(__lhs) > 0; }
 
   /**
-   * @brief Tests the ordering of a string and a regular expression submatch.
-   * @param __lhs A string.
+   * @brief Tests the ordering of a C string and a regular expression submatch.
+   * @param __lhs A null-terminated string.
    * @param __rhs A regular expression submatch.
    * @returns true if @a __lhs succeeds @a __rhs, false otherwise.
    */
@@ -1252,8 +1286,8 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return __rhs < __lhs; }
 
   /**
-   * @brief Tests the ordering of a string and a regular expression submatch.
-   * @param __lhs A string.
+   * @brief Tests the ordering of a C string and a regular expression submatch.
+   * @param __lhs A null-terminated string.
    * @param __rhs A regular expression submatch.
    * @returns true if @a __lhs does not precede @a __rhs, false otherwise.
    */
@@ -1264,8 +1298,8 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return !(__lhs < __rhs); }
 
   /**
-   * @brief Tests the ordering of a string and a regular expression submatch.
-   * @param __lhs A string.
+   * @brief Tests the ordering of a C string and a regular expression submatch.
+   * @param __lhs A null-terminated string.
    * @param __rhs A regular expression submatch.
    * @returns true if @a __lhs does not succeed @a __rhs, false otherwise.
    */
@@ -1276,10 +1310,10 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return !(__rhs < __lhs); }
 
   /**
-   * @brief Tests the equivalence of a regular expression submatch and a
+   * @brief Tests the equivalence of a regular expression submatch and a C
    *        string.
    * @param __lhs A regular expression submatch.
-   * @param __rhs A pointer to a string?
+   * @param __rhs A null-terminated string.
    * @returns true if @a __lhs  is equivalent to @a __rhs, false otherwise.
    */
   template<typename _Bi_iter>
@@ -1292,7 +1326,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
    * @brief Tests the inequivalence of a regular expression submatch and a
    *        string.
    * @param __lhs A regular expression submatch.
-   * @param __rhs A pointer to a string.
+   * @param __rhs A null-terminated string.
    * @returns true if @a __lhs is not equivalent to @a __rhs, false otherwise.
    */
   template<typename _Bi_iter>
@@ -1302,9 +1336,9 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return !(__lhs == __rhs); }
 
   /**
-   * @brief Tests the ordering of a regular expression submatch and a string.
+   * @brief Tests the ordering of a regular expression submatch and a C string.
    * @param __lhs A regular expression submatch.
-   * @param __rhs A string.
+   * @param __rhs A null-terminated string.
    * @returns true if @a __lhs precedes @a __rhs, false otherwise.
    */
   template<typename _Bi_iter>
@@ -1314,9 +1348,9 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return __lhs.compare(__rhs) < 0; }
 
   /**
-   * @brief Tests the ordering of a regular expression submatch and a string.
+   * @brief Tests the ordering of a regular expression submatch and a C string.
    * @param __lhs A regular expression submatch.
-   * @param __rhs A string.
+   * @param __rhs A null-terminated string.
    * @returns true if @a __lhs succeeds @a __rhs, false otherwise.
    */
   template<typename _Bi_iter>
@@ -1326,9 +1360,9 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return __rhs < __lhs; }
 
   /**
-   * @brief Tests the ordering of a regular expression submatch and a string.
+   * @brief Tests the ordering of a regular expression submatch and a C string.
    * @param __lhs A regular expression submatch.
-   * @param __rhs A string.
+   * @param __rhs A null-terminated string.
    * @returns true if @a __lhs does not precede @a __rhs, false otherwise.
    */
   template<typename _Bi_iter>
@@ -1338,9 +1372,9 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return !(__lhs < __rhs); }
 
   /**
-   * @brief Tests the ordering of a regular expression submatch and a string.
+   * @brief Tests the ordering of a regular expression submatch and a C string.
    * @param __lhs A regular expression submatch.
-   * @param __rhs A string.
+   * @param __rhs A null-terminated string.
    * @returns true if @a __lhs does not succeed @a __rhs, false otherwise.
    */
   template<typename _Bi_iter>
@@ -1350,9 +1384,9 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return !(__rhs < __lhs); }
 
   /**
-   * @brief Tests the equivalence of a string and a regular expression
+   * @brief Tests the equivalence of a character and a regular expression
    *        submatch.
-   * @param __lhs A string.
+   * @param __lhs A character.
    * @param __rhs A regular expression submatch.
    * @returns true if @a __lhs is equivalent to @a __rhs, false otherwise.
    */
@@ -1360,15 +1394,12 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     inline bool
     operator==(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
 	       const sub_match<_Bi_iter>& __rhs)
-    {
-      typedef typename sub_match<_Bi_iter>::string_type string_type;
-      return __rhs.compare(string_type(1, __lhs)) == 0;
-    }
+    { return __rhs._M_compare(std::__addressof(__lhs), 1) == 0; }
 
   /**
-   * @brief Tests the inequivalence of a string and a regular expression
+   * @brief Tests the inequivalence of a character and a regular expression
    *        submatch.
-   * @param __lhs A string.
+   * @param __lhs A character.
    * @param __rhs A regular expression submatch.
    * @returns true if @a __lhs is not equivalent to @a __rhs, false otherwise.
    */
@@ -1379,8 +1410,9 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return !(__lhs == __rhs); }
 
   /**
-   * @brief Tests the ordering of a string and a regular expression submatch.
-   * @param __lhs A string.
+   * @brief Tests the ordering of a character and a regular expression
+   *        submatch.
+   * @param __lhs A character.
    * @param __rhs A regular expression submatch.
    * @returns true if @a __lhs precedes @a __rhs, false otherwise.
    */
@@ -1388,14 +1420,12 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     inline bool
     operator<(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
 	      const sub_match<_Bi_iter>& __rhs)
-    {
-      typedef typename sub_match<_Bi_iter>::string_type string_type;
-      return __rhs.compare(string_type(1, __lhs)) > 0;
-    }
+    { return __rhs._M_compare(std::__addressof(__lhs), 1) > 0; }
 
   /**
-   * @brief Tests the ordering of a string and a regular expression submatch.
-   * @param __lhs A string.
+   * @brief Tests the ordering of a character and a regular expression
+   *        submatch.
+   * @param __lhs A character.
    * @param __rhs A regular expression submatch.
    * @returns true if @a __lhs succeeds @a __rhs, false otherwise.
    */
@@ -1406,8 +1436,9 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return __rhs < __lhs; }
 
   /**
-   * @brief Tests the ordering of a string and a regular expression submatch.
-   * @param __lhs A string.
+   * @brief Tests the ordering of a character and a regular expression
+   *        submatch.
+   * @param __lhs A character.
    * @param __rhs A regular expression submatch.
    * @returns true if @a __lhs does not precede @a __rhs, false otherwise.
    */
@@ -1418,8 +1449,9 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return !(__lhs < __rhs); }
 
   /**
-   * @brief Tests the ordering of a string and a regular expression submatch.
-   * @param __lhs A string.
+   * @brief Tests the ordering of a character and a regular expression
+   *        submatch.
+   * @param __lhs A character.
    * @param __rhs A regular expression submatch.
    * @returns true if @a __lhs does not succeed @a __rhs, false otherwise.
    */
@@ -1431,25 +1463,22 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
 
   /**
    * @brief Tests the equivalence of a regular expression submatch and a
-   *        string.
+   *        character.
    * @param __lhs A regular expression submatch.
-   * @param __rhs A const string reference.
+   * @param __rhs A character.
    * @returns true if @a __lhs  is equivalent to @a __rhs, false otherwise.
    */
   template<typename _Bi_iter>
     inline bool
     operator==(const sub_match<_Bi_iter>& __lhs,
 	       typename iterator_traits<_Bi_iter>::value_type const& __rhs)
-    {
-      typedef typename sub_match<_Bi_iter>::string_type string_type;
-      return __lhs.compare(string_type(1, __rhs)) == 0;
-    }
+    { return __lhs._M_compare(std::__addressof(__rhs), 1) == 0; }
 
   /**
    * @brief Tests the inequivalence of a regular expression submatch and a
-   *        string.
+   *        character.
    * @param __lhs A regular expression submatch.
-   * @param __rhs A const string reference.
+   * @param __rhs A character.
    * @returns true if @a __lhs is not equivalent to @a __rhs, false otherwise.
    */
   template<typename _Bi_iter>
@@ -1459,24 +1488,23 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return !(__lhs == __rhs); }
 
   /**
-   * @brief Tests the ordering of a regular expression submatch and a string.
+   * @brief Tests the ordering of a regular expression submatch and a
+   *        character.
    * @param __lhs A regular expression submatch.
-   * @param __rhs A const string reference.
+   * @param __rhs A character.
    * @returns true if @a __lhs precedes @a __rhs, false otherwise.
    */
   template<typename _Bi_iter>
     inline bool
     operator<(const sub_match<_Bi_iter>& __lhs,
 	      typename iterator_traits<_Bi_iter>::value_type const& __rhs)
-    {
-      typedef typename sub_match<_Bi_iter>::string_type string_type;
-      return __lhs.compare(string_type(1, __rhs)) < 0;
-    }
+    { return __lhs._M_compare(std::__addressof(__rhs), 1) < 0; }
 
   /**
-   * @brief Tests the ordering of a regular expression submatch and a string.
+   * @brief Tests the ordering of a regular expression submatch and a
+   *        character.
    * @param __lhs A regular expression submatch.
-   * @param __rhs A const string reference.
+   * @param __rhs A character.
    * @returns true if @a __lhs succeeds @a __rhs, false otherwise.
    */
   template<typename _Bi_iter>
@@ -1486,9 +1514,10 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return __rhs < __lhs; }
 
   /**
-   * @brief Tests the ordering of a regular expression submatch and a string.
+   * @brief Tests the ordering of a regular expression submatch and a
+   *        character.
    * @param __lhs A regular expression submatch.
-   * @param __rhs A const string reference.
+   * @param __rhs A character.
    * @returns true if @a __lhs does not precede @a __rhs, false otherwise.
    */
   template<typename _Bi_iter>
@@ -1498,9 +1527,10 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
     { return !(__lhs < __rhs); }
 
   /**
-   * @brief Tests the ordering of a regular expression submatch and a string.
+   * @brief Tests the ordering of a regular expression submatch and a
+   *        character.
    * @param __lhs A regular expression submatch.
-   * @param __rhs A const string reference.
+   * @param __rhs A character.
    * @returns true if @a __lhs does not succeed @a __rhs, false otherwise.
    */
   template<typename _Bi_iter>
diff --git a/libstdc++-v3/include/bits/regex_compiler.h b/libstdc++-v3/include/bits/regex_compiler.h
index 6eee9cb9072..f34b148742b 100644
--- a/libstdc++-v3/include/bits/regex_compiler.h
+++ b/libstdc++-v3/include/bits/regex_compiler.h
@@ -154,42 +154,25 @@  namespace __detail
     };
 
   template<typename _Tp>
-    struct __has_contiguous_iter : std::false_type { };
-
-  template<typename _Ch, typename _Tr, typename _Alloc>
-    struct __has_contiguous_iter<std::basic_string<_Ch, _Tr, _Alloc>>
-    : std::true_type
-    { };
-
-  template<typename _Tp, typename _Alloc>
-    struct __has_contiguous_iter<std::vector<_Tp, _Alloc>>
-    : std::true_type
-    { };
-
-  template<typename _Tp>
-    struct __is_contiguous_normal_iter : std::false_type { };
-
-  template<typename _CharT>
-    struct __is_contiguous_normal_iter<_CharT*> : std::true_type { };
+    struct __is_contiguous_iter : is_pointer<_Tp>::type { };
 
   template<typename _Tp, typename _Cont>
     struct
-    __is_contiguous_normal_iter<__gnu_cxx::__normal_iterator<_Tp, _Cont>>
-    : __has_contiguous_iter<_Cont>::type
-    { };
+    __is_contiguous_iter<__gnu_cxx::__normal_iterator<_Tp*, _Cont>>
+    : true_type { };
 
   template<typename _Iter, typename _TraitsT>
-    using __enable_if_contiguous_normal_iter
-      = typename enable_if< __is_contiguous_normal_iter<_Iter>::value,
-                           std::shared_ptr<const _NFA<_TraitsT>> >::type;
+    using __enable_if_contiguous_iter
+      = __enable_if_t< __is_contiguous_iter<_Iter>::value,
+                       std::shared_ptr<const _NFA<_TraitsT>> >;
 
   template<typename _Iter, typename _TraitsT>
-    using __disable_if_contiguous_normal_iter
-      = typename enable_if< !__is_contiguous_normal_iter<_Iter>::value,
-                           std::shared_ptr<const _NFA<_TraitsT>> >::type;
+    using __disable_if_contiguous_iter
+      = __enable_if_t< !__is_contiguous_iter<_Iter>::value,
+                       std::shared_ptr<const _NFA<_TraitsT>> >;
 
   template<typename _TraitsT, typename _FwdIter>
-    inline __enable_if_contiguous_normal_iter<_FwdIter, _TraitsT>
+    inline __enable_if_contiguous_iter<_FwdIter, _TraitsT>
     __compile_nfa(_FwdIter __first, _FwdIter __last,
 		  const typename _TraitsT::locale_type& __loc,
 		  regex_constants::syntax_option_type __flags)
@@ -201,7 +184,7 @@  namespace __detail
     }
 
   template<typename _TraitsT, typename _FwdIter>
-    inline __disable_if_contiguous_normal_iter<_FwdIter, _TraitsT>
+    inline __disable_if_contiguous_iter<_FwdIter, _TraitsT>
     __compile_nfa(_FwdIter __first, _FwdIter __last,
 		  const typename _TraitsT::locale_type& __loc,
 		  regex_constants::syntax_option_type __flags)
diff --git a/libstdc++-v3/include/std/type_traits b/libstdc++-v3/include/std/type_traits
index 01972d125c7..0c7e97286ca 100644
--- a/libstdc++-v3/include/std/type_traits
+++ b/libstdc++-v3/include/std/type_traits
@@ -2331,7 +2331,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     : public __invoke_result<_Functor, _ArgTypes...>
     { };
 
-#if __cplusplus > 201103L
+#if __cplusplus >= 201402L
   /// Alias template for aligned_storage
   template<size_t _Len, size_t _Align =
 	    __alignof__(typename __aligned_storage_msa<_Len>::__type)>
@@ -2363,11 +2363,16 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
   /// Alias template for result_of
   template<typename _Tp>
     using result_of_t = typename result_of<_Tp>::type;
-#endif
+#endif // C++14
 
+  // __enable_if_t (std::enable_if_t for C++11)
+  template<bool _Cond, typename _Tp = void>
+    using __enable_if_t = typename enable_if<_Cond, _Tp>::type;
+
+  // __void_t (std::void_t for C++11)
   template<typename...> using __void_t = void;
 
-#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
+#if __cplusplus >= 201703L || !defined(__STRICT_ANSI__) // c++17 or gnu++11
 #define __cpp_lib_void_t 201411
   /// A metafunction that always yields void, used for detecting valid types.
   template<typename...> using void_t = void;
diff --git a/libstdc++-v3/testsuite/28_regex/sub_match/compare.cc b/libstdc++-v3/testsuite/28_regex/sub_match/compare.cc
new file mode 100644
index 00000000000..e6093afcfe8
--- /dev/null
+++ b/libstdc++-v3/testsuite/28_regex/sub_match/compare.cc
@@ -0,0 +1,303 @@ 
+// Copyright (C) 2018 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++11 } }
+
+#include <regex>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::bidirectional_iterator_wrapper;
+
+template<typename C> struct traits : std::char_traits<C> { };
+
+void
+test01()
+{
+  const std::basic_string<char, traits<char>> s0, s1 = "1";
+  const std::ssub_match sm, sm2;
+
+  VERIFY( sm.compare(sm) == 0 );
+  VERIFY( sm.compare(sm2) == 0 );
+  VERIFY( sm.compare(sm.str()) == 0 );
+  VERIFY( sm.compare(sm.str().c_str()) == 0 );
+  VERIFY( sm.compare(sm2.str()) == 0 );
+  VERIFY( sm.compare(sm2.str().c_str()) == 0 );
+  VERIFY( sm.compare(std::string(s1.c_str())) == -1 );
+  VERIFY( sm.compare(s1.c_str()) == -1 );
+
+  VERIFY( sm == sm2 );
+  VERIFY( !(sm != sm2) );
+  VERIFY( !(sm < sm2) );
+  VERIFY( !(sm > sm2) );
+  VERIFY( sm <= sm2 );
+  VERIFY( sm >= sm2 );
+
+  VERIFY( sm == s0 );
+  VERIFY( !(sm != s0) );
+  VERIFY( !(sm < s0) );
+  VERIFY( !(sm > s0) );
+  VERIFY( sm <= s0 );
+  VERIFY( sm >= s0 );
+
+  VERIFY( s0 == sm );
+  VERIFY( !(s0 != sm) );
+  VERIFY( !(s0 < sm) );
+  VERIFY( !(s0 > sm) );
+  VERIFY( s0 <= sm );
+  VERIFY( s0 >= sm );
+
+  VERIFY( sm == s0.c_str() );
+  VERIFY( !(sm != s0.c_str()) );
+  VERIFY( !(sm < s0.c_str()) );
+  VERIFY( !(sm > s0.c_str()) );
+  VERIFY( sm <= s0.c_str() );
+  VERIFY( sm >= s0.c_str() );
+
+  VERIFY( s0.c_str() == sm );
+  VERIFY( !(s0.c_str() != sm) );
+  VERIFY( !(s0.c_str() < sm) );
+  VERIFY( !(s0.c_str() > sm) );
+  VERIFY( s0.c_str() <= sm );
+  VERIFY( s0.c_str() >= sm );
+
+  VERIFY( !(sm == s1) );
+  VERIFY( sm != s1 );
+  VERIFY( sm < s1 );
+  VERIFY( !(sm > s1) );
+  VERIFY( sm <= s1 );
+  VERIFY( !(sm >= s1) );
+
+  VERIFY( !(sm == s1.c_str()) );
+  VERIFY( sm != s1.c_str() );
+  VERIFY( sm < s1.c_str() );
+  VERIFY( !(sm > s1.c_str()) );
+  VERIFY( sm <= s1.c_str() );
+  VERIFY( !(sm >= s1.c_str()) );
+
+  VERIFY( !(s1.c_str() == sm) );
+  VERIFY( s1.c_str() != sm );
+  VERIFY( !(s1.c_str() < sm) );
+  VERIFY( s1.c_str() > sm );
+  VERIFY( !(s1.c_str() <= sm) );
+  VERIFY( s1.c_str() >= sm );
+
+  VERIFY( !(sm == s1[0]) );
+  VERIFY( sm != s1[0] );
+  VERIFY( sm < s1[0] );
+  VERIFY( !(sm > s1[0]) );
+  VERIFY( sm <= s1[0] );
+  VERIFY( !(sm >= s1[0]) );
+
+  VERIFY( !(s1[0] == sm) );
+  VERIFY( s1[0] != sm );
+  VERIFY( !(s1[0] < sm) );
+  VERIFY( s1[0] > sm );
+  VERIFY( !(s1[0] <= sm) );
+  VERIFY( s1[0] >= sm );
+}
+
+void
+test02()
+{
+  const std::basic_string<char, traits<char>> s0, s1 = "1";
+  std::csub_match sm;
+  const std::csub_match sm2;
+  const char c[] = "1";
+  sm.matched = true;
+  sm.first = c;
+  sm.second = c+1;
+
+  VERIFY( sm.compare(sm) == 0 );
+  VERIFY( sm.compare(sm2) == 1 );
+  VERIFY( sm.compare(sm.str()) == 0 );
+  VERIFY( sm.compare(sm.str().c_str()) == 0 );
+  VERIFY( sm.compare(sm2.str()) == 1 );
+  VERIFY( sm.compare(sm2.str().c_str()) == 1 );
+  VERIFY( sm.compare(std::string(s1.c_str())) == 0 );
+  VERIFY( sm.compare(s1.c_str()) == 0 );
+
+  VERIFY( !(sm == sm2) );
+  VERIFY( sm != sm2 );
+  VERIFY( !(sm < sm2) );
+  VERIFY( sm > sm2 );
+  VERIFY( !(sm <= sm2) );
+  VERIFY( sm >= sm2 );
+
+  VERIFY( !(sm2 == sm) );
+  VERIFY( sm2 != sm );
+  VERIFY( sm2 < sm );
+  VERIFY( !(sm2 > sm) );
+  VERIFY( sm2 <= sm );
+  VERIFY( !(sm2 >= sm) );
+
+  VERIFY( !(sm == s0) );
+  VERIFY( sm != s0 );
+  VERIFY( !(sm < s0) );
+  VERIFY( sm > s0 );
+  VERIFY( !(sm <= s0) );
+  VERIFY( sm >= s0 );
+
+  VERIFY( !(sm == s0.c_str()) );
+  VERIFY( sm != s0.c_str() );
+  VERIFY( !(sm < s0.c_str()) );
+  VERIFY( sm > s0.c_str() );
+  VERIFY( !(sm <= s0.c_str()) );
+  VERIFY( sm >= s0.c_str() );
+
+  VERIFY( !(s0.c_str() == sm) );
+  VERIFY( s0.c_str() != sm );
+  VERIFY( s0.c_str() < sm );
+  VERIFY( !(s0.c_str() > sm) );
+  VERIFY( s0.c_str() <= sm );
+  VERIFY( !(s0.c_str() >= sm) );
+
+  VERIFY( s1 == sm );
+  VERIFY( !(s1 != sm) );
+  VERIFY( !(s1 < sm) );
+  VERIFY( !(s1 > sm) );
+  VERIFY( s1 <= sm );
+  VERIFY( s1 >= sm );
+
+  VERIFY( sm == s1.c_str() );
+  VERIFY( !(sm != s1.c_str()) );
+  VERIFY( !(sm < s1.c_str()) );
+  VERIFY( !(sm > s1.c_str()) );
+  VERIFY( sm <= s1.c_str() );
+  VERIFY( sm >= s1.c_str() );
+
+  VERIFY( s1.c_str() == sm );
+  VERIFY( !(s1.c_str() != sm) );
+  VERIFY( !(s1.c_str() < sm) );
+  VERIFY( !(s1.c_str() > sm) );
+  VERIFY( s1.c_str() <= sm );
+  VERIFY( s1.c_str() >= sm );
+
+  VERIFY( sm == s1[0] );
+  VERIFY( !(sm != s1[0]) );
+  VERIFY( !(sm < s1[0]) );
+  VERIFY( !(sm > s1[0]) );
+  VERIFY( sm <= s1[0] );
+  VERIFY( sm >= s1[0] );
+
+  VERIFY( s1[0] == sm );
+  VERIFY( !(s1[0] != sm) );
+  VERIFY( !(s1[0] < sm) );
+  VERIFY( !(s1[0] > sm) );
+  VERIFY( s1[0] <= sm );
+  VERIFY( s1[0] >= sm );
+}
+
+void
+test03()
+{
+  const std::basic_string<char, traits<char>> s0, s1 = "1";
+  const char c[] = "1";
+  test_container<const char, bidirectional_iterator_wrapper> tc(c, c+1);
+  std::sub_match<bidirectional_iterator_wrapper<const char>> sm;
+  const std::sub_match<bidirectional_iterator_wrapper<const char>> sm2;
+  sm.matched = true;
+  sm.first = tc.begin();
+  sm.second = tc.end();
+
+  VERIFY( sm.compare(sm) == 0 );
+  VERIFY( sm.compare(sm2) == 1 );
+  VERIFY( sm.compare(sm.str()) == 0 );
+  VERIFY( sm.compare(sm.str().c_str()) == 0 );
+  VERIFY( sm.compare(sm2.str()) == 1 );
+  VERIFY( sm.compare(sm2.str().c_str()) == 1 );
+  VERIFY( sm.compare(std::string(s1.c_str())) == 0 );
+  VERIFY( sm.compare(s1.c_str()) == 0 );
+
+  VERIFY( !(sm == sm2) );
+  VERIFY( sm != sm2 );
+  VERIFY( !(sm < sm2) );
+  VERIFY( sm > sm2 );
+  VERIFY( !(sm <= sm2) );
+  VERIFY( sm >= sm2 );
+
+  VERIFY( !(sm2 == sm) );
+  VERIFY( sm2 != sm );
+  VERIFY( sm2 < sm );
+  VERIFY( !(sm2 > sm) );
+  VERIFY( sm2 <= sm );
+  VERIFY( !(sm2 >= sm) );
+
+  VERIFY( !(sm == s0) );
+  VERIFY( sm != s0 );
+  VERIFY( !(sm < s0) );
+  VERIFY( sm > s0 );
+  VERIFY( !(sm <= s0) );
+  VERIFY( sm >= s0 );
+
+  VERIFY( !(sm == s0.c_str()) );
+  VERIFY( sm != s0.c_str() );
+  VERIFY( !(sm < s0.c_str()) );
+  VERIFY( sm > s0.c_str() );
+  VERIFY( !(sm <= s0.c_str()) );
+  VERIFY( sm >= s0.c_str() );
+
+  VERIFY( !(s0.c_str() == sm) );
+  VERIFY( s0.c_str() != sm );
+  VERIFY( s0.c_str() < sm );
+  VERIFY( !(s0.c_str() > sm) );
+  VERIFY( s0.c_str() <= sm );
+  VERIFY( !(s0.c_str() >= sm) );
+
+  VERIFY( s1 == sm );
+  VERIFY( !(s1 != sm) );
+  VERIFY( !(s1 < sm) );
+  VERIFY( !(s1 > sm) );
+  VERIFY( s1 <= sm );
+  VERIFY( s1 >= sm );
+
+  VERIFY( sm == s1.c_str() );
+  VERIFY( !(sm != s1.c_str()) );
+  VERIFY( !(sm < s1.c_str()) );
+  VERIFY( !(sm > s1.c_str()) );
+  VERIFY( sm <= s1.c_str() );
+  VERIFY( sm >= s1.c_str() );
+
+  VERIFY( s1.c_str() == sm );
+  VERIFY( !(s1.c_str() != sm) );
+  VERIFY( !(s1.c_str() < sm) );
+  VERIFY( !(s1.c_str() > sm) );
+  VERIFY( s1.c_str() <= sm );
+  VERIFY( s1.c_str() >= sm );
+
+  VERIFY( sm == s1[0] );
+  VERIFY( !(sm != s1[0]) );
+  VERIFY( !(sm < s1[0]) );
+  VERIFY( !(sm > s1[0]) );
+  VERIFY( sm <= s1[0] );
+  VERIFY( sm >= s1[0] );
+
+  VERIFY( s1[0] == sm );
+  VERIFY( !(s1[0] != sm) );
+  VERIFY( !(s1[0] < sm) );
+  VERIFY( !(s1[0] > sm) );
+  VERIFY( s1[0] <= sm );
+  VERIFY( s1[0] >= sm );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+}
diff --git a/libstdc++-v3/testsuite/util/testsuite_iterators.h b/libstdc++-v3/testsuite/util/testsuite_iterators.h
index 74b6b6064f9..4100514879d 100644
--- a/libstdc++-v3/testsuite/util/testsuite_iterators.h
+++ b/libstdc++-v3/testsuite/util/testsuite_iterators.h
@@ -185,6 +185,11 @@  namespace __gnu_test
     void operator,(const T&, const output_iterator_wrapper<U>&) = delete;
 #endif
 
+  template<typename T> struct remove_cv { typedef T type; };
+  template<typename T> struct remove_cv<const T> { typedef T type; };
+  template<typename T> struct remove_cv<volatile T> { typedef T type; };
+  template<typename T> struct remove_cv<const volatile T> { typedef T type; };
+
   /**
    * @brief input_iterator wrapper for pointer
    *
@@ -194,7 +199,8 @@  namespace __gnu_test
    */
   template<class T>
   class input_iterator_wrapper
-  : public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T&>
+  : public std::iterator<std::input_iterator_tag, typename remove_cv<T>::type,
+			 std::ptrdiff_t, T*, T&>
   {
   protected:
     input_iterator_wrapper()