C++ STL Overview

Concept

The C++ Standard Template Library (STL) provides ready-to-use containers and algorithms. In competitive programming, the most important ones are vector, pair, map, set, priority_queue, stack, queue, and the sort/lower_bound functions. Knowing when to use each container saves time and avoids bugs.

When to Use

  • ▸vector — dynamic array, default container for almost everything
  • ▸map/set — when you need sorted keys or unique elements with O(log n) operations
  • ▸unordered_map/unordered_set — O(1) average lookup, frequency counting
  • ▸priority_queue — when you need the min/max element quickly (Dijkstra, greedy)
  • ▸stack/queue — BFS (queue), DFS iterative (stack), expression parsing

Intuition

Think of STL containers as tools in a toolbox. Vector is your hammer — use it for almost everything. Map is a sorted dictionary. Set is a sorted bag of unique items. Priority queue is a heap that always gives you the biggest (or smallest) element. Stack is LIFO (last in, first out), queue is FIFO (first in, first out). Pick the right tool for the job and you avoid writing data structures from scratch.

Complexity

Time
Varies by container (see examples below)
Space
O(n) for all containers

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    // --- vector: O(1) push_back, O(1) access ---
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    sort(v.begin(), v.end());

    // --- pair ---
    vector<pair<int, int>> edges;
    edges.push_back({3, 5});
    int a = edges[0].first;   // 3
    int b = edges[0].second;  // 5

    // --- map: sorted keys, O(log n) insert/find ---
    map<string, int> mp;
    mp["apple"] = 3;
    mp["banana"] = 5;
    for(auto &[key, val] : mp){
        cout << key << " " << val << "\n";
    }

    // --- set: sorted unique elements, O(log n) ---
    set<int> s;
    s.insert(3);
    s.insert(1);
    s.insert(3);  // duplicate ignored
    // s = {1, 3}

    // --- priority_queue (max-heap by default) ---
    priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(5);
    cout << pq.top() << "\n";  // 5
    pq.pop();

    // --- min-heap ---
    priority_queue<int, vector<int>, greater<int>> minpq;
    minpq.push(3);
    minpq.push(1);
    cout << minpq.top() << "\n";  // 1

    // --- stack: LIFO ---
    stack<int> st;
    st.push(1);
    st.push(2);
    cout << st.top() << "\n";  // 2
    st.pop();

    // --- queue: FIFO ---
    queue<int> q;
    q.push(1);
    q.push(2);
    cout << q.front() << "\n";  // 1
    q.pop();

    // --- useful algorithms ---
    // sort(v.begin(), v.end());
    // reverse(v.begin(), v.end());
    // *min_element(v.begin(), v.end());
    // *max_element(v.begin(), v.end());
    // lower_bound(v.begin(), v.end(), x) - v.begin();  // first >= x
    // upper_bound(v.begin(), v.end(), x) - v.begin();  // first > x

    return 0;
}