Cheatsheet STL

C++

1. Data structures for C++:

1.1 Vector

#include <vector>

std::vector

Use for

Simple storage
Adding but not deleting
Serialization
Quick lookups by index
Easy conversion to C-style arrays
Efficient traversal (contiguous CPU caching)

Do not use for

Insertion/deletion in the middle of the list
Dynamically changing storage
Non-integer indexing

Time Complexity

Operation	Time Complexity
Insert Head	`O(n)`
Insert Index	`O(n)`
Insert Tail	`O(1)`
Remove Head	`O(n)`
Remove Index	`O(n)`
Remove Tail	`O(1)`
Find Index	`O(1)`
Find Object	`O(n)`

1.2 Deque

#include <deque>

std::deque

Use for

Similar purpose of std::vector
Basically std::vector with efficient push_front and pop_front

Do not use for

C-style contiguous storage (not guaranteed)

Notes

Pronounced ‘deck’
Stands for Double Ended Queue

1.3 List

#include <list>

std::list

Use for

Insertion into the middle/beginning of the list
Efficient sorting (pointer swap vs. copying)

Do not use for

Direct access

Time Complexity

Operation	Time Complexity
Insert Head	`O(1)`
Insert Index	`O(n)`
Insert Tail	`O(1)`
Remove Head	`O(1)`
Remove Index	`O(n)`
Remove Tail	`O(1)`
Find Index	`O(n)`
Find Object	`O(n)`

1.4 Map

#include <map>

std::map

Use for

Key-value pairs
Constant lookups by key
Searching if key/value exists
Removing duplicates
std::map
- Ordered map
std::unordered_map
- Hash table

Do not use for

Sorting

Notes

Typically ordered maps (std::map) are slower than unordered maps (std::unordered_map)
Maps are typically implemented as binary search trees

Time Complexity

std::map

Operation	Time Complexity
Insert	`O(log(n))`
Access by Key	`O(log(n))`
Remove by Key	`O(log(n))`
Find/Remove Value	`O(log(n))`

std::unordered_map

Operation	Time Complexity
Insert	`O(1)`
Access by Key	`O(1)`
Remove by Key	`O(1)`
Find/Remove Value	—

1.5 Set

#include <set>

std::set

Use for

Removing duplicates
Ordered dynamic storage

Do not use for

Simple storage
Direct access by index

Notes

Sets are often implemented with binary search trees

Time Complexity

Operation	Time Complexity
Insert	`O(log(n))`
Remove	`O(log(n))`
Find	`O(log(n))`

1.6 Stack

#include <stack>

std::stack

Use for

First-In Last-Out operations
Reversal of elements

Time Complexity

Operation	Time Complexity
Push	`O(1)`
Pop	`O(1)`
Top	`O(1)`

1.7 Queue

#include <queue>

std::queue

Use for

First-In First-Out operations
Ex: Simple online ordering system (first come first served)
Ex: Semaphore queue handling
Ex: CPU scheduling (FCFS)

Notes

Often implemented as a std::deque

1.8 Priority Queue

#include <priority_queue>

std::priority_queue

Use for

First-In First-Out operations where priority overrides arrival time
Ex: CPU scheduling (smallest job first, system/user priority)
Ex: Medical emergencies (gunshot wound vs. broken arm)

Notes

Often implemented as a std::vector