C++11 STL Include Map

Quick reference grouping all containers, adapters, iterators, and algorithms by their #include header.

Sequence Containers

#include <vector>

Component Type Description
std::vector<T> Container Dynamic contiguous array. Heap-allocated. Random Access Iterator.
std::vector<T>::iterator Iterator Random Access. Supports it + n, it - n, it[n].
std::vector<T>::reverse_iterator Iterator Reverse traversal via rbegin(), rend().

Key Operations:

vec.reserve(n);      // Pre-allocate capacity (CRITICAL for performance)
vec.resize(n);       // Change size, default-construct new elements
vec.emplace_back();  // Construct in-place (avoids copy)
vec.shrink_to_fit(); // Release excess capacity (C++11)

#include <deque>

Component Type Description
std::deque<T> Container Double-ended queue. Chunked memory. Random Access Iterator.

Key Operations:

dq.push_front(x);    // O(1) insert at front
dq.push_back(x);     // O(1) insert at back
dq[i];               // O(1) random access (two pointer dereferences)

#include <list>

Component Type Description
std::list<T> Container Doubly-linked list. Per-element heap allocation. Bidirectional Iterator.

Key Operations:

lst.splice(pos, other);           // O(1) transfer nodes between lists
lst.splice(pos, lst, it);         // O(1) move single node within same list
lst.sort();                       // O(N log N) member sort (cannot use std::sort)
lst.merge(other);                 // O(N) merge sorted lists
lst.remove(val);                  // O(N) remove all matching
lst.unique();                     // O(N) remove consecutive duplicates

#include <forward_list>

Component Type Description
std::forward_list<T> Container Singly-linked list. Forward Iterator only. No size().

Key Operations:

fl.insert_after(pos, x);   // O(1) insert after position
fl.erase_after(pos);       // O(1) erase element after position
fl.before_begin();         // Iterator to before-the-first element

#include <array>

Component Type Description
std::array<T, N> Container Fixed-size contiguous array. Stack-allocated. Random Access Iterator.

Key Operations:

arr.fill(val);       // Set all elements to val
arr.data();          // Raw pointer to underlying array
arr.at(i);           // Bounds-checked access (throws std::out_of_range)

Associative Containers (Red-Black Tree)

#include <set>

Component Type Description
std::set<T> Container Sorted unique keys. O(log N) operations. Bidirectional Iterator.
std::multiset<T> Container Sorted keys with duplicates allowed.

Key Operations:

s.insert(x);              // O(log N) insert
s.erase(x);               // O(log N) + count of duplicates
s.find(x);                // O(log N) returns iterator
s.count(x);               // O(log N) + count
s.lower_bound(x);         // O(log N) first element >= x
s.upper_bound(x);         // O(log N) first element > x
s.equal_range(x);         // O(log N) pair of iterators

#include <map>

Component Type Description
std::map<K, V> Container Sorted key-value pairs. Unique keys. Bidirectional Iterator.
std::multimap<K, V> Container Sorted key-value pairs. Duplicate keys allowed.

Key Operations:

m[key] = val;             // O(log N) insert or update (DEFAULT-CONSTRUCTS if missing!)
m.at(key);                // O(log N) access (throws if missing)
m.emplace(key, val);      // O(log N) construct in-place
m.insert({key, val});     // O(log N) insert pair
m.find(key);              // O(log N) returns iterator (use this for existence check!)
m.lower_bound(key);       // O(log N) first key >= key
m.upper_bound(key);       // O(log N) first key > key

Unordered Containers (Hash Table)

#include <unordered_set>

Component Type Description
std::unordered_set<T> Container Hash-based unique keys. O(1) average. Forward Iterator.
std::unordered_multiset<T> Container Hash-based with duplicate keys.

Key Operations:

