Efficient way to solve this problem

[gaurav13191]

I have a problem in which we are given 2 sets A and B and we have to find set C which contains elements common to A and B.The set A and B can contain duplicates and set C is expected to contain distinct elements(i.e no repetition of the same element) common to A and B.

As a solution to this, I thought that first all the duplicates in A and B can be removed and then set C can be formed by comparing each element of A and B.
Is there any other efficient way to solve the problem?

Just post your idea and I will do the coding. Thanks in advance!

[helios]

If A and B are sorted, it can be easily solved by iterating over both sets in parallel (so to speak). It's kinda late, so I don't feel like figuring out the details right now, but basically you increment one pointer/index or the other based on which element is greater or lower, and if they're both the same, they belong to C. You can skip duplicates by doing something like

while (*pointer==pointer[-1])
    pointer++;

By the way, in set theory, this operation is called intersection.

[EzwRko23]

STL doesn't have a set intersection method?

[helios]

Oh, right.
http://www.cplusplus.com/reference/algorithm/set_intersection/
Well, I assumed it was homework.