2

第一个问题,是否std::string::erase重新分配?

第二个问题,有没有更快的方法可以快速删除某个单词或短语std::string?字符串的长度通常在 300K 左右。

4

7 回答 7

5

未定义是否string::erase要触发重新分配。您可以通过string::capacity在调用该方法之后和之前进行比较来检查会发生什么。删除字符串的一部分总是会触发删除部分之后的所有字符的副本,因为字符串的存储需要是连续的。

对于大字符串的操作,您可能需要考虑使用绳索或 std::list 代替。根据您的操作,这可能会更快。

于 2013-02-20T07:45:57.157 回答
4

21.4.1/3

任何erase() 或pop_back() 成员函数都不应抛出任何异常。

由于分配器上不存在这样的限制,我认为可以肯定地说不、不、std::string::erase不能重新分配。

于 2013-02-20T07:57:11.150 回答
2

你可能想看看rope。它是为大字符串设计的重型字符串(明白吗?),具有更快的子字符串操作。不幸的是,它不是 . 的一部分std,而是一个常见的添加(在 SGI、STLPort 和 GNU 的 libstdc++ 中)。

请参阅STL 绳索 - 何时何地使用

于 2013-02-20T07:59:14.053 回答
2

已经提到,它的实现取决于 std::string::erase 是否触发重新分配。所以我想专注于字符串搜索。解决这个问题的传统方法是使用Aho-Corasick 算法

或者,David Musser 写了一篇关于使用 Boyer-Moore 和 Knuth-Morris-Pratt 算法的混合算法在大型干草堆(字符串)中搜索针(子字符串)的论文。该论文可在此处获得。调整它可能比滚动 Aho-Corasick 实现更简单。

Musser 的方法展示了必须比简单的搜索和替换更快的行为。应该可以通过修改 BM 跳过循环和 KNP 查找表来根据您的目的调整算法,以考虑您要替换的所有针。预先分配一个输出缓冲区,并通过将干草堆的所有不匹配段附加到它来迭代地构造输出字符串。随着针数的增加和 BM/KNP 查找饱和,这种方法将变得不那么有效。

于 2013-02-20T08:00:01.507 回答
1

从我对 STL 的实现中,我可以看到在调用期间重新分配字符串的条件std::string::erase是: if (__new_size > this->capacity() || _M_rep()->_M_is_shared()) 我认为这意味着字符串在erase调用期间没有重新分配。

于 2013-02-20T07:48:46.090 回答
1
  1. 不,std::string::erase不重新分配 - 因为它不需要,而且因为它是 C++ 哲学,你不需要为你不需要的东西支付(重新分配时间)。
  2. 取决于您要擦除的内容以及快速(快速键入或执行)的含义。

首先要做的当然是找到一种快速算法来找到您要删除的单词/短语。然后,如果只有一块要擦除,std::string::erase应该完全适合您的需求。但是,例如,如果您有字符串“000aa11111bbbbb2222222c3333333333”,并且想要删除所有包含字母的短语,则一个接一个地查找并删除它们将导致字符串其余部分的多个副本 - '1' 将被复制一次,' 2 将被复制两次,依此类推。因此,如果字符串中有许多要擦除的短语,则有可能提高性能 - 只需复制应单独保留在字符串中的块并覆盖您要擦除的块:(| 表示迭代器,直到字符串是正确的”):

  • “000|aa11111bbbbb2222222c3333333333”
  • “00011111|11bbbbb2222222c3333333333”
  • “000111112222222|2222222c3333333333”
  • “0001111122222223333333333|33333333”
  • “0001111122222223333333333”

这样,您必须将第一个删除的短语之后的每个字符都复制一次。

于 2013-02-20T07:59:44.947 回答
0

我正在使用 MS 的 VC6,最后一个 DO 在 std::string::erase() 调用上重新分配缓冲区。我不得不从我的代码中删除所有的 erase() 调用,因为我有时会使用大字符串,因此我发现速度很慢。所以关心你的编译器并避免擦除()。就个人而言,我使用 reaffectations str = ""; 作为一种解决方法。

于 2013-09-02T09:17:54.080 回答