Hi,

I'm trying to come up with an efficient way to solve the following

problem.

Let A = { (1, b), (2, d), (3, a), (4, c) ,... }

B = { (1, d), (2, a), (3, e), (4, f),... }

where a,b,c... belong to set of integers and are UNIQUE.

Achieve

C = A - B;

D = B - A;

where the difference operator is defined such that

C = { (1, b), (4, c),... }

D = { (3, e), (4, f),... }

My *tedious* solution:

------------------------------

std::vector<int> V1, V2, V1sort, V2sort, V3, V4, V5, V6

std::vector<int>::Iterator iter;

std::map<int, int> C,D;

V1= { b, d, a, c, ... } /* get all the elements of A */

V2= { d, a, e, f, ... }

V1sort = /* sorted V1 */

V2sort = /* sorted V2 */

set_difference ( V1sort.begin(), V1sort.end(), V2sort.begin(),

V2sort.end(), V3.begin(), V3.end())

set_difference ( V2sort.begin(), V2sort.end(), V1sort.begin(),

V1sort.end(), V4.begin(), V4.end())

for (iter= V3.begin(); iter != V3.end(); ++iter)

{

for (int i = 0; i< V1.size(); i++)

{

if ( *iter = V1[i] )

{

V5.push_back(i);

break;

}

}

}

/* Similarly compute V6 for vector V4 */

sort( V5.begin(), V5.end() );

sort( V6.begin(), V6.end() );

for ( iter = V5.begin(); i != V5.end(); ++iter)

C[*iter] = V1(*iter);

for ( iter = V6.begin(); i != V6.end(); ++iter)

D[*iter] = V1(*iter);

The above program is not tested for errors but you get the idea. As you

see in the above approach I've been using several for loops and sort

functions which slow down the execution when the sizes of V1 & V2 are

huge. Is there an efficient way to achieve the above task?

Thank you very much.

-KK