Differences

This shows you the differences between two versions of the page.

--- coding_cheat_sheet [2020/08/30 05:57]
paul [Strings]
+++ coding_cheat_sheet [2021/11/08 00:09] (current)
paul [Using Custom Data With Priority Queues]
@@ Line 35: / Line 35: @@
 isalnum(char c) // alpha numeric
 isalpha(char c) // alphabetic
+isdigit(char c) // is a number
 </code>
 Returns false (0) if not.
+==== Split ====
+How to split a stream in an array of words.
+<code cpp>
+// Utility function to split the string using a delim. Refer -
+// http://stackoverflow.com/questions/236129/split-a-string-in-c
+vector<string> split(const string &s, char delim)
+{
+    vector<string> elems;
+    stringstream ss(s);
+    string item;
+    while (getline(ss, item, delim))
+        elems.push_back(item);
+    return elems;
+}
+</code>
 ===== Maps =====
+==== Going to middle element ====
+Use ''std::advance()'' to advance the iterator from begin to ''size()/2''
+<code cpp>
+#include <iterator>
+auto it = mySet.begin();
+std::advance(it, mySet.size()/2);
+</code>
 ==== Iterating over a map and deleting an element ====
@@ Line 87: / Line 116: @@
 There are version for all flavours of numbers: long stol(string), float stof(string), double stod(string),... see http://en.cppreference.com/w/cpp/string/basic_string/stol
+===== Ordered Container Order =====
+In C++ associative containers such as sets and maps store values in ascending order. You can easily change this by passing a comparative function that takes in two parameters a and b and returns true if a goes before b. STL provides basic versions of these functions for you!
+<code cpp>
+// Here if greater<int> is used to make
+// sure that elements are stored in
+// descending order of keys.
+map<int, string, greater <int> > mymap;
+</code>
 ===== Vectors =====
@@ Line 96: / Line 136: @@
 <code cpp>
-bool sortFunc(const vector<int> &v1, const vector<int> &v2)
+bool compareFunc(const vector<int> &v1, const vector<int> &v2)
 {
   return v1[0] < v2[0];
 }
+// use the sort function by passing in the custom compare fucnction
+sort(myVect.begin(), myVect.end(), compareFunc);
 </code>
@@ Line 142: / Line 185: @@
 }
 </code>
+==== Unordered Sets of Pairs ====
+Pairs need a special hashing function for them to work. Regular ordered sets work just fine too.
+<code cpp>
+struct pair_hash
+{
+	template <class T1, class T2>
+	std::size_t operator () (std::pair<T1, T2> const &pair) const
+	{
+		std::size_t h1 = std::hash<T1>()(pair.first);
+		std::size_t h2 = std::hash<T2>()(pair.second);
+		return h1 ^ h2;
+	}
+};
+unordered_set<pair<int,int>, pair_hash> mySet;
+</code>
 ===== Queue ====
@@ Line 151: / Line 215: @@
   - ''push()'' - pushes an element to the back of the queue.
   - ''front()'' - reference to element in the front of the queue.
-  - ''back()'' - reference to the elemnt in the back of the queue.
+  - ''back()'' - reference to the element in the back of the queue.
   - ''size()''
   - ''empty()'' - returns whether empty or not.
-===== Ordered Container Order =====
+===== Priority Queue =====
-In C++ associative containers such as sets and maps store values in ascending order. You can easily change this by passing a comparative function that takes in two parameters a and b and returns true if a goes before b. STL provides basic versions of these functions for you!
+A C++ ''priority_queue'' is a heap, which is by default a max heap as it uses
+the standard less comparator. Easy to get confused here, because the ''top()''
+function isn't getting the begin element of the container. Just remember, by
+default a prioirty queue is a max heap.
 <code cpp>
