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

This is a discussion on CAN'T FIGURE IT -- structs on a linked list within the C++ Programming forums, part of the General Programming Boards category; hey all-- i'm new to c++ (as the difficulties below will undoubtedly prove) and would GREATLY appreciate any/all help i ...

  1. #1
    Unregistered
    Guest

    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~

  2. #2
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    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;
    	}

  3. #3
    Something Clever ginoitalo's Avatar
    Join Date
    Dec 2001
    Posts
    187
    In your for loop you have newQPtr!=newQ.end()
    list::end() returns 1 PAST the list.
    which is fine.

    I also Initialized your iterator

    Therefore Try This :
    Code:
         for(newQ.begin(), newQPtr=newQ.begin();newQPtr!=(newQ.end()); newQPtr++){ 
    		cout<<"hi"<<endl;
    		if(newQPtr->arrivalTime == time){ 
    			readyQ.push_back(*newQPtr); 
    			newQ.erase(newQPtr); 
    		} 
         }
    Last edited by ginoitalo; 03-29-2002 at 02:46 PM.

  4. #4
    Something Clever ginoitalo's Avatar
    Join Date
    Dec 2001
    Posts
    187
    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;
    }

  5. #5
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    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.

  6. #6
    Something Clever ginoitalo's Avatar
    Join Date
    Dec 2001
    Posts
    187
    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;
    }

  7. #7
    Unregistered
    Guest

    trying it out...i'll let you know

    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 11-04-2006, 06:39 PM
  2. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 11:01 AM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 06:46 PM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21