Velocity Reviews > C++ > Removing elements in a list that are also in another list

Removing elements in a list that are also in another list

Guest
Posts: n/a

 01-26-2006
Hi All,

I was wondering if somebody could tell me if there is an efficient way
to do the following. Say I have a list(or vector) A and a list B, I want
to remove any elements in B, that are also elements in A.

Victor Bazarov
Guest
Posts: n/a

 01-26-2006
> I was wondering if somebody could tell me if there is an efficient way
> to do the following. Say I have a list(or vector) A and a list B, I want
> to remove any elements in B, that are also elements in A.

Sort both lists and use 'set_difference'.

V

Patrick Kowalzick
Guest
Posts: n/a

 01-27-2006
Hello Victor,

>> I was wondering if somebody could tell me if there is an efficient way to
>> do the following. Say I have a list(or vector) A and a list B, I want to
>> remove any elements in B, that are also elements in A.

>
> Sort both lists and use 'set_difference'.

For set_difference you have to create a target list/vector. Do you know a
solution to remove the elements in B directly?

Regards,
Patrick

Pete Becker
Guest
Posts: n/a

 01-27-2006
Patrick Kowalzick wrote:

> Hello Victor,
>
>
>>>I was wondering if somebody could tell me if there is an efficient way to
>>>do the following. Say I have a list(or vector) A and a list B, I want to
>>>remove any elements in B, that are also elements in A.

>>
>>Sort both lists and use 'set_difference'.

>
>
> For set_difference you have to create a target list/vector. Do you know a
> solution to remove the elements in B directly?
>

Assuming you've already sorted the two lists, you do essentially what
list, and walk through the target list until you reach an element that
isn't less than that one. If it's equal, remove it and move to the next
element. Move to the next element in the selector list. Repeat until done.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

Victor Bazarov
Guest
Posts: n/a

 01-27-2006
Patrick Kowalzick wrote:
>>>I was wondering if somebody could tell me if there is an efficient way to
>>>do the following. Say I have a list(or vector) A and a list B, I want to
>>>remove any elements in B, that are also elements in A.

>>
>>Sort both lists and use 'set_difference'.

>
>
> For set_difference you have to create a target list/vector. Do you know a
> solution to remove the elements in B directly?

A solution would be to write your own "is_contained_in" predicate and then
run 'remove_if'. Something like

list_A.remove_if(is_contained_in(list_B));

That has O(n*m) complexity but without them both sorted it should suffice.

V

Patrick Kowalzick
Guest
Posts: n/a

 01-27-2006
Hello Victor,

>>>>I was wondering if somebody could tell me if there is an efficient way
>>>>to do the following. Say I have a list(or vector) A and a list B, I want
>>>>to remove any elements in B, that are also elements in A.
>>>
>>>Sort both lists and use 'set_difference'.

>>
>>
>> For set_difference you have to create a target list/vector. Do you know a
>> solution to remove the elements in B directly?

>
> A solution would be to write your own "is_contained_in" predicate and then
> run 'remove_if'. Something like
>
> list_A.remove_if(is_contained_in(list_B));
>
> That has O(n*m) complexity but without them both sorted it should suffice.

Yes, this would be a solution for unsorted lists. For sorted lists it could
be more effective.

Thanks,
Patrick

Patrick Kowalzick
Guest
Posts: n/a

 01-27-2006
Hello Pete,

>>>>I was wondering if somebody could tell me if there is an efficient way
>>>>to do the following. Say I have a list(or vector) A and a list B, I want
>>>>to remove any elements in B, that are also elements in A.
>>>
>>>Sort both lists and use 'set_difference'.

>>
>>
>> For set_difference you have to create a target list/vector. Do you know a
>> solution to remove the elements in B directly?
>>

>
> Assuming you've already sorted the two lists, you do essentially what
> set_difference does: start with the first element from the selector list,
> and walk through the target list until you reach an element that isn't
> less than that one. If it's equal, remove it and move to the next element.
> Move to the next element in the selector list. Repeat until done.

"remove" in the sense of the Standard Library (pushing non removed elements
as far to the front as possible?).

So we get something like:
iterator remove_set_difference( iterator,
iterator,const_iterator,const_iterator );
v.erase( v.remove_set_difference( v.begin(), v.end(), v2.begin(),
v1.begin() ), v.end() );

Regards,
Patrick

Pete Becker
Guest
Posts: n/a

 01-27-2006
Patrick Kowalzick wrote:
> Hello Pete,
>
>
>>>>>I was wondering if somebody could tell me if there is an efficient way
>>>>>to do the following. Say I have a list(or vector) A and a list B, I want
>>>>>to remove any elements in B, that are also elements in A.
>>>>
>>>>Sort both lists and use 'set_difference'.
>>>
>>>
>>>For set_difference you have to create a target list/vector. Do you know a
>>>solution to remove the elements in B directly?
>>>

>>
>>Assuming you've already sorted the two lists, you do essentially what
>>and walk through the target list until you reach an element that isn't
>>less than that one. If it's equal, remove it and move to the next element.
>>Move to the next element in the selector list. Repeat until done.

>
>
> "remove" in the sense of the Standard Library (pushing non removed elements
> as far to the front as possible?).
>

No, remove as in remove from the list. We're dealing here with a
container, so we're not limited to the thngs you can do with a sequence.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)