W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Back to DSA Theory

C++ STL

Standard Template Library - your secret weapon for competitive programming!

🚀 STL Quick Reference

vector

Dynamic array

set/map

Sorted unique

stack/queue

LIFO/FIFO

priority_queue

Heap

What is STL?

Varies by container and operation

Ready-To-Use Container Building Blocks

Imagine cooking with pre-chopped vegetables and pre-made sauces from a grocery store. You do not need to cultivate fields and mill flour from scratch to bake a pizza crust. Instead, you focus on crafting the custom toppings.

The C++ Standard Template Library (STL) is a collection of templates that provides pre-built, highly-optimized data structures and generic algorithms so you don't have to write them yourself.

The Four Core Components of STL:

Containers: Structures that store data (e.g., vectors, sets, maps).
Algorithms: Functions for sorting, searching, reversing, and transforming data.
Iterators: Objects that act as pointer-like interfaces to traverse container elements.
Functors (Function Objects): Objects that can be called like functions (overloading operator()).

C++ Code — What is STL?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3};
    
    // Sort vector in ascending order
    sort(v.begin(), v.end());
    
    cout << "Sorted: ";
    for (int x : v) cout << x << " "; // 1 2 3 5 8 9
    cout << endl;
    
    // Find maximum element
    auto maxIt = max_element(v.begin(), v.end());
    if (maxIt != v.end()) {
        cout << "Max: " << *maxIt << endl; // 9
    }
    return 0;
}

Vector

Access: O(1) | Insert/Delete at end: O(1) amortized | Insert/Delete middle: O(n)

Dynamic Array Resize Slots

Imagine an expanding dining table. As more guests arrive (more items added), the table extends its leaves to fit them, doubling its capacity when fully filled.

A std::vector is a dynamic array container that automatically grows or shrinks in size as elements are inserted or deleted.

Core Mechanics:

Contiguous Memory Layout: Elements are stored in contiguous memory blocks, allowing constant-time random access via indices (O(1)).
Capacity vs Size: size() is the number of active elements, while capacity() is the total allocated slot space. When size == capacity, inserting a new element triggers a relocation to a new, double-sized memory block, running in amortized O(1) time.

C++ Code — Vector

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    
    v.push_back(6); // Add 6 to the end
    
    cout << "Size: " << v.size() << endl; // 6
    cout << "Index 2: " << v[2] << endl;   // 3
    
    v.pop_back(); // Remove last element
    
    // Safe index access with bounds checking
    try {
        cout << "At index 10: " << v.at(10) << endl;
    } catch (const out_of_range& e) {
        cout << "Index is out of range!" << endl;
    }
    return 0;
}

Pair

All operations: O(1)

Two-Tuple Luggage Tags

Imagine a pair of luggage tags stapled together. One tag has the customer's ID and the second tag has their name, allowing you to route them as a single parcel.

A std::pair is a simple container that holds two values of possibly different types.

Core Mechanics:

Fields: Accessed via .first and .second.
Comparisons: Evaluated lexicographically (compares first values; if equal, compares second values). This makes pairs highly useful as keys in sets or maps.

C++ Code — Pair

#include <iostream>
#include <utility>
#include <string>
using namespace std;

int main() {
    pair<int, string> student = {101, "Alice"};
    cout << "ID: " << student.first << ", Name: " << student.second << endl;
    
    // Nested pair
    pair<int, pair<double, double>> point = {1, {4.5, -2.1}};
    cout << "X: " << point.second.first << ", Y: " << point.second.second << endl;
    return 0;
}

Set and Unordered Set

Set - Insert/Delete/Find: O(log n) | Unordered Set - O(1) average

Ordered Balanced Trees vs Hashed Closets

Imagine sorting document sheets. You can store them in alphabetized filing cabinets (an ordered Set where sheets remain sorted), or check them into a coat room where each coat is assigned a fast hook number (an Unordered Set where lookup is fast but ordering is random).

1. std::set (Ordered Set)