-// Here if greater<int> is used to make
+priority_queue<int> max_heap;
-// sure that elements are stored in
+max_heap.push(10);
-// descending order of keys.
+max_heap.push(1);
-map<int, string, greater <int> > mymap;
+cout << "Top of max_heap: " << max_heap.top() << endl;
+// prints 10
+priority_queue<int, vector<int>, greater<int>> min_heap;
+min_heap.push(10);
+min_heap.push(1);
+cout << "Top of min_heap: " << min_heap.top() << endl;
+// prints 1
+</code>
+==== Max Heap with Pairs ====
+By default, max heaps using type pair are ordered by the first element. You do not need to create a custom Compare class. See [[https://www.geeksforgeeks.org/priority-queue-of-pairs-in-c-ordered-by-first/|here]]
+<code cpp>
+typedef pair<int,int> num_t;
+priority_queue<num_t> maxHeap;
+maxHeap.push(make_pair(1,2));
+maxHeap.push(make_pair(2,2));
+// This will be true
+assert_true(maxHeap.top().first == 2);
+</code>
+==== Using Custom Data With Priority Queues ====
+There are numerous was of doing this but here is the most elegant way:
+<code cpp>
+struct node{
+  node(int id, int value) : id(id), value(value){}
+  int id;
+  int value;
+};
+auto cmp = [](const node &a, const node &b){
+  //Max Heap:
+  //======================
+  //larger b will appear later in the container and therefore have a higher priority
+  return a.value < b.value;
+  //MIN Heap:
+  //if a is larger than b, it will appear before b, so smaller b will have higher priority
+  return a.value > b.value;
+};
+priority_queue<node, vector<node>, decltype(cmp)> maxHeap(cmp);
+</code>
+A less elegant way of overloading the default less than operator is as follows:
+<code cpp>
+struct node{
+  node(int _id, int _value) : id(_id), value(_value){}
+  int id;
+  int value;
+};
+bool operator<(const node& A, const node& B) {
+  // Priority look at the "last" element of their list as the one having
+  // the highest priority
+  /*--- FOR A MAX HEAP ---*/
+  // B will go after A and have a higher priority than A
+  return A.value < B.value;
+  /*--- FOR A MIN HEAP ---*/
+  // a GREATER THAN b means b will go before a. The smaller element a will have
+  // a higher priority than b.
+  return A.value > B.value;
+}
+// Now you initalize your priority queue normally, as it will call the
+// overloaded LESS THAN comparator
+priority_queue<node> pQ;
+</code>
+See [[https://stackoverflow.com/questions/9178083/priority-queue-for-user-defined-types|here]].
+Another option:
+<code cpp>
+typedef pair<string, int> p_d;
+class Compare{
+public:
+    bool operator() (const p_d& a, const p_d& b){
+        if(a.second == b.second){
+            return a.first > b.first;
+        }else {
+            return a.second < b.second;
+        }
+    }
+};
+// This is a max heap based on number of the int in the pair, and if numbers are the same, word thats lower on the alphabetical compare wins.
+priority_queue<p_d, vector<p_d>, Compare> heap;
 </code>
+[[https://stackoverflow.com/questions/16111337/declaring-a-priority-queue-in-c-with-a-custom-comparator|here]].
 ===== Range Based Loops =====
@@ Line 186: / Line 357: @@
 }
 </code>
+===== Lists =====
+Lists are C++ implementations of doubly linked lists. They allow for
+manipulation of data from both ends of the list. The following functions allow
+you to control them:
+  * pop_back()
+  * push_back()
+  * pop_front()
+  * push_front()
+  * front()
+  * back()
+List iteartors are bidrectional! ''--myList.end()'' is a valid iterator that
+points the last element of the list (assuming the list has size greater than
+zero).
+We can also splice in elemnts into a position. For example, say we had a list
+like the following:
+<code cpp>
+myList.push_back(1);
+myList.push_back(2);
+myList.push_back(3);
+myList.push_back(4);
+</code>
+''1 <-> 2 <-> 3 <-> 4''
+And we want to place 4 in the front. We can do the following:
+''myList.splice(myList.begin(), myList, --myList.end());''