Data Structures and Algorithms Cheatsheet (C++)

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

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
#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 */
#include<cctype>
isalnum(ch);
isalpha(ch);
islower(ch);
isupper(ch);
isdigit(ch);
isblank(ch);
ispunct(ch);
tolower(ch);
toupper(ch);

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

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
#include <unordered_map>
/* Operator[] */
value = hashmap[key];
hashmap[key] = newValue;
/* Hashmap as counter */
if (hashmap.count(key) > 0) // update
++hashmap[key];
else // insert
hashmap[key] = 1;