Data Structures

Arrays

/* Built-in Array (fixed size) */

/* Initialization */
//     the dimension must be a constant expression, 
//     or be omitted when using list initialization
int a1[5];                                      // if defined in a function, it will have undefined values
int a2[] = {1, 2, 3};                           // dimension is 3
int a3[5] = {1, 2, 3};                          // equivalent to a3[] = {1, 2, 3, 0, 0}

/* Size */
int size = sizeof(a) / sizeof(*a);

/* Iteration */
for (int i = 0; i < size; ++i) {                    // using subscript
    // a[i] ... 
}

for (auto element : a) {                            // traverse the entire array
    // element ...
}

                                                
for (int *p = begin(a); p != end(a); ++p) {         // using pointer
    // *p ...
}

/* Sort */
sort(a, a + size);

/* vector */
#include <vector>

/* Initialization */
vector<int> v0;                                             // empty vector
vector<int> v1(5, 1);                                       // 5 elements with value 1
vector<int> v2(5);                                          // 5 elements with default value 0
vector<int> v3{1, 2, 3};                                    // equivalent = vector<int> v3 = {1, 2, 3};

/* Copy */
vector<int> v4(v0);
vector<int> v5 = v4;

/* Size */
v.size();

/* Iteration */
for (int i = 0; i < v.size(); ++i) {
    // v[i] ...
}

for (auto ele : v) {
    // ele ...
}

for (auto it = v.begin(); it != v.end(); ++it) {
    // *it ...
}

/* Initialize a 2D vector */
vector<vector<int>> vec(m, vector<int>(n));                 // initialize m * n matrix with default value
vector<vector<int>> vec(m, vector<int>(n, value));          // initialize with given value

/* find whether a given value in the vector */
// https://stackoverflow.com/questions/571394/how-to-find-out-if-an-item-is-present-in-a-stdvector
#include<algorithm>
if (find(vec.begin(), vec.end(), value) != vec.end())
    // the vector contains the value
else
    // does not contain


/* Extract a subvector from the vector */
auto left = vec.begin() + n1;
auto right = vec.begin() + n2;          // right is not included
vector<T> subvec(left, right);

/* Concatenation */
v1.insert(v1.end(), v2.begin(), v2.end());

/* Sort: see the below section */

String

http://www.cplusplus.com/reference/string/string/

#include<string>

/* Initialization */
string s1;
string s2(s1);
string s2 = s1;
string s3("value");
string s3 = "value";
string s4(n, 'c');
// copy initialize: initialize a variable using =
// direct initialize: omit the =

/* string to number */
stoi(str);                  // to int
stof(str);                  // to float
stod(str);                  // to double
// atoi() is a C-way, not suggested
// from_chars() is introduced in C++17

/* number to string */
to_string(value);           // value type: int, float, double, long, unsigned, etc.

string::npos                // the value is -1
// when used as the value for a len, it means until the end of the string
// when used as a return value, it is usually used to indicate no matches

/* sub string */
s1.substr(pos = 0, len = npos);        // note that the second parameter is the length of substring, not the ending position

/* find the index of another string/char */
s1.find();                              // return npos if not found

/* cctype functions */
#include<cctype>

isalnum(ch);
isalpha(ch);
islower(ch);
isupper(ch);
isdigit(ch);
isblank(ch);
ispunct(ch);
tolower(ch);
toupper(ch);

/* split string(sentence) into vector of string(words) */
// reference: https://stackoverflow.com/a/5208977
#include <sstream>
string str("the sentence to split");
string buf;                             // a buffer string
stringstream ss(str);                   // insert the string into a stream

vector<string> tokens;

while (ss >> buf)                       // in this way, the delimiter is space
    tokens.push_back(buf);

while (getline(ss, buf, ','))           // set other delimiter (e.g., ',') using getline
    tokens.push_back(buf);

/* join the vector into a string */
// reference: https://stackoverflow.com/a/1430774
stringstream ss;
for (int i = 0; i < tokens.size(); ++i) {
    if (i)
        ss << " ";                      // or ',', or whatever delimiter
    ss << tokens[i];
}
string s = ss.str();

Pair

#include <utility>

/* Declaration and initialiaztion */
pair<int, int> p1;          // default constructor
pair<int, int> p2 (1, 2);   // value init
pair<int, int> p3 (p2);     // copy constructor

