CODEWITHSUNDEEP
c++
Jaideep Shekhar
Jaideep Shekhar

Reputation: 886

Encrypting a string but receiving an infinite loop

Problem:

I was trying to encrypt a std::string password with a single rule:

So that bAnanASplit becomes b0A0n0a0n0A0Spl0i0t. However, I got stuck in an infinite loop.

Here is the code:

    const std::string VOWELS = "AEIOUaeiou";
    std::string pass = "bAnanASplit";

    //Add zeroes before and after vowels
    for (int i = 0; i < pass.length(); ++i)
    {
        i = pass.find_first_of(VOWELS, i);
        std::cout << pass << "\n";
        if(i != std::string::npos)
        {
            std::cout << pass[i] << ": " << i << "\n";
            pass.insert(pass.begin() + i++, '0');
            pass.insert(pass.begin() + ++i, '0');
        }
    }

...And the result:

bAnanASplit
A: 1
b0A0nanASplit
a: 5
b0A0n0a0nASplit
A: 9
b0A0n0a0n0A0Split
i: 15
b0A0n0a0n0A0Spl0i0t
b0A0n0a0n0A0Spl0i0t
A: 2
b00A00n0a0n0A0Spl0i0t
a: 8
b00A00n00a00n0A0Spl0i0t
A: 14
b00A00n00a00n00A00Spl0i0t
i: 22
b00A00n00a00n00A00Spl00i00t
b00A00n00a00n00A00Spl00i00t
...

Any help? This sure seems strange.

Edit: All the answers were useful, and therefore I have accepted the one which I think best answers the question. However, the best way to solve the problem is shown in this answer.

Upvotes: 0

Views: 170

Answers (3)

Tanveer Badar
Tanveer Badar

Reputation: 5523

Never, ever, modify the collection/container you are iterating upon!

Saves you a lot of trouble that way.

Let's start with your code and generate a new string with vowels surrounded by 0.

const std::string VOWELS = "AEIOUaeiou";
std::string pass = "bAnanASplit", replacement;

//Add zeroes before and after vowels
for (auto ch : pass)
{
    if(VOWELS.find(ch) != std::string::npos)
        replacement += '0' + ch + '0';
    else
        replacement += ch;
}

And there you have it!

Upvotes: 5

Anubis
Anubis

Reputation: 7435

As the OP seems to look for the exact reason for the misbehavior, I thought to add another answer as the existing answers do not show the exact issue.

The reason for the unexpected behavior is visible in following lines.

for (int i = 0; i < pass.length(); ++i)
{
    i = pass.find_first_of(VOWELS, i);
    ...

Problem 1:

The loop counter i is an int (i.e. a signed int). But std::string::find_first_of returns std::string::npos if there's no match. This is usually the maximum number representable by an unsigned long. Assigning a huge unsigned value to a shorter signed variable will store a totally unexpected value (assuming you are not aware of that). In this case, i will becomes -1 in most platforms (try int k = std::string::npos; and print k if you need to be sure). i = -1 is valid state for the loop condition i < pass.length(), so the next iteration will be allowed.

Problem 2:

Closely related to the above problem, same variable i is used to define the start position for the find operation. But, as explained, i will not represent the index of the character as you would expect.

Solution:

Storing a malformed value can be solved by using the proper data type. In the current scenario, best options would be using std::string::size_type as this is always guaranteed to work (most probably this will be equal to size_t everywhere). To make the program work with the given logic, you will also have to use a different variable to store the find result.

However, a better solution would be using a std::stringstream for building the string. This will perform better than modifying a string by inserting characters in the middle.

e.g.

#include <iostream>
#include <sstream>

int main() {
    using namespace std;

    const string VOWELS = "AEIOUaeiou";
    const string pass = "bAnanASplit";

    stringstream ss;

    for (const char pas : pass) {
        if (VOWELS.find(pas) == std::string::npos) {
            ss << pas;
        } else {
            ss << '0' << pas << '0';
        }
    }
    cout << pass << "\n";
    cout << ss.str() << endl;
}

Upvotes: 1

kuro
kuro

Reputation: 3226

You are not exiting the loop in case i becomes std::string::npos. So, the i value is changed to some unexpected value (likely something like -1) when it gets to the position of last i or 0 after i(here I am referring to i of split). This is because i is an signed integer but in this case find_first_of() returns std::string::npos which is largest value that can be held by a size_t. In that case the terminating condition i < pass.length() may hold true and the loop continues. So, I am recommending following changes in your code -

for (size_t i = 0; i < pass.length(); ++i)
{
    i = pass.find_first_of(VOWELS, i);
    if(i == std::string::npos)
        break;

    pass.insert(pass.begin() + i++, '0');
    pass.insert(pass.begin() + ++i, '0');
}

On the same note if (i != std::String::npos) does not do what you are expecting it to do.

But then again it better not to modify the container while you are iterating over it which @Tanveer mentioned in his answer

Upvotes: 1

Related Questions