The C++ Standard Template Library (STL) is essential for competitive programming (CP) on platforms like Codeforces. It provides powerful, optimized data structures and algorithms that save time and prevent you from reinventing the wheel during contests.The primary STL containers every competitive programmer must know are grouped below by their functionality, use cases, and time complexities:1. Sequence Containersstd::vector (Dynamic Array)What it is: A dynamic array that can resize itself automatically when an element is inserted or deleted.Why it's essential: It is the default container for storing sequential data. Unlike standard static arrays, vectors can be passed to functions seamlessly, resized on the fly, and integrated directly with STL algorithms like std::sort.Key Operations: * Access: v[i]

Unable to parse markup [type=CF_MATHJAX]

\rightarrow \mathcal{O}(1)$$$ amortizedInsert/Delete in middle: $$$\rightarrow \mathcal{O}(N)$$$std::deque (Double-Ended Queue)What it is: Similar to a vector, but optimized for fast insertion and deletion at both the beginning and the end.Why it's essential: Useful for problems requiring a sliding window maximum/minimum or any algorithm where elements must push or pop from both ends.Key Operations:Push/Pop front & back: push_front(), pop_front(), push_back(), pop_back() $$$\rightarrow \mathcal{O}(1)$$$Random Access: dq[i] $$$\rightarrow \mathcal{O}(1)$$$2. Container Adaptorsstd::stack & std::queueWhat they are: LIFO (Last In, First Out) and FIFO (First In, First Out) structures.Why they're essential: * std::queue is fundamental for implementing Breadth-First Search (BFS).std::stack is used for maintaining monotonic stacks (finding the next greater/smaller element) and evaluating mathematical expressions.Key Operations: push(), pop(), top() / front() $$$\rightarrow \mathcal{O}(1)

Unable to parse markup [type=CF_MATHJAX]

-th largest element efficiently, and implementing Dijkstra's Algorithm or Prim's Algorithm.Key Operations: * Push: pq.push()

Unable to parse markup [type=CF_MATHJAX]

\rightarrow \mathcal{O}(\log N)$$$Top element: pq.top() $$$\rightarrow \mathcal{O}(1)$$$Tip: To turn it into a min-heap, declare it as: priority_queue \lt int, vector \lt int \gt , greater \lt int» pq;3. Associative Containers (Sorted by Default)std::set & std::multisetWhat they are: Containers that store unique elements (set) or duplicate elements (multiset) in a strictly sorted order using a Balanced Binary Search Tree (Red-Black Tree).Why they're essential: Whenever you need to maintain a dynamically changing, sorted collection of numbers. They also allow you to use binary search operations (lower_bound and upper_bound) natively.Key Operations: insert(), erase(), find() $$$\rightarrow \mathcal{O}(\log N)$$$std::mapWhat it is: A sorted collection of Key-Value pairs where each key is unique.Why it's essential: Ideal for coordinate compression, frequency counting, or building dynamic lookups where elements need to remain sorted by their keys.Key Operations: Insertion/Lookup: mp[key] $$$\rightarrow \mathcal{O}(\log N)$$$4. Unordered Associative Containers (Hash Tables)std::unordered_set & std::unordered_mapWhat they are: Hash table-based versions of set and map. They do not keep elements in a sorted order.Why they're essential: When you need ultra-fast lookups, inserts, or frequency counting and do not care about ordering.Key Operations: Average case $$$\rightarrow \mathcal{O}(1)$$$; Worst case $$$\rightarrow \mathcal{O}(N)$$$Warning for Codeforces: The worst-case $$$\mathcal{O}(N)$$$ can be triggered intentionally by adversaries using custom-crafted inputs designed to cause hash collisions (known as "hacking"). To prevent getting a Time Limit Exceeded (TLE) verdict, you should either stick to std::map / std::set or plug a custom, randomized anti-hash test function into your unordered container.5. Advanced Container / Policy-Based Data Structuresordered_set (Policy-Based Data Structure)What it is: A non-standard C++ extension (available in GCC/G++ used by Codeforces) often referred to as a Policy-Based Data Structure (PBDS).Why it's essential: Standard std::set lacks the ability to find the index of an element or find an element at a specific index in logarithmic time. An ordered_set gives you two powerful operations in $$$\mathcal{O}(\log N)

Unable to parse markup [type=CF_MATHJAX]

-th largest element (0-indexed).order_of_key(x): Returns the number of elements strictly smaller than $$$x$$$ (useful for counting inversions).Quick Cheat Sheet SummaryContainerUnderlying StructureOrderSearch / Insert / Delete TimevectorDynamic ArrayInsertion order$\mathcal{O}(1)$$$ at end, $$$\mathcal{O}(N)$$$ middledequeBlocked array pointersInsertion order$$$\mathcal{O}(1)$$$ at front and endset / mapRed-Black TreeSorted$$$\mathcal{O}(\log N)$$$unordered_mapHash TableNo order$$$\mathcal{O}(1)$$$ average, $$$\mathcal{O}(N)$$$ worstpriority_queueBinary HeapMax/Min on top$$$\mathcal{O}(\log N)$ insert/po