c++ - std::regex_constants::optimize 使用的优化技术

Question

我正在使用 std::regex，在阅读 std::regex_constants 中定义的各种常量时，我​​遇到了 std::optimize ，阅读它，听起来它在我的应用程序中很有用(我只需要一个正则表达式实例，在开始时初始化，但在整个加载过程中多次使用它)。

根据 working paper n3126(第 1077 页)，std::regex_constants::optimize:

Specifies that the regular expression engine should pay more attention to the speed with which regular expressions are matched, and less to the speed with which regular expression objects are constructed. Otherwise it has no detectable effect on the program output.

我很好奇会执行什么类型的优化，但似乎没有太多关于它的文献(事实上，它似乎是未定义的)，我发现的唯一东西之一是在 cppreference.com 处，其中声明 std::regex_constants::optimize:

Instructs the regular expression engine to make matching faster, with the potential cost of making construction slower. For example, this might mean converting a non-deterministic FSA to a deterministic FSA.

但是，我没有正式的计算机科学背景，虽然我知道什么是 FSA 的基础知识，并且了解确定性 FSA(每个状态只有一个可能的下一个状态)和确定性 FSA 之间的基本区别一个非确定性的 FSA(具有多个潜在的下一个状态)；我不明白这如何缩短匹配时间。此外，我很想知道在各种 C++ 标准库实现中是否还有任何其他优化。

Answer 1

Mastering Regular Expressions 中有一些关于正则表达式引擎和性能权衡主题的有用信息(远远超出了 stackoverflow 的答案)作者:杰弗里·弗里德尔。

值得注意的是，作为 N3126 源代码的 Boost.Regex 将 optimize 记录为“这目前对 Boost.Regex 没有影响。”

附言

indeed, it seems to be implementation-defined

不，它是未指定的。实现定义意味着需要实现来定义行为选择。实现不需要记录它们的正则表达式引擎是如何实现的，或者 optimize 标志有什么区别(如果有的话)。

附言2

in various STL implementations

std::regex 不是 STL 的一部分，C++ 标准库与 STL 不是一回事。