algorithm copy from vector to set - newbie question

S

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
 
J

Juha Nieminen

Soumen said:
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());
 
J

Jerry Coffin

[ ... ]
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.
 
S

Soumen

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

Soumen

[ ... ]
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
 
J

Jerry Coffin

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

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top