↓Skip to main content
  1. Posts/

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

··830 words·4 mins·
Table of Contents

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