us.insert(x);             // O(1) average
us.erase(x);              // O(1) average
us.find(x);               // O(1) average (use for existence check)
us.count(x);              // O(1) average
us.reserve(n);            // Pre-allocate buckets to avoid rehash
us.bucket_count();        // Number of buckets
us.load_factor();         // size / bucket_count

#include <unordered_map>

Component Type Description
std::unordered_map<K, V> Container Hash-based key-value. O(1) average. Forward Iterator.
std::unordered_multimap<K, V> Container Hash-based with duplicate keys.

Key Operations:

um[key] = val;            // O(1) avg insert/update (DEFAULT-CONSTRUCTS if missing!)
um.at(key);               // O(1) avg (throws if missing)
um.emplace(key, val);     // O(1) avg construct in-place
um.find(key);             // O(1) avg (use for existence check!)
um.reserve(n);            // Pre-allocate to avoid O(N) rehash

Custom Hash for User Types:

struct MyHash {
    size_t operator()(const MyType& x) const {
        return std::hash<int>()(x.id);
    }
};
std::unordered_set<MyType, MyHash> custom_set;

Container Adapters

#include <stack>

Component Type Description
std::stack<T> Adapter LIFO. Default backing: std::deque. No iterators.

Key Operations:

stk.push(x);              // O(1)
stk.top();                // O(1) read top (does NOT remove)
stk.pop();                // O(1) remove top (returns void!)
stk.empty();              // O(1)
stk.size();               // O(1)
// NO clear()! Use: stk = std::stack<T>();

#include <queue>

Component Type Description
std::queue<T> Adapter FIFO. Default backing: std::deque. No iterators.

Key Operations:

q.push(x);                // O(1)
q.front();                // O(1) read front (does NOT remove)
q.back();                 // O(1) read back
q.pop();                  // O(1) remove front (returns void!)
// NO clear()! Use: q = std::queue<T>();

#include <queue> (also contains priority_queue)

Component Type Description
std::priority_queue<T> Adapter Heap. Default: Max-Heap. Backing: std::vector. No iterators.

Key Operations:

pq.push(x);               // O(log N) sift-up
pq.top();                 // O(1) read max (does NOT remove)
pq.pop();                 // O(log N) remove max (returns void!)
pq.emplace(args...);      // O(log N) construct in-place

// Min-Heap declaration:
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;

Algorithms

#include <algorithm>

Sorting

Algorithm Iterator Requirement Complexity Description
std::sort(beg, end) Random Access O(N log N) Introsort. Not stable.
std::stable_sort(beg, end) Random Access O(N log N) Merge sort. Stable.
std::partial_sort(beg, mid, end) Random Access O(N log K) Sort first K elements.
std::nth_element(beg, nth, end) Random Access O(N) avg QuickSelect. Element at nth position.
std::is_sorted(beg, end) Forward O(N) Check if sorted.

Binary Search (requires sorted range)

Algorithm Iterator Requirement Complexity Description
std::lower_bound(beg, end, val) Forward* O(log N) First element >= val.
std::upper_bound(beg, end, val) Forward* O(log N) First element > val.
std::binary_search(beg, end, val) Forward* O(log N) Returns bool.
std::equal_range(beg, end, val) Forward* O(log N) Pair of lower/upper bounds.

*O(log N) comparisons, but O(N) iterator advances for non-Random Access.

Searching

Algorithm Iterator Requirement Complexity Description
std::find(beg, end, val) Input O(N) First match.
std::find_if(beg, end, pred) Input O(N) First match by predicate.
std::count(beg, end, val) Input O(N) Count matches.
std::count_if(beg, end, pred) Input O(N) Count by predicate.
std::search(beg1, end1, beg2, end2) Forward O(N*M) Find subsequence.

Modifying

