Subscribe to MentalFloss Minutes
Leave Comment
This entry is just a slow walk through getting familiar with sets.
Compile:
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:
Discovery: Set elements are unique. Updating insert to
Union
Union of two sets results in a new set that consists of all elements from s1 and all elements from s2.
Intersection
Intersection of two sets results in a set comprised of elements that were in both sets.
Difference
Set difference, denoted s1 \ s2, removes all elements in s2 that are in s1, and results in a new set.
Generalizing
Being confined to integers isn't fun. So, let's create a template of our helpers
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.
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.
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 }
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 }
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 }
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 }
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) }
===========================================
{ (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
Share This Entry:
0 Comments On This Entry
Tags
My Blog Links
Recent Entries
Recent Comments
Search My Blog
1 user(s) viewing
1 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)
| 