Differences

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

--- coding_cheat_sheet [2020/09/18 04:01]
paul [Strings]
+++ coding_cheat_sheet [2021/11/08 00:09] (current)
paul [Using Custom Data With Priority Queues]
@@ Line 40: / Line 40: @@
 Returns false (0) if not.
+==== Split ====
 How to split a stream in an array of words.
@@ Line 135: / 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 181: / 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 215: / Line 240: @@
 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 least verbose way.
+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>
@@ Line 226: / Line 289: @@
   int id;
   int value;
-}
+};
 bool operator<(const node& A, const node& B) {
@@ Line 253: / Line 316: @@
 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 =====