unorderedSetIntersectionBenchmark.cpp

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


int unorderedSetIntersectionBenchmark() 
{
  const int nBags        = 1000;
  const int maxBagLength = 10;
    
  typedef unordered_set<int> Bag;

  vector<Bag> bags;
  ifstream    input("10000ran.dat");  // http://www.agner.org/random/10000ran.zip
  int         similarity = 0;
    
  bags.reserve(nBags);

  for (int iBag = 0; iBag < nBags; ++iBag) {
    bags.push_back(Bag());
    
    for (int j = 0; j < maxBagLength; ++j) {
      string number;

      getline(input, number, ',');
      bags.back().insert(round(atof(number.c_str())*maxBagLength));
    }
  }

  for (int i = 0; i < bags.size(); ++i)
    for (int j = i+1; j < bags.size(); ++j) {
      Bag intersec;

      unordered_set_intersection(bags[i].begin(), bags[i].end(), bags[j].begin(), bags[j].end(), inserter(intersec, intersec.begin()));
      similarity += intersec.size();
    }

  return similarity;    
}