Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
coding_cheat_sheet [2020/05/09 21:13]
paul
coding_cheat_sheet [2020/10/08 00:34] (current)
paul [Using Custom Data With Priority Queues]
Line 1: Line 1:
 ====== Coding Cheat Sheet ====== ====== Coding Cheat Sheet ======
 +
 +For general techniques, see [[Algorithm Techniques]].
 +
 +For explanations of problems see [[Algorithm Problems]].
 +
 +===== Strings =====
  
 Length of a string: Length of a string:
  
 C++:<code c> stringVar.length() </code> C++:<code c> stringVar.length() </code>
-Python: <code python> len(stringVar) </code> 
  
 Adding a character to a string: Adding a character to a string:
Line 15: Line 20:
 init = init + add;  init = init + add; 
 </code> </code>
 +
 +To convert anything into a string use ''to_string()''.
 +
 +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>
 +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 sortFunc(const vector<int> &v1, const vector<int> &v2)
 +{
 +  return v1[0] < v2[0];
 +}
 +</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>
 +
 +std::unordered_set<int> my_set;
 +
 +my_set.insert(12);
 +
 +std::unordered_set<int>::iterator it = my_set.find(13);
 +
 +if(it == my_set.end())
 +{
 +    std::cout << "13 not found!" << std::endl;
 +}
 +else
 +{
 +    std::cout << "Found: " << it* << std::endl;
 +    // Erase it:
 +    my_set.erase(it);
 +    // my_set.erase(13); // you can erase by iterator or by key, the function will return 0 or 1 depending on if erased.
 +}
 +</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 ====
 +
 +A queue is just a line man. First in fist out. You can only remove the element
 +in the front of the line of a queue. Remember that!
 +
 +  - ''pop()'' - pops front of the queue, does NOT return the element!
 +  - ''push()'' - pushes an element to the back of the queue.
 +  - ''front()'' - reference to element in the front of the queue.
 +  - ''back()'' - reference to the element in the back of the queue.
 +  - ''size()''
 +  - ''empty()'' - returns whether empty or not.
 +
 +===== Priority Queue =====
 +
 +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>
 +priority_queue<int> max_heap;
 +max_heap.push(10);
 +max_heap.push(1);
 +
 +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>
 +
 +==== Using Custom Data With Priority Queues ====
 +
 +There are numerous was of doing this but here is the least verbose way.
 +
 +<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());''
  
  • coding_cheat_sheet.1589058798.txt.gz
  • Last modified: 2020/05/09 21:13
  • by paul