C++ 字符串插入

Question

我有一些文本存储在字符串中。每当我看到特定的字符序列时，我想在模式后面插入一些字符（将字符串中的所有现有字符移动到字符串中较晚/较高的索引）。我认为最有效的方法是保留一个大字符数组（大是因为我不知道到底需要多少插入，但我确实知道添加的字符总数将小于原始字符串的长度），然后迭代原始字符串，将字符复制到新的字符数组中，然后每当识别到字符模式时，插入新字符串，然后继续从源/原始字符串复制字符。有人能想到更快或更好的方法吗？这会经常发生，所以我想尽可能地优化它。

更新：一些人建议使用 std::string 路线而不是字符数组，以避免与字符数组相关的内存管理。

我正在寻找的模式是一个 5 个字符的字符串，然后我一直寻找，直到看到换行符，然后在此时附加 3 或 5 个字符。我会通过做这样的事情来实现它：

bool matchedstart = false;
std::string origstr;
unsigned int strlength = origstr.length();
int strlengthm5 = origstr.length() - 5;
for(int i = 0, j = 0; i < strlength; i++, j++) {       
    if(!matchedstart && i < strlengthm5) {
       if(origstr[i] == 't' && origstr[i+1] == 'n' && origstr[i+2] = 'a'...) {
           matchedstart = true;
       }
     }
    else if(origstr[i] == '\n') {
         //append extra text here
         matchedstart = false;
     }
     outputstr[j] = origstr[i];
}

该算法比 string.find() 更有效吗？我怀疑这是因为我已将输入文本硬编码到上面的算法中。我怀疑 string.find() 会涉及一个与字符串长度成比例的短内部 for 循环，尽管这可能不会比我的 if 链中涉及的编译器优化短路评估节省太多时间。我想我必须对此进行分析，以了解字符串涉及多少开销。我稍后会发布我的发现。

Answer 1

您可以使用std::string，它具有find()和insert()方法，例如：

std::string str = "whatever you want to search in...";
std::string seq = "what to find";

auto pos = str.find(seq);
if (pos != std::string::npos)
    str.insert(pos + seq.length(), "what to insert");

如果要替换序列的多个实例，find()有一个可选pos参数来指定要搜索的起始索引：

std::string str = "whatever you want to search in...";
std::string seq = "what to find";
std::string ins = "what to insert";

auto pos = str.find(seq);
while (pos != std::string::npos)
{
    pos += seq.length();
    str.insert(pos, ins);
    pos = str.find(seq, pos + ins.length());
}

既然您说“知道添加的字符总数将小于原始字符串的长度”，您可以使用std:string::reserve()增加字符串的容量来避免插入期间的重新分配：

std::string str = "whatever you want to search in...";
std::string seq = "what to find";
std::string ins = "what to insert";

auto pos = str.find(seq);
if (pos != std::string::npos)
{
    str.reserve(str.length() * 2);
    do
    {
        pos += seq.length();
        str.insert(pos, ins);
        pos = str.find(seq, pos + ins.length());
    }
    while (pos != std::string::npos);
    str.shrink_to_fit();
}

更新：如果insert()事实证明太慢，您可以考虑建立第二个，std::string这样您就不会浪费时间在原始文件中移动字符std::string，例如：

std::string str = "whatever you want to search in...";
std::string seq = "what to find";
std::string ins = "what to insert";
std::string newStr;

auto foundPos = str.find(seq);
if (foundPos == std::string::npos)
{
    newStr = str;
}
else
{
    newStr.reserve(str.length() * 2);
    decltype(foundPos) startPos = 0;
    auto ptr = str.c_str();
    do
    {
        foundPos += seq.length();
        newStr.append(ptr + startPos, foundPos - startPos);
        newStr.append(ins);
        startPos = foundPos;
        foundPos = str.find(seq, startPos);
    }
    while (foundPos != std::string::npos);
    newStr.append(ptr + startPos, str.length() - startPos);
}