removing duplicate entries in a list.

Discussion in 'C++' started by Amit, Sep 5, 2005.

  1. Amit

    Amit Guest

    Hi,
    I have a list of integers. At each iteration, I remove some element
    from it and then insert new elements in it. The order of elements is
    not important. So I guess I could use a vector also for this purpose.
    However, I am also interested in having no duplicacy in elements of
    the vector. So I do not want to have any integer repeated more than
    once in the list.
    One very naive approach could be to compare the new integer being
    added to every element of the list already present. Can I do any
    better, by using sort() and unique() methods(in conjunction) in the
    list? I am not aware of any such methods for a vector.. Any suggestions
    which one might be better in terms of efficiency?

    thanks,
    --a.
     
    Amit, Sep 5, 2005
    #1
    1. Advertising

  2. Amit

    Filip Dreger Guest

    Uzytkownik "Amit" <> napisal w wiadomosci
    news:...
    > Hi,
    > I have a list of integers. At each iteration, I remove some element
    > from it and then insert new elements in it. The order of elements is
    > not important. So I guess I could use a vector also for this
    > purpose.
    > However, I am also interested in having no duplicacy in elements of
    > the vector. So I do not want to have any integer repeated more than
    > once in the list.
    > One very naive approach could be to compare the new integer being
    > added to every element of the list already present. Can I do any
    > better, by using sort() and unique() methods(in conjunction) in the
    > list? I am not aware of any such methods for a vector.. Any
    > suggestions
    > which one might be better in terms of efficiency?

    If the range of integers in question is limited and you want really
    efficient 'sort' and 'unique' functions, you might be better off using
    a bitfield with number of fields equal to the biggest integer you wish
    to store. It takes quite a lot of memory (max. range of integers / 8
    bytes) but gives you zero time 'sort' and zero time 'unique' functions
    :)

    regards,
    Filip Dreger
     
    Filip Dreger, Sep 5, 2005
    #2
    1. Advertising

  3. Amit

    Cy Edmunds Guest

    "Amit" <> wrote in message
    news:...
    > Hi,
    > I have a list of integers. At each iteration, I remove some element
    > from it and then insert new elements in it. The order of elements is
    > not important. So I guess I could use a vector also for this purpose.
    > However, I am also interested in having no duplicacy in elements of
    > the vector. So I do not want to have any integer repeated more than
    > once in the list.
    > One very naive approach could be to compare the new integer being
    > added to every element of the list already present. Can I do any
    > better, by using sort() and unique() methods(in conjunction) in the
    > list? I am not aware of any such methods for a vector.. Any suggestions
    > which one might be better in terms of efficiency?
    >
    > thanks,
    > --a.
    >


    Have a look at std::set<int>.

    --
    Cy
    http://home.rochester.rr.com/cyhome/
     
    Cy Edmunds, Sep 5, 2005
    #3
  4. In message <>, Amit
    <> writes
    >Hi,
    > I have a list of integers. At each iteration, I remove some element
    >from it and then insert new elements in it. The order of elements is
    >not important. So I guess I could use a vector also for this purpose.
    > However, I am also interested in having no duplicacy in elements of
    >the vector. So I do not want to have any integer repeated more than
    >once in the list.
    > One very naive approach could be to compare the new integer being
    >added to every element of the list already present. Can I do any
    >better, by using sort() and unique() methods(in conjunction) in the
    >list? I am not aware of any such methods for a vector..


    That doesn't mean you can't do it: the reason there are no
    vector-specific member functions for this is merely that the generic
    (non-member) std:: algorithms will work on std::vector (unlike
    std::list), so there's no point in having class-specific equivalents.

    > Any suggestions
    >which one might be better in terms of efficiency?


    Since you're adding and removing all the time (which would entail
    repeatedly re-sorting a vector) you might do better to use std::set,
    which is intrinsically sorted already.

    --
    Richard Herring
     
    Richard Herring, Sep 5, 2005
    #4
    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. sri2097
    Replies:
    4
    Views:
    590
    sri2097
    Jan 10, 2006
  2. Replies:
    2
    Views:
    565
    Andy Dingley
    Dec 6, 2006
  3. Replies:
    1
    Views:
    475
    Paul Lutus
    Dec 6, 2006
  4. Don Bruder
    Replies:
    3
    Views:
    1,013
    spikeysnack
    Aug 3, 2010
  5. ppnair
    Replies:
    0
    Views:
    426
    ppnair
    Oct 11, 2012
Loading...

Share This Page