algorithm copy from vector to set - newbie question

Discussion in 'C++' started by Soumen, Jul 7, 2008.

  1. Soumen

    Soumen Guest

    I need to write code to copy unique elements in from a sequence
    container (say vector) to a set (or another sequence container will
    do). Is following code efficient?

    template <class T>
    void copyUniqueObject(const vector<T> &seqContainer,
    set<T> &uniqueSet)
    {
    std::copy(seqContainer.begin(), seqContainer.end(),
    std::inserter(uniqueSet, uniqueSet.end()));
    }

    Or is there a better (more efficient) way (say, some way using
    lower_bound or so) to write similar functionality?
    Does using unique_copy over copy gives any advantage in this case?

    Thanks in advance,
    Regards,
    ~ Soumen
     
    Soumen, Jul 7, 2008
    #1
    1. Advertising

  2. Soumen wrote:
    > I need to write code to copy unique elements in from a sequence
    > container (say vector) to a set (or another sequence container will
    > do). Is following code efficient?


    A set will already contain only unique elements, so you could simply do a:

    uniqueSet.insert(seqContainer.begin(), seqContainer.end());
     
    Juha Nieminen, Jul 7, 2008
    #2
    1. Advertising

  3. Soumen

    Jerry Coffin Guest

    In article <d886de30-a5f8-441f-83c8-c88d680a6731
    @m3g2000hsc.googlegroups.com>, says...

    [ ... ]

    > Or is there a better (more efficient) way (say, some way using
    > lower_bound or so) to write similar functionality?
    > Does using unique_copy over copy gives any advantage in this case?


    Assuming your input is already sorted, there's a pretty good chance that
    unique_copy will give a slight performance advantage. If your input is
    in a vector, the memory is guaranteed to be contiguous, so it'll tend to
    have better locality of reference. The memory in the set will normally
    be in the form of noncontiguous dynamically allocated nodes. As such,
    traversing the identical inputs in the vector will usually be faster
    than in the set.

    OTOH, if your input is NOT already sorted, sorting it first so you can
    use unique_copy (meaningfully) isn't likely to work out so well.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
     
    Jerry Coffin, Jul 7, 2008
    #3
  4. Soumen

    Soumen Guest

    On Jul 7, 6:14 pm, Juha Nieminen <> wrote:
    > Soumen wrote:
    > > I need to write code to copy unique elements in from a sequence
    > > container (say vector) to a set (or another sequence container will
    > > do). Is following code efficient?

    >
    >   A set will already contain only unique elements, so you could simply do a:
    >
    >   uniqueSet.insert(seqContainer.begin(), seqContainer.end());


    Thanks, I missed the range member function of set.
     
    Soumen, Jul 7, 2008
    #4
  5. Soumen

    Soumen Guest

    On Jul 7, 6:48 pm, Jerry Coffin <> wrote:
    > In article <d886de30-a5f8-441f-83c8-c88d680a6731
    > @m3g2000hsc.googlegroups.com>, says...
    >
    > [ ... ]
    >
    > > Or is there a better (more efficient) way (say, some way using
    > > lower_bound or so) to write similar functionality?
    > > Does using unique_copy over copy gives any advantage in this case?

    >
    > Assuming your input is already sorted, there's a pretty good chance that
    > unique_copy will give a slight performance advantage. If your input is
    > in a vector, the memory is guaranteed to be contiguous, so it'll tend to
    > have better locality of reference. The memory in the set will normally
    > be in the form of noncontiguous dynamically allocated nodes. As such,
    > traversing the identical inputs in the vector will usually be faster
    > than in the set.
    >
    > OTOH, if your input is NOT already sorted, sorting it first so you can
    > use unique_copy (meaningfully) isn't likely to work out so well.
    >
    > --
    >     Later,
    >     Jerry.
    >
    > The universe is a figment of its own imagination.


    Thanks. But my input is not sorted. Even in that case I believe
    sorting and using
    unique_copy will give better performance if I use with vector and
    back_inserter
    for destination. Correct me if it's going to be worse than using deque
    as pointed by
    Victor.

    Regards,
    - Soumen
     
    Soumen, Jul 7, 2008
    #5
  6. Soumen

    Jerry Coffin Guest

    In article <390c72eb-7502-445c-9f63-6fc36335d488
    @m36g2000hse.googlegroups.com>, says...

    [ ... ]

    > Thanks. But my input is not sorted. Even in that case I believe
    > sorting and using
    > unique_copy will give better performance if I use with vector and
    > back_inserter
    > for destination. Correct me if it's going to be worse than using deque
    > as pointed by Victor.


    I think a few options that are all likely to be viable have been pointed
    out, so at this point picking out the best will probably involve some
    testing and profiling.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
     
    Jerry Coffin, Jul 7, 2008
    #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. Dennis
    Replies:
    1
    Views:
    2,587
    Dennis
    Jun 7, 2004
  2. pmatos
    Replies:
    6
    Views:
    23,821
  3. Alex
    Replies:
    2
    Views:
    1,237
  4. Replies:
    8
    Views:
    1,930
    Csaba
    Feb 18, 2006
  5. Replies:
    26
    Views:
    2,120
    Roland Pibinger
    Sep 1, 2006
Loading...

Share This Page