Trouble with vectors

Started by
14 comments, last by Lajnold 18 years, 9 months ago

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

using namespace std;

vector<string> games;                //database for the game titles
vector<string>::iterator myIterator; //iterator...
vector<string>::const_iterator iter; //same

bool quit = false; // if user wants to quit
int counter = 0; // for counting purposes 
string choice; // user input
string gameName; // contains name of the game, which can be used for several operations

int main()
{
	           // welcome screen
	cout << "\tWelcome to the game database\n\n";
	cout << "Here you can create a list of games.\n\n";
	cout << "To add a game title to the list, enter 'add'.\n";
	cout << "To remove a game title from the list, enter 'remove'.\n";
	cout << "To take a look at the list, enter 'list'.\n";
	cout << "To receive help on the commands, enter 'help'.\n";
	cout << "To quit the program, enter 'quit'.\n";
	
	while (quit != true)
	{
		cout << "\n: "; // creating a dos like enviroment
		cin >> choice;  // and asking for input
 		cout << endl;   //

		if (choice == "list") //when the user wants to see the list
		{
			if (games.size() == 0)
				cout << "No games in the list, yet.\n";
			else
			{
				cout << "The games:\n"; 
				          // we display the list
				for (iter = games.begin(); iter != games.end(); ++iter)
					cout << *iter << endl;
			}
		}

		if (choice == "add") // when user wants to  add something
		{
			cout << "enter the title of the game.\n";
			cout << ": ";
			cin  >> gameName;
			cout << endl;

			      // if he actually entered something, we add it to the database
			if (gameName != "")
				games.push_back(gameName);
			else
				cout << "invalid input...\n";

			gameName = ""; // reset
		}

		if (choice == "remove") // when user wants to delete something
		{
			cout << "Enter the title you would like to remove.\n";
			cout << ": ";
			cin >> gameName;
			cout << endl;

			for (myIterator = games.begin(); myIterator != games.end(); ++myIterator)
			{
				if (*myIterator == gameName)
				{
					games.erase((games.begin() + counter));
					cout << "Game removed.\n";
				}
				counter++;
			
			}
			counter = 0; // reset
		}

	}
}




this is the troublesome piece o code: for (myIterator = games.begin(); myIterator != games.end(); ++myIterator) { if (*myIterator == gameName) { games.erase((games.begin() + counter)); cout << "Game removed.\n"; } counter++; } counter = 0; // reset I'm going though the games vector, comparing the vector values with the game the player wants to remove (gameName). Once it spots identical values it deletes the value from the vector. Once it deletes it I get: Access violation reading location... Obviously I erase something not contained by the vector, but I can't see what I did wrong. btw, the program is not finished (loop doesn't end etc.) but that's not the problem atm.
Advertisement
Quote:Original post by Deere


this is the troublesome piece o code:

for (myIterator = games.begin(); myIterator != games.end(); ++myIterator)
{
if (*myIterator == gameName)
{
games.erase((games.begin() + counter));
cout << "Game removed.\n";
}
counter++;

}
counter = 0; // reset



Im currently reading the same book as you but havent got to writing this program yet so im not sure but shouldnt:
for (myIterator = games.begin(); myIterator != games.end(); ++myIterator)
be: for (Iter = games.begin(); Iter != games.end(); ++Iter)
The problem you have here is you are removing an element from the vector but still assuming the vector is the same size. Your for loop is correct, but you shouldn't be using the counter variable to address the erase. That's what the iterator is for.

games.erase(myIterator);


Of course, once you do this, you've made a common mistake. From the SGI manual:

Quote:
[5] A vector's iterators are invalidated when its memory is reallocated. Additionally, inserting or deleting an element in the middle of a vector invalidates all iterators that point to elements following the insertion or deletion point. It follows that you can prevent a vector's iterators from being invalidated if you use reserve() to preallocate as much memory as the vector will ever use, and if all insertions and deletions are at the vector's end.


