Subscribe to MentalFloss Minutes

## C++ Set Exploration

This entry is just a slow walk through getting familiar with sets.

Compile:
g++ -std=c++11 program.cc -o demo

References:
http://www.cplusplus...erence/set/set/
http://www.cplusplus...ce/set/set/set/
http://www.cplusplus...ence/algorithm/

Getting Started

Let's just get started with some boilerplate:

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

void print(set<int> nums, string name="")
{
string comma = "";
cout << name << "{ ";
for(int i : nums)
{
cout << comma << i;
comma = ", ";
}
cout << " }" << endl;
}

int main()
{
set<int> s1;
s1.insert( { 1,2,3 } );
print(s1, "s1 = ");
}

Quote

s1 = { 1, 2, 3 }

Discovery: Set elements are unique. Updating insert to
s1.insert( { 1,2,3,3,3,3,3,3 } );
results in same output:

Quote

s1 = { 1, 2, 3 }

Union

Union of two sets results in a new set that consists of all elements from s1 and all elements from s2.

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

void print(set<int> nums, string name="")
{
string comma = "";
cout << name << "{ ";
for(int i : nums)
{
cout << comma << i;
comma = ", ";
}
cout << " }" << endl;
}

set<int> get_union(set<int> s1, set<int> s2)
{
set<int> output;
set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(output, output.begin()));
return output;
}

int main()
{
set<int> s1;
s1.insert( { 1,3,5,7,9 } );
print(s1, "s1 = ");

set<int> s2;
s2.insert( { 0,2,4,6,8,10 } );
print(s2, "s2 = ");

set<int> s1_u_s2 = get_union(s1, s2);
print(s1_u_s2, "s1 U s2 = ");
}

Quote

s1 = { 1, 3, 5, 7, 9 }
s2 = { 0, 2, 4, 6, 8, 10 }
s1 U s2 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

Intersection

Intersection of two sets results in a set comprised of elements that were in both sets.

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

void print(set<int> nums, string name="")
{
string comma = "";
cout << name << "{ ";
for(int i : nums)
{
cout << comma << i;
comma = ", ";
}
cout << " }" << endl;
}

set<int> get_union(set<int> s1, set<int> s2)
{
set<int> output;
set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(output, output.begin()));
return output;
}

set<int> get_intersection(set<int> s1, set<int> s2)
{
set<int> output;
set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(output, output.begin()));
return output;
}

int main()
{
set<int> s1;
s1.insert( { 1,2,3 } );
print(s1, "s1 = ");

set<int> s2;
s2.insert( { 2,3,4 } );
print(s2, "s2 = ");

set<int> s1_n_s2 = get_intersection(s1, s2);
print(s1_n_s2, "s1 n s2 = ");
}

Quote

s1 = { 1, 2, 3 }
s2 = { 2, 3, 4 }
s1 n s2 = { 2, 3 }

Difference

Set difference, denoted s1 \ s2, removes all elements in s2 that are in s1, and results in a new set.

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

void print(set<int> nums, string name="")
{
string comma = "";
cout << name << "{ ";
for(int i : nums)
{
cout << comma << i;
comma = ", ";
}
cout << " }" << endl;
}

set<int> get_union(set<int> s1, set<int> s2)
{
set<int> output;
set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(output, output.begin()));
return output;
}

set<int> get_intersection(set<int> s1, set<int> s2)
{
set<int> output;
set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(output, output.begin()));
return output;
}

set<int> get_difference(set<int> s1, set<int> s2)
{
set<int> output;
set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(output, output.begin()));
return output;
}

int main()
{
set<int> s1;
s1.insert( { 1,2,3,4,5,6,7,8 } );
print(s1, "s1 = ");

set<int> s2;
s2.insert( { 2,4,6,8,10 } );
print(s2, "s2 = ");

set<int> s1_d_s2 = get_difference(s1, s2);
print(s1_d_s2, "s1 \\ s2 = ");
}

Quote

s1 = { 1, 2, 3, 4, 5, 6, 7, 8 }
s2 = { 2, 4, 6, 8, 10 }
s1 \ s2 = { 1, 3, 5, 7 }

Generalizing

Being confined to integers isn't fun. So, let's create a template of our helpers

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

template <class T>
void print(set<T> items, string name="")
{
string comma = "";
cout << name << "{ ";
for(T i : items)
{
cout << comma << i;
comma = ", ";
}
cout << " }" << endl;
}

template <class T>
set<T> get_union(set<T> s1, set<T> s2)
{
set<T> output;
set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(output, output.begin()));
return output;
}

template <class T>
set<T> get_intersection(set<T> s1, set<T> s2)
{
set<T> output;
set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(output, output.begin()));
return output;
}

template <class T>
set<T> get_difference(set<T> s1, set<T> s2)
{
set<T> output;
set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(output, output.begin()));
return output;
}

int main()
{
set<string> s1;
s1.insert( { "a","b","c","d","e","f","g" } );
print<string>(s1, "s1 = ");

set<string> s2;
s2.insert( { "b","a","d" } );
print<string>(s2, "s2 = ");

set<string> s1_d_s2 = get_difference<string>(s1, s2);
print<string>(s1_d_s2, "s1 \\ s2 = ");
}

Quote

s1 = { a, b, c, d, e, f, g }
s2 = { a, b, d }
s1 \ s2 = { c, e, f, g }

Complex Data Types?

We can also operate on complex data types. Here, I created a 3d point struct, and created a comparison operator overload for use with set operations. We can construct two volumes, and find where they overlap, for instance.

#include <iostream>
#include <string>
#include <algorithm>
#include <set>

using namespace std;

struct Point
{
int x;
int y;
int z;

Point(int x, int y, int z)
{
this->x = x;
this->y = y;
this->z = z;
}

string to_string()
{
return "(" + std::to_string(x) + "," + std::to_string(y) + "," + std::to_string(z) + ")";
}
};

bool operator<(const Point& p1, const Point& p2) {
return ( (p1.x < p2.x) || (p1.x == p2.x && p1.y < p2.y) || (p1.x == p2.x && p1.y == p2.y && p1.z < p2.z) );
}

template <class T>
void print(set<T> items, string name="")
{
string comma = "";
cout << name << "{ ";
for(T i : items)
{
cout << comma << i.to_string();
comma = ", ";
}
cout << " }" << endl;
}

template <class T>
set<T> get_union(set<T> s1, set<T> s2)
{
set<T> output;
set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(output, output.begin()));
return output;
}

template <class T>
set<T> get_intersection(set<T> s1, set<T> s2)
{
set<T> output;
set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(output, output.begin()));
return output;
}

template <class T>
set<T> get_difference(set<T> s1, set<T> s2)
{
set<T> output;
set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(output, output.begin()));
return output;
}

int main()
{

set<Point, less<Point>> cube1;
for(int x=0; x < 3; x++)
for(int y=0; y < 3; y++)
for(int z=0; z < 3; z++)
cube1.insert( Point(x, y, z) );

print<Point>(cube1);
cout << "===========================================" << endl;

set<Point, less<Point>> cube2;
for(int x=1; x < 4; x++)
for(int y=1; y < 4; y++)
for(int z=1; z < 4; z++)
cube2.insert( Point(x, y, z) );

print<Point>(cube2);
cout << "===========================================" << endl;

set<Point, less<Point>> volume = get_intersection(cube1, cube2);

print<Point>(volume);

}

Quote

{ (0,0,0), (0,0,1), (0,0,2), (0,1,0), (0,1,1), (0,1,2), (0,2,0), (0,2,1), (0,2,2), (1,0,0), (1,0,1), (1,0,2), (1,1,0), (1,1,1), (1,1,2), (1,2,0), (1,2,1), (1,2,2), (2,0,0), (2,0,1), (2,0,2), (2,1,0), (2,1,1), (2,1,2), (2,2,0), (2,2,1), (2,2,2) }
===========================================
{ (1,1,1), (1,1,2), (1,1,3), (1,2,1), (1,2,2), (1,2,3), (1,3,1), (1,3,2), (1,3,3), (2,1,1), (2,1,2), (2,1,3), (2,2,1), (2,2,2), (2,2,3), (2,3,1), (2,3,2), (2,3,3), (3,1,1), (3,1,2), (3,1,3), (3,2,1), (3,2,2), (3,2,3), (3,3,1), (3,3,2), (3,3,3) }
===========================================
{ (1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2) }

OK. So, it's not really a volume... I'm just poking around with it. Anyway, some interesting ideas.

I'm starting to get more serious about learning C++. So, I'm thinking my posts will center around that.

S M T W T F S
1234567
891011121314
151617 18 192021
22232425262728
293031