DATA STRUCTURES AND ALGORITHMS ALGORITHMS IN C++ Jordi Petit Salvador Roura Albert Atserias 15defebrerde2017 DepartamentdeLlenguatgesiSistemesInforma`tics UniversitatPolite`cnicadeCatalunya 1 STL Usage Examples 1.1 Reading the input line by line: istringstream Reading the input line by line. Readsasequenceoflinesand,foreachline,writesthesumofthenumbersitcontains. #include <sstream> #include <iostream> #include <string> using namespace std; int main() { string s; while (getline(cin, s)) { istringstream ss(s); int sum = 0; int x; while (ss >> x) sum += x; cout << sum << endl; } } 1.2 Stacks: stack Stacks. Readsasequenceofnumbersandwritesitbackwards. #include <stack> #include <iostream> using namespace std; int main() { stack<int> s; int x; while (cin >> x) s.push(x); while (not s.empty()) { cout << s.top() << endl; s.pop(); } } 1.3 Queues: queue Queues. Readsasequenceofnumbersandwritesitstraight. #include <queue> #include <iostream> using namespace std; int main() { queue<int> q; int x; while (cin >> x) q.push(x); while (not q.empty()) { cout << q.front() << endl; q.pop(); } } 1.4 Priority queues: priority_queue Priority queues. Readsasequenceofnumbersandwritesitindecreasingorder. #include <queue> #include <iostream> using namespace std; int main() { priority_queue<int> pq; int x; while (cin >> x) pq.push(x); while (not pq.empty()) { cout << pq.top() << endl; pq.pop(); } } 1.5 Priority queues with inverted order (Analternativemethodistoinvertthesign) Priority queues with inverted order. Readsasequenceofnumbersandwritesitinincreasingorder. Thethirdparameterofthetypeisthe importantone,butprovidingthesecondisrequired. #include <queue> #include <iostream> using namespace std; int main() { priority_queue<int, vector<int>, greater<int>> pq; int x; while (cin >> x) pq.push(x); while (not pq.empty()) { cout << pq.top() << endl; pq.pop(); } } 1.6 Sets: set Sets. Readstwosequencesofnumbersendedwith0andwritestheirintersection. #include <set> #include <iostream> #include <string> using namespace std; int main() { set<int> s1, s2; int x; cin >> x; while (x != 0) { s1.insert(x); cin >> x; } cin >> x; while (x != 0) { s2.insert(x); cin >> x; } for (set<int>::iterator it = s1.begin(); it != s1.end(); ++it) { if (s2.find(*it) != s2.end()) cout << *it << endl; } } 1.7 Dictionaries: map Maps. Readsasequenceofwordsand, foreachword, inalphabeticalorder, writesthenumberoftimesit appears. #include <map> #include <iostream> #include <string> using namespace std; int main() { map<string, int> m; string x; while (cin >> x) ++m[x]; for (map<string, int>::iterator it = m.begin(); it != m.end(); ++it) { cout << it->first << " " << it->second << endl; } } 1.8 New features in C++11 New features of C++11. In C++11 one can let the compiler ”guess”variable types. Moreover, the loop-construction for has beenextendedtoalloweasyiterationsovercollections. Itisnolongernecessarytoaddablankin>> intemplates,anditispossibletoinitializecomplextypesthroughlistsofinitialvalues. To compile with C++11, a recent version of GCC is needed (for example gcc-4.7.0). Compilation requirestheparameter-std=c++11. WithslightlyolderversionsofGCC(suchas4.6.2)therequired parameteris-std=c++0x. #include <vector> #include <set> #include <iostream> using namespace std; int main() { // readavectorfrominput vector<int> v; int x; while (cin >> x) v.push_back(x); // writeallelementsofvtooutput for (int y : v) cout << y << "endl"; // doubleallelementsofv(notethereferencetomodifytheelements!!!) for (int& y : v) y *= 2; // writeallelementsofvagain for (int y : v) cout << y << endl; // makeasetofsetsofintegersandwriteit set<set<int>> S = {{2,3}, {5,1,5}, {}, {3}}; for (auto s : S) { cout << "{"; for (auto x : s) cout << x << ","; cout << "}" << endl; } } 1.9 Unordered sets: unordered_set Unordered sets. Readstwosequencesofnumbersendedwith0andwritestheirintersection. ThiscodeusesC++11. #include <unordered_set> #include <iostream> #include <string> using namespace std; int main() { unordered_set<int> s1, s2; int x; cin >> x; while (x != 0) { s1.insert(x); cin >> x; } cin >> x; while (x != 0) { s2.insert(x); cin >> x; } for (auto x : s1) { if (s2.find(x) != s2.end()) cout << x << endl; } } 1.10 Unordered dictionaries: unordered_map Unordered maps. Reads a sequence of words and, for each word, prints the number of times it appears. Since an unorderedmapisused,theorderoftheoutputisundefined. ThiscodeusesC++11. #include <unordered_map> #include <iostream> #include <string> using namespace std; int main() { unordered_map<string, int> m; string x; while (cin >> x) ++m[x]; for (auto elem : m) { cout << elem.first << " " << elem.second << endl; } } 1.11 Definition of hash functions Definition of hash functions. Inthiscasethehashfunctionisthesumofthehashfunctionsappliedtoallthreefields. Definingthe comparatoroperatorforequalityisrequired. ThiscodeusesC++11. #include <unordered_set> using namespace std; struct Point { int x, y, z; friend bool operator== (const Point& p1, const Point& p2) { return p1.x == p2.x and p1.y == p2.y and p1.z == p2.z; } struct Hash { size_t operator() (const Point& p) const { return hash<int>()(p.x) + hash<int>()(p.y) + hash<int>()(p.z); } }; }; int main() { unordered_set<Point, Point::Hash> cloud; cloud.insert({5,2,3}); }