Introductions and Iterators

Hi,

I Just started programming C last week using Beginnning C++ programming which I must say is excellent. I have a basic grounding in PHP and did some Java in college so am moving through the book at quite a pace but im stuck on one of the exercise questions on Vectors,iterators and the erase member function so I joined up here to ask what will probably be the first of many questions and her e it is:

Im trying to match user input against a string object contained in a vector and erase that object but I get compile errors. Can anyone put me right? Heres the relevant code snippit....

Code:

for(myIterator = games.begin(); myIterator < games.end(); ++myIterator)
        temp = *myIterator;
        if (gameEntered == temp)
                 games.erase(myIterator);
                 cout << "Game removed.\n\n" << endl;
        else
                 out << "No match.\n\n" << endl;

variable declarations and actual error message text will help

Possibly that you misspelled cout as out in the second case?
Or that you're missing the curly braces on the two-statement then-clause? (You know, that shouldn't happen to a Java programmer.)
Or the same problem for the for-loop?
Then there's the less-than comparison for the iterators. That may work with vector, but it's a bad idea because it won't work for e.g. list.

Of course, there's still the problem with invalidating your iterator. In short, you can't do an erase-loop this way. C++ iterators aren't like Java iterators. You can't call the remove() (or whatever it's called) method of the iterator and just move on. You have to do it somewhat more complicated.

Code:

for(vector_t::iterator it = vec.begin(); it != vec.end(); /* nothing here */) {
  if(*it == theGame) {
    it = vec.erase(it);
    std::cout << "Game removed." << std::endl;
  } else {
    ++it;
    std::cout << "No match." << std::endl;
  }
}

Thanks for the replies. It was the curly brackets on the If Else that was nested in the for loop that did it.

In response to some of the comments:

The Cout was just a cut and paste error.

I never said I was any good at Java , I only did it to a basic level and that was 3 years ago now. With the curly brackets I am following the book syntax and they dont use curlys very much at all. I use them all the time in PHP and didnt know you could get away without them, the C book im using says they are unessicary and its all to do with scope. I gotta say I dont fully understand this but im just following how they do it. Any comments on this?

Anyway thanks a lot for the help, here is the full working code :

Code:

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cctype>

using namespace std;

int main()
{

vector<string> games;
char option;
vector<string>::iterator myIterator;
vector<string>::const_iterator iter;

cout << "Games Inventory\n\n";
string gameEntered;
string temp;

while (option != 'X')
{
    cout << "(D)isplay, (A)dd or (R)emove Games or e(X)it : ";
    cin >> option;
    option = toupper(option);

    switch(option)
    {

        case 'D':
                cout << "Displaying Games....\n\n";
                if (games.size() > 0)
                                for (iter = games.begin(); iter < games.end(); ++iter)
                                     cout << *iter << endl;

                else
                                cout << "There are no games to display.\n\n";
                cout << "\n\n";
                break;
        case 'A':
              cout << "Enter a game title to add : ";
              cin >> gameEntered;
              games.push_back(gameEntered);
              cout << gameEntered << " added.\n\n";
              break;
        case 'R':
                if (games.empty())
                {
                      cout << "There are no games to remove.\n\n";
                }
                else
                {
                      cout << "Enter a game title to remove : ";
                      cin >> gameEntered;

                        for(myIterator = games.begin(); myIterator < games.end(); ++myIterator)
                             temp = *myIterator;
                             if (gameEntered == temp) {
                                 games.erase(myIterator);
                                 cout << "Game removed.\n\n" << endl;
                             } else {
                                 cout << "No match.\n\n" << endl;
                             }
                 }
                break;
        case 'X':
                cout << "Exiting..........\n\n";
                break;
        default:
                cout << "You made an illegal choice.\n";
    }


}



cout << "\nPress the enter key to exit";
cin.ignore(cin.rdbuf()->in_avail() + 2);

return 0;

}

Read #3 again, especially the bit about INVALIDATING ITERATORS.

Originally Posted by Mad Frank

Any comments on this?

Yes. It's total nonsense.

Here's how control statements work in C and C++:

Code:

keyword [ '(' control expression ')' ] statement

This means that a control statement starts with a keyword ("if", "for", "while", "try", ...) possibly followed by a control expression ("else", "do" and "try" aren't, all others are), followed by a single statement.
This statement can either be a normal statement, like

Code:

std::cout << "Hello!";

or it can be a block statement. And a block statement is

Code:

'{' statements '}'

(It can also be another control statement, or some other type of statement that C++ has, but these two are the most important.)

In other words, if you have exactly one statement, you can do away with the braces. If you have more, you need them.
Personally, I always put them there. All too often, I start out with one statement and later add more, and I don't like the possibility of forgetting to add the braces then.

Thanks, that makes it a lot clearer as I was confused over that. I will always use them from now.

Re Invalidating my iterators. Would this be because once I remove an item from a vecor that all my iterators become invalid as they all shift? So by not incrementing it when you erase you compensate for the remaining values all shifting up one?

Anyway I have rewritten my loop according to your advice and I have also changed the No Match output as it was outputting it for every element in the vector that didnt match. However the way I have done it seems messy, is there a better way?

Code:

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cctype>

using namespace std;

int main()
{

vector<string> games;
char option;
vector<string>::iterator myIterator;
vector<string>::const_iterator iter;

cout << "Games Inventory\n\n";
string gameEntered;
string temp;
char match;

while (option != 'X')
{
    cout << "(D)isplay, (A)dd or (R)emove Games or e(X)it : ";
    cin >> option;
    option = toupper(option);

    switch(option)
    {

        case 'D':
                cout << "Displaying Games....\n\n";
                if (games.size() > 0)
                                for (iter = games.begin(); iter < games.end(); ++iter)
                                     cout << *iter << endl;

                else
                                cout << "There are no games to display.\n\n";
                cout << "\n\n";
                break;
        case 'A':
              cout << "Enter a game title to add : ";
              cin >> gameEntered;
              games.push_back(gameEntered);
              cout << gameEntered << " added.\n\n";
              break;
        case 'R':
                if (games.empty())
                {
                      cout << "There are no games to remove.\n\n";
                }
                else
                {
                      cout << "Enter a game title to remove : ";
                      cin >> gameEntered;

                        for(myIterator = games.begin(); myIterator != games.end(); /* removed this bit */ )
                             if (gameEntered == (*myIterator)) {
                                 games.erase(myIterator);
                                 cout << "Game removed.\n\n" << endl;
                                 match = 'Y';
                             } else {
                                 ++myIterator;
                             }
                        if (match != 'Y') {
                                cout << "No match.\n\n" << endl;
                        }
                 }
                break;
        case 'X':
                cout << "Exiting..............\n";
                break;
        default:
                cout << "You made an illegal choice.\n";
    }


}


cout << "\nPress the enter key to exit";
cin.ignore(cin.rdbuf()->in_avail() + 2);

return 0;

}

Clue: Look at the return value from games.erase(myIterator), you need to use it.

Ah right, I can see I forgot to assign the return value from my erase statement to myIterator as CornedBee told me to so I have done that now.

I might be a bit thick though but I still cant see why and whats going on.

I tried this in my prog to help myself understand :

Code:

                        for(myIterator = games.begin(); myIterator != games.end(); /* removed this bit */ )
                             if (gameEntered == (*myIterator)) {
                                cout << "Myiterator before= " << (*myIterator) << endl;
                                games.erase(myIterator);
                                cout << "Myiterator after = " << (*myIterator) << endl;
                                 cout << "Game removed.\n\n" << endl;
                                 match = 'Y';
                             } else {
                                 ++myIterator;
                             }

Code:

                        for(myIterator = games.begin(); myIterator != games.end(); /* removed this bit */ )
                             if (gameEntered == (*myIterator)) {
                                cout << "Myiterator before = " << (*myIterator) << endl;
                                myIterator = games.erase(myIterator);
                                cout << "Myiterator after = " << (*myIterator) << endl;
                                 cout << "Game removed.\n\n" << endl;
                                 match = 'Y';
                             } else {
                                 ++myIterator;
                             }

and the results were the same. What am I not getting?

I think you're accessing memory that is no longer yours. When you erase() an element, the new end() moves one to the left and marks the end of your allowed memory. That means the old end() is now two past the end, so between the old end and the new end there is one block of memory that is not yours. The vector probably doesn't reallocate by creating a smaller array, copy the elements into it, and release the current memory, so the block of memory between the new end and the old end is probably still reserved for the vector, but by continuing on until you hit the old end(), you are iterating over memory that isn't part of the allowed memory for the current vector.

I can't get it to crash with strings in the vector, but with ints in the vector, the following crashes(no matter how you handle the interator after calling erase() ):

Code:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
	
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	

	vector<int>::iterator iter = v.begin();
	vector<int>::iterator end = v.end();
	
	int counter = 0;
	while(iter != end)
	{

		if(*iter == 2)
		{
			v.erase(iter);
		}
		else
		{
			++iter;
		}
		
		cout<<counter<<endl;
		++counter;
	}

	
	return 0;
}

What you are not getting is that C++ is a very weird language compared to managed languages like Java and PHP. Just because something is wrong doesn't mean it won't work. It might work. It might work a hundred times, perhaps a thousand, and then crash. Or it might until you use a different compiler, or even just different compiler settings. Have you tried your program with Visual Studio.Net 2005 in debug mode? I'm pretty sure it would assert there. (The debug iterators are supposed to detect incorrect usage.)

What exactly is the problem with the code?
The iterator becomes invalid. The documentation for std::vector states that upon erase, all iterators after and including the iterator referencing the deleted element become invalid. When an iterator becomes invalid, there's absolutely nothing you can do anymore with it. You can't increment it. You can't decrement it. You certainly can't dereference it. The standard says that all these operations invoke undefined behaviour.
This is an important term. It means that it is absolutely unpredictable what happens. This is not as in Java: there, a specification will say, "causes an InvalidStateException to be thrown" or "causes a ConcurrentModificationException to be thrown". In C++, the behaviour is undefined: it can do whatever it feels like: throw an exception, abort the program, do more or less random things, even work as intended. The point is that the programmer shouldn't do it in the first place, so it is not prescribed what happens if he does it.
In your case, the effect is "happens to work as intended". But because this behaviour is far from guaranteed, it is not something to rely on.

So why does this work in this case?
The reason is in the way vector works. It is effectively a linear region in memory, and an iterator over it is nothing more than a pointer.

Code:

1 | 2 | 3 | 4 | 5
    ^

When you delete, the vector is adjusted. The iterator is now invalid, but it still points to the same memory location.

Code:

1 | 3 | 4 | 5
    ^

So it appears as if you could still use it.
Of course, if this were a linked list, the node the iterator refers to has been deleted. Perhaps the memory was zeroed out and the next pointer now points to NULL. That would be a mess next time you increment it. Or perhaps the node was the only thing left on the memory page and the whole page has been returned to the OS. Hello, access violation.

The erase() member function of the linear containers (std::list, std::vector, std::deque) is defined to return a valid iterator to the element after the deleted one. This is the ONLY valid way to obtain the iterator after the delete element, aside from keeping an index and recalculating the iterator.

This is what you should do:

Code:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> //remove()

using namespace std;

int main()
{
	
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(4);
	v.push_back(2);
	

	vector<int>::iterator newEnd;
	newEnd = remove(v.begin(), v.end(), 2);
	
	vector<int>::iterator iter = v.begin();
	for(;iter != newEnd; ++iter)
	{
		cout<<*iter<<endl;
	}

	//if you actually need to use erase():
	v.erase(newEnd, v.end());
	
	return 0;
}

Note: when you use remove(), the elements are just copied over one spot, which means the vector still has the same size.

The documentation for std::vector states that upon erase, all iterators after and including the iterator referencing the deleted element become invalid...The standard says that [ed. using invalid iterators] invokes undefined behaviour. This is an important term. It means that it is absolutely unpredictable what happens.

I vote for that explanation.

Thats much clearer now, thank you very much guys. You had solved my problem with my code in the first few replies and the rest of it was just me seeking to get a better understanding and handle on Iterators. After all your help and advice I have a much better handle on them. Once again thank you for your patience and help.