Why aren't all the string characters being accessed?

user_11694794 0
Viewed 87

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?

c++ string
4 Answers

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.

user_39370

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 !

user_136020760

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.

user_21046970

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.

user_4777710
Related