c++ - 迭代集合并集的简洁方法？

<分区>

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

我想遍历这两个集合的并集(在数学意义上)，这样:

union 的每个元素都被处理一次
对于每个元素，我可以在常数时间内判断它是在第一组、第二组还是两者中

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

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

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

有没有人有想法？

谢谢

最佳答案

你可以这样做:

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

关于c++ - 迭代集合并集的简洁方法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27594086/

上一篇：c++ - 当我们在这个函数中反转字符串时，为什么 char *str 的指针没有改变？

下一篇：c++ - 在 Boost.Geometry rtree 中存储 OGRPoint

相关文章：

c++ - While 函数中的输入循环

c++ - 如何使用 STL 对包含相关条目的两个 vector 进行排序？

c++ - 从模板函数返回迭代器到 STL 容器

c++ - 快速确定 C 预处理器分支的方法

c++ - 以 weak_ptr 作为参数的函数重载决议

c++ - STL 迭代器 std::distance() 错误

c++ - 错误 - 按频率对数组元素排序

c++ - RHEL 6.0 两段相似的代码 : One Compiles One Does Not

c++ - 如何将对 ole32.dll 的调用重定向到我自己的代理 DLL？

c++ - static_assert 引用封闭模板类