Algorithm Iterator Requirement Complexity Description
std::copy(beg, end, dest) Input + Output O(N) Copy range.
std::move(beg, end, dest) Input + Output O(N) Move range.
std::fill(beg, end, val) Forward O(N) Fill with value.
std::replace(beg, end, old, new) Forward O(N) Replace values.
std::transform(beg, end, dest, op) Input + Output O(N) Apply operation.
std::reverse(beg, end) Bidirectional O(N) Reverse in-place.
std::rotate(beg, mid, end) Forward O(N) Rotate range.
std::unique(beg, end) Forward O(N) Remove consecutive duplicates.
std::remove(beg, end, val) Forward O(N) Move removed to end, return new end.
std::remove_if(beg, end, pred) Forward O(N) Remove by predicate.

Permutations

Algorithm Iterator Requirement Complexity Description
std::next_permutation(beg, end) Bidirectional O(N) Next lexicographic permutation.
std::prev_permutation(beg, end) Bidirectional O(N) Previous permutation.

Min/Max

Algorithm Iterator Requirement Complexity Description
std::min(a, b) N/A O(1) Minimum of two values.
std::max(a, b) N/A O(1) Maximum of two values.
std::minmax(a, b) N/A O(1) Pair of min and max.
std::min_element(beg, end) Forward O(N) Iterator to minimum.
std::max_element(beg, end) Forward O(N) Iterator to maximum.
std::minmax_element(beg, end) Forward O(N) Pair of iterators.

Heap Operations (use with vector)

Algorithm Iterator Requirement Complexity Description
std::make_heap(beg, end) Random Access O(N) Build heap from range.
std::push_heap(beg, end) Random Access O(log N) Insert last element into heap.
std::pop_heap(beg, end) Random Access O(log N) Move max to end, re-heapify.
std::sort_heap(beg, end) Random Access O(N log N) Sort a heap into ascending order.

Set Operations (sorted ranges)

Algorithm Iterator Requirement Complexity Description
std::set_union(...) Input x2 + Output O(N+M) Union of two sorted ranges.
std::set_intersection(...) Input x2 + Output O(N+M) Intersection.
std::set_difference(...) Input x2 + Output O(N+M) Difference.
std::includes(beg1, end1, beg2, end2) Input O(N+M) Check if first contains second.

#include <numeric>

Algorithm Iterator Requirement Complexity Description
std::accumulate(beg, end, init) Input O(N) Sum/fold operation.
std::inner_product(...) Input O(N) Dot product.
std::partial_sum(beg, end, dest) Input + Output O(N) Running sum (prefix sum).
std::adjacent_difference(...) Input + Output O(N) Differences between adjacent.
std::iota(beg, end, start) Forward O(N) Fill with incrementing values.

Iterators & Utilities

#include <iterator>

Component Type Description
std::advance(it, n) Function Move iterator by n (O(1) for Random Access, O(N) otherwise).
std::distance(first, last) Function Count elements (O(1) for Random Access, O(N) otherwise).
std::next(it, n) Function Return iterator n positions forward.
std::prev(it, n) Function Return iterator n positions backward.
std::back_inserter(container) Output Iterator Calls push_back on assignment.
std::front_inserter(container) Output Iterator Calls push_front on assignment.
std::inserter(container, pos) Output Iterator Calls insert at position.
std::istream_iterator<T> Input Iterator Read from stream.
std::ostream_iterator<T> Output Iterator Write to stream.
std::reverse_iterator<It> Iterator Adapter Reverse direction of base iterator.

#include <functional>

Component Type Description
std::less<T> Functor a < b (default for sort, priority_queue max-heap).
std::greater<T> Functor a > b (use for min-heap).
std::equal_to<T> Functor a == b.
std::hash<T> Functor Hash function for built-in types.
std::function<R(Args...)> Wrapper Type-erased callable wrapper.
std::bind(fn, args...) Function Bind arguments to function.
std::ref(x) / std::cref(x) Wrapper Reference wrapper for bind/thread.

#include <utility>

