c++ - 从 C++ 中的字符串中删除字符

Question

我正在实现一种方法，以就地从字符串 txt 中删除某些字符。以下是我的代码。结果预期为“bdeg”。然而结果是“bdegfg”，似乎没有设置空终止符。奇怪的是，当我使用 gdb 进行调试时，在设置空终止符之后

(gdb) p txt
$5 = (std::string &) @0xbffff248: {static npos = <optimized out>, 
  _M_dataplus = {<std::allocator<char>> = {<__gnu_cxx::new_allocator<char>> = {<No data fields>}, <No data fields>}, _M_p = 0x804b014 "bdeg"}}

我觉得很合适。那么这里的问题是什么？

#include <iostream>
#include <string>

using namespace std;

void censorString(string &txt, string rem)
{
    // create look-up table
    bool lut[256]={false};
    for (int i=0; i<rem.size(); i++)
    {
        lut[rem[i]] = true;
    }
    int i=0;
    int j=0;

    // iterate txt to remove chars
    for (i=0, j=0; i<txt.size(); i++)
    {
        if (!lut[txt[i]]){
            txt[j]=txt[i];
            j++;
        }
    }

    // set null-terminator
    txt[j]='\0';
}

int main(){
    string txt="abcdefg";
    censorString(txt, "acf");

    // expect: "bdeg"
    std::cout << txt <<endl;
}

后续问题:

如果字符串没有像 c 字符串那样被截断。那么 txt[j]='\0' 会发生什么以及为什么它是 "bdegfg"而不是 'bdeg'\0'g' 或一些损坏的字符串。

另一个跟进:如果我使用 txt.erase(txt.begin()+j, txt.end());它工作正常。所以我最好使用字符串相关的api。关键是我不知道这些api的底层代码的时间复杂度。

Answer 1

std::string 并非如您所想的那样以 null 终止，因此您必须使用其他方式来执行此操作

修改函数为:

void censorString(string &txt, string rem)
{
    // create look-up table
    bool lut[256]={false};
    for (int i=0; i<rem.size(); i++)
    {
        lut[rem[i]] = true;
    }

    // iterate txt to remove chars
    for (std::string::iterator it=txt.begin();it!=txt.end();)
    {

        if(lut[*it]){
            it=txt.erase(it);//erase the character pointed by it and returns the iterator to next character
            continue;
        }
        //increment iterator here to avoid increment after erasing the character
        it++;
    }
}

这里基本上你必须使用 std::string::erase 函数来删除字符串中的任何字符，它将迭代器作为输入并将迭代器返回到下一个字符 http://en.cppreference.com/w/cpp/string/basic_string/erase http://www.cplusplus.com/reference/string/string/erase/

erase函数的复杂度是O(n)。所以整个函数的复杂度为 o(n^2)。一个非常长的字符串的空间复杂度，即 >256 个字符将是 O(n)。好吧，还有另一种方法，它的时间复杂度仅为 O(n)。创建另一个字符串并在遍历未审查的 txt 字符串时附加字符。

新函数是:

void censorString(string &txt, string rem)
{
    // create look-up set
    std::unordered_set<char> luckUpSet(rem.begin(),rem.end());
    std::string newString;

    // iterate txt to remove chars
    for (std::string::iterator it=txt.begin();it!=txt.end();it++)
    {

        if(luckUpSet.find(*it)==luckUpSet.end()){
            newString.push_back(*it);
        }
    }
    txt=std::move(newString);
}

现在这个函数的复杂度为 O(n)，因为函数std::unordered_set::find 和 std::string::push_back 的复杂度为 O( 1).如果您使用复杂度为 O(log n) 的普通 std::set find，则整个函数的复杂度将变为 O(n log n)。