3

The purpose of my program is to remove all the vowels in a string.

std::string disemvowel(std::string str) { for (unsigned int i = 0; i < str.length(); ++i) { switch(str[i]) { case 'A': case 'a': case 'E': case 'e': case 'I': case 'i': case 'O': case 'o': case 'u': case 'U': str.erase(str.begin() + i); break; default: break; } } return str; }

Inputting a string: aaAAaiieEeOoU,,,.,132@

The characters that are accessed and deleted are: aAaiEOU,,.,132@

Result String: aAieeo,,,.,132@

The program seems to just never access the vowels above.

I don't see any issue with how I'm approaching this. I should be accessing every character in the string until the end of its length, no?

Improve this question

4 Answers 4

Reset to default
8

Every time you erase a character, str changes, and then when you increment i, you are skipping the next letter.

Generally, don't remove things from a sequence as you are iterating it, but if you are iterating with an index, then a good trick is to go backwards if you can. You are changing everything after i, but you don't care.

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

8 Comments

Would an appropriate solution to this be that I decrement 'i' every time I erase?
It will work, but it will make your code more complex -- I usually iterate backwards and then it stays simple
So you would suggest to move backwards in a string if I'm making changes to its sequence?
Yes if, (1) you are using indexes that don't invalidate on changes (2) changing the sequence only affects elements at i and after.
@AngoMango Seek ye the Erase-Remove Idiom
|
4

Try this -

std::string disemvowel(std::string str) { for (unsigned int i = 0; i < str.length(); ++i) { switch(str[i]) { case 'A': case 'a': case 'E': case 'e': case 'I': case 'i': case 'O': case 'o': case 'u': case 'U': str.erase(str.begin() + i),i--; break; default: break; } } return str; }

You were deleting a character and moving to the next character. But when you deleted the current character, you were moving the next character to current index. So your loop was skipping few letters. The above code will work.

Another possible solution would be to loop backwards where you wouldn't have to worry about increasing/decreasing index after you delete a vowel.

Yet another simple method, just so you know that this exists, is a solution using regex as follows -

std::string disemvowel(std::string str) { regex r("[aAeEiIoOuU]"); return regex_replace(str, r, ""); }

You have to use #include <regex> for the above solution to work.

Hope this helps !

Improve this answer

Comments

3

You can implement this in terms of std::remove_if and a function:

auto is_vowel(char c) -> bool { switch(c) { case 'A': case 'a': case 'E': case 'e': case 'I': case 'i': case 'O': case 'o': case 'u': case 'U': return true; default: return false; } } auto disemvowel(std::string str) -> std::string { str.erase( std::remove_if(str.begin(), str.end(), is_vowel), str.end() ); return str; }

The call to std::remove_if with std::string::erase implement the algorithm to correctly and efficiently remove multiple character based on a condition.

If you don't use such provided algorithm, you have to take into account the index of the deleted stuff, either by iterating in reverse or by not incrementing the index when a character is deleted from the string.

Improve this answer

2 Comments

Since you are using auto, you must be using C++11 or later, so you can alternatively use a lambda instead of a function, eg: std::string disemvowel(std::string str) { str.erase(std::remove_if(str.begin(), str.end(), [](char ch){ return ...; }), str.end()); return str; }
@RemyLebeau I found the function large enough to be clearer as being separate with its own name.
0

I suggest a two-pass approach.

  1. In the first pass, you build a container (vector) of all the elements you wish to remove.
  2. In the second pass, you build a new string containing only the elements not removed.

When you delete elements from anywhere but the end of a vector, string, or array, you have to copy all the values after that 1 forward of their original position. O(n^2). The above method is just O(n). Walking through a string and a vector is pretty cache friendly, so that's not as much of a concern.

Note that preventing pass 2 from becoming O(n^2) makes the code a bit more complex, but entirely doable.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.