gpt4 book ai didi

c++ - std::regex 是否保证最坏情况下的时间复杂度?

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:06:24 25 4
gpt4 key购买 nike

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

我只是想知道:

std::regex 是否保证最坏情况下的时间复杂度?

最佳答案

它似乎确实考虑了时间复杂度,但我怀疑它是否基于任何理论上的最坏或最好情况假设;它应该可能基于一些相对超过一定时间的权衡,这里称为 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);

关于c++ - std::regex 是否保证最坏情况下的时间复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57765124/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com