c++rle

How can I iterate through the last element of the vector without going out of bounds?


The expected output is 1a1b1c but I only get 1a1b If I try putting '-1' next to input.size() in the for loop but that will just ignore the bug. What I'm looking for is that I want to be able to iterate through the last member of the string without going out of bounds.

 std::string input = "abc";

for (unsigned int i = 0; i < input.size(); i++){
     int counter = 1;
    while(input.at(i) == input.at(i+1) && i < input.size()-1){

        counter++;
        i++;
    }
        number.push_back(counter);
        character.push_back(input.at(i));
}

Solution

  • Few points for you to consdier:

    1: for (unsigned int i = 0; i < input.size(); i++) specifically i++. This is a postfix operation meaning it returns i then increments the value of i. Not as big a deal here with integers but with iterators this can get very expensive as you create a copy of the iterator each time. Prefer to say what you mean / what you actually want, which is to increment i, not get a copy of i and increment i afterwards. So prefer ++i which only increments i and does not make a copy.

    2: unsigned int i = 0 Firstly its better than using an int which has a signed -> unsigned conversaion every comparison with input.size() which returns a size_t. Secondly unsigned int is not guaranteed to be big enough to hold the size of the string and requires a promotion from (probably) 32 bit -> 64 bit unsigned to compare with size_t

    3: cognitive complexity, nested loops which both mutate the same invariant (in this case i) makes the code more difficult to reason about and will ultimately lead to more bugs as code evolves over time. where possible only have one place where a loop invariant is mutated.

    4: As pointed out by others the while loop while(input.at(i) == input.at(i+1) && i < input.size()-1) can exceed the size of the string and using the .at member function of string will throw for an out of bounds access. This can be simply resolved with point 3 by refactoring ther nested loop into a single loop.

    5: Avoid so many calls to .at, we are in complete control of the index we use to index the string so you can use operator[] safely as long as we can guarantee i will always be a valid index which in this case i think you can.

    6: i < input.size() using < when its not the check you want and its much more expensive than the check you actually want which is i != input.size(). Check out this trivial comparison in compiler explorer

    Thankfully the fix from shadowranger Fixes your problem completely ie: while(i < s.size()-1 && s.at(i) == s.at(i+1)) However i would like to offer an alternitive with no nested loops to show you how to avoid my points 3,4, 5 and 6 :

    void do_the_thing(std::string const& s) {
        std::cout << "Considering: \"" + s + "\"\n";
        if(s.empty()) {
            return;
        }
    
        size_t const length = s.length(); // avoiding repeated calls to length which never changes in this case
        if(length == 1) {
            std::cout << "1" << s[0] << "\n";
            return;
        }
    
        std::vector<unsigned> number;
        std::vector<char> character;
    
        // do the stuff your example did
        char last = s[0];
        unsigned same_count = 1;
        for(size_t ii = 1; ii != length; ++ii) {
            char const cur = s[ii];
            if(cur == last) {
                ++same_count;
            } else {
                number.push_back(same_count);
                character.push_back(last);
                last = cur;
                same_count = 1;
            }
        }
    
        if(*s.rbegin() == last) {
            number.push_back(same_count);
            character.push_back(last);
        }
    
        // print the things or use them in some way
        assert(number.size() == character.size());
    
        size_t const out_len = character.size();
        for(size_t ii = 0; ii != out_len; ++ii) {
            std::cout << number[ii] << character[ii];
        }
        std::cout << "\n";
    }