clean way to iterate over union of sets ?

Question

I have 2 instances of std::set, for examples one instance correspond to the state of a set at time t, and the other one at t+1.

I want to iterate over the union (in the mathematical sense) of these 2 sets, such that :

each element of the union is processed once
for each element I can tell in constant time if it is in the first set, the second set, or both

Here is an example of what I'm currently doing :

std::set<A> old_set, new_set;
for(auto it = old_set.begin(); it != old_set.end(); ++it) {
        if(new_set.count(*it) == 0) {
            //only in old set but not in new set
        }
    }

for(auto it = new_set.begin(); it != new_set.end(); ++it) {
    if(old_set.count(*it) == 0) {
        //only in new set but not in old set
    }
}

As you can see, it is missing the part where we process elements in both sets, and also the complexity isn't good enough. I think there should be a way to do what I want by simply iterating over all the elements of the set

Does anyone have an idea?

Thanks

How is this a duplicate? The other question explicitly states: "Again I'm only using `vector`, `std::set` isn't allowed." The answer might be the same, but the question isn't! — TonyK, Dec 21 '14 at 22:50

score 4 · Accepted Answer · answered Dec 21 '14 at 21:50

4

You may do something like:

template <typename T, typename D>
void iterate(std::set<T>& s1, std::set<T>& s2, D d)
{
    auto it1 = s1.begin();
    auto it2 = s2.begin();

    while (it1 != s1.end() && it2 != s2.end()) {
        if (*it1 < *it2) {
            // only in set1
            d.visit1(*it1);
            ++it1;
        } else if (*it2 < *it1) {
            // only in set2
            d.visit2(*it2);
            ++it2;
        } else {
            // in both
            d.visitboth(*it1, *it2);
            ++it1;
            ++it2;
        }
    }
    for (; it1 != s1.end(); ++it1) {
        // only in set1
        d.visit1(*it1);
    }
    for (; it2 != s2.end(); ++it2) {
        // only in set2
        d.visit2(*it2);
    }
}

answered Dec 21 '14 at 21:50

Jarod42

203,559
14
181
302

thanks, this seems to be exactly what I was looking for ! I'll just try to run a few tests to make sure that this works as intended – lezebulon Dec 21 '14 at 21:52
is there any reason why d.visitboth(*it1, *it2) takes 2 arguments ? since they compare equal couldn't it take 1 argument only ? – lezebulon Dec 21 '14 at 21:56
@lezebulon If the `visitx` methods of `D` take their arguments by reference, `visitboth` could modify one or the other or both of them – wakjah Dec 21 '14 at 22:00
@lezebulon: In addition to wakjak remark, if `T` is a type where equivalence is not the same as equality, you may have different value in both side: consider for example a class `insensitive_string` (insensitive for comparison but not for display...) – Jarod42 Dec 21 '14 at 22:01
This is a great solution. But modifying elements would only work on (say) sorted vectors as `std::set` iterators are const. – Galik Dec 21 '14 at 22:02
@Galik Good point, forgot about that :) – wakjah Dec 21 '14 at 22:04
@Galik: element may contain pointer, so modifying the pointed object and not the pointer is possible (but care to not modify the order). – Jarod42 Dec 21 '14 at 22:05

score 0 · Answer 2 · answered Dec 21 '14 at 21:46

After all that counting it may be more efficient to create a union in a fast container like a std::vector and iterate over that:

int main()
{
    std::set<int> s1 {1, 2, 4, 6, 9};
    std::set<int> s2 {2, 3, 4, 6, 11};

    std::vector<int> u;

    u.reserve(s1.size() + s2.size());

    std::set_union(s1.begin(), s1.end(), s2.begin(), s2.end()
        , std::back_inserter(u));

    for(auto it = u.begin(); it != u.end(); ++it)
    {
        // do stuff on union
        std::cout << "u: " << *it << '\n';
    }
}

In fact, OP wants `std::set_intersection` and the two differences done via `std::set_difference`. — Jarod42, Dec 21 '14 at 22:08

score 0 · Answer 3 · edited May 23 '17 at 11:49

One idea is to write your own iterator which can perform the iteration over the containers and merge them in that way:

template<typename... T>
class MergeIterator{
 MergeIterator( T... constainers ):m_containers(std::forward(containers)...){}
 std::tuple< T... > m_containers;
 /// implement the operators here.
 MergeIterator operator ++(){///... here switch the tuple if needed until it is not on the last element}
};

For simplicity you can use std::vector< ContainerType > instead of tuple and T as a variable type in a container. I am not sure if there is something already available in a boost or other libraries...

What's the best way to iterate over two or more containers simultaneously

clean way to iterate over union of sets ?

3 Answers3