algorithm copy from vector to set - newbie question

[Soumen]

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

[Juha Nieminen]

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());

[Victor Bazarov]

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?

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

If your vector is sorted, *and* you don't mind mutating it, then using
'std::unique' on it might give you some advantage. If it isn't sorted,
and/or you don't want to mutate it, then your approach is sufficient.

The problem (as I see it) with 'std::set' is that its "insert" member
will have to attempt insertion every time, which means it will search
through the set more than necessary. Sorting the source container and
then using 'unique_copy' has the advantage of skipping the search for
any object that is equal to the one that was just inserted. You can use
'std::deque' as the destination container in that case (the fastest from
the insertion-at-end/indexed-retrieval POV).

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Jerry Coffin]

In article <d886de30-a5f8-441f-83c8-c88d680a6731
@m3g2000hsc.googlegroups.com>, so******@gmail.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.

[Soumen]

On Jul 7, 6:14*pm, Juha Nieminen <[e-mail]:

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]

On Jul 7, 6:48*pm, Jerry Coffin <[e-mail]:

In article <d886de30-a5f8-441f-83c8-c88d680a6731
@m3g2000hsc.googlegroups.com>, [e-mail] 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

[Pete Becker]

On 2008-07-07 12:48:34 -0400, Soumen <so******@gmail.comsaid:

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

Better yet: try it and see. Hypothetical analyses of what might be
faster often collapse when confronted with real data.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

[Jerry Coffin]

In article <390c72eb-7502-445c-9f63-6fc36335d488
@m36g2000hse.googlegroups.com>, so******@gmail.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.