[LLVMdev] set_intersect and Visual C compiler

[Vikram S. Adve]

On Oct 13, 2004, at 3:44 AM, Patrick Meredith wrote:

>
> ----- Original Message -----
> From: "Paolo Invernizzi" <arathorn at fastwebnet.it>
> To: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>
> Sent: Wednesday, October 13, 2004 3:12 AM
> Subject: Re: [LLVMdev] set_intersect and Visual C compiler
>
>
>> Both are working well on VC. Just tested.
>>
>> template<class STy>
>> void set_intersect(STy &S1, const STy &S2) {
>>   for(STy::iterator I = S1.begin(), E = S1.end(); I != E; )
>>     if (S2.count(*I))
>>       S1.erase(*I++);
>>     else
>>       ++I;
>> }
>>
>> template <class S1Ty, class S2Ty>
>> void set_intersect(S1Ty &S1, const S2Ty &S2) {
>>    for (typename S1Ty::iterator I = S1.begin(); I != S1.end();) {
>>      const S1Ty::key_type &E = *I;
>>      ++I;
>>      if (!S2.count(E)) S1.erase(E);   // Erase element if not in S2
>>    }
>> }
>>
>> ---
>> Paolo Invernizzi
>
> But like Alkis said we should probably just use the stl 
> set_intersection, it
> runs in linear time instead of n*lg(n).


Either use it directly if possible, or otherwise use the better 
algorithm.  It may not be possible because the code above works for STL 
containers other than sets.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.cs.uiuc.edu/