# intersection of two STL lists

• 05-11-2009
misterMatt
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:
Quote:

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; } ```
• 05-11-2009
arpsmack
Quote:

Originally Posted by misterMatt
Code:

```...         while(L1itr == L1.end() || L2itr == L2.end()){ ...```

What did you expect this while loop condition to do?
• 05-11-2009
misterMatt
Quote:

Originally Posted by arpsmack
What did you expect this while loop condition to do?

Ahh yeah. That would be the first issue. :D

Code:

`while(L1itr != L1.end() || L2itr != L2.end()){ }`
would be the correct one
• 05-11-2009
arpsmack
Issue #2:

Quote:

Code:

```...                 }                 if(*L1itr < *L2itr){                         //advance L1 iterator ...```

Notice anything missing?

Hint:

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

[/edit]
• 05-11-2009
misterMatt
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.
• 05-11-2009
misterMatt
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```
• 05-12-2009
iMalc
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.