cleanest stl algorithm?

[kfmfe04]

ok, here is some pseudo-code for my requirements - it's not hard to do with nested loops and multiple passes, but I'd like to see if anyone has any idea of how to do this with cleaner/faster/simpler algorithms:

// ---------------------------------------------------                                                                                                   
// m_cur     m_tgt     m_final                                                                                                                           
// ---------------------------------------------------                                                                                                   
// m_cur      -        m_cur.cancel                                                                                                                      
// m_cur     m_tgt     m_cur.update( m_tgt.qty ) if diff                                                                                                   
//  -        m_tgt     m_tgt.new                                                                                                                         
// --------------------------------------------------- 

essentially, m_cur, m_tgt, and m_final are stl sets (current state, target state, and final state) and the first line reads, "if it's in m_cur and not in m_tgt, insert an m_cur.cancel into m_final"

the second line reads, if it's in m_cur and in m_tgt, and their qty are different, update m_cur's qty with m_tgt's qty and insert into m_final

the mickey-mouse way of doing this would be to do 2 passes - the first pass with looping over m_cur on the outside and m_tgt on the inside; the second pass with m_tgt on the outside and a check to make sure it's not in m_cur on the inside

any other suggestions for faster, cleaner, or simpler algorithms in C++?

responses in pseudo-code or real stl code are both fine - ty

[hamsterman]

This surely won't make it faster, but I guess you could use set_difference for the 1st and 3rd and set_intersection for 2nd. You'll need 3 for loops, but they will take somewhat one line each.

Though I'm a bit confused about the second one. If you use set_intersection, you won't be able to compare the two objects, but if they may by not identical, how can you say that object of m_cur is in m_tgt? Does your comparator ignore qty (whatever it is) ?

[kfmfe04]

thx for the tip, hamsterman!

yes, my comparator ignores qty (quantity) - my objects contain data members that I've categorized as part of the key, or part of the data - qty is part of the data, so it's not used for comparison purposes...

[m4ster r0shi]

Since m_cur and m_tgt are sets (which means they are sorted)
and you don't modify them, you can do it in one pass, but it's dirty...

#include <iostream>
#include <set>
using namespace std;

struct Data
{
    int id;
    int qt;

    Data(int id, int qt):
        id(id), qt(qt) {}

    bool operator<(const Data & d) const { return id<d.id; }
};

void msg(const char * str, int n) { cout << str << " - " << n << endl; }

void DoIt(const set<Data> & s1, const set<Data> & s2)
{
    set<Data>::const_iterator it1=s1.begin(), end1=s1.end(), it2=s2.begin(), end2=s2.end();

    while (true)
    {
        if (it1==end1) { while (it2!=end2) { msg("new", it2->id);    it2++; } break; }
        if (it2==end2) { while (it1!=end1) { msg("cancel", it1->id); it1++; } break; }

        if (*it2<*it1)        { msg("new", it2->id);           it2++; } else
        if (*it1<*it2)        { msg("cancel", it1->id);        it1++; } else
        if (it1->qt!=it2->qt) { msg("update", it1->id);        it1++; it2++; }
        else                  { msg("do not update", it1->id); it1++; it2++; }
    }
}

int main()
{
    set<Data> set1, set2;

    set1.insert(Data(2,10));
    set1.insert(Data(5,15));
    set1.insert(Data(6,120));
    set1.insert(Data(8,150));
    set1.insert(Data(10,40));

    set2.insert(Data(1,20));
    set2.insert(Data(4,35));
    set2.insert(Data(6,120));
    set2.insert(Data(8,200));
    set2.insert(Data(11,70));

    DoIt(set1, set2);

    //cin.get();
    return 0;
}