The work around is to use the return value of erase(), which is an iterator, to set the value of the for loop iterator. This is off the top of my head (I don't have my reference manual here) so it may be incorrect, but it will set you in the right direction:

for (myIterator = games.begin(); myIterator != games.end(); ++myIterator){if (*myIterator == gameName){myIterator = games.erase(myIterator);cout << "Game removed.\n";}}
dek001:
As you'll see in the book, the use of iter (::const_iterator iter) is actually redundant. It's main use though, is to make clear to the programmer that it can only be read from (read only mem).
In my particular case I AM actually only reading from the iterator, but I am changing values here and there, so I thought it'd be clearer for myself if I used the iterator (::iterator myIterator) saying: "Hey, some stuff is going to be changed."
edit: Ok, now with what MidoriKid is suggesting, I'd had to use the myIterator anyway

MidoriKid

Ok, I tried the work-around, but it's still not working completely.
If i have two strings in my database and I remove the first, everything's ok. But when I try to remove the last string the prog goes nuts. It gives some access violations and freezes.

I'm still utterly confused.
When you erase the last item, the iterator is at the end. But the way the for-loop works is it increments and then compares. So it is incrementing past the end of the loop.
Using a while loop seems pretty clean.
myIterator = games.begin(); while (myIterator != games.end()){	if (*myIterator == gameName)	{		myIterator = games.erase(myIterator);		cout << "Game removed.\n";	}	else		++myIterator;}
nprz, thank you!

What a mistake... the loop continued while the last item was deleted.

Thanks again. :D

the working code, might anyone be interested. ^^

#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;vector<string> games;                //database for the game titlesvector<string>::iterator myIterator; //iterator...vector<string>::const_iterator iter; //samebool quit = false; // if user wants to quitint counter = 0; // for counting purposes string choice; // user inputstring gameName; // contains name of the game, which can be used for several operationsint main(){	           // welcome screen	cout << "\tWelcome to the game database\n\n";	cout << "Here you can create a list of games.\n\n";	cout << "To add a game title to the list, enter 'add'.\n";	cout << "To remove a game title from the list, enter 'remove'.\n";	cout << "To take a look at the list, enter 'list'.\n";	cout << "To receive help on the commands, enter 'help'.\n";	cout << "To quit the program, enter 'quit'.\n";		while (quit != true)	{		cout << "\n: "; // creating a dos like enviroment		cin >> choice;  // and asking for input 		cout << endl;   //		if (choice == "list") //when the user wants to see the list		{			if (games.size() == 0)				cout << "No games in the list, yet.\n";			else			{				cout << "The games:\n"; 				          // we display the list				for (iter = games.begin(); iter != games.end(); ++iter)					cout << *iter << endl;			}		}		if (choice == "add") // when user wants to  add something		{			cout << "enter the title of the game.\n";			cout << ": ";			cin  >> gameName;			cout << endl;			      // if he actually entered something, we add it to the database			if (gameName != "")				games.push_back(gameName);			else				cout << "invalid input...\n";			gameName = ""; // reset		}		if (choice == "remove") // when user wants to delete something		{			cout << "Enter the title you would like to remove.\n";			cout << ": ";			cin >> gameName;			cout << endl;			myIterator = games.begin(); 			while (myIterator != games.end())			{				if (*myIterator == gameName)				{					myIterator = games.erase(myIterator);					cout << "Game removed.\n";				}				else					++myIterator;			}		}		if (choice == "help")		{			cout << "To add a game title to the list, enter 'add'.\n";			cout << "To remove a game title from the list, enter 'remove'.\n";			cout << "To take a look at the list, enter 'list'.\n";			cout << "To receive help on the commands, enter 'help'.\n";			cout << "To quit the program, enter 'quit'.\n";		}		if (choice == "quit")			quit = true;		}		system("PAUSE");		return 0;}


not completely foolproof etc, but it does what it's supposed to do.




[Edited by - Deere on July 25, 2005 5:38:48 AM]
You could, perhaps, break from the while loop once the game had been found and erased, so you wouldn't need to go all the way to the end once you'd deleted the one you were looking for:

myIterator = games.begin(); while (myIterator != games.end()){	if (*myIterator == gameName)	{		myIterator = games.erase(myIterator);		std::cout << "Game removed.\n";                break; /* Break iterator while loop */                            	}	else		++myIterator;}


As an aside, using std::list<> instead would by-pass this problem as deletion from a list wouldn't change the list structure. Anyway, just an idea. Hope you got it all working..:)
Gary.Goodbye, and thanks for all the fish.
That is indeed not a bad idea at all.

I must admit though, that I don't understand the second part of your reply, about the std::list.
Using a linked list (std::list) instead of a vector allows efficient inserts and deletes at the cost of efficient random access.

Example: You have 10 objects in your vector and decide to delete the fifth. The vector now has to move objects 6-10 into slots 5-9. With a linked list it simply removes object 5 without shuffling things around.

PS: I like this way:
myIterator = games.begin(); while (*myIterator != gameName) { ++myIterator; }myIterator = games.erase(myIterator);std::cout << "Game removed.\n";
Indeed...this also has another side effect...there's no need to keep "recalculating" the end of a list as the structure remains the same.

so you could actually have:

std::list<string> games;typedef std::list<string>::iterator listIter;typedef std::list<string>::const_iterator clistIter;listIter myIterator = games.begin();clistIter listEnd = games.end();while (myIterator != listEnd){	if (*myIterator == gameName)	{		myIterator = games.erase(myIterator);		std::cout << "Game removed.\n";                break; /* Break iterator while loop */                            	}	else		++myIterator;}


Just a small thing but it can increase effeciency in the loop...not by a great deal on it's own but if the loop is called 1000s of times per frame then it could stack up.

Just another thought...Must admit though, MidoriKid's implementation is pretty good..:)

you could also use the standard library supplied find() algorithm:

games.erase(std::find(games.begin(),games.end(),gameName));

std::find() returns an iterator to the 1st occurence of value in the range games.begin() -> games.end(). The range can be any two iterators that support sequential read onlyaccess strategies.

Hope that helps a little.

This topic is closed to new replies.

Advertisement