list intersection ..!

[new1]

Hello, i Got stuck in this
I have 2 lists list<string>list1,list2
For ex: list1 => abc,def,ghi,klm,zzz.
list2 => fff,zzz.

i want to maintain the both lists into single list1.
list1 => abc,def,ghi,klm,fff.

for( itr1=list1.begin();itr1 != list1.end();itr1++)
 {
        itr2 = std::find(list2.begin(),list2.end(),itr1->c_str());  // whats wrong with this statement in value place.
        if(itr2 != list1.end())
                list1.push_back(*itr2);

 }

is this method is suitable for huge list size ?

suggest me thanks inadvance.

[new1]

Messed up completely, it goes endless loop..

This is the one below

for( itr1=list2.begin();itr1 != list2.end();++itr1)
 {
 
        if (!(std::find(list1.begin(),list1.end(),*itr1)!=list1.end()))
        {
                list1.push_back(*itr1);
 
        }

getting intersection list in list1 display.. but i want to know one thing is this right way of doing things for huge list intersection..

[ne555]

> is this right way of doing things for huge list
calculate the order of the algorithm.

If you can assure that the lists are sorted, then there is a O(n) solution.

[new1]

what is that ..
not a problem in sorting the lists ..tell me the best way to do this.

[ne555]

This is what you're doing

traverse(at, a)
   if( is_member(at, b) )
      result.insert(at);

Now, your `is_member()' function is traversing all the list to find the element.
Your algorithm ends being O(n*m)


If the lists were sorted then you may stop as soon as you find a bigger element.
Also, there is no need to start at the beginning of the list because you know that till some point all those element are lesser than the one you're searching

bt = b.begin();
traverse( at, A )
   bt = lower_bound( bt, b.end(), *at );
   if( bt == b.end() ) break;
   if( *bt == *at )
      result.push_back(*at);

this way you only traverse each list one single time, so O(n+m)