unordered set intersection in C++

Question

Here is my code, wondering any ideas to make it faster? My implementation is brute force, which is for any elements in a, try to find if it also in b, if so, put in result set c. Any smarter ideas is appreciated.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> a = {1,2,3,4,5};
    std::unordered_set<int> b = {3,4,5,6,7};
    std::unordered_set<int> c;
    for (auto i = a.begin(); i != a.end(); i++) {
        if (b.find(*i) != b.end()) c.insert(*i);
    }
    for (int v : c) {
        std::printf("%d \n", v);
    }
}

Questions asking for improvement of already working code should go to [SE Code Review](https://codereview.stackexchange.com/). — user0042, Dec 20 '17 at 08:04
C++ have many nice [algorithmic functions in the standard library](http://en.cppreference.com/w/cpp/algorithm). For example one called [`std::set_intersection`](http://en.cppreference.com/w/cpp/algorithm/set_intersection). — Some programmer dude, Dec 20 '17 at 08:05
@Someprogrammerdude ... which requires sorted input ranges, something `std::unoredered_set` does not readily provide. — Angew is no longer proud of SO, Dec 20 '17 at 08:16
@Someprogrammerdude, yes, agree with Angew, I looked at this API and I think sorting requires additional time. — Lin Ma, Dec 20 '17 at 08:23
@user0042 Code that doesn't meet performance requirements is not working. — n. m. could be an AI, Dec 20 '17 at 08:53

Angew is no longer proud of SO · Accepted Answer · 2017-12-20T08:29:06.663

10

Asymptotically, your algorithm is as good as it can get.

In practice, I'd add a check to loop over the smaller of the two sets and do lookups in the larger one. Assuming reasonably evenly distributed hashes, a lookup in a std::unoredered_set takes constant time. So this way, you'll be performing fewer such lookups.

edited Dec 20 '17 at 08:29

answered Dec 20 '17 at 08:20

Angew is no longer proud of SO

167,307
17
350
455

Thanks Angew, why your method is faster? Could you elaborate a bit more? – Lin Ma Dec 20 '17 at 08:23

score 5 · Answer 2 · answered Dec 07 '18 at 15:29

5

You can do it with std::copy_if()

std::copy_if(a.begin(), a.end(), std::inserter(c, c.begin()), [b](const int element){return b.count(element) > 0;} );

answered Dec 07 '18 at 15:29

stephane k.

1,668
20
21

score 3 · Answer 3 · answered Dec 20 '17 at 08:59

3

Your algorithm is as good as it gets for a unordered set. however if you use a std::set (which uses a binary tree as storage) or even better a sorted std::vector, you can do better. The algorithm should be something like:

get iterators to a.begin() and b.begin()
if the iterators point to equal element add to intersection and increment both iterators.
Otherwise increment the iterator pointing to the smallest value
Go to 2.

Both should be O(n) time but using a normal set should save you from calculating hashes or any performance degradation that arises from hash collisions.

answered Dec 20 '17 at 08:59

doron

27,972
12
65
103

Why do you think set is faster then unordered set in my use case? – Lin Ma Dec 20 '17 at 23:12
Save on hash calculation and true O(1) iteration without dealing with collisions. But benchmark if not sure. – doron Dec 21 '17 at 16:27
@doron depends on how fast hash calculation actually is - but if numbers of elements differ largely, hash sets gain advantage again (provided one selects the smaller one as reference). We'd now have to know the use cases, tree sets might come with trade-offs at other locations (random element access). Still good to show up an alternative... – Aconcagua Dec 28 '17 at 12:11
Note that step 3 can be tweaked a bit: instead of incrementing just once, look for the first element not smaller than the first of the other list. Phrased this way, it gets clearer that you can take advantage of random access (galloping strategy) or tree structure, to skip some elements. That does not affect the worst case, but it can matter in practice. – Marc Glisse Jan 17 '18 at 12:08

Aconcagua · Answer 4 · 2020-09-16T13:13:47.307

2

Thanks Angew, why your method is faster? Could you elaborate a bit more?

Well, let me provide you some additional info...

It should be pretty clear that, whichever data structures you use, you will have to iterate over all elements in at least one of those, so you cannot get better than O(n), n being the number of elements in the data structure selected to iterate over. Elementary now is, how fast you can look up the elements in the other structure – with a hash set, which std::unordered_set actually is, this is O(1) – at least if the number of collisions is small enough ("reasonably evenly distributed hashes"); the degenerate case would be all values having the same key...

So far, you get O(n) * O(1) = O(n). But you still the choice: O(n) or O(m), if m is the number of elements in the other set. OK, in complexity calculations, this is the same, we have a linear algorithm anyway, in practice, though, you can spare some hash calculations and look-ups if you choose the set with the lower number of elements...

edited Sep 16 '20 at 13:13

answered Dec 20 '17 at 08:20

Aconcagua

24,880
4
34
59

Nice catch! Thanks. – Lin Ma Dec 20 '17 at 23:12
Note that this is a worst case analysis. Depending on what the sets typically look like in this application, intersecting sorted sets may or may not be possible in sub-linear time (think of the extreme case where you intersect [0,100] with [200,300], one comparison is enough to notice that the result is empty). – Marc Glisse Jan 17 '18 at 11:30
@MarcGlisse Ah, back at doron's idea... (my answer - actually addition to a previous one - being about hash sets...). But we'd have to modify doron's algorithm to profit from such cases (as a whole or for partial ranges), maybe some clever partition algorithm? – Aconcagua Jan 17 '18 at 12:03
For the ordered case, some references can be found at https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66418 . – Marc Glisse Jan 17 '18 at 12:11

unordered set intersection in C++

4 Answers4

Linked