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).