C++ Tokenizer 复杂性与 strtok_r

Question

我提出这个问题是因为我将分词器从 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++ 版本具有更高的复杂性...... 你怎么看？

Answer 1

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