removing a character from a string in C++

Question

I am aware of the fact that there already exist solutions to this that make use of the #include <algorithm> but I was wondering if the following could be a viable way of doing it:

#include <iostream>
using namespace std;
void remove_character_from_result(string& result, char remove){
    int size = result.size(); 
    for (int i = 0; i < size; i++){
        int pos = result.find(remove); 
        if(pos == result.npos) break;
            else{
                if(pos == 0)
                    result = result.substr(1); 
                else
                    result = result.substr(0, pos) + result.substr(pos + 1);
            }
    }
}
int main() {
    string result = "Asad Ahmad";
    remove_character_from_result(result, 'A');
    cout << result << endl;
    return 0;
}

I have tested my code against normal test cases and it does seem to work, I am not sure whether the time complexity would be any better than result.erase(remove(result.begin(), result.end(), 'A'), result.end()); would appreciate if any one could shed some light on this :) PS I apologize for not using references instead of pointers or '*' instead of '->' earlier - this is code that I have written that I am not really proud of..

Answer 1

Your code has an assortment of issues.

#include <iostream>

If you are going to access the std::string class, you need to #include <string>. You shouldn't rely on it being included by <iostream>

using namespace std;

This is a terrible practice, polluting your global namespace with all the names from std. If you want to avoid having to repeat a specific name, prefer the syntax

using std::string;

for example.

void remove_character_from_result(string* result, char remove){

Your code doesn't check for this pointer being null. It would be better to take the parameter by reference.

void remove_character_from_result(string& result, char remove){

int size = (*result).size(); 

While (*result).size() achieves the end, you should probably use -> to remind yourself you're working with a pointer, and perhaps remember to check it isn't null.

size = result->size();

Here we run into a bug in your program too:

int size = result->size();

size() returns a std::string::size_type which is unsigned and possibly significantly larger that int. Your code stops working as soon as a string is larger than std::numeric_limits<int>::max().

This should either be

auto size = result->size();

or

std::string::size_type size = result->size();

for (int i = 0; i < size; i++){

Again we have the size problem here, but we also have the problem that the size may change during our operations. You should replace both of these lines with:

for (std::string::size_type i = 0; i < result->size(); ++i) {

The next chunk of code:

    int pos = (*result).find(remove); 
    if(pos == (*result).npos) break;
        else{
            if(pos == 0)
                *result = (*result).substr(1); 
            else
                *result = (*result).substr(0, pos) + (*result).substr(pos + 1);

doesn't make a whole lot of sense, and does things the hard way. In the first case, you create a new substring and then copy it into yourself. In the second case you create two temporary substrings which you add together creating a third, and then you copy this into yourself.

It would be better to use erase.

It's also not clear why you have the size-constrained loop in the first place.

You could better replace the whole function with something like this:

#include <iostream>
#include <string>

void remove_character_from_result(std::string& result, char remove) {
   for (size_t pos = 0; (pos = result.find(remove, pos)) != result.npos; ) {
       size_t end = pos + 1;
       while (end < result.size() && result[end] == remove)
           ++end;
       result.erase(pos, end - pos);
   }
}

int main() {
    std::string s = "hello world";
    remove_character_from_result(s, 'l');
    std::cout << s << '\n';
}

The time complexity of this for worst case is that it has to remove half the characters, which would be O(NlogN).

You could improve the performance by working from the right rather than the left: Consider removing the character 'a' from 'ababab'. The first erase is followed by copying 5 characters left, the second erase 3 characters and the third erase 1 character. If we worked the other way around, the first erase would be 1 character, the second erase 2 and the third erase 3.

Answer 2

If you really insist on doing this on your own, you probably want to use string's member functions to do the searching. For a (probably tiny) gain in efficiency, you also want to do the searching from the end back to the beginning of the string. I'd also pass the string by reference instead of passing a pointer.

Finally, instead of building a new string out of substrings, you might as well just erase the character you want gone:

void remove_character(string &result, char remove) {   
    std::string::size_type pos;
    while ((pos = result.rfind(remove)) != std::string::npos)
        result.erase(pos, 1);
}

If you want to optimize a little (or possibly even quite a bit) more, you can resume the second and subsequent searches from the point where you found the previous instance:

void remove_character(string &result, char remove) {   
    std::string::size_type pos = std::string::npos;
    while ((pos = result.rfind(remove, pos)) != std::string::npos)
        result.erase(pos, 1);
}