1

I was implementing a method to remove certain characters from a string txt, in-place. the following is my code. The result is expected as "bdeg". however the result is "bdegfg", which seems the null terminator is not set. the weird thing is that when I use gdb to debug, after setting null terminator 

(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"}}

it looks right to me. So what is the problem here?

#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; }

follow-up question:

if string is not truncated like c string. so what happens with txt[j]='\0' and why it is "bdegfg" not 'bdeg'\0'g' or some corrupted strings.

another follow-up: if I use txt.erase(txt.begin()+j, txt.end()); it works fine. so I'd better use string related api. the point is that I do not know the time complexity of the underlying code of these api.

Improve this question
12
  • what did you intend this "bool lut[256]={false};" to do? It doesn't initialize the array to all false values. Commented Sep 19, 2013 at 20:14
  • 2
    @Jay: Actually, it does. So would this: bool lut[256] = {}; -- When you provide an initializer for an array, any unspecified elements are value initialized. For bool, value initialized means false. Commented Sep 19, 2013 at 20:15
  • I think only by accident though. "The elements of global and static arrays, on the other hand, are automatically initialized with their default values, which for all fundamental types this means they are filled with zeros." i.e. the "={false}" does nothing but initialize the first element to false. All the remaining are the default value, which I would guess is false. Commented Sep 19, 2013 at 20:18
  • Can you use C++11? std::remove_if(... ) would make this code a lot simpler. Commented Sep 19, 2013 at 20:19
  • 1
    @Jay: = {false}; will initialize the first element to false, and then, because there is an initializer at all, all of the elements will be initialized to false. If he had written = {true};, that would initialize the first element to true, and all the rest to false (again, because he provided an initializer). If, however, he had simply written bool lut[256]; -- with no initializer, the elements would be left uninitialized, in an uncertain state. It's just a rule of the language. Commented Sep 19, 2013 at 20:25

5 Answers 5

Reset to default
2

std::string is not null terminated as you think therefore you have to use other ways to do this

modify the function to:

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++; } }

Here basically you have to use std::string::erase function to erase any character in the string which take iterator as input and return iterator to next character http://en.cppreference.com/w/cpp/string/basic_string/erase http://www.cplusplus.com/reference/string/string/erase/

the complexity of erase function is O(n). So the whole function would have complexity of o(n^2). space complexity for a very long string i.e. >256 chars would be O(n). Well there is another way which will have only O(n) complexity for time. create a another string and append the character while iterating over the txt string which are not censored.

The new function would be:

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); }

Now this function has complexity of O(n), since functionstd::unordered_set::find and std::string::push_back have complexity of O(1). if You use normal std::set find which has complexity of O(log n), then complexity of whole function would become O(n log n).

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I believe you only want to do it++ if lut[*it] == true. In the case that if(!lut[*it]), the txt.erase() causes you to already point at the next valid character.
I changed the if condition. Now when the character is censored or is true in lookup table, character would be erased and it will point to next character.
2

Embedding null-terminators inside a std::string is completely valid and will not change the length of the string. It will give you unexpected results if you, for example, try to output it using a stream extraction, though.

The goal you are attempting to reach can be done much easier:

#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; }

In the same vein as Himanshu's answer, you can accomplish an O(N) complexity (using additional memory) like so:

#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; }
Improve this answer

4 Comments

what is the time complexity of your solution? O(n-square)?
The short answer: it would work out to be either O(N^2) or O(N^3), depending on the implementation of std::string::erase. std::find is an O(N) operation (on the filter array). std::remove_if is another O(N) operation. std::string::erase can be O(N) (worst case), but the implementation can also be done in O(1) (in fact, I believe all modern implementations are currently O(1) - I haven't seen one that is O(N) in over 10 years).
look at the answer below it does it in O(n) time.
Updated with a version that utilizes the appropriate algorithm.
1

You have not told the string that you have changed it's size. You need to use the resize method to update the size if you remove any characters from the string.

Improve this answer

1 Comment

Yep, seems like you could truncate the string to the final value of j after the character-removal loop is done.
0

Problem is you can't treat the C++ string like a C style string is the problem. I.e. you can't just insert a 0 like in C. To convince your self of this, add this to your code "cout << txt.length() << endl;" - you'll get 7. You want to use the erase() method;

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).
Improve this answer

Comments

0

Text is a string not a character array. This code

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

Will not truncate the string at the j-th position.

Improve this answer

2 Comments

so then what happens with txt after this is executed? any changes to txt?
It just changes the j-th character to a zero. The remainder of the string is still present. @Himanshu Pandey has what looks like a good solution

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.