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