Differences

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

--- coding_cheat_sheet [2020/08/16 17:00]
paul [Queue]
+++ coding_cheat_sheet [2021/11/08 00:09] (current)
paul [Using Custom Data With Priority Queues]
@@ Line 1: / Line 1: @@
 ====== Coding Cheat Sheet ======
+For general techniques, see [[Algorithm Techniques]].
+For explanations of problems see [[Algorithm Problems]].
+===== Strings =====
 Length of a string:
@@ Line 15: / Line 21: @@
 </code>
-=== Sorting a 2D Vector ===
+To convert anything into a string use ''to_string()''.
-To make a sorting function do as follows:
+To erase characters, we use ''string.erase(pos, len)''.
+To convert to upper case or lower case you have to iterate over every character
+and use ''tolower(int c)'' or ''toupper(int c)''. They return the case converted
+character.
+To check if a character is alphanumeric (letters and numbers) or just
+alphabetic:
 <code cpp>
-bool sortFunc(const vector<int> &v1, const vector<int> &v2)
+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 ====
+This is tricky! The following does NOT work!!
+[[https://stackoverflow.com/questions/8234779/how-to-remove-from-a-map-while-iterating-it|Stack overflow article]].
+<code cpp>
+for(auto& entry : dm)
 {
-  return v1[0] < v2[0];
+  if( dm.find(entry.second) == dm.end() )
+  {
+      dm.erase(entry.first);
+      changed = true;
+  }
 }
 </code>
-=== Initialize 2D Vector ===
+Use a regular for loop with constant interators.
+<code cpp>
+for (auto it = m.cbegin(); it != m.cend() /* not hoisted */; /* no increment */)
+{
+  if (must_delete)
+  {
+    m.erase(it++);    // or "it = m.erase(it)" since C++11
+  }
+  else
+  {
+    ++it;
+  }
+}
+</code>
-<code cpp>vector<vector<int>> nums(NUMBER_OF_ROWS, vector<int>(NUMBER_OF_COLS, 0) );</code>
+==== Removing Whitespace from a string ====
-==== Hashtable ====
+<code cpp>
+s.erase(std::remove_if(s.begin(), s.end(), ::isspace), s.end());
+</code>
-A hashtable allows for the rapid lookup of data based on a key. It works as follows:
+==== String to Number ====
+you can use
-  - a hash function converts a key to an index.
+''std::stoi( str )''
-  - the value is stored or retrieved from that index.
+where str is your number as ''std::string''.
-===== Uordered Set =====
+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
-  - unordered_set: It is an ordered set of unique numbers that are stored by a key, which is equal to the number in each element. They are not ordered and allow for the fast retrieval and insertion of each element (constant time O(1)). To make them you use the following syntax:
+===== Ordered Container Order =====
-<code c++>
+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 =====
+==== Sorting a 2D Vector ====
+To make a sorting function do as follows. Remember, it means what has to be true
+for v1 to go before v2.
+<code cpp>
+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>
+Or with a lambda:
+<code cpp>
+sort(in.begin(), in.end(), [] (vector<int> &a, vector<int> &b) {return a[0] < b[0];});
+</code>
+==== Initialize 2D Vector ====
+Use the std::vector::vector(count, value) constructor that accepts an initial
+size and a default value.
+<code cpp>vector<vector<int>> nums(NUMBER_OF_ROWS, vector<int>(NUMBER_OF_COLS, 0) );</code>
+===== Unordered Set =====
+An ordered set of unique numbers that are stored by a key, which is equal to the
+number in each element. They are not ordered and allow for the fast retrieval
+and insertion of each element (constant time O(1)). To make them you use the
+following syntax:
+<code cpp>
 #include <unordered_set>
@@ Line 62: / 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 68: / Line 212: @@
 in the front of the line of a queue. Remember that!
-  - **pop()** - pops front of the queue, does NOT return the element!
+  - ''pop()'' - pops front of the queue, does NOT return the element!
-  - **push()** - pushes an element to the back of the queue.
+  - ''push()'' - pushes an element to the back of the queue.
-  - **front()** - reference to element in the front 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()**
+  - ''size()''
-  - **empty()** - returns whether empty or not.
+  - ''empty()'' - returns whether empty or not.
+===== Priority Queue =====
-===== Associative Container Order =====
+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.
-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>
+priority_queue<int> max_heap;
+max_heap.push(10);
+max_heap.push(1);
-<code c++>
+cout << "Top of max_heap: " << max_heap.top() << endl;
-// Here if greater<int> is used to make
+// prints 10
-// sure that elements are stored in
-// descending order of keys.
+priority_queue<int, vector<int>, greater<int>> min_heap;
-map<int, string, greater <int> > mymap;
+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 =====
+Range based loops return copies unless a reference is requested. They return the
+pair, so no pointer member access required.
+<code cpp>
+unordered_map<int, int> counts;
+multimap<int,int, greater<int>> sorted;
+for(auto& i : counts)
+{
+    sorted.insert(make_pair(i.second, i.first));
+}
+vector<int> out;
+for(auto& i : sorted)
+{
+    out.push_back(i.second);
+    if(--k == 0)
+        break;
+}
+</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());''