Thread: CAN'T FIGURE IT -- structs on a linked list

hey all--

i'm new to c++ (as the difficulties below will undoubtedly prove) and would GREATLY appreciate any/all help i can get...

i'm trying to set up and manipulate several linked lists, each containing structs as their elements. so ->

#include <list>
using namespace std;

struct Process {
string PID;
int arrivalTime;
....
};



list <Process> newQ;
list <Process> readyQ;
list <Process> diskQ;
list <Process> runQ;
list <Process> exitQ;
list<Process>::iterator newQPtr;
list<Process>::iterator readyQPtr;
list<Process>::iterator diskQPtr;
list<Process>::iterator runQPtr;
list<Process>::iterator exitQPtr;




the code compiles fine...first I populate the newQ with Processes, and that works... but i get indistinguishable run-time errors when i try something akin to


for(newQPtr=newQ.begin(); newQPtr!=newQ.end(); newQPtr++)
{
if(newQPtr->arrivalTime == time)
{
readyQ.push_back(*newQPtr);
newQ.erase(newQPtr);
}
}


(basically trying to take a Process struct off the newQ and place it on the readyQ)

does anyone have any idea what i'm doing wrong here? is the problem with the iterator? if so, what kind of pointer should i be using? i need to be able to iterate through the various lists, taking nodes off one list and placing them on another.

thanks in advance~

It's often tricky to iterate through a std::list using a for loop if you are removing elements. By erasing the node referred to by the iterator, you are invalidating the iterator. To use a popular analogy, you are cutting off the branch you're sitting on.

std::list::erase() returns the following iterator so that you can continue to iterate through the list. It's easier using a while loop -

Code:

	list <int> ilist;
	ilist.push_back(1);
	ilist.push_back(2);
	ilist.push_back(3);

	list<int>::iterator it;

	it=ilist.begin();

	while(it!=ilist.end())
	{
		cout << *it;
		if(*it>1)
			it = ilist.erase(it);
		else
			++it;
	}

To help you grasp it better here's how I tested it :

Code:

#include<list> 
#include<string> 
#include<iostream>
using namespace std;

struct Process { 
	string PID; 
	int arrivalTime; 	
};


int main(void){

	list <Process> newQ; 
	list <Process> readyQ; 
	list <Process> diskQ; 
	list <Process> runQ; 
	list <Process> exitQ; 
	list <Process>::iterator newQPtr; 
	list <Process>::iterator readyQPtr; 
	list <Process>::iterator diskQPtr; 
	list <Process>::iterator runQPtr; 
	list <Process>::iterator exitQPtr;

	int time=0;         //Junk
	Process x, a, c;
	newQ.push_back(x);
	newQ.push_back(a);
	newQ.push_back(c);

	for(newQ.begin(), newQPtr=newQ.begin();newQPtr!=(newQ.end()); newQPtr++){ 
		cout<<"Nice Work"<<endl;
		if(newQPtr->arrivalTime == time){ 
			readyQ.push_back(*newQPtr); 
			newQ.erase(newQPtr); 
		} 
	} 
	

return 0;
}

ginoitalo's solution won't work for the same reason as yours. As soon as std::list::erase() is called the iterator is invalidated. His code only appears to work beccause his for loop never calls std::list::erase().

Also, you should always use the pre-increment operator with iterators rather than the post increment to prevent a temporary.

Alright, Let's try and try again !

...and see if this gets Sorensen's approval

Code:

#include<list> 
#include<string> 
#include<iostream>
using namespace std;

struct Process { 
	string PID; 
	int arrivalTime; 	

	bool operator!=(Process x){return PID!=x.PID;}
};


int main(void){


	list <Process> newQ; 
	list <Process> readyQ; 
	list <Process> diskQ; 
	list <Process> runQ; 
	list <Process> exitQ; 
	list <Process>::iterator newQPtr; 
	list <Process>::iterator readyQPtr; 
	list <Process>::iterator diskQPtr; 
	list <Process>::iterator runQPtr; 
	list <Process>::iterator exitQPtr;

	list <Process>::iterator tmp; 

	int time=7;         

	Process x, a, c;

	x.arrivalTime=3;
	x.PID=3;

	a.arrivalTime=7;
	a.PID=7;

	c.arrivalTime=9;
	c.PID=9;

	newQ.push_back(x);
	newQ.push_back(a);
	newQ.push_back(c);

	cout<<"Start"<<endl;
	newQPtr=newQ.begin();
		
	while(newQPtr != newQ.end()){

		cout<<newQPtr->arrivalTime<<endl;
		tmp=newQPtr;
		
			if(newQPtr->arrivalTime == time){ 
				readyQ.push_back(*newQPtr); 
				if(newQPtr != newQ.end() )
					++newQPtr;
				newQ.erase(tmp); 
			}
			else
				if(newQPtr != newQ.end() )
					++newQPtr;

	} 

cout<<"End"<<endl<<endl<<endl;

cout<<"# elements in newQ    == "<<newQ.size()<<endl;
cout<<"# elements in readyQ  == "<<readyQ.size()<<endl;

return 0;
}

thanks ginoitalo, sorensen--

i really appreciate your responses. i'm going to try your last set of code (ginoitalo) out and see if it works.

getting somewhere

-justin