удалить символы из строки в 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; 
} 

последующий вопрос:

, если строка не обрезается, как гр строки. так что происходит с txt[j]='\0' и почему это «bdegfg» не «bdeg» \ 0'g 'или некоторые поврежденные строки.

другой последующий: если я использую txt.erase(txt.begin()+j, txt.end()); он отлично работает. поэтому я лучше использую связанный с строкой api. Дело в том, что я не знаю временную сложность базового кода этих api.

Answer 1

Проблема в том, что вы не можете обрабатывать строку C++, как строка стиля C, является проблемой. То есть вы не можете просто вставить 0, как в C. Чтобы убедиться в этом, добавьте это в свой код «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). 

Answer 2

станд :: строка не нулем, как вы думаете, поэтому вы должны использовать другие способы, чтобы сделать это

изменить функцию:

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). , если вы используете обычный std :: set find, который имеет сложность O (log n), тогда сложность целой функции станет O (n log n).

Answer 3

Текст - это строка, которая не является массивом символов. Этот код

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

Не обрезает строку на j-й позиции.

Answer 4

Вы не сказали строке, что вы изменили ее размер. Вам нужно использовать метод resize для обновления размера, если вы удалите любые символы из строки.

Answer 5

Внедрение нуль-терминаторов внутри 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; 
}