c++ - 对大字符串进行更快的操作

Question

假设我有一个像这样的大随机字符串......

_W:,aLH#J&A4=IY;    ?RVUc?W+</59JG4WSGW6G6$QEHQ:>,*b60$BYR=D=-^8-4(0    "??YaI0Y    SD9 FJ;MZ,V+'S]0:9L%;#a23cO%bMY[O6^S;ULRV2XA    8&  6_5W21E+Y$RYY$K"Q.0J+:cJC301M3H![7
L%K
Q5(4I9/9DAFR,-8<BJ=4H>9M,OX!.A4aQ:
BK<a"1ID.=U-US`R_])>GG)UL\!G?U$RRG_
HcW 3;<U5`X.?:6K@H*ZD3[M!ZU#KJXbE<Y*VV#ZYU#=]?Q
5:a^]#T

XRT.V]>57#W"U1=K$X]&JIY)::AE :K'7!_DV1B>SJ9D_`]>aC"N'US$;CaHK<N#-
"cJ,%RT)!J0DLFUb[[FOCQX(/.E3#
U
L$("+$) ;TDZ
;T#XS-'6U4`UKZ0a85D&+a]I.C/-7LDM_#/aS9OYA!#^G1II*XKL`;c
ES62Wa^=BQHK6E&A .X+4FDZ:   3UOaJ
#1<BY:;@D:`^`8E\-[9&7PXPH

... a lot more

我想对整个字符串进行操作，比如在分号后插入换行符。

#include <iostream>
#include <cmath>
#include <algorithm>

int main()
{
    std::string buffer = "";
    std::string line = "";
    while (std::getline(std::cin, line))
        buffer += line + std::string("\n");

    auto it = std::find(buffer.begin(), buffer.end(), ';');
    while (it != buffer.end())
    {
        buffer.insert(it, '\n');
        it = std::find(it+1, buffer.end(), ';');
    }
    std::cout << buffer << std::endl;
    return 0;
}

这显然需要很长时间。我应该怎么办？如果我将它们分成更小的字符串会更好吗？如果没有，我怎样才能让它更快？

编辑

我是个傻子。我在这里的这一行有一个无限循环

- it = std::find(buffer.begin(), buffer.end(), ';');
+ it = std::find(it+1, buffer.end(), ';');

虽然我仍然赞扬提供了很好答案的人。

Answer 1

虽然我通常更喜欢使用 C++ 标准库，但在这种特殊情况下，我认为良好的旧 C 风格代码可能是更好的选择。

如果您要进行的处理仅取决于一次解释一个字符(例如，在分号后插入换行符)，那么一次读入一个字符，然后写出一个(或两个，如果该字符是一个分号并且后面必须跟一个额外的换行符)如果输入和输出都被缓冲，将会非常快。

如果字符 n 的处理只依赖于字符 1 到 n ，那么类似的方法会起作用——只需要根据目前看到的字符预先决定处理 Action ，或者存储所有前面的字符，以便可以根据所有字符 1 到 n 来决定 Action 。

在这两种情况下，都没有必要将字符插入字符串的中间，因此必须移动大块内存。

仅当对字符 n 的处理(例如，是否在该字符后插入一个字符)取决于字符 n 之后的字符时，才需要在处理之前读入所有文本。即便如此，通过使用一个函数如下:

void copyWithProcessing (char *from, char *to) {
    while (*from) {
        // do any pre-processing
        *to++ = *from++;
        // do any post-processing
     }
 }

这假设我们可以为 N 指向的字符数组预分配足够的空间，因为我们预先知道由于即将发生的处理将需要多少额外字符。或者，如果我们不需要将结果字符串存储在内存中，我们可以在对每个字符的处理完成后逐个字符地写出它，这意味着我们根本不必为它分配任何空间。