Advanced Guide to C++ STL for Competitive Programming

Advanced Guide to C++ STL for Competitive Programming

3K views
Summary
The C++ STL is built on three fundamental components: containers, algorithms, and iterators. Understanding how these components interact and their underlying implementations is crucial for optimal usage in competitive programming.

Introduction to STL

The C++ Standard Template Library (STL) is a powerful set of C++ template classes to provide general-purpose classes and functions with templates that implement many popular and commonly used algorithms and data structures. For competitive programming, STL is an essential tool that can significantly reduce development time and improve code reliability.

Core Components of STL

1. Containers

Objects that store data. STL includes the following container classes:

Sequence Containers:

vector

Dynamic array that can grow and shrink in size.

#include <vector>
vector<int> v = {1, 2, 3};
v.push_back(4);        // Add element
v.pop_back();         // Remove last element
v.size();            // Get size
v.empty();           // Check if empty
v[0];               // Access element
list

Doubly linked list implementation.

#include <list>
list<int> lst = {1, 2, 3};
lst.push_back(4);     // Add to end
lst.push_front(0);    // Add to front
lst.pop_back();      // Remove from end
lst.pop_front();     // Remove from front
deque

Double-ended queue with dynamic array implementation.

#include <deque>
deque<int> dq = {1, 2, 3};
dq.push_back(4);     // Add to end
dq.push_front(0);    // Add to front
dq.pop_back();      // Remove from end
dq.pop_front();     // Remove from front

Associative Containers:

set

Sorted unique elements.

#include <set>
set<int> s = {3, 1, 2, 1};  // Stores: {1, 2, 3}
s.insert(4);         // Insert element
s.erase(1);         // Remove element
s.count(2);         // Count occurrences (0 or 1)
s.find(3);          // Find element
map

Sorted key-value pairs with unique keys.

#include <map>
map<string, int> m;
m["apple"] = 1;
m["banana"] = 2;
m.count("apple");    // Check if key exists
m.erase("banana");   // Remove key-value pair
multiset & multimap

Allow duplicate elements/keys.

#include <set>
#include <map>
multiset<int> ms = {1, 1, 2, 2, 3};
multimap<string, int> mm;
mm.insert({"apple", 1});
mm.insert({"apple", 2});

Unordered Containers:

unordered_set & unordered_map

Hash table implementations with O(1) average time complexity.

#include <unordered_set>
#include <unordered_map>
unordered_set<int> us = {3, 1, 2};
unordered_map<string, int> um;
um["fast"] = 1;     // O(1) insertion
us.find(2);         // O(1) lookup

2. Algorithms

STL provides various algorithms for sorting, searching, and manipulating containers:

Sorting Algorithms
#include <algorithm>
vector<int> v = {3, 1, 4, 1, 5};
sort(v.begin(), v.end());                    // Sort ascending
sort(v.begin(), v.end(), greater<int>());    // Sort descending
// Custom sort
sort(v.begin(), v.end(), 
     [](int a, int b) { return a > b; });    // Lambda function
Binary Search
// On sorted containers:
binary_search(v.begin(), v.end(), 3);    // Returns bool
lower_bound(v.begin(), v.end(), 3);      // First element >= value
upper_bound(v.begin(), v.end(), 3);      // First element > value
Other Common Algorithms
// Min/Max
*max_element(v.begin(), v.end());
*min_element(v.begin(), v.end());

// Sum
accumulate(v.begin(), v.end(), 0);

// Count
count(v.begin(), v.end(), 1);

// Find
find(v.begin(), v.end(), 5);

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

// Next permutation
next_permutation(v.begin(), v.end());

LeetCode Problems and Solutions

1. Two Sum (LeetCode #1)

Problem: Find two numbers in an array that add up to a target.

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (map.count(complement))
            return {map[complement], i};
        map[nums[i]] = i;
    }
    return {};
}

Key concept: Using unordered_map for O(1) lookup

2. Valid Parentheses (LeetCode #20)

Problem: Check if string has valid parentheses.

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[')
            st.push(c);
        else {
            if (st.empty()) return false;
            if (c == ')' && st.top() != '(') return false;
            if (c == '}' && st.top() != '{') return false;
            if (c == ']' && st.top() != '[') return false;
            st.pop();
        }
    }
    return st.empty();
}

Key concept: Using stack for matching pairs

Competitive Programming Tips

Time-saving Techniques

  1. Use typedef for long types: 
    typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
  2. Fast I/O for large inputs: 
    ios_base::sync_with_stdio(false);
cin.tie(NULL);
  3. Use '\n' instead of endl for faster output

Common Patterns

  • Use unordered_map/set instead of map/set when order doesn't matter
  • For sliding window problems, use deque
  • For graph problems, use vector<vector<int>> for adjacency list
  • Use priority_queue for heap operations

Practice Resources

  • LeetCode - Start with Easy problems focusing on specific data structures
  • Codeforces - For real competitive programming experience
  • AtCoder - For practicing implementation skills
  • SPOJ - For classical algorithmic problems
Advanced Guide to C++ STL for Competitive Programming