std::regex 能保证最坏情况下的时间复杂度吗？

Question

C++ 标准 [30.5.3, n4830 ] 定义 std::error_complexity 以指示正则表达式模式可能太复杂而无法完成。

我只是想知道：

std::regex能保证最坏情况下的时间复杂度吗？

Answer 1

它似乎确实考虑了时间复杂度，但我怀疑它是否基于任何理论上的最坏或最好情况假设；它应该可能基于一些相对超过一定时间的权衡，这里称为 pre-set level:

/** * The complexity of an attempted match against a regular expression exceeded a pre-set level. */

Reference

  /** The expression contained an invalid collating element name. */
  constexpr error_type error_collate(_S_error_collate);

  /** The expression contained an invalid character class name. */
  constexpr error_type error_ctype(_S_error_ctype);

  /**
   * The expression contained an invalid escaped character, or a trailing
   * escape.
   */
  constexpr error_type error_escape(_S_error_escape);

  /** The expression contained an invalid back reference. */
  constexpr error_type error_backref(_S_error_backref);

  /** The expression contained mismatched [ and ]. */
  constexpr error_type error_brack(_S_error_brack);

  /** The expression contained mismatched ( and ). */
  constexpr error_type error_paren(_S_error_paren);

  /** The expression contained mismatched { and } */
  constexpr error_type error_brace(_S_error_brace);

  /** The expression contained an invalid range in a {} expression. */
  constexpr error_type error_badbrace(_S_error_badbrace);

  /**
   * The expression contained an invalid character range,
   * such as [b-a] in most encodings.
   */
  constexpr error_type error_range(_S_error_range);

  /**
   * There was insufficient memory to convert the expression into a
   * finite state machine.
   */
  constexpr error_type error_space(_S_error_space);

  /**
   * One of <em>*?+{</em> was not preceded by a valid regular expression.
   */
  constexpr error_type error_badrepeat(_S_error_badrepeat);

  /**
   * The complexity of an attempted match against a regular expression
   * exceeded a pre-set level.
   */
  constexpr error_type error_complexity(_S_error_complexity);

  /**
   * There was insufficient memory to determine whether the
   * regular expression could match the specified character sequence.
   */
  constexpr error_type error_stack(_S_error_stack);

std::regex 能保证最坏情况下的时间复杂度吗？

Does std::regex guaranttee the time-complexity in worst cases?

c++

regex

standards

time-complexity

c++11

Reference