pair<int, int> p4 = {3, 4}; // in C++11
pair<int, int> p5 = make_pair(5, 6);

/* Element access */
p2.first                    // no parentheses
p2.second

Stack

#include <stack>

/* Declaration */
stack<T> s;

/* Element access */
s.top();

/* Capacity */
s.size();
s.empty();

/* Modifiers */
s.push();
s.pop();                        // return type of pop() is void, it doesn't return the top value. 
                                // usually used with top() together

Queue

Queue (Normal)

#include <queue>

/* Declaration */
queue<T> q;

/* Element access */
q.front();                      // not top()
q.back();                       // used more in deque

/* Capacity */
q.size();
q.empty();

/* Modifiers */
q.push();
q.pop();

Priority Queue

#include <queue>
#include <functional>

/* Priority Queue */
priority_queue<T> pq;
pq.push();
pq.pop();
pq.top();                        // note that it is not consistent with queue!

// By default, priority queue would pop largest first (as a max heap). 
// If we want to pop smallest first (as a min heap), we can declare as follows:
priority_queue<int, vector<int>, greater<int>> pq;

Set

Hash Set

#include <unordered_set>

unordered_set<int> hashset;

/* Modifier */
hashset.insert();

/* Check if the set contains a value */
if (hashset.count(value) > 0)           // original way, if contains, hashset.count(value) == 1
    // ...

if (hashset.contains(value))            // newly introduced in C++20
    // ...

Set (Tree Set)

#include <set>

set<int> s;
/*
    The functions of set are basically the same as unordered_set.
    set containers are generally slower than unordered_set containers to access individual elements by their key, 
    but they allow the direct iteration on subsets based on their order. and elements in set are stored in order (typically implemented as binary search trees).
*/

Map

Hash Map

#include <unordered_map>

/* Operator[] */
value = hashmap[key];
hashmap[key] = newValue;

/* Iterator */
for (auto it : hashmap) {
    cout << it.first << endl;           // key
    cout << it.second << endl;          // value
}

/* Hashmap as counter */
if (hashmap.count(key) > 0)             // update
    ++hashmap[key];
else                                    // insert
    hashmap[key] = 1;
// in fact, we can simplify in one line:
hashmap[key]++;

Algorithms

Well, algorithm is not a separated concept from data structure, and some algorithms have been covered in the above section. Here I’ll just list some more.

Sort

For sorting algorithms, refer to my GitHub post. The post currently includes insertion sort, merge sort and quick sort.

#include <algorithm>
//vector<int> v;
sort(v.begin(), v.end());                   // sort the vector in ascending order
sort(v.begin(), v.end(), greater<int>())    // sort the vector in descending order

// What if we want to sort in custom order?
// E.g., vector<pair<int, int>> v1
// if we want to order the vector with the pairs' second value:
bool compareSecond(pair<int, int> p1, pair<int, int> p2) {
    return p1.second < p2.second;
}
sort(v1.begin(), v1.end(), compareSecond);


// And how about priority queue?
// E.g., we have a pair, which contains a point (expressed as a pair) and its distance to origin.
// We want to build a min-heap with the distance.
typedef pair<pair<int, int>, int> point_dist;
class myCompare {
public: 
    bool operator()(point_dist pd1, point_dist pd2) {
        return pd1.second > pd2.second;
    }
}
priority_queue<point_dist, vector<point_dist>, myCompare> pq;

Binary Search

Given a sorted array, binary search could find the target with a time complexity of $O(n)$ . Following is the basic template:

int binarySearch(vector<int>& nums, int target) {
    if (nums.empty()) 
        return -1;

    int left = 0, right = nums.size() - 1, mid;
    while (left <= right) {
        mid = left + (right - left) / 2;        // avoid overflow
        if (nums[mid] == target)
            return mid;
        else if (nums[mid] < target)
            left = mid + 1;
        else                                    // nums[mid] > target
            right = mid - 1;
    }

    return -1;
}

The pointer left and right are used to control the search area.
If the middle value equals our target, then we just make it. If the middle value is less than the target, then it means that we should search the larger part. We need to move the left pointer to right. Otherwise, we need to move the right pointer to left if the middle value is greater.
Note that the calculation of mid is a bit counterintuitive. The purpose is to prevent the overflow caused by adding. Suppose that left is 1 and right is INT_MAX, then the adding will cause overflow and lead to errors. Therefore, it’s advised to use left + (right - left) / 2 instead.