23

如何在 c++ 中对类型为 tr1::unordered_set 的集合进行交集和并集？我找不到太多关于它的参考。

任何参考和代码将不胜感激。非常感谢你。

更新：我只是猜想 tr1::unordered_set 应该提供交集、并集、差集的功能。因为这是集合的基本操作。当然我可以自己写一个函数，但我只是想知道是否有来自 tr1 的内置函数。非常感谢你。

4

3 回答 3

17

我看到了set_intersection()等。from algorithmheader 将不起作用，因为它们明确要求对输入进行排序——猜你已经排除了它们。

在我看来，遍历散列 A 并查找散列 B 中的每个元素的“天真”方法实际上应该为您提供接近最佳的性能，因为散列 B 中的连续查找将转到同一个散列桶（假设两者哈希使用相同的哈希函数）。这应该会给你不错的内存局部性，即使这些桶几乎肯定是作为链表实现的。

这是 的一些代码unordered_set_difference()，您可以对其进行调整以制作 set union 和 set difference 的版本：

template <typename InIt1, typename InIt2, typename OutIt>
OutIt unordered_set_intersection(InIt1 b1, InIt1 e1, InIt2 b2, InIt2 e2, OutIt out) {
    while (!(b1 == e1)) {
        if (!(std::find(b2, e2, *b1) == e2)) {
            *out = *b1;
            ++out;
        }

        ++b1;
    }

    return out;
}

假设您有两个unordered_setsx和y，您可以使用它们的交集z：

unordered_set_intersection(
    x.begin(), x.end(),
    y.begin(), y.end(),
    inserter(z, z.begin())
);

与bdonlan 的答案不同，这实际上适用于任何键类型和容器类型的任何组合（尽管set_intersection()如果对源容器进行排序，使用当然会更快）。

注意：如果存储桶占用率很高，将每个散列复制到 avector中，然后将它们排序并set_intersection()在那里排序可能会更快，因为在包含 n 个元素的存储桶中搜索是 O(n)。

于 2009-05-22T05:08:10.650 回答
14

没什么大不了的 - 对于相交，只需遍历一个元素的每个元素并确保它在另一个元素中。对于联合，添加两个输入集中的所有项目。

例如：

void us_isect(std::tr1::unordered_set<int> &out,
        const std::tr1::unordered_set<int> &in1,
        const std::tr1::unordered_set<int> &in2)
{
    out.clear();
    if (in2.size() < in1.size()) {
        us_isect(out, in2, in1);
        return;
    }
    for (std::tr1::unordered_set<int>::const_iterator it = in1.begin(); it != in1.end(); it++)
    {
        if (in2.find(*it) != in2.end())
            out.insert(*it);
    }
}

void us_union(std::tr1::unordered_set<int> &out,
        const std::tr1::unordered_set<int> &in1,
        const std::tr1::unordered_set<int> &in2)
{
    out.clear();
    out.insert(in1.begin(), in1.end());
    out.insert(in2.begin(), in2.end());
}
于 2009-05-22T04:49:40.317 回答
3

基于上一个答案：C++11 版本，如果集合支持快速查找功能find() （返回值被有效移动）

/** Intersection and union function for unordered containers which support a fast lookup function find()
 *  Return values are moved by move-semantics, for c++11/c++14 this is efficient, otherwise it results in a copy
 */

namespace unorderedHelpers {

    template<typename UnorderedIn1, typename UnorderedIn2,
             typename UnorderedOut = UnorderedIn1>
    UnorderedOut makeIntersection(const  UnorderedIn1 &in1, const  UnorderedIn2 &in2)
    {
        if (in2.size() < in1.size()) {
            return makeIntersection<UnorderedIn2,UnorderedIn1,UnorderedOut>(in2, in1);
        }

        UnorderedOut out;
        auto e = in2.end();
        for(auto & v : in1)
        {
            if (in2.find(v) != e){
                out.insert(v);
            }
        }
        return out;
    }

    template<typename UnorderedIn1, typename UnorderedIn2,
             typename UnorderedOut = UnorderedIn1>
    UnorderedOut makeUnion(const UnorderedIn1 &in1, const UnorderedIn2 &in2)
    {
        UnorderedOut out;
        out.insert(in1.begin(), in1.end());
        out.insert(in2.begin(), in2.end());
        return out;
    }
}
于 2015-08-03T16:50:41.593 回答