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 回答