std::set_intersection takes sorted ranges of elements (well, iterator pairs). But suppose I have unsorted data, e.g. two std::unordered_sets. Is there a standard facility for intersection them?
Asked
Active
Viewed 357 times
3
einpoklum
- 118,144
- 57
- 340
- 684
-
3related: [tr1::unordered_set union and intersection](http://stackoverflow.com/questions/896155/tr1unordered-set-union-and-intersection). It is the pre-standard names. Also not a full solution so no actual close vote from me. – NathanOliver May 03 '16 at 15:48
2 Answers
1
There's no shortcut in this case. You should check each element of the smaller set for membership in the larger set and insert it into an output set if it's found. Since unordered_set is implemented using a hash with buckets, the lookup times should (with a decent hash function and reasonable maximum loading of the hash) be small. You should be able to write a call to for_each on the smaller set that performs the check on the larger one and the insert into the output set without it getting too ugly.
If you want to build the intersection in place in one of the two original sets, you could check whether each of its elements is in the other set and remove that element if not. This could be written with remove_if on the unordered_set that will hold the result.
Yet another option would be to use copy_if with an insertion iterator. There are lots of options for doing this within the same time and space. Pick one that seems to optimize for clarity.
I know of no canned library function that will just do it for you.
Thomas Kammeyer
- 4,457
- 21
- 30
-
1That would give you the union, not intersection, and the function that will do it is `s1.insert(s2.begin(), s2.end())` – Jonathan Wakely May 03 '16 at 16:11
-
Blarg. Many thanks. Got distracted thinking about it and answered the wrong question. I edited my answer. – Thomas Kammeyer May 03 '16 at 16:25