STL Containers Cheat Sheet

#include <vector>
std::vector<T> v;
std::vector<T> v(n);           // n default-constructed elements
std::vector<T> v(n, val);      // n copies of val
std::vector<T> v = {1, 2, 3};

// Add / remove
v.push_back(x);               // O(1) amortized
v.emplace_back(args...);      // construct in-place
v.pop_back();                 // O(1)
v.insert(it, x);              // O(n)
v.erase(it);                  // O(n)
v.clear();                    // O(n)

// Access
v[i]          // no bounds check
v.at(i)       // throws out_of_range
v.front()     // first element
v.back()      // last element
v.data()      // raw pointer

// Size / capacity
v.size()
v.empty()
v.capacity()
v.reserve(n)  // pre-allocate
v.shrink_to_fit()

// Iteration
for (auto& x : v) { }

#include <array>
std::array<T, N> a;
std::array<T, N> a = {1, 2, 3};   // N must match
a[i]; a.at(i); a.front(); a.back(); a.data();
a.size();    // constexpr — compile-time constant
a.fill(val);

#include <deque>
std::deque<T> dq;
dq.push_front(x); dq.push_back(x);
dq.pop_front();   dq.pop_back();
dq[i]; dq.at(i); dq.front(); dq.back();

#include <map>
std::map<K, V> m;
m[key] = val;                 // insert or assign
m.insert({key, val});
m.emplace(key, val);
m.find(key);                  // returns iterator
m.count(key);                 // 0 or 1
m.contains(key);              // C++20
m.erase(key);
m.lower_bound(key);           // first >= key
m.upper_bound(key);           // first > key
for (auto& [k, v] : m) { }   // sorted order

#include <unordered_map>
std::unordered_map<K, V> m;
// Same interface as map but O(1) avg lookup
m.bucket_count();
m.load_factor();
m.reserve(n);       // pre-size hash table

#include <set>
#include <unordered_set>
std::set<T> s;
std::unordered_set<T> us;

s.insert(x);
s.erase(x);
s.count(x);           // 0 or 1
s.contains(x);        // C++20
s.find(x);            // iterator
// set: sorted; unordered_set: O(1) avg

#include <stack>
#include <queue>

// Stack (LIFO)
std::stack<T> st;
st.push(x); st.pop(); st.top(); st.empty(); st.size();

// Queue (FIFO)
std::queue<T> q;
q.push(x); q.pop(); q.front(); q.back(); q.empty(); q.size();

// Priority queue (max-heap by default)
std::priority_queue<T> pq;
pq.push(x); pq.pop(); pq.top(); pq.empty(); pq.size();

// Min-heap
std::priority_queue<T, std::vector<T>, std::greater<T>> minpq;