Differences

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

--- coding_cheat_sheet [2020/08/19 00:55]
127.0.0.1 external edit
+++ coding_cheat_sheet [2021/11/08 00:09] (current)
paul [Using Custom Data With Priority Queues]
@@ Line 25: / Line 25: @@
 To erase characters, we use ''string.erase(pos, len)''.
-=== Sorting a 2D Vector ===
+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 make a sorting function do as follows:
+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)
+{
+  if( dm.find(entry.second) == dm.end() )
+  {
+      dm.erase(entry.first);
+      changed = true;
+  }
+}
+</code>
+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>
+==== Removing Whitespace from a string ====
+<code cpp>
+s.erase(std::remove_if(s.begin(), s.end(), ::isspace), s.end());
+</code>
+==== String to Number ====
+you can use
+''std::stoi( str )''
+where str is your number as ''std::string''.
+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 =====
+==== 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 ===
+==== Initialize 2D Vector ====
 Use the std::vector::vector(count, value) constructor that accepts an initial
@@ Line 71: / 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 80: / 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 115: / 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());''