Adding unique data to a vector

Discussion in 'C++' started by Abhishek Pandey, Jan 19, 2005.

  1. Hi,
    I have a vector of strings. I want to hold it only unique strings.
    That is, before adding any new string, I want to check if it is already
    present, and if yes, then I will not add the new item.
    Is there a simpler and efficient way of doing it (instead of traversing
    linearly through the whole list and comparing strings everytime I want to
    add new item).

    Thanks in advance,
    Abhishek
     
    Abhishek Pandey, Jan 19, 2005
    #1
    1. Advertising

  2. Abhishek Pandey wrote:
    > Hi,
    > I have a vector of strings. I want to hold it only unique strings.
    > That is, before adding any new string, I want to check if it is already
    > present, and if yes, then I will not add the new item.
    > Is there a simpler and efficient way of doing it (instead of traversing
    > linearly through the whole list and comparing strings everytime I want to
    > add new item).


    std::map should be an obvious alternative to vector.

    Perhaps the best alternative would be a hash container, but that's not
    part of the standard stl, although many stl implementations have one.

    So, *must* it be a vector, or can you change the container ?
     
    Gianni Mariani, Jan 19, 2005
    #2
    1. Advertising

  3. "Gianni Mariani" <> wrote in message
    news:...
    > Abhishek Pandey wrote:
    > > Hi,
    > > I have a vector of strings. I want to hold it only unique strings.
    > > That is, before adding any new string, I want to check if it is already
    > > present, and if yes, then I will not add the new item.
    > > Is there a simpler and efficient way of doing it (instead of traversing
    > > linearly through the whole list and comparing strings everytime I want

    to
    > > add new item).

    >
    > std::map should be an obvious alternative to vector.
    >
    > Perhaps the best alternative would be a hash container, but that's not
    > part of the standard stl, although many stl implementations have one.
    >
    > So, *must* it be a vector, or can you change the container ?


    Thanks for the reply,
    Changing the container will require more code changes, which I was trying to
    avoid if possible.

    -Abhishek
     
    Abhishek Pandey, Jan 19, 2005
    #3
  4. Abhishek Pandey wrote:
    >
    > "Gianni Mariani" <> wrote in message
    > news:...
    > > Abhishek Pandey wrote:
    > > > Hi,
    > > > I have a vector of strings. I want to hold it only unique strings.
    > > > That is, before adding any new string, I want to check if it is already
    > > > present, and if yes, then I will not add the new item.
    > > > Is there a simpler and efficient way of doing it (instead of traversing
    > > > linearly through the whole list and comparing strings everytime I want

    > to
    > > > add new item).

    > >
    > > std::map should be an obvious alternative to vector.
    > >
    > > Perhaps the best alternative would be a hash container, but that's not
    > > part of the standard stl, although many stl implementations have one.
    > >
    > > So, *must* it be a vector, or can you change the container ?

    >
    > Thanks for the reply,
    > Changing the container will require more code changes, which I was trying to
    > avoid if possible.


    How do you build up the vector?
    Is it built in one rush or are things added as needed?

    If the former then a possible solution is:
    Just add all of the strings (you will have duplicates now).
    Then sort the vector. In this way all the duplicates will be
    at consecutive vector positions. Walk through the vector and
    remove the duplicates.

    Look up: std::sort std::unique

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Jan 19, 2005
    #4
  5. "Karl Heinz Buchegger" <> wrote in message
    news:...
    > Abhishek Pandey wrote:
    > >
    > > "Gianni Mariani" <> wrote in message
    > > news:...
    > > > Abhishek Pandey wrote:
    > > > > Hi,
    > > > > I have a vector of strings. I want to hold it only unique strings.
    > > > > That is, before adding any new string, I want to check if it is

    already
    > > > > present, and if yes, then I will not add the new item.
    > > > > Is there a simpler and efficient way of doing it (instead of

    traversing
    > > > > linearly through the whole list and comparing strings everytime I

    want
    > > to
    > > > > add new item).
    > > >
    > > > std::map should be an obvious alternative to vector.
    > > >
    > > > Perhaps the best alternative would be a hash container, but that's not
    > > > part of the standard stl, although many stl implementations have one.
    > > >
    > > > So, *must* it be a vector, or can you change the container ?

    > >
    > > Thanks for the reply,
    > > Changing the container will require more code changes, which I was

    trying to
    > > avoid if possible.

    >
    > How do you build up the vector?
    > Is it built in one rush or are things added as needed?
    >
    > If the former then a possible solution is:
    > Just add all of the strings (you will have duplicates now).
    > Then sort the vector. In this way all the duplicates will be
    > at consecutive vector positions. Walk through the vector and
    > remove the duplicates.


    I add the things as and when needed and not in one go. :-(
    Thanks


    > Look up: std::sort std::unique
    >
    > --
    > Karl Heinz Buchegger
    >
     
    Abhishek Pandey, Jan 19, 2005
    #5
  6. Abhishek Pandey

    shez Guest

    make sure the vector is sorted at all times, then before you insert, do
    a binary search.

    or just use std::set.

    If you cannot change the order of elements in the vector, then maintain
    a separate std::set using the minimal data needed to define uniqueness.
    -shez-
     
    shez, Jan 19, 2005
    #6
    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. pmatos
    Replies:
    6
    Views:
    23,821
  2. Replies:
    8
    Views:
    1,930
    Csaba
    Feb 18, 2006
  3. Javier
    Replies:
    2
    Views:
    567
    James Kanze
    Sep 4, 2007
  4. ToshiBoy
    Replies:
    6
    Views:
    852
    ToshiBoy
    Aug 12, 2008
  5. Token Type
    Replies:
    9
    Views:
    360
    Chris Angelico
    Sep 9, 2012
Loading...

Share This Page