C++ Tokenizer 复杂性与 strtok_r

我提出这个问题是因为我将标记器从 strtok_r 移动到 C++ 中的等效版本。我必须使用 strtok_r 代替 strtok，因为我有 2 个嵌套的标记化要执行大部分时间。

strtok_r 算法是这样的:

char *end_token, *token, *word ;
// fill 'word'
token = strtok_r (word, " ", &end_token) ;
while (token != NULL) {
  // do something
  token = strtok_r (NULL, " ", &end_token) ;
}

而 C++ 版本是这样的(取自这里的另一篇文章):

string mystring, token ;
size_t next_token ;
// fill 'mystring'
while (token != mystring) {
    next_token = mystring.find_first_of (" ") ;
    token = mystring.substr (0, next_token) ;
    mystring = mystring.substr (next_token + 1) ;
    // do something
}

现在的问题是:为什么 C++ 版本对 C 版本的尊重如此严重？
对于长字符串，我必须使用 C++ 版本等待大约 10 秒，而 C 版本对于相同的字符串则是瞬时的。
因此，似乎 C++ 版本具有更高的复杂性...
你有什么想法？

最佳答案

strtok() 修改字符串，用空终止符替换标记分隔符。如果您的长字符串有 n 个标记，则该函数只是遍历字符串，将 n 个字符更改为 null，这非常快。

在您的 C++ 替代方案中，您正在制作 2*n 个字符串拷贝，这意味着可能有 2*n 个分配操作，加上(非常长的)剩余字符串的纯粹拷贝，这比第一个替代方案要重得多。不同之处在于您不必更改原始字符串。

您可以通过保持您正在迭代的字符串不变来改进，例如使用偏移量进行搜索:

string mystring, token ;
size_t cur_token=0, next_token ;
// fill 'mystring'
do {
    next_token = mystring.find_first_of (" ", cur_token) ;
    token = mystring.substr (cur_token, next_token-cur_token);  // next_token-(nex_token==string::npos ? 0:cur_token) would be cleaner
    if (next_token!=string::npos)
        cur_token = next_token+1;
    // do something with token;
} while (next_token!=string::npos);

Live demo

关于C++ Tokenizer 复杂性与 strtok_r，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32102180/