The Fellowship of the STL: C++ Data Structures Every Competitive Programmer Needs

The Quest Begins (The Why)

In the author's early competitive programming days, a dynamic median problem proved elusive. They relied on a priority_queue, but each pop destroyed half the data. After hours of frustration, they discovered the heap's hidden container, leading to a pivotal moment in their journey.

The Revelation (The Insight)

1. Priority Queue's Secret Container

The author explains that priority_queue's standard interface hides its underlying container. By inheriting from it, you gain access to iterate, clear, or re-heapify manually. This insight is crucial for problems requiring heap manipulation beyond popping the top element.

2. Unordered Map's Reserve & Load-Factor Control

Unordered_map offers O(1) average performance for insertions and lookups. However, its efficiency can degrade if rehashing occurs too frequently. The author reveals that pre-allocating buckets with reserve(n) and setting max_load_factor(z) can prevent unnecessary rehashes, saving precious time in contests.

3. Vector's Capacity Tricks – Shrink-to-Fit & Swap Idiom

Unlike priority_queue and unordered_map, vector's clear() does not release allocated memory. This can lead to wasted memory when reusing the vector across multiple test cases. The author introduces two techniques to truly shrink a vector: shrink_to_fit() and the swap trick. Both methods ensure minimal memory usage, a crucial consideration in competitive programming environments with strict memory limits.

Wielding the Power (Code & Examples)

The author provides code snippets demonstrating the practical application of these STL features. These examples showcase how to implement an inspectable priority_queue, optimize unordered_map performance, and manage vector capacity efficiently in competitive programming scenarios.