Thursday, January 17, 2008

Finding Intersections between two sets in C++

Following C++ code (intersection.cpp) creates 2 sets ( a and b), creates a vector out of those (av and bv) and then finds the intersection between the two vectors.



#include <iostream>
#include <vector>
#include <set>
#include<sys/time.h>

using namespace std;

#define MAX_SIZE 1000000

int main()
{
set<int> a,b,un,in,di;
timeval tim;

srand ( time(NULL) );

cout << "Adding to a : " << endl;

for( int i = 0; i < MAX_SIZE; i++ ) {
int r = rand() % MAX_SIZE;
a.insert( r );
}

cout << "Creating vector av" << endl;
vector<int> av(a.begin(),a.end());
cout << "There are " << av.size() << " elements in av" << endl;

cout << "Adding to b : " << endl;

for( int i = 0; i < MAX_SIZE; i++ ) {
int r = rand() % MAX_SIZE;
b.insert( r );
}

cout << "Creating vector bv" << endl;

vector<int> bv(b.begin(),b.end());
cout << "There are " << bv.size() << " elements in bv" << endl;

gettimeofday(&tim, NULL);
double t1=tim.tv_sec+(tim.tv_usec/1000000.0);

set_intersection(a.begin(),a.end(),b.begin(),b.end(),insert_iterator<set<int> >(in,in.begin()));

gettimeofday(&tim, NULL);
double t2=tim.tv_sec+(tim.tv_usec/1000000.0);

vector<int> inv(in.begin(),in.end());

cout << "Elements in intersection " << inv.size() << endl;
cout << "Intersection time " << (t2-t1) << " seconds" << endl;
return 0;
}


compile: c++ intersection.cpp -o intersection
Sample Output

./intersection
Adding to a :
Creating vector av
There are 632163 elements in av
Adding to b :
Creating vector bv
There are 631924 elements in bv
Elements in intersection 399250
Intersection time 0.65199 seconds

1 comment:

AtlasDog said...

Thanks! This bit of code:

insert_iterator >(in,in.begin())

really helped.