# efficient algorithm for customized set_difference

Discussion in 'C++' started by KK, Dec 21, 2005.

1. ### KKGuest

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 )
{
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

KK, Dec 21, 2005

2. ### Guest

The elements of the groups are not: a,b,c.. but the pairs. You should
define a struct that represents the pair, and define a "less than"
function object (actually a struct with () operator), that compares two
pair by comparing the right members from them.
If it wasn't too clear, just look for "set" in an STL help, like:
http://www.sgi.com/tech/stl

Yuval.

, Dec 21, 2005