Component Type Description
std::pair<T1, T2> Type Two-element tuple.
std::make_pair(a, b) Function Create pair with type deduction.
std::move(x) Function Cast to rvalue reference.
std::forward<T>(x) Function Perfect forwarding.
std::swap(a, b) Function Exchange values.

#include <tuple>

Component Type Description
std::tuple<T...> Type N-element heterogeneous container.
std::make_tuple(...) Function Create tuple with type deduction.
std::get<N>(tuple) Function Access Nth element (compile-time index).
std::tie(a, b, ...) Function Unpack tuple into references.

Strings

#include <string>

Component Type Description
std::string Container std::basic_string<char>. SSO-optimized. Random Access Iterator.
std::wstring Container std::basic_string<wchar_t>. Wide characters.
std::to_string(num) Function Convert number to string.
std::stoi(str) Function String to int.
std::stol(str) Function String to long.
std::stoll(str) Function String to long long.
std::stof(str) Function String to float.
std::stod(str) Function String to double.

Key Operations:

s.substr(pos, len);       // O(len) substring
s.find(substr);           // O(N*M) find substring
s.rfind(substr);          // O(N*M) find from end
s.find_first_of(chars);   // O(N*M) find any char in set
s.c_str();                // Null-terminated C string
s.data();                 // Raw pointer (modifiable in C++11)
s.append(other);          // Amortized O(M)
s += other;               // Same as append

#include <sstream>

Component Type Description
std::stringstream Stream Read/write string as stream.
std::istringstream Stream Read from string.
std::ostringstream Stream Write to string. 
std::istringstream iss("10 20 30");
int a, b, c;
iss >> a >> b >> c;  // Parse whitespace-separated

std::ostringstream oss;
oss << "Value: " << 42;
std::string result = oss.str();

Other Useful Headers

#include <limits>

Component Type Description
std::numeric_limits<T>::max() Function Maximum value for type T.
std::numeric_limits<T>::min() Function Minimum value (or smallest positive for float).
std::numeric_limits<T>::lowest() Function Lowest value (most negative for float).

#include <climits> (C-style limits)

Macro Description
INT_MAX Maximum int value.
INT_MIN Minimum int value.
LLONG_MAX Maximum long long value.
LLONG_MIN Minimum long long value.

#include <cmath>

Function Description
std::abs(x) Absolute value.
std::pow(base, exp) Power.
std::sqrt(x) Square root.
std::log(x) Natural logarithm.
std::log2(x) Base-2 logarithm.
std::ceil(x) Round up.
std::floor(x) Round down.

#include <cstdlib>

Function Description
std::abs(x) Absolute value (int version).
std::rand() Pseudo-random number (avoid in modern C++).
std::srand(seed) Seed random generator.

#include <random> (C++11)

Component Type Description
std::mt19937 Engine Mersenne Twister (32-bit).
std::mt19937_64 Engine Mersenne Twister (64-bit).
std::uniform_int_distribution<T> Distribution Uniform integers in [a, b].
std::uniform_real_distribution<T> Distribution Uniform reals in [a, b). 
std::mt19937 rng(std::random_device{}());
std::uniform_int_distribution<int> dist(1, 100);
int random_num = dist(rng);

Quick Reference: Common Interview Includes

// Almost always needed
#include <vector>
#include <string>
#include <algorithm>

// Hash-based containers
#include <unordered_map>
#include <unordered_set>

// Tree-based containers
#include <map>
#include <set>

// Adapters
#include <stack>
#include <queue>  // includes priority_queue

// Utilities
#include <utility>    // pair, move
#include <functional> // greater, less, hash

// Numeric
#include <numeric>    // accumulate, iota
#include <climits>    // INT_MAX, INT_MIN
#include <cmath>      // sqrt, pow, abs

// I/O
#include <iostream>
#include <sstream>    // stringstream
#include <fstream>    // file I/O

// Iterator utilities
#include <iterator>   // advance, distance, back_inserter

C++11 STL Include Map | Bijup.com