How to program boolean union and intersection in C++?

[luckie7456969]

It involves some discrete mathematics.
Any code snippet to get me started?
Thanks
Jack

[luckie7456969]

Or just union and intersection without boolean...

[laserlight]

You might want to elaborate. I am not familiar with the terms "boolean union" and "boolean intersection", and a quick search brings up constructive solid geometry, which may or may not be what you are trying to ask about.

If you are talking about sets in general: if you have two containers of elements that are sorted, then you can use std::set_union and std::set_intersection to obtain the union and intersection, treating these containers as sets.

[razzle]

It involves some discrete mathematics.
Any code snippet to get me started?

One very efficient set representation is the bitset. Here the individual bits of an integer are used to represent set elements. If the n'th bit of the integer is set then the n'th element of the set is present, otherwise not.

Set operations can be performed very efficiently by basic bitwise operations. This is sometimes referred to as bit-fiddling. Basically the whole book 4A of Knuth's The Art of Computer Programming series is devoted to this. But to get going you only need the very basics, like here,

http://www.catonmat.net/blog/low-lev...ely-must-know/

Union and intersection becomes,

int setA = .....;
int setB = .....;
int unionAB = setA | setB;
int intersectionAB = setA & setB;

To set the n'th bit you do,

setA |= (1<<n);

and to clear it,

setA &= ~(1<<n);

This is just the beginning and it goes on and on. It's quite amazing how many clever bitset algorithms there are available. My all time favorite is the so called Gosper's hack which allows you to efficiently generate all k-subsets of an n-set.

The drawback of bitsets is that they're limited by the widest integer primitive type available which today typically is 64 bit (a long long). So in practice 64 elements are the biggest sets that can be handled by way of bitsets.