# algorithm copy from vector to set - newbie question

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

1. ### SoumenGuest

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?

Regards,
~ Soumen

Soumen, Jul 7, 2008

2. ### Juha NieminenGuest

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

3. ### Jerry CoffinGuest

In article <d886de30-a5f8-441f-83c8-c88d680a6731

[ ... ]

> 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
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
4. ### SoumenGuest

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
5. ### SoumenGuest

On Jul 7, 6:48 pm, Jerry Coffin <> wrote:
> In article <d886de30-a5f8-441f-83c8-c88d680a6731
>
> [ ... ]
>
> > 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
6. ### Jerry CoffinGuest

In article <390c72eb-7502-445c-9f63-6fc36335d488

[ ... ]

> 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