Implemented as a self-balancing binary search tree (typically a Red-Black Tree).
Keys are kept strictly in sorted order.
Insertion, deletion, and lookup take logarithmic O(log n) time.

2. std::unordered_set

Implemented as a hash table.
Keys are stored in arbitrary order.
Insertion, deletion, and lookup run in constant O(1) average time.

C++ Code — Set and Unordered Set

#include <iostream>
#include <set>
#include <unordered_set>
using namespace std;

int main() {
    set<int> sortedSet = {30, 10, 20, 10}; // Duplicates ignored
    
    cout << "Sorted Set: ";
    for (int x : sortedSet) cout << x << " "; // 10 20 30
    cout << endl;
    
    unordered_set<int> hashSet = {30, 10, 20};
    if (hashSet.count(10)) {
        cout << "10 is present in the hash set!" << endl;
    }
    return 0;
}

Map and Unordered Map

Map - O(log n) | Unordered Map - O(1) average

Key-Value Dictionaries

Imagine looking up word definitions. You can open an alphabetical dictionary (an ordered Map sorted by key), or retrieve items from lockers using unique combinations (an Unordered Map using hash lookups).

1. std::map (Ordered Map)

Stores key-value pairs sorted by key.
Logarithmic O(log n) time complexity for search, insertion, and deletion.

2. std::unordered_map

Stores key-value pairs using a hash table.
Constant O(1) average time complexity.

C++ Code — Map and Unordered Map

#include <iostream>
#include <map>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    map<string, int> ages;
    ages["Alice"] = 25;
    ages["Bob"] = 30;
    
    cout << "Ages (alphabetical):" << endl;
    for (auto& p : ages) {
        cout << p.first << ": " << p.second << endl;
    }
    
    unordered_map<string, string> phoneBook;
    phoneBook["Emergency"] = "911";
    cout << "Emergency contact: " << phoneBook["Emergency"] << endl;
    return 0;
}

Stack and Queue (STL)

Stack/Queue - All O(1) | Priority Queue - Push/Pop O(log n), Top O(1)

Buffer Pipelines

Containers manage how elements enter and leave your structures:

1. Stack (LIFO)

Think of a stack of heavy plates at a buffet. You add new plates to the top and remove plates from the top.
Last-In, First-Out (LIFO).

2. Queue (FIFO)

Think of a line of people waiting to buy tickets. The first person to join the line is the first person served.
First-In, First-Out (FIFO).

3. Priority Queue (Heap)

Think of an emergency room triage queue. High-severity patients are served first, regardless of their arrival order.
By default, it is configured as a Max-Heap (largest element at the top).

C++ Code — Stack and Queue (STL)

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

int main() {
    stack<int> st;
    st.push(10);
    st.push(20);
    cout << "Stack Top: " << st.top() << endl; // 20
    st.pop();
    
    queue<int> q;
    q.push(10);
    q.push(20);
    cout << "Queue Front: " << q.front() << endl; // 10
    q.pop();
    
    // Min-Heap configuration
    priority_queue<int, vector<int>, greater<int>> minHeap;
    minHeap.push(30);
    minHeap.push(10);
    minHeap.push(20);
    cout << "Min-Heap Top: " << minHeap.top() << endl; // 10
    return 0;
}

Common STL Algorithms

Sort: O(n log n) | Binary Search: O(log n) | Others: O(n)

Swiss Army Knife Functions

Instead of writing manual loops to search, reverse, or aggregate data, you can use generic algorithm templates:

Essential Algorithms:

std::sort(begin, end): Sorts a range in ascending order (O(n log n) hybrid Introsort).
std::binary_search(begin, end, val): Checks if a value exists in a sorted range (O(log n)).
std::accumulate(begin, end, init): Sums all elements in a range.
std::max_element(begin, end): Returns an iterator to the largest element.

