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.
0 Comments On This Entry
Tags
My Blog Links
Recent Entries
Recent Comments
Search My Blog
0 user(s) viewing
0 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)