Rationale:

Applied to working paper while issue was still in New status.

Proposed resolution:

In [re.alg.search]/5 replace all three occurences of param "iterator" with "BidirectionalIterator"

template <class iterator BidirectionalIterator, class charT, class traits>
  bool regex_search(iterator BidirectionalIterator first, iterator BidirectionalIterator last, 
                    const basic_regex<charT, traits>& e, 
                    regex_constants::match_flag_type flags = 
                      regex_constants::match_default);

-6- Effects: Behaves "as if" by constructing an object what of type match_results<iterator BidirectionalIterator> and then returning the result of regex_search(first, last, what, e, flags).

[re.alg.search]/5 declares

template <class iterator, class charT, class traits>
bool regex_search(iterator first, iterator last,
                  const basic_regex<charT, traits>& e,
                  regex_constants::match_flag_type flags =
                      regex_constants::match_default);

where it's not explained, which iterator category the parameter iterator belongs to. This is inconsistent to the preceding declaration in the synopsis section [re.syn], which says:

template <class BidirectionalIterator, class charT, class traits>
bool regex_search(BidirectionalIterator first, BidirectionalIterator last,
                  const basic_regex<charT, traits>& e,
                  regex_constants::match_flag_type flags =
                      regex_constants::match_default);