tr1 :: unordered_set联合和交集 [英] tr1::unordered_set union and intersection

问题描述

如何对c ++中的tr1 :: unordered_set类型的集合进行交集和联合？我找不到很多参考。

How to do intersection and union for sets of the type tr1::unordered_set in c++? I can't find much reference about it.

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

Any reference and code will be highly appreciated. Thank you very much.

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

Update: I just guessed the tr1::unordered_set should provide the function for intersection, union, difference.. Since that's the basic operation of sets. Of course I can write a function by myself, but I just wonder if there are built in function from tr1. Thank you very much.

推荐答案

我看到 set_intersection $ c> et al。从算法头不会工作，因为他们明确要求他们的输入被排序 - 猜你已经排除了它们。

I see that set_intersection() et al. from the algorithm header won't work as they explicitly require their inputs to be sorted -- guess you ruled them out already.

我发现，遍历哈希A和查找哈希B中的每个元素的朴素方法应该实际上给你接近最优的性能，因为哈希B中的连续查找将进入相同的哈希桶（假设两个散列使用相同的散列函数）。

It occurs to me that the "naive" approach of iterating through hash A and looking up every element in hash B should actually give you near-optimal performance, since successive lookups in hash B will be going to the same hash bucket (assuming that both hashes are using the same hash function). That should give you decent memory locality, even though these buckets are almost certainly implemented as linked lists.

下面是一些 unordered_set_difference（）

Here's some code for unordered_set_difference(), you can tweak it to make the versions for set union and 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_set s， x 和 y ，可以将它们的交集放在 z 使用：

Assuming you have two unordered_sets, x and y, you can put their intersection in z using:

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

与 bdonlan的回答，这将适用于任何键类型和任何容器类型的组合（虽然使用如果源容器被排序，set_intersection（）当然会更快）。

Unlike bdonlan's answer, this will actually work for any key types, and any combination of container types (although using set_intersection() will of course be faster if the source containers are sorted).

注意：如果桶占用率高，将每个散列复制到向量中，对它们进行排序，并将 set_intersection（）是O（n）。

NOTE: If bucket occupancies are high, it's probably faster to copy each hash into a vector, sort them and set_intersection() them there, since searching within a bucket containing n elements is O(n).

这篇关于tr1 :: unordered_set联合和交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！