Data Structures and Algorithms Cheatsheet (C++)

Data Structures

Arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* 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);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/* 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 ...
}

/* Sort */
sort(v.begin(), v.end());

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

String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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.

/* 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) // 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

1
2
3
4
5
6
7
8
9
10
11
12
13
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stack>

/* Declaration */
stack<T> s;

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

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

/* Modifiers */
s.push();
s.pop(); // return type is void, doesn't return the top value

Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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 */
priority_queue<T> pq;
pq.push();
pq.pop();
pq.top(); // not consistent with queue!

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

From now on, the declaration and capacity part will be omitted.

Hash Table

1
2
3
4
5
6
7
8
9
10
11
#include <unordered_set>

/* Element access */
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!
// ...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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;

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.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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.