C++ STL Cheatsheet-Version 1.0.0 - Competitive Programming and Technical Interview Essentials

Oct 13, 2026

C++ STL cheatsheet covering core containers, algorithms, and utilities with practical operation lists and typical time complexities. Containers include vector, set, map, unordered_set, unordered_map, stack, queue, and priority_queue, with notes on underlying implementations such as dynamic arrays, balanced binary search trees, and hash tables. Algorithms cover sort, binary_search, lower_bound/upper_bound, max/min element, while utilities summarize pair, tuple, swap, reverse, and next/previous permutation for interview-ready reference.

LanguageEnglish

CategoryGeneral

FormatPDF

Pages1

AccessFree to download

Containers

Vector (vector)

Set (set)

Map (map)

Unordered Set (unordered_set)

Unordered Map (unordered_map)

Stack (stack)

Queue (queue)

Priority Queue (priority_queue)

Algorithms

Sort

Binary Search (binary_search)

Lower Bound and Upper Bound

Max Element and Min Element

Utilities

Pair (pair)

Tuple (tuple)

Swap

Reverse

Next Permutation and Previous Permutation

C++ STL Cheatsheet-Version 1.0.0 Essentials for Competitive Programming and Technical Interviews By Habibur Rahman | ML Developer, Ex-Software Engineer February 4, 2024 Containers Vector (vector) • Operations: Access (O(1)), Insert/Delete at end (O(1) amortized), Insert/Delete elsewhere (O(n)) . • Note: vector is implemented as a dynamic array. \#include std::vector vec ; // Declaration vec .push_back (10); // Insert at the end - Amortized `O(1) ` vec .size (); // Get the number of elements - `O(1) ` vec .insert (vec .begin() + i , 20); // Insert at index i (0-based) - `O(n) ` vec .erase (vec .begin() + i); // Remove at index i (0-based) - `O(n) ` vec .pop_back (); // Remove the last element - `O(1) ` vec .clear (); // Remove all elements - `O(n) ` Set (set) • Operations: Insert/Delete/Search (O(log n)) . • Note: set is implemented as a balanced binary search tree (Red-Black Tree) . \#include std::set s ; s .insert (1); // Insert an element - `O(log n) ` s .find (1); // Find an element - `O(log n) ` s .erase (1); // Remove an element - `O(log n) ` s .clear (); // Remove all elements - `O(n) ` s .size (); // Get the number of elements - `O(1) ` Map (map) • Operations: Insert/Delete/Search by key (O(log n)) . • Note: map is implemented as a balanced binary search tree (Red-Black Tree) . \#include std::map m; m [1] = 2 ; // Insert or update a key-value pair - `O(log n) ` m .emplace (1 , 2); // Insert a key-value pair - `O(log n) ` m .find (1); // Find an element by key - `O(log n) ` m .erase (1); // Remove an element by key - `O(log n) ` m .clear (); // Remove all elements - `O(n) ` m .size (); // Get the number of elements - `O(1) ` Unordered Set (unordered_set) • Operations: Insert/Delete/Search (Average: O(1), Worst: O(n)) . • Note: unordered_set is implemented as a hash table. \#include std::unordered_set us ; us .insert (1); // Insert an element - `Average: O(1) ` , Worst: `O(n) ` us .find (1); // Find an element - `Average: O(1) ` , Worst: `O(n) ` us .erase (1); // Remove an element - `Average: O(1) ` , Worst: `O(n) ` us .clear (); // Remove all elements - `O(n) ` us .size (); // Get the number of elements - `O(1) ` Unordered Map (unordered_map) • Operations: Insert/Delete/Search by key (Average: O(1), Worst: O(n)) . • Note: unordered_map is implemented as a hash table. \#include std::unordered_map um; um [1] = 2 ; // Insert or update a key-value pair-`Average: O(1) ` , Worst: `O(n) ` um .emplace (1 , 2); // Insert a key-value pair - `Average: O(1) ` , Worst: `O(n) ` um .find (1); // Find an element by key - `Average: O(1) ` , Worst: `O(n) ` um .erase (1); // Remove an element by key - `Average: O(1) ` , Worst: `O(n) ` um .clear (); // Remove all elements - `O(n) ` um .size (); // Get the number of elements - `O(1) ` Stack (stack) • Operations: Push/Pop/Top (O(1)) . • Note: stack is implemented as a deque (double-ended queue) . \#include std::stack st ; st .push (10); // Push an element - `O(1) ` st .pop(); // Pop an element - `O(1) ` [st](st.top)[.](st.top)[top](st.top)(); // Get the top element - `O(1)` st .size (); // Get the number of elements - `O(1) ` st .empty(); // Check if the stack is empty - `O(1) ` st .clear (); // Remove all elements - `O(n) ` Queue (queue) • Operations: Enqueue/Dequeue/Front (O(1)) . • Note: queue is implemented as a deque (double-ended queue) . \#include std::queue q; q.push (10); // Enqueue an element - `O(1) ` q.pop(); // Dequeue an element - `O(1) ` q.front (); // Get the front element - `O(1) ` q.size (); // Get the number of elements - `O(1) ` q.empty(); // Check if the queue is empty - `O(1) ` q.clear (); // Remove all elements - `O(n) ` Priority Queue (priority_queue) • Operations: Insert/Delete Max (O(log n)), Get Max (O(1)) . • Note: priority_queue is imple

FAQs

What are the main time complexities for common std::vector operations?

Access is O(1). Insert/delete at the end is O(1) amortized, while insert/delete elsewhere is O(n). pop_back and clear are O(1) and O(n) respectively.

How do std::set and std::map differ in their performance characteristics?

Both provide insert, delete, and search in O(log n). They are implemented as balanced binary search trees (Red-Black Tree), and map operations are performed by key.

When should std::unordered_set and std::unordered_map be used instead of ordered containers?

They offer average O(1) insert/delete/search with worst-case O(n). They are implemented as hash tables, trading guaranteed ordering for hash-based performance.

Oct 13, 2026

Upload by Taylor Morgan