Data Structures and Algorithms Cheatsheet (C++)

Posted on | Post modified: | | Visitors:
Arrays, string, stack, queue, etc. Common data structures and algorithms.

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;