Why does the performance of this non-matching pattern scale with the size of the search space?
It's simply because libstdc++ and libc++ do not implement such optimization.
The following is the main part of libstdc++'s implementation of regex_search
:
template<typename _BiIter, typename _Alloc, typename _TraitsT,
bool __dfs_mode>
bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
_M_search()
{
if (_M_search_from_first())
return true;
if (_M_flags & regex_constants::match_continuous)
return false;
_M_flags |= regex_constants::match_prev_avail;
while (_M_begin != _M_end)
{
++_M_begin;
if (_M_search_from_first())
return true;
}
return false;
}
So it does traverse the whole range even if the regular expression contains ^
.
So is libc++'s implementation.