Removing elements in a list that are also in another list

Discussion in 'C++' started by Adam Hartshorne, Jan 26, 2006.

  1. 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.

    Adam
     
    Adam Hartshorne, Jan 26, 2006
    #1
    1. Advertising

  2. Adam Hartshorne 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'.

    V
     
    Victor Bazarov, Jan 26, 2006
    #2
    1. Advertising

  3. 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
     
    Patrick Kowalzick, Jan 27, 2006
    #3
  4. Adam Hartshorne

    Pete Becker Guest

    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
    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.

    --

    Pete Becker
    Dinkumware, Ltd. (http://www.dinkumware.com)
     
    Pete Becker, Jan 27, 2006
    #4
  5. 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
     
    Victor Bazarov, Jan 27, 2006
    #5
  6. 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, Jan 27, 2006
    #6
  7. 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
     
    Patrick Kowalzick, Jan 27, 2006
    #7
  8. Adam Hartshorne

    Pete Becker Guest

    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
    >>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?).
    >


    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)
     
    Pete Becker, Jan 27, 2006
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Lukasz Indyk
    Replies:
    1
    Views:
    1,517
    Andrew Thompson
    Sep 22, 2004
  2. Adam Hartshorne
    Replies:
    2
    Views:
    391
    Nitin Motgi
    Jan 27, 2006
  3. Debajit Adhikary
    Replies:
    17
    Views:
    727
    Debajit Adhikary
    Oct 18, 2007
  4. bgold12
    Replies:
    5
    Views:
    615
    Stor Ursa
    Nov 21, 2008
  5. bgold12
    Replies:
    6
    Views:
    141
    dhtml
    Nov 22, 2008
Loading...

Share This Page