CODEWITHSUNDEEP
c++regexqtqregexpqregularexpression
Alex Huszagh
Alex Huszagh

Reputation: 14644

Does QRegularExpression remove Backreferences (and faster searching as a result)

A cursory look at the documentation for QRegexp shows that it supports backreferences, while QRegularExpression makes no mention of it. This would be notable since regular expression matching without backreferences can scale in linear time, while including backreferences scales as exponential time (source [dead link], cached version).

A similar StackOverflow answer also mentions the main differences are in the speed of execution. It would be logical to consider that the new regular expression class could employ a new algorithm, which would allow it to search in linear time, however, I have no direct knowledge of this. Are there any differences similar to the above in the new QRegularExpression class?

Upvotes: 4

Views: 514

Answers (1)

Jonathan Mee
Jonathan Mee

Reputation: 38969

QRegularExpression departs from the functionality of QRegExp in 5 particular areas:

  1. Support for \A and \z
  2. Support for Global Matching
  3. Removal of Wildcard Matching
  4. Removal of support for inferior regex syntaxes (only Perl Compatible Regular Expressions (PCRE) are supported now)
  5. Added support for *? and +? modifiers
  6. Removed support for the un-useful QRegExp::CaretModes with the exception of QRegExp::CaretAtOffset

Of these changes 4 is very relevant to this question. PCRE is by far the most advanced regular expression engine available. So it certainly supports back-references as well as many other features QRegExp could never aspire to.

As far as the rationale behind not explicitly mentioning every functionality provided by PCRE is related to the fact that PCRE is defined by a 70k word document. If you're interested in burning through a toner cartridge, QRegularExpression links directly to this page: http://pcre.org/pcre.txt

Incidentally quoting from that tome these are the back reference sytaxes PCRE supports:

  • \n reference by number (can be ambiguous)
  • \gn reference by number
  • \g{n} reference by number
  • \g{-n} relative reference by number
  • \k<name> reference by name (Perl)
  • \k'name' reference by name (Perl)
  • \g{name} reference by name (Perl)
  • \k{name} reference by name (.NET)
  • (?P=name) reference by name (Python)

Upvotes: 4

Related Questions