# intersection of two STL lists

This is a discussion on intersection of two STL lists within the C++ Programming forums, part of the General Programming Boards category; Hi guys, this is a homework assignment. Right now, I'm thinking that my solution should probably work - but of ...

1. ## 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){
temp.push_back(*L1itr);

L1itr++;
L2itr++;
}
if(*L1itr < *L2itr){
L1itr++;
}
else{
//*L1itr > *L2itr
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. Originally Posted by misterMatt
Code:
```...
while(L1itr == L1.end() || L2itr == L2.end()){
...```
What did you expect this while loop condition to do?

3. Originally Posted by arpsmack
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. Issue #2:

Code:
```...
}
if(*L1itr < *L2itr){
...```
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]

5. 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. 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){
temp.push_back(*L1itr);
L1itr++;
L2itr++;
}
else if(*L1itr < *L2itr){
L1itr++;
}
else{
//*L1itr > *L2itr