efficient algorithm for customized set_difference

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

  1. KK

    KK Guest

    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
    #1
    1. Advertising

  2. KK

    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
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    6
    Views:
    1,095
  2. Timasmith
    Replies:
    36
    Views:
    878
  3. Replies:
    3
    Views:
    390
    Pete Becker
    May 22, 2006
  4. tezheng
    Replies:
    3
    Views:
    3,414
    dasjotre
    Nov 28, 2006
  5. JThangiah
    Replies:
    10
    Views:
    1,037
    Robert Klemme
    Mar 6, 2008
Loading...

Share This Page