迭代集联合的干净方法？

lezebulon 发表于 Dev

116

大风球

我有2个std :: set实例，例如，一个实例对应于时间t处集合的状态，另一个实例对应于t + 1处。

我想遍历这两个集合的联合（在数学意义上），使得：

联合的每个元素都要处理一次
对于每个元素，我都可以在恒定时间内告诉它是在第一组，第二组还是两者中

这是我目前正在做的一个例子：

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
    }
}

如您所见，它缺少我们处理两个集合中的元素的部分，而且复杂性还不够好。我认为应该有一种方法可以通过简单地迭代集合中的所有元素来做我想做的事情

有人有主意吗？

谢谢

贾罗德42

您可以执行以下操作：

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);
    }
}