C++ Essential Data Structures

instantiate

unordered_map<KeyType, ValType> mp;

O(1)

is empty?

mp.empty();

O(1)

get length

mp.size();

O(1)

set value for key

mp[some_key] = some_val;

O(1)**

check if key exists

auto it = mp.find(some_key);

O(1)

erase key value pair

mp.erase(some_key);

O(1)**

filter out some pairs

for (auto it = mp.begin(); it != c.end();) {
    if (someKeyCondition(it->first)) {
         it = mp.erase(it);
    } else { ++it; }
}

O(n)

instantiate empty

vector<ValType> vc;

O(1)

instantiate 2D Array

vector<vector<ValType>> fog(  // 4 rows x 3 cols 
    4, vector<ValType>(3, initial_value)  
 );

O(m*n)

get length

vc.size();

O(1)

assign value

vc[4] = some_val;

O(1)**?

add value to end

vc.push_back(some_val);

O(1)**

iterate through indexes

for (unsigned i = 0; i < vc.size(); i++) {
    cout << vc[i] << endl;  // print each value
}

O(n)

iterate through values

for (auto it = vc.begin(); it != vc.end(); it++) {
    cout << *it << endl;  // print each value
}

O(n)

iterate through values

for (aValType val: vc) {
    cout << val << endl;  // print each value
}

O(n)

instantiate

unordered_set<ValType> my_set;

O(1)

is empty?

my_set.empty();

O(1)

get length

my_set.size();

O(1)

insert element

my_set.insert(some_val)

O(1)**

if set contains

if (my_set.contains(some_val)) {/*do something*/}

O(1)

remove element

my_set.erase(some_val)

O(1)**

instantiate

queue<ValType> qu;

O(1)

is empty?

qu.empty();

O(1)

get length

qu.size();

O(1)

add to queue

qu.push(some_val);

O(1)

remove from queue

qu.pop();

O(1)

get value at front

qu.front();

O(1)

get value at back

qu.back();

O(1)

instantiate

stack<ValType> stk;

O(1)

is empty?

stk.empty();

O(1)

get length

stk.size();

O(1)

push onto stack

stk.push(some_val);

O(1)

pop stack

stk.pop(); // returns void

O(1)

peek at top

stk.top();

O(1)

build max heap

// where data is an iterable of type ValType
 priority_queue<ValType> max_pq(data.begin(), data.end());

O(n)

build min heap

priority_queue<ValType> min_pq(data.begin(), data.end(), greater<ValType>());

O(n)

is empty?

pq.empty();

O(1)

get length

pq.size();

O(1)

push value

pq.push(some_val);

O(log(n))

pop max/min

pq.pop(); // returns void

O(log(n))

get max/min value

pq.top();

O(1)

instantiate

map<KeyType, ValType> mp;

O(n)

is empty?

mp.empty();

O(1)

get length

mp.size();

O(1)

set value for key

mp[some_key] = some_val;

O(log(n))

if key exists

auto it = mp.find(some_key);
 if (it != mp.end()) {/* do something */}

O(log(n))

erase key value pair

mp.erase(some_key);

O(log(n))

define tree node type

struct node {
    int data;
    struct node* left;
    struct node* right;
};

n/a

define list node type

struct node {
    int data;
    struct node* next;
};

n/a