1

我正在实现一种方法来从字符串 txt, in-place中删除某些字符。以下是我的代码。结果预期为“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底层代码的时间复杂度。

4

5 回答 5

2

在 a 中嵌入空终止符std::string是完全有效的，不会改变字符串的长度。但是，例如，如果您尝试使用流提取来输出它，它会给您带来意想不到的结果。

您尝试达到的目标可以更容易地完成：

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>

int main()
{
    std::string txt="abcdefg";
    std::string filter = "acf";
    txt.erase(std::remove_if(txt.begin(), txt.end(), [&](char c) 
    { 
        return std::find(filter.begin(), filter.end(), c) != filter.end(); 
    }), txt.end());

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

与 Himanshu 的回答一样，您可以完成 O(N) 复杂性（使用额外的内存），如下所示：

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <unordered_set>

int main()
{
    std::string txt="abcdefg";
    std::string filter = "acf";

    std::unordered_set<char> filter_set(filter.begin(), filter.end());
    std::string output;

    std::copy_if(txt.begin(), txt.end(), std::back_inserter(output), [&](char c)
    {
        return filter_set.find(c) == filter_set.end();  
    });

    // expect: "bdeg"
    std::cout << output << std::endl;
}
于 2013-09-19T20:46:10.253 回答
2

std::string 不是您认为的空终止，因此您必须使用其他方法来执行此操作

修改函数为：

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/

擦除函数的复杂度为 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)。

于 2013-09-19T20:26:00.443 回答
1

你没有告诉字符串你已经改变了它的大小。resize如果从字符串中删除任何字符，则需要使用该方法更新大小。

于 2013-09-19T20:26:46.433 回答
0

问题是你不能像对待 C 风格的字符串一样对待 C++ 字符串是问题所在。即你不能像在 C 中那样只插入一个 0。为了说服你自己，把它添加到你的代码中“cout << txt.length() << endl;” - 你会得到 7。你想使用 erase() 方法；

Removes specified characters from the string.
1) Removes min(count, size() - index) characters starting at index.
2) Removes the character at position.
3) Removes the character in the range [first; last).
于 2013-09-19T20:25:24.333 回答
0

文本是字符串而不是字符数组。这段代码

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

不会截断第 j 个位置的字符串。

于 2013-09-19T20:26:35.727 回答