tr1 :: unordered_set union和intersection

Question

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

任何参考和代码将受到高度赞赏.非常感谢你.

更新:我只是猜到了tr1 :: unordered_set应该提供交集,联合,差异的函数.因为那是集合的基本操作.当然我可以自己编写一个函数,但我只是想知道是否有来自tr1的内置函数.非常感谢你.

Answer 1

我看到了set_intersection()等人.从algorithm标题中将无法正常工作,因为他们明确要求对其输入进行排序 - 猜测你已经排除了它们.

在我看来,迭代哈希A并查找哈希B中的每个元素的"天真"方法实际上应该给你接近最优的性能,因为哈希B中的连续查找将转到相同的哈希桶(假设两者都是哈希使用相同的哈希函数).这应该给你体面的内存,即使这些桶几乎肯定是作为链表实现的.

这里有一些代码unordered_set_difference(),你可以调整它来制作set union的版本并设置差异:

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_setS,x并且y,你可以把它们的交点在z使用:

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

与bdonlan的答案不同,这实际上适用于任何键类型,以及容器类型的任何组合(尽管set_intersection()如果源容器被排序,使用当然会更快).

注意:如果存储桶占用率很高,则将每个散列复制到a中可能会更快,在那里vector对它们进行排序set_intersection(),因为在包含n个元素的存储桶中进行搜索是O(n).

Answer 2

没有什么东西 - 为了交叉,只需要通过一个元素的每个元素并确保它在另一个元素中.对于union,添加两个输入集中的所有项.

例如:

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