Thread: intersection of two STL lists

  1. #1
    village skeptic
    Join Date
    Aug 2008
    Posts
    31

    intersection of two STL lists

    Hi guys, this is a homework assignment. Right now, I'm thinking that my solution should probably work - but of course it doesn't and I cant spot the problem. I was hoping one of you would be kind enough to look it over and see where I'm going wrong. My first guess is that nothing is being added to the temp array that gets returned in the function - because nothing is printed out in the loop inside of main. Please help me find the logic problem causing this.

    Thank you

    Here is the problem:
    Given two sorted lists L1 and L2 (here STL list's),
    write a procedure to compute L1 ∩ L2 (the intersection of L1 and L2). Specifically,
    write the following template function:

    template<typename T>
    list<T> listIntersection(const list<T>& L1, const list<T>& L2);

    For example, if L1, L2 are (STL) list of int's, and L1 contains {2, 5, 7, 8, 10} and
    L2 contains {5, 6, 10, 24}, the function returns a new/different list which contains{5, 10}.

    IMPORTANT: Think about an EFFICIENT logic. Take advantage of the fact/assumption that
    L1 and L2 are in the sorted order. You should be able to do this procedure by traversing
    two lists exactly once (i.e., O(n) linear complexity).

    Here is my solution:
    Code:
    template<typename T>
    list<T> listIntersection(const list<T>& L1, const list<T>& L2){
    
    //list to return 
    	list<T> temp;
    	//iterators
    	list<T>::const_iterator L1itr = L1.begin();
    	list<T>::const_iterator L2itr = L2.begin();
    	
    	
    	while(L1itr == L1.end() || L2itr == L2.end()){
    		
    		//check to see if they're equal, add to our temp list
    		if(*L1itr == *L2itr){
    			//add to temp
    			temp.push_back(*L1itr);
    
    			//advance iterators 
    			L1itr++;
    			L2itr++;
    		}
    		if(*L1itr < *L2itr){
    			//advance L1 iterator
    			L1itr++;
    		}
    		else{
    			//*L1itr > *L2itr
    			//advance L2 iterator
    			L2itr++;
    		}//end if else if block
    	}//end while
    
    	return temp;
    }//end function
    
    here is the main() implementation:
    
    Code:
    #include <iostream> 
    #include <list>
    
    using namespace std;
    
     template<typename T>
      list<T> listIntersection(const list<T>& L1, const list<T>& L2);
    
    int main(){
    
    	list<int> L1;
    	L1.push_back(2);
    	L1.push_back(5);
    	L1.push_back(7);
    	L1.push_back(8);
    	L1.push_back(10);
    	
    	list<int> L2;
    	L2.push_back(5);
    	L2.push_back(6);
    	L2.push_back(10);
    	L2.push_back(24);
    	system("pause");
    
    	list<int> t = listIntersection(L1, L2);
    
    
    
    
    
    	for(list<int>::iterator i = t.begin(); i != t.end(); i++){
    		cout << *i;
    	}
    
    	
    
    	system("pause");
    	return 0;
    }

  2. #2
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    Quote Originally Posted by misterMatt View Post
    Code:
    ...
    	while(L1itr == L1.end() || L2itr == L2.end()){
    ...
    What did you expect this while loop condition to do?

  3. #3
    village skeptic
    Join Date
    Aug 2008
    Posts
    31
    Quote Originally Posted by arpsmack View Post
    What did you expect this while loop condition to do?

    Ahh yeah. That would be the first issue.

    Code:
    while(L1itr != L1.end() || L2itr != L2.end()){ }
    would be the correct one

  4. #4
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    Issue #2:

    Code:
    ...
    		}
    		if(*L1itr < *L2itr){
    			//advance L1 iterator
    ...
    Notice anything missing?

    [edit]
    Hint:

    Try it with these lists: {1, 2} {1, 2}
    Then try it with these lists {1, 2, 3} {1, 2, 3}

    Bad things should happen.
    [/edit]
    Last edited by arpsmack; 05-11-2009 at 10:25 PM.

  5. #5
    village skeptic
    Join Date
    Aug 2008
    Posts
    31
    I can see that after L1itr, and L2itr both hit 5(original data), that L2itr++ is done twice. Instead of it being just 6, it jumps to 10 because it's meeting that second condition - but even then in the debugger I can see that it fails completely when the iterator reaches the last element in one of the lists. I tried checking to see if the iterators were at the end before each increment line but it still ends in an assertion error. But I guess the more important question is how to get it to stop executing the second increment when the first one was done when the two were equal.

  6. #6
    village skeptic
    Join Date
    Aug 2008
    Posts
    31
    This seemed to work

    Code:
    template<typename T>
    list<T> listIntersection(const list<T>& L1, const list<T>& L2)
    
    	//list to return 
    	list<T> temp;
    	//iterators
    	list<T>::const_iterator L1itr = L1.begin();
    	list<T>::const_iterator L2itr = L2.begin();
    	
    	
    	while(L1itr != L1.end() && L2itr != L2.end()){
    		//check to see if they're equal, add to our temp list
    		if(*L1itr == *L2itr){
    			//add to temp
    			temp.push_back(*L1itr);
    			//advance iterators 
    			L1itr++;
    			L2itr++;
    		}
    		else if(*L1itr < *L2itr){
    			//advance L1 iterator
    			L1itr++;
    		}
    		else{
    			//*L1itr > *L2itr
    			//advance L2 iterator
    			L2itr++;
    		}//end if else if block
    	}//end while
    
    	return temp;
    }//end function

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Don't throw == comparions between elements in there when it isn't needed. Put the == case last such that it is the else part. Then flip the greater-than comparison over so that it is *L2itr < *L1itr. Now all the class that the list is of has to implement is the less-than operator.

    Also, don't post-increment your iterators. That involves returning a copy of them. Using preincrement (++ before the variable) is more efficient for iterators, well depending on the optimisation settings of course.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. STL Linked Lists
    By stanlvw in forum C++ Programming
    Replies: 12
    Last Post: 04-11-2008, 01:33 AM
  2. Question about using erase() with lists (STL)
    By apacz in forum C++ Programming
    Replies: 2
    Last Post: 11-01-2005, 11:51 AM
  3. A question about STL Lists.
    By joenching in forum C++ Programming
    Replies: 9
    Last Post: 04-25-2005, 09:23 PM
  4. Stl lists and user defined types
    By figa in forum C++ Programming
    Replies: 8
    Last Post: 03-28-2005, 12:09 PM
  5. help with STL lists
    By WebmasterMattD in forum C++ Programming
    Replies: 2
    Last Post: 05-03-2003, 06:41 PM