https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85472
--- Comment #5 from Tim Shen <timshen at gcc dot gnu.org> --- (In reply to Hans Ã…berg from comment #4) > (In reply to Tim Shen from comment #1) > > I know exactly how libc++ produces this result. It creates an empty > > match_result during each repetition ("*" operator). It's less confusing but > > much slower. > > I wrote an NFA/DFA that computes all matches, it seems, in an efficient > manner: Action numbers are marked on the states of the sub-NFAs one is > interested in. While lexing a string, the partial reverse NFA is recorded, > which is searched when a final state is encountered. The string position > action numbers, as marked on the corresponding states, are recorded, and for > each action number, the contiguous string sequences are the possible > submatches. I'm not following the meaning of "action number" and "the partial reverse NFA is recorded". How many actions numbers are recorded? for regex_match(s, regex(re)), is it on the order of O(s.size()), or O(re.size())? The goal is to allocate O(re.size()) of memory exactly once.