coding_cheat_sheet [Paul's Wiki]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Coding Cheat Sheet ======

For general techniques, see [[Algorithm Techniques]].

For explanations of problems see [[Algorithm Problems]].

===== Strings =====

Length of a string:

C++:<code c> stringVar.length() </code>

Adding a character to a string:
c++:<code c>
// Appending the string. 
init.append(add);
// concatenating the string. 
strcat(init, add);  
// Appending the string. 
init = init + add; 
</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 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>

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>
==== 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());''