The C++ Time Complexity Cheat Sheet serves as a quick reference for beginners and intermediates looking to learn C++ data structures. This is a 1-page PDF in A4 paper size which can be printed at home.
Did you know that pushing an element on a stack in C++ takes O(1) but only if the stack adapts a deque? If the stack adapts a vector then pushing an element takes Θ(1); the big Theta symbol, Θ, represents amortized/average time complexity. Details such as these matter during tech screens and interviews, and we sincerely hope that this quick reference guide will help you stand out and win that dream job.
- Array (std::array)
- Vector (std::vector)
- Deque (std::deque)
- Singly Linked List (std::forward_list)
- Doubly Linked List (std::list)
- Ordered Set (std::set)
- Ordered Map (std::map)
- Ordered Multiset (std::multiset)
- Ordered Multimap (std::multimap)
- Unordered Set (std::unordered_set)
- Unordered Map (std::unordered_map)
- Unordered Multiset (std::unordered_multiset)
- Unordered Multimap (std::unordered_multimap)
- Stack (std::stack)
- Queue (std::queue)
- Priority Queue (std::priority_queue)
Algorithm Library Functions:
GCC Builtin Functions:
You'll get a high-quality LaTeX-based PDF which you can use indefinitely as a quick reference to double-check time complexities during tech screens and interviews.