Advanced Guide to C++ STL for Competitive Programming

The Standard Template Library (STL) is one of the most powerful parts of C++ for competitive programming. If you are solving problems on platforms like Codeforces, AtCoder, LeetCode, or CodeChef, STL is not optional. Without STL mastery, you will write slower code, make more bugs, and lose time during contests.

Most beginners misuse STL by memorizing syntax without understanding complexity, internal behavior, iterator invalidation, and optimal use cases. Competitive programming requires more than syntax. You need speed, precision, and understanding of tradeoffs.

1. What is STL?

STL (Standard Template Library) is a collection of:

Containers
Algorithms
Iterators
Functors
Utility classes

It provides optimized implementations of common data structures and algorithms.

Main STL Components

Component	Purpose
Containers	Store data
Algorithms	Sorting, searching, manipulation
Iterators	Traverse containers
Functors	Custom comparison/functions
Utilities	Pairs, tuples, etc.

2. Vector — The Most Important STL Container

If you do not deeply understand vector, you are not ready for competitive programming.

Declaration

vector<int> v;

Initialization

vector<int> v(5);          // size 5 initialized with 0
vector<int> v(5, 10);      // size 5 initialized with 10

Important Functions

v.push_back(5);
v.pop_back();

v.size();
v.empty();

v.front();
v.back();

v.clear();

Traversal

for(int x : v)
{
    cout << x << " ";
}

Complexity

Operation	Complexity
push_back()	O(1) amortized
pop_back()	O(1)
Access by index	O(1)
Insertion in middle	O(n)

Common Mistake

Many beginners use vectors inefficiently:

vector<int> v;

for(int i=0;i<1000000;i++)
{
    v.push_back(i);
}

This repeatedly reallocates memory. Better:

v.reserve(1000000);

Reserve avoids unnecessary reallocations.

3. Pair and Tuple

Pair

pair<int,int> p;

p = {10, 20};

cout << p.first;
cout << p.second;

Useful in

Coordinate problems
Graphs
Sorting multiple values

Tuple

tuple<int,int,string> t;

t = {1, 2, "Skytup"};

cout << get<0>(t);

4. Stack

LIFO (Last In First Out)

Declaration

stack<int> st;

Operations

st.push(10);
st.pop();

st.top();

st.empty();

Complexity

All operations are O(1)

Applications

Balanced parentheses
Expression evaluation
Monotonic stack
DFS

5. Queue and Deque

Queue

FIFO (First In First Out)

queue<int> q;

q.push(5);
q.pop();

q.front();
q.back();

Deque

Double-ended queue.

deque<int> dq;

dq.push_front(10);
dq.push_back(20);

dq.pop_front();
dq.pop_back();

Why deque matters

Deque is heavily used in sliding window maximum problems.

6. Priority Queue (Heap)

Extremely important for greedy problems and graph algorithms.

Max Heap

priority_queue<int> pq;

Min Heap

priority_queue<int, vector<int>, greater<int>> pq;

Operations

pq.push(10);

pq.top();

pq.pop();

Complexity

Operation	Complexity
push	O(log n)
pop	O(log n)
top	O(1)

Applications

Dijkstra Algorithm
K largest elements
Scheduling problems
Greedy optimization

7. Set and Multiset

Set

Stores unique sorted elements.

set<int> s;

s.insert(5);
s.insert(2);

s.erase(5);

if(s.find(2) != s.end())
{
    cout << "Found";
}

Complexity

O(log n)

Multiset

Allows duplicates.

multiset<int> ms;

Important Insight

Internally implemented using Red-Black Trees.

That means operations are logarithmic, not constant.

8. Unordered Set

Hash-table based implementation.

unordered_set<int> us;

Complexity

Operation	Average	Worst
Insert	O(1)	O(n)
Find	O(1)	O(n)

Critical Warning

Many beginners blindly use unordered_set because they hear "O(1)". Bad idea.

In competitive programming, hash collision attacks can make unordered containers very slow.

For strict worst-case guarantees, use set.

9. Map and Unordered Map

Map

map<string, int> mp;

mp["apple"] = 5;

cout << mp["apple"];

Properties

Sorted by key
O(log n)
Tree based

Unordered Map

unordered_map<string, int> ump;

