By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,234 Members | 1,889 Online
Bytes IT Community
+ Ask a Question
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
KK
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

Dec 21 '05 #1
Share this Question
Share on Google+
1 Reply


P: n/a
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 '05 #2

This discussion thread is closed

Replies have been disabled for this discussion.