c++ - 比较 C++ 中的 str.erase() 效率

Question

假设一个字符串包含许多前导空白字符。我的任务是删除这些字符。

我在想这个:

while(1) {
    if(str[i] == ' ')
        str.erase(str.begin()+i);
    else
        break;
}

每个操作的复杂度是 O(1) 还是超过 O(n)？我在许多博客中读到我们不应该删除单个元素，因为整个字符串可能会被复制到另一个地方以保持连续的内存分配。

那么这种删除呢:

while(1) {
    if(str[i] == ' '){
        cnt++;
        break; 
    }
}
str.erase(0, cnt);

哪个更好？

Answer 1

第一个例子效率很低。 erase 将删除点以外的所有元素向下移动以填充 erase 创建的空间；此代码最终将字符串的所有后续元素复制一次每个前导空格。第二个示例没有执行问题要求的操作，因为 break 语句提前退出了循环。但是第二种方法要好得多。一般来说，如果您多次调用 erase，您可能已经犯了错误。最好找到您要保留的第一个字符，然后删除它前面的所有字符。所以:

std::string::size_type pos = str.find_first_not_of(' ');
if (pos != std::string::npos)
    str.erase(0, pos);