C++ Code — Common STL Algorithms

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3};
    
    sort(v.begin(), v.end());
    
    if (binary_search(v.begin(), v.end(), 8)) {
        cout << "8 is in the vector!" << endl;
    }
    
    int sum = accumulate(v.begin(), v.end(), 0);
    cout << "Sum: " << sum << endl; // 28
    return 0;
}

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> v = {5, 2, 8, 1, 9, 3}; // Sort vector in ascending order sort(v.begin(), v.end()); cout << "Sorted: "; for (int x : v) cout << x << " "; // 1 2 3 5 8 9 cout << endl; // Find maximum element auto maxIt = max_element(v.begin(), v.end()); if (maxIt != v.end()) { cout << "Max: " << *maxIt << endl; // 9 } return 0; }

Dynamic Array Resize Slots

Imagine an expanding dining table. As more guests arrive (more items added), the table extends its leaves to fit them, doubling its capacity when fully filled.

A std::vector is a dynamic array container that automatically grows or shrinks in size as elements are inserted or deleted.

Core Mechanics:

Contiguous Memory Layout: Elements are stored in contiguous memory blocks, allowing constant-time random access via indices (O(1)).
Capacity vs Size: size() is the number of active elements, while capacity() is the total allocated slot space. When size == capacity, inserting a new element triggers a relocation to a new, double-sized memory block, running in amortized O(1) time.

#include <iostream> #include <vector> using namespace std; int main() { vector<int> v = {1, 2, 3, 4, 5}; v.push_back(6); // Add 6 to the end cout << "Size: " << v.size() << endl; // 6 cout << "Index 2: " << v[2] << endl; // 3 v.pop_back(); // Remove last element // Safe index access with bounds checking try { cout << "At index 10: " << v.at(10) << endl; } catch (const out_of_range& e) { cout << "Index is out of range!" << endl; } return 0; }

#include <iostream> #include <utility> #include <string> using namespace std; int main() { pair<int, string> student = {101, "Alice"}; cout << "ID: " << student.first << ", Name: " << student.second << endl; // Nested pair pair<int, pair<double, double>> point = {1, {4.5, -2.1}}; cout << "X: " << point.second.first << ", Y: " << point.second.second << endl; return 0; }

#include <iostream> #include <set> #include <unordered_set> using namespace std; int main() { set<int> sortedSet = {30, 10, 20, 10}; // Duplicates ignored cout << "Sorted Set: "; for (int x : sortedSet) cout << x << " "; // 10 20 30 cout << endl; unordered_set<int> hashSet = {30, 10, 20}; if (hashSet.count(10)) { cout << "10 is present in the hash set!" << endl; } return 0; }

#include <iostream> #include <map> #include <unordered_map> #include <string> using namespace std; int main() { map<string, int> ages; ages["Alice"] = 25; ages["Bob"] = 30; cout << "Ages (alphabetical):" << endl; for (auto& p : ages) { cout << p.first << ": " << p.second << endl; } unordered_map<string, string> phoneBook; phoneBook["Emergency"] = "911"; cout << "Emergency contact: " << phoneBook["Emergency"] << endl; return 0; }

#include <iostream> #include <stack> #include <queue> using namespace std; int main() { stack<int> st; st.push(10); st.push(20); cout << "Stack Top: " << st.top() << endl; // 20 st.pop(); queue<int> q; q.push(10); q.push(20); cout << "Queue Front: " << q.front() << endl; // 10 q.pop(); // Min-Heap configuration priority_queue<int, vector<int>, greater<int>> minHeap; minHeap.push(30); minHeap.push(10); minHeap.push(20); cout << "Min-Heap Top: " << minHeap.top() << endl; // 10 return 0; }

#include <iostream> #include <vector> #include <algorithm> #include <numeric> using namespace std; int main() { vector<int> v = {5, 2, 8, 1, 9, 3}; sort(v.begin(), v.end()); if (binary_search(v.begin(), v.end(), 8)) { cout << "8 is in the vector!" << endl; } int sum = accumulate(v.begin(), v.end(), 0); cout << "Sum: " << sum << endl; // 28 return 0; }