fork(1) download
copy 
  1. #include <cassert>
  2.  
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <set>
  6. #include <vector>
  7.  
  8. // Do not call this method if you have a single set...
  9. // And the pointers better not be null either!
  10. std::vector<int> intersect(std::vector< std::set<int> const* > const& sets) {
  11.     for (auto s: sets) { assert(s && "I said no null pointer"); }
  12.  
  13.     std::vector<int> result; // only return this one, for NRVO to kick in
  14.  
  15.     // 0. Check obvious cases
  16.     if (sets.empty()) { return result; }
  17.  
  18.     if (sets.size() == 1) {
  19.         result.assign(sets.front()->begin(), sets.front()->end());
  20.         return result;
  21.     }
  22.  
  23.  
  24.     // 1. Merge first two sets in the result
  25.     std::set_intersection(sets[0]->begin(), sets[0]->end(),
  26.                           sets[1]->begin(), sets[1]->end(),
  27.                           std::back_inserter(result));
  28.  
  29.     if (sets.size() == 2) { return result; }
  30.  
  31.  
  32.     // 2. Merge consecutive sets with result into buffer, then swap them around
  33.     //    so that the "result" is always in result at the end of the loop.
  34.  
  35.     std::vector<int> buffer; // outside the loop so that we reuse its memory
  36.  
  37.     for (size_t i = 2; i < sets.size(); ++i) {
  38.         buffer.clear();
  39.  
  40.         std::set_intersection(result.begin(), result.end(),
  41.                               sets[i]->begin(), sets[i]->end(),
  42.                               std::back_inserter(buffer));
  43.  
  44.         swap(result, buffer);
  45.     }
  46.  
  47.     return result;
  48. }
  49.  
  50. int main() {
  51. 	std::set<int> x = {1, 2, 3};
  52. 	std::set<int> y = {1, 3, 4};
  53.  
  54. 	auto result = intersect({&x, &y});
  55.  
  56. 	std::cout << result.size() << ": " << result[0] << ", " << result[1] << "\n";
  57. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2: 1, 3
https://ideone.com/0IoJv2
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!