Subscribe to MentalFloss Minutes        RSS Feed
-----

C++ Set Exploration

23 September 2018
Icon Leave Comment
Posted by MentalFloss 
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.

Categories: Uncategorized

Back to MentalFloss Minutes →

0 Comments On This Entry

 

← October 2020 →

S M T W T F S
    123
45678910
11121314151617
1819202122 23 24
25262728293031

Tags

    Recent Entries

    Recent Comments

    Search My Blog

    0 user(s) viewing

    0 Guests
    0 member(s)
    0 anonymous member(s)