446,234 Members | 1,889 Online
Need help? Post your question and get tips & solutions from a community of 446,234 IT Pros & Developers. It's quick & easy.

# efficient algorithm for customized set_difference

 P: n/a 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 V1, V2, V1sort, V2sort, V3, V4, V5, V6 std::vector::Iterator iter; std::map 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 Dec 21 '05 #1