# A CheatSheet of C++ Container/Adapter and Common Structure

··830 words·4 mins·

I use Python in my work, and rarely need C++. So I need to compile this C++ cheatsheet for common STL containers/adapters, just in case I need them.

# vector#

• Define a 1D vector: `vector<int> arr = {1, 2, 3};`
• Define a 2D vector: `vector<vector<int>> mat = {{1, 2, 3}, {4, 5}};`
• Define a 2D vector of size 3x4: `vector<vector<int> > mat(3, vector<int>(4, 0));`
• Add an element: `arr.push_back(2);`
• Insert an element: `arr.insert(arr.begin(), -1);`
• Insert another vector: `vector<int> another = {1, 2, 3}; arr.insert(arr.begin(), another.begin(), another.end());`
• Check its size: `cout << arr.size();`
• Check if vector is empty: `cout << arr.empty();`
• Slice a vector, i.e., get a sub-vector from an existing vector: `vector<int> arr(10, 1); vector<int> new_vec(arr.begin(), arr.begin()+3);` (this is end-exclusive, so the resulting vector has 3 elements)
• Sort a vector:
• In ascending order (the default): `std::sort(arr.begin(), arr.end());`
• In descending order (we need to use custom compare function): `std::sort(arr.begin(), arr.end(), std::greater<int>());`

Ref:

# string#

• Define a string: `string myStr = "hello";`
• Get string size: `myStr.size()`
• Get sub-string: `myStr.substr(0, 2)` (Get the substring starting at index 0 and with length 2, end-exclusive style)
• Get sub-string: `myStr.substr(1)` (Get substring starting at index 1 till the end)
• Check if string is empty: `myStr.empty();`
• Generate a string with `n` same character `ch`: `string(n, ch)`;
• Reverse a string: use `std::reverse`, `std::reverse(myStr.begin(), myStr.end())`.

Ref:

# set (works like a Python set)#

`set` in C++ is typically implemented using balanced binary search tree.

• Define a set: `set<int> x = {1, 2, 3};`
• Add an element: `x.insert(5);`
• Check size: `x.size()`
• Check if set is empty: `x.empty();`
• Check if set contains a key: `x.find(2) != x.end();` or `x.count(2) != 0`
• Initialize set from a vector of int: `vector<int> arr = {1, 2, 1, 3}; set<int> my_set(arr.begin(), arr.end());`

There is also `unordered_set`, which is different from `set`:

• The underlying implementation for `set` is binary search tree (BST), while the underlying implementation for `unordered_set` is hash table.
• The element in `set` is sorted so that their order is guaranteed, while for `unordered_set`, there is no guarantee for the element order.
• `set` requires less memory than `unordered_set` (`unordered_set` has to store a hash table).
• Search time is at most `O(log(n))` for `set`, while for `unordered_set`, the search time is on average `O(1)`, but may be `O(n)` in worst case (highly unlikely)

# map (works like a Python dict)#

Typically implemented using balanced binary search tree.

• Define an empty map: `map<int, string> items;`

• Define a constant map: `map<int, string> num2str = {{1, "ab"}, {2, "cd"}, {3, "ef"}};`

• Add an element: `items.insert({1, "apple"});` or `items[1] = "apple";`

• Remove an element: `items.erase("apple");`

• Access a key (no check): `cout << items[1] << endl;` (we have to make sure the key exists, otherwise it will be inserted silently)

• Access a key (with check): `cout << items.at(4);` (will error out)

• Show map element key and value:

``````for (auto item: items){
cout << item.first << " " << item.second << endl;
}
``````

ref:

There is also `unordered_map`. The different between map and unordered_map is similar to the difference between set and unordered_set. So I will not elaborate on this.

Note that when map is defined using the `const` modifier, you can not access map element with operator `[]`, since it is possible to alter map value when accessing map element like this, check this post for more details.

# queue#

Queue is a data structure that provides FIFO (first in first out) feature. Element that is added first will also be removed first.

• Get queue size: `queue<int> q; cout << q.size() << endl;`
• Check if queue is empty: use `q.empty()` or `q.size() == 0`
• Get front element of queue: `cout << q.front() << endl;`
• Add element to queue: `q.push(4);`
• Pop up front element: `q.pop();`

# stack#

Stack is the opposite of queue. It provides a LIFO (last in first out) data structure. Element that is added last will be removed first.

• Get stack size: `stack<int> s; cout << s.size() << endl;`
• Check if stack is empty: `s.empty()` or `s.size() == 0`
• Get top element from stack: `cout << s.top() << endl;` (note that getting top element when stack is empty leads to errors!)
• Add element to stack: `s.push(1);`
• Pop up element from stack: `s.pop();`

# tuple#

Tuple can be used to different types of data.

• Create a tuple: `std::make_tuple("abc", 2, 3);`
• Get tuple element: `std:get<0>(some_tuple);` (get first element, really weird and unintuitive syntax!)

# pair#

Pair can be used to hold two different data types conveniently.

• Create a pair: `pair<int, string> my_pair = std::make_pair(2, "abc")`
• Get pair element: `my_pair.first` and `my_pair.second`

Ref:

# References#

## Related

Integer Literal Type and Overflow In C++
·288 words·2 mins
Databricks Cli Usage
·141 words·1 min
File Systems in Databricks
·304 words·2 mins