When to use map?

Need sorted order
Need lower_bound/upper_bound
Avoid hacking via collisions

When to use unordered_map?

Need faster average lookup
No ordering required

10. STL Algorithms

This is where STL becomes truly powerful.

sort()

sort(v.begin(), v.end());

Descending Sort

sort(v.begin(), v.end(), greater<int>());

Binary Search

binary_search(v.begin(), v.end(), 5);

Lower Bound

lower_bound(v.begin(), v.end(), 5);

Upper Bound

upper_bound(v.begin(), v.end(), 5);

Reverse

reverse(v.begin(), v.end());

Maximum Element

max_element(v.begin(), v.end());

Minimum Element

min_element(v.begin(), v.end());

Count

count(v.begin(), v.end(), 5);

11. Custom Comparator

Essential for advanced sorting problems.

bool cmp(pair<int,int> a, pair<int,int> b)
{
    return a.second < b.second;
}

sort(v.begin(), v.end(), cmp);

Common Mistake

Comparator must define strict weak ordering.

Wrong comparator logic causes undefined behavior.

12. Iterators

Basic Iterator

vector<int>::iterator it;

for(it = v.begin(); it != v.end(); it++)
{
    cout << *it;
}

Auto Keyword

for(auto it = v.begin(); it != v.end(); it++)
{
    cout << *it;
}

Reverse Iterator

for(auto it = v.rbegin(); it != v.rend(); it++)
{
    cout << *it;
}

13. Lambda Functions

Modern competitive programming heavily uses lambdas.

sort(v.begin(), v.end(), [](int a, int b)
{
    return a > b;
});

Why lambdas matter

Cleaner code
Fast custom comparators
Useful in STL algorithms

14. Bitset

Very memory efficient binary storage.

bitset<8> b("10101010");

cout << b.count();

Applications

Bitmask DP
Sieve optimization
State compression

15. Important Competitive Programming Tricks

Fast Input Output

ios::sync_with_stdio(false);
cin.tie(NULL);

Remove Duplicates from Vector

sort(v.begin(), v.end());

v.erase(unique(v.begin(), v.end()), v.end());

Frequency Counting

map<int,int> freq;

for(int x : v)
{
    freq[x]++;
}

16. Time Complexity Summary

Container	Insert	Search	Delete
vector	O(1)	O(n)	O(n)
set	O(log n)	O(log n)	O(log n)
unordered_set	O(1)	O(1)	O(1)
map	O(log n)	O(log n)	O(log n)
unordered_map	O(1)	O(1)	O(1)
priority_queue	O(log n)	O(1)	O(log n)

17. Advanced STL Concepts

Policy Based Data Structures (PBDS)

Not officially STL, but widely used in advanced contests.

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

Ordered Set

Supports:

Find by order
Order of key

Useful for rank queries.

18. Common STL Mistakes in Competitive Programming

Using vector erase repeatedly inside loops
Using unordered_map everywhere blindly
Ignoring iterator invalidation
Using map instead of array for small ranges
Sorting repeatedly unnecessarily
Not understanding complexity

Example of Bad Code

for(int i=0;i<v.size();i++)
{
    v.erase(v.begin());
}

This becomes O(n²).

19. Best STL Containers for Different Problems

Problem Type	Recommended STL
Frequency counting	unordered_map
Sorted unique elements	set
Priority processing	priority_queue
Fast sequential storage	vector
Sliding window	deque
Balanced parentheses	stack

20. Final Advice

Most students learn STL passively. That does not work.

You must:

Practice implementation daily
Memorize complexities
Understand internal structures
Know when NOT to use a container
Solve real contest problems

Competitive programming is largely about choosing the correct data structure under time pressure.

A weak STL foundation guarantees slow progress.

A strong STL foundation makes algorithms significantly easier.

Conclusion

C++ STL is not just a library. It is the backbone of competitive programming.

If you deeply understand vectors, sets, maps, heaps, iterators, algorithms, and complexity analysis, you can solve problems faster, write cleaner code, and compete effectively in contests.

Do not stop at syntax. Understand behavior, performance, and tradeoffs. That is what separates average coders from strong competitive programmers.

Advanced Guide to C++ STL for Competitive Programming

Comments