0

The question is:

Jay had borrowed a friend's coffee mug and somehow lost it. As his friend will be extremely angry when he finds out about it, Jay has decided to buy his friend a replacement mug to try to control the damage. Unfortunately, Jay does not remember the color of the mug he had borrowed. He only knows that the color was one of White, Black, Blue, Red or Yellow. Jay goes around his office asking his colleagues if they are able to recall the color but his friends don't seem to remember the color of the mug either. What they do know is what color the mug definitely was not. Based on this information, help Jay figure out what the color of the mug was.

The way I'm going about this:

I create a vector of all possible colors: White, Black, Blue, Red or Yellow. Then ask the user to enter the number of colleagues he will be questioning. Then take the color suggestions, and for every entry I compare it against the vector. If it is in there, I pop the color out. Eventually only one color will be left in the vector which is the color of the lost mug.

My issue:

I get an out of bound error after entering the first color and I am not able to figure out why. The exact error is:

terminate called after throwing an instance of 'std::out_of_range'
what():  vector::_M_range_check
Abort (core dumped)

My code is:

        #include <iostream>
        #include <string>
        #include <algorithm>
        #include <climits>
        #include <stdio.h>
        #include <vector>

        using namespace std;

        int main(int argv, char* argc[])
        {
            string color;
            vector<string> colorVector;

            colorVector.push_back("White");
            colorVector.push_back("Black");
            colorVector.push_back("Blue");
            colorVector.push_back("Red");
            colorVector.push_back("Yellow");

            int numColleagues;

            cout<< "Please enter the number of Colleagues" << endl;
            cin >> numColleagues;

            cout<< "Please enter each suggested color" << endl;

            int counter = 0;
            while (counter < numColleagues) {
            getline(cin, color);
            counter++;

                for (int i = 0; i < 5; i++) {
                    if (colorVector.at(i) == color) {
                        colorVector.erase(colorVector.begin() + i);
                    }
                }
            }
            return 0;
        }
Gela
  • 1
  • 1
  • 1
    You are attempting to remove elements from your vector as you are iterating through it. This often presents a number of issues, one of which you just ran into. You should investigate the [erase-remove idiom](http://en.wikipedia.org/wiki/Erase-remove_idiom). You can look at [this post](http://stackoverflow.com/questions/347441/erasing-elements-from-a-vector) for good discussion of that. – Cory Kramer Oct 10 '14 at 18:17

3 Answers3

1

You are erasing elements of your vector, but you wish to access all five elements (the loop runs from 0 to 5). So, let's say you remove the first and then you try to access the element at position 4. Out of bounds!

So change your loop to this:

colorVector.erase(std::remove(colorVector.begin(),
                              colorVector.end(), color), colorVector.end());

More on erase-remove idiom.

Community
  • 1
  • 1
gsamaras
  • 71,951
  • 46
  • 188
  • 305
  • If you are going to implement the erase remove idiom, you do not need to keep the `for` loop, nor do you have to keep the `if` block. Literally just the one line `colorVector.erase(std::remove_if(colorVector.begin(), colorVector.end(), color), colorVector.end());` is required (note I replaced `remove` with `remove_if`. – Cory Kramer Oct 10 '14 at 18:30
  • I suspect you are right @Cyber. However, I assume this will not compile. I am testing... (I mean `remove_if` requires a predicate). – gsamaras Oct 10 '14 at 18:32
  • I think `std::remove` would so just fine. The problem with the predicate of the `std::remove_if` is that we want to compare every element with `color`. – gsamaras Oct 10 '14 at 18:42
0

When you call vector::erase, it will return an iterator pointing to the new location of the element that followed the erased element. So if we erase this element:

1 2 3 4 5 6
      ^

Our iterator will automatically update to point to the 5. So we don't have to increment the iterator again, it's already sort of incremented. With that in mind:

auto it = colorVector.begin();
for (; it != colorVector.end(); /* do not increment it */ )
{
    if (*it == color) 
    {
        it = colorVector.erase(it); // erase and update
    }
    else
    {
        ++it; // just update
    }
}

Of course even better to just use the algorithms which are less error prone

colorVector.erase(
    std::remove(colorVector.begin(), colorVector.end(), color),
    colorVector.end()
);
Barry
  • 286,269
  • 29
  • 621
  • 977
-1

You are modifying colorVector during an iteration.

As soon as you remove one of the colors, the vector is suddenly only 4 items in length. Now when you try to go to the 5th item (which was safe to do before the deletion) - it crashes

Try this:

for (int i = 0; i < colorVector.size(); i++) {
    if (colorVector.at(i) == color) {
        colorVector.erase(colorVector.begin() + i);
        --i;
    }
}

By stopping at colorVector.size instead of a hard-coded 5 you are ensured that the list never goes out of bounds.

Edit:
Added --i statement to avoid skipping next one

Edit2:
As the comments below state, it is generally a bad idea to remove items from the array you're currently iterating from.

Daniel Blake
  • 44
  • 4
  • 2
    Erasing from a vector while you are iterating over it is a bad idea even if you do check the size every loop. Sure, you won't go out-of-bounds but you may skip over some elements. – Chris Drew Oct 10 '14 at 18:38
  • You should decrease `i` if you delete something. Better use the technique suggested in the other answer. – gsamaras Oct 10 '14 at 18:49