第一个问题,是否std::string::erase
重新分配?
第二个问题,有没有更快的方法可以快速删除某个单词或短语std::string
?字符串的长度通常在 300K 左右。
未定义是否string::erase
要触发重新分配。您可以通过string::capacity
在调用该方法之后和之前进行比较来检查会发生什么。删除字符串的一部分总是会触发删除部分之后的所有字符的副本,因为字符串的存储需要是连续的。
对于大字符串的操作,您可能需要考虑使用绳索或 std::list 代替。根据您的操作,这可能会更快。
21.4.1/3
任何erase() 或pop_back() 成员函数都不应抛出任何异常。
由于分配器上不存在这样的限制,我认为可以肯定地说不、不、std::string::erase
不能重新分配。
你可能想看看rope
。它是为大字符串设计的重型字符串(明白吗?),具有更快的子字符串操作。不幸的是,它不是 . 的一部分std
,而是一个常见的添加(在 SGI、STLPort 和 GNU 的 libstdc++ 中)。
已经提到,它的实现取决于 std::string::erase 是否触发重新分配。所以我想专注于字符串搜索。解决这个问题的传统方法是使用Aho-Corasick 算法。
或者,David Musser 写了一篇关于使用 Boyer-Moore 和 Knuth-Morris-Pratt 算法的混合算法在大型干草堆(字符串)中搜索针(子字符串)的论文。该论文可在此处获得。调整它可能比滚动 Aho-Corasick 实现更简单。
Musser 的方法展示了必须比简单的搜索和替换更快的行为。应该可以通过修改 BM 跳过循环和 KNP 查找表来根据您的目的调整算法,以考虑您要替换的所有针。预先分配一个输出缓冲区,并通过将干草堆的所有不匹配段附加到它来迭代地构造输出字符串。随着针数的增加和 BM/KNP 查找饱和,这种方法将变得不那么有效。
从我对 STL 的实现中,我可以看到在调用期间重新分配字符串的条件std::string::erase
是:
if (__new_size > this->capacity() || _M_rep()->_M_is_shared())
我认为这意味着字符串在erase
调用期间没有重新分配。
std::string::erase
不重新分配 - 因为它不需要,而且因为它是 C++ 哲学,你不需要为你不需要的东西支付(重新分配时间)。首先要做的当然是找到一种快速算法来找到您要删除的单词/短语。然后,如果只有一块要擦除,std::string::erase
应该完全适合您的需求。但是,例如,如果您有字符串“000aa11111bbbbb2222222c3333333333”,并且想要删除所有包含字母的短语,则一个接一个地查找并删除它们将导致字符串其余部分的多个副本 - '1' 将被复制一次,' 2 将被复制两次,依此类推。因此,如果字符串中有许多要擦除的短语,则有可能提高性能 - 只需复制应单独保留在字符串中的块并覆盖您要擦除的块:(| 表示迭代器,直到字符串是正确的”):
这样,您必须将第一个删除的短语之后的每个字符都复制一次。
我正在使用 MS 的 VC6,最后一个 DO 在 std::string::erase() 调用上重新分配缓冲区。我不得不从我的代码中删除所有的 erase() 调用,因为我有时会使用大字符串,因此我发现速度很慢。所以关心你的编译器并避免擦除()。就个人而言,我使用 reaffectations str = ""; 作为一种解决方法。