Coding Cheat Sheet

For general techniques, see Algorithm Techniques.

For explanations of problems see Algorithm Problems.

Length of a string:

C++:

 stringVar.length() 

Adding a character to a string: c++:

// Appending the string. 
init.append(add);
// concatenating the string. 
strcat(init, add);  
// Appending the string. 
init = init + add; 

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:

isalnum(char c) // alpha numeric
isalpha(char c) // alphabetic
isdigit(char c) // is a number

Returns false (0) if not.

How to split a stream in an array of words.

// 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; 
} 

Use std::advance() to advance the iterator from begin to size()/2

#include <iterator>
 
auto it = mySet.begin();
std::advance(it, mySet.size()/2);

This is tricky! The following does NOT work!!

Stack overflow article.

for(auto& entry : dm)
{
  if( dm.find(entry.second) == dm.end() )
  { 
      dm.erase(entry.first);
      changed = true;
  }
}

Use a regular for loop with constant interators.

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;
  }
}

s.erase(std::remove_if(s.begin(), s.end(), ::isspace), s.end());

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

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!

// Here if greater<int> is used to make 
// sure that elements are stored in 
// descending order of keys. 
map<int, string, greater <int> > mymap; 

To make a sorting function do as follows. Remember, it means what has to be true for v1 to go before 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);

Or with a lambda:

sort(in.begin(), in.end(), [] (vector<int> &a, vector<int> &b) {return a[0] < b[0];});

Use the std::vector::vector(count, value) constructor that accepts an initial size and a default value.

vector<vector<int>> nums(NUMBER_OF_ROWS, vector<int>(NUMBER_OF_COLS, 0) );

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:

#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.
}

Pairs need a special hashing function for them to work. Regular ordered sets work just fine too.

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;

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!

1. pop() - pops front of the queue, does NOT return the element!
2. push() - pushes an element to the back of the queue.
3. front() - reference to element in the front of the queue.
4. back() - reference to the element in the back of the queue.
5. size()
6. empty() - returns whether empty or not.

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.

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

By default, max heaps using type pair are ordered by the first element. You do not need to create a custom Compare class. See here

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);

There are numerous was of doing this but here is the most elegant way:

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);

A less elegant way of overloading the default less than operator is as follows:

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;

See here.

Another option:

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;

here.

Range based loops return copies unless a reference is requested. They return the pair, so no pointer member access required.

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;
}

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:

myList.push_back(1);
myList.push_back(2);
myList.push_back(3);
myList.push_back(4);

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