C++分词器复杂度与strtok_r比较

Question

C++分词器复杂度与strtok_r比较

3

我制作这个问题是因为我将分词器从strtok_r移动到了C++的等效版本。我必须使用strtok_r代替strtok，因为大多数情况下我需要执行两个嵌套的分词。

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++版本似乎具有更高的复杂性... 你对此有什么想法？

- nicolati

3

strtok 会修改输入的字符串，而 C++ 版本则是在创建副本。尽管它们可能产生相同的结果，但这两个版本采取了完全不同的方式来达到最终结果。 - Chad

1

你可能想看一下如何在C++中拆分字符串，因为它更有效率：https://dev59.com/k3VC5IYBdhLWcg3wnCj6。你的数据长什么样子？你想用它做什么？ - NathanOliver

如果您正在对常量字符串进行测试，则具有等效__builtin_的函数将始终胜出，因为它们会被折叠。 - technosaurus

也许是因为 C 库是在资源稀缺、效率优先于整洁设计的时代编写的，而 C++ 更注重鲁棒性和设计 - 但这只是我的个人观点 :-) - Serge Ballesta

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Christophe · Accepted Answer

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);

现场演示