C++ Standard Library Overview

Vector — Dynamic Resizing and Operations — Watch how a vector grows dynamically by doubling its capacity when full, and how push_back, access, and pop_back operations work.

#include <vector>
#include <deque>
#include <list>
#include <array>
#include <iostream>
using namespace std;

int main() {
    // --- Vector ---
    vector<int> vec = {1, 2, 3};
    vec.push_back(4);          // Add to end: {1, 2, 3, 4}
    vec.pop_back();            // Remove from end: {1, 2, 3}
    cout << vec[1] << endl;    // Random access: 2
    cout << "Vector size: " << vec.size() << endl; // 3

    // --- Deque ---
    deque<int> dq = {2, 3, 4};
    dq.push_front(1);          // Add to front: {1, 2, 3, 4}
    dq.push_back(5);           // Add to end: {1, 2, 3, 4, 5}
    dq.pop_front();            // Remove from front: {2, 3, 4, 5}
    cout << dq[0] << endl;     // Random access: 2

    // --- List ---
    list<int> lst = {1, 2, 3};
    lst.push_front(0);         // {0, 1, 2, 3}
    auto it = lst.begin();
    advance(it, 2);            // Move iterator to index 2
    lst.insert(it, 99);        // Insert 99 before index 2: {0, 1, 99, 2, 3}
    lst.remove(99);            // Remove all 99s: {0, 1, 2, 3}

    // --- Array (fixed-size) ---
    array<int, 4> arr = {10, 20, 30, 40};
    cout << arr[2] << endl;    // 30
    cout << "Array size: " << arr.size() << endl; // 4

    return 0;
}

# Python equivalents of C++ sequence containers

# --- list (equivalent to C++ vector) ---
vec = [1, 2, 3]
vec.append(4)          # Add to end: [1, 2, 3, 4]
vec.pop()              # Remove from end: [1, 2, 3]
print(vec[1])          # Random access: 2
print(f"List size: {len(vec)}")  # 3

# --- collections.deque (equivalent to C++ deque) ---
from collections import deque
dq = deque([2, 3, 4])
dq.appendleft(1)       # Add to front: deque([1, 2, 3, 4])
dq.append(5)           # Add to end: deque([1, 2, 3, 4, 5])
dq.popleft()           # Remove from front: deque([2, 3, 4, 5])
print(dq[0])           # Random access: 2

# Note: Python's list is a dynamic array (like C++ vector)
# Python has no built-in doubly linked list equivalent to C++ list
# Python has no fixed-size array equivalent to C++ array
# (but you can use tuple for immutable fixed-size sequences)

import java.util.*;

public class SequenceContainers {
    public static void main(String[] args) {
        // --- ArrayList (equivalent to C++ vector) ---
        ArrayList<Integer> vec = new ArrayList<>(Arrays.asList(1, 2, 3));
        vec.add(4);                    // Add to end: [1, 2, 3, 4]
        vec.remove(vec.size() - 1);    // Remove from end: [1, 2, 3]
        System.out.println(vec.get(1)); // Random access: 2
        System.out.println("Size: " + vec.size()); // 3

        // --- ArrayDeque (equivalent to C++ deque) ---
        ArrayDeque<Integer> dq = new ArrayDeque<>(Arrays.asList(2, 3, 4));
        dq.addFirst(1);    // Add to front: [1, 2, 3, 4]
        dq.addLast(5);     // Add to end: [1, 2, 3, 4, 5]
        dq.removeFirst();  // Remove from front: [2, 3, 4, 5]
        System.out.println(dq.peek()); // Front element: 2

        // --- LinkedList (equivalent to C++ list) ---
        LinkedList<Integer> lst = new LinkedList<>(Arrays.asList(1, 2, 3));
        lst.addFirst(0);   // {0, 1, 2, 3}
        lst.add(2, 99);    // Insert 99 at index 2: {0, 1, 99, 2, 3}
        lst.remove(Integer.valueOf(99)); // Remove first 99: {0, 1, 2, 3}

        // --- Array (fixed-size) ---
        int[] arr = {10, 20, 30, 40};
        System.out.println(arr[2]);     // 30
        System.out.println("Array length: " + arr.length); // 4
    }
}

Building a Frequency Map — Character Counting — Watch how an unordered_map builds up as we scan each character of 'hello', inserting new keys or incrementing existing counts.

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

int main() {
    // --- Set (sorted, unique) ---
    set<int> s = {3, 1, 4, 1, 5};  // Duplicates removed: {1, 3, 4, 5}
    s.insert(2);                    // {1, 2, 3, 4, 5}
    cout << "Contains 3: " << s.count(3) << endl;  // 1 (true)
    s.erase(4);                     // {1, 2, 3, 5}

    // Sorted iteration
    for (int x : s) cout << x << " ";  // 1 2 3 5
    cout << endl;

    // Range query: elements >= 2 and < 5
    auto lo = s.lower_bound(2);
    auto hi = s.lower_bound(5);
    for (auto it = lo; it != hi; ++it)
        cout << *it << " ";  // 2 3
    cout << endl;

    // --- Map (sorted key-value) ---
    map<string, int> scores;
    scores["Alice"] = 95;
    scores["Bob"] = 87;
    scores["Charlie"] = 92;

    if (scores.find("Bob") != scores.end())
        cout << "Bob's score: " << scores["Bob"] << endl;  // 87

    // --- Unordered Map (hash-based, fastest lookup) ---
    unordered_map<char, int> freq;
    string word = "hello";
    for (char c : word) {
        freq[c]++;  // Auto-initializes to 0, then increments
    }
    cout << "'l' appears " << freq['l'] << " times" << endl;  // 2

    return 0;
}

# Python equivalents of C++ associative containers

# --- set (equivalent to C++ unordered_set — NOT sorted in Python) ---
s = {3, 1, 4, 1, 5}  # Duplicates removed: {1, 3, 4, 5}
s.add(2)               # {1, 2, 3, 4, 5}
print(3 in s)          # True (O(1) average)
s.discard(4)           # {1, 2, 3, 5}

# --- dict (equivalent to C++ unordered_map) ---
scores = {}
scores["Alice"] = 95
scores["Bob"] = 87
scores["Charlie"] = 92

if "Bob" in scores:
    print(f"Bob's score: {scores['Bob']}")  # 87

# --- Counter (frequency counting shortcut) ---
from collections import Counter
freq = Counter("hello")
print(f"'l' appears {freq['l']} times")  # 2

# --- SortedDict (equivalent to C++ map — requires sortedcontainers) ---
# from sortedcontainers import SortedDict
# Python has no built-in sorted map; use sortedcontainers library
# or sort dict keys manually when needed

import java.util.*;

public class AssociativeContainers {
    public static void main(String[] args) {
        // --- TreeSet (equivalent to C++ set — sorted, unique) ---
        TreeSet<Integer> s = new TreeSet<>(Arrays.asList(3, 1, 4, 1, 5));
        s.add(2);                           // {1, 2, 3, 4, 5}
        System.out.println(s.contains(3));   // true (O(log n))
        s.remove(4);                         // {1, 2, 3, 5}

        // Range query: elements >= 2 and < 5
        System.out.println(s.subSet(2, 5));  // [2, 3]

        // --- TreeMap (equivalent to C++ map — sorted key-value) ---
        TreeMap<String, Integer> scores = new TreeMap<>();
        scores.put("Alice", 95);
        scores.put("Bob", 87);
        scores.put("Charlie", 92);

        if (scores.containsKey("Bob"))
            System.out.println("Bob's score: " + scores.get("Bob")); // 87

        // --- HashMap (equivalent to C++ unordered_map) ---
        HashMap<Character, Integer> freq = new HashMap<>();
        String word = "hello";
        for (char c : word.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        System.out.println("'l' appears " + freq.get('l') + " times"); // 2
    }
}

Stack LIFO — Push and Pop Operations — Watch how a stack enforces Last-In-First-Out order: elements are always added and removed from the top.

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

int main() {
    // --- Stack (LIFO) ---
    stack<int> st;
    st.push(10);
    st.push(20);
    st.push(30);
    cout << "Stack top: " << st.top() << endl;  // 30
    st.pop();  // Removes 30
    cout << "Stack top after pop: " << st.top() << endl;  // 20

    // --- Queue (FIFO) ---
    queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);
    cout << "Queue front: " << q.front() << endl;  // 10
    q.pop();  // Removes 10 (front)
    cout << "Queue front after pop: " << q.front() << endl;  // 20

    // --- Priority Queue (Max-Heap by default) ---
    priority_queue<int> pq;
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);
    cout << "PQ top (max): " << pq.top() << endl;  // 50
    pq.pop();  // Removes 50
    cout << "PQ top after pop: " << pq.top() << endl;  // 30

    // --- Min-Heap (using greater<int>) ---
    priority_queue<int, vector<int>, greater<int>> minPQ;
    minPQ.push(30);
    minPQ.push(10);
    minPQ.push(50);
    cout << "Min-PQ top: " << minPQ.top() << endl;  // 10

    return 0;
}

# Python equivalents of C++ container adaptors

# --- Stack (using list) ---
stack = []
stack.append(10)   # push
stack.append(20)
stack.append(30)
print(f"Stack top: {stack[-1]}")   # 30 (peek)
stack.pop()                         # Removes 30
print(f"Stack top after pop: {stack[-1]}")  # 20

# --- Queue (using collections.deque) ---
from collections import deque
q = deque()
q.append(10)     # enqueue
q.append(20)
q.append(30)
print(f"Queue front: {q[0]}")    # 10
q.popleft()                       # dequeue: removes 10
print(f"Queue front after pop: {q[0]}")  # 20

# --- Priority Queue (Min-Heap using heapq) ---
import heapq
pq = []
heapq.heappush(pq, 30)
heapq.heappush(pq, 10)
heapq.heappush(pq, 50)
heapq.heappush(pq, 20)
print(f"PQ top (min): {pq[0]}")   # 10 (Python heapq is min-heap)
heapq.heappop(pq)                  # Removes 10
print(f"PQ top after pop: {pq[0]}")  # 20

# For max-heap, negate values:
max_pq = []
heapq.heappush(max_pq, -30)
heapq.heappush(max_pq, -10)
heapq.heappush(max_pq, -50)
print(f"Max-PQ top: {-max_pq[0]}")  # 50

import java.util.*;

public class ContainerAdaptors {
    public static void main(String[] args) {
        // --- Stack (LIFO) ---
        Stack<Integer> st = new Stack<>();
        st.push(10);
        st.push(20);
        st.push(30);
        System.out.println("Stack top: " + st.peek());  // 30
        st.pop();  // Removes 30
        System.out.println("Stack top after pop: " + st.peek());  // 20

        // --- Queue (FIFO) ---
        Queue<Integer> q = new LinkedList<>();
        q.add(10);
        q.add(20);
        q.add(30);
        System.out.println("Queue front: " + q.peek());  // 10
        q.poll();  // Removes 10
        System.out.println("Queue front after pop: " + q.peek());  // 20

        // --- PriorityQueue (Min-Heap by default in Java) ---
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(30);
        pq.add(10);
        pq.add(50);
        pq.add(20);
        System.out.println("PQ top (min): " + pq.peek());  // 10
        pq.poll();  // Removes 10
        System.out.println("PQ top after poll: " + pq.peek());  // 20

        // --- Max-Heap ---
        PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
        maxPQ.add(30);
        maxPQ.add(10);
        maxPQ.add(50);
        System.out.println("Max-PQ top: " + maxPQ.peek());  // 50
    }
}

Sort + Lower Bound — Sorting and Binary Search — Watch the array get sorted, then see how lower_bound performs binary search to find the position of a target value in the sorted array.

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

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 5, 2};

    // --- Sorting ---
    sort(v.begin(), v.end());  // {1, 2, 2, 3, 5, 5, 8, 9}

    // --- Binary Search ---
    bool found = binary_search(v.begin(), v.end(), 5);  // true
    cout << "Found 5: " << found << endl;

    // --- Lower/Upper Bound ---
    auto lo = lower_bound(v.begin(), v.end(), 5);  // iterator to first 5
    auto hi = upper_bound(v.begin(), v.end(), 5);  // iterator past last 5
    cout << "Number of 5s: " << (hi - lo) << endl;  // 2
    cout << "First 5 at index: " << (lo - v.begin()) << endl;  // 4

    // --- Counting ---
    int cnt = count(v.begin(), v.end(), 2);  // 2
    cout << "Count of 2: " << cnt << endl;

    // --- Accumulate (sum) ---
    int total = accumulate(v.begin(), v.end(), 0);  // 35
    cout << "Sum: " << total << endl;

    // --- Min/Max ---
    auto minIt = min_element(v.begin(), v.end());
    auto maxIt = max_element(v.begin(), v.end());
    cout << "Min: " << *minIt << ", Max: " << *maxIt << endl;  // 1, 9

    // --- Reverse ---
    reverse(v.begin(), v.end());  // {9, 8, 5, 5, 3, 2, 2, 1}

    // --- Unique (remove consecutive duplicates) ---
    sort(v.begin(), v.end());          // Must sort first: {1, 2, 2, 3, 5, 5, 8, 9}
    auto last = unique(v.begin(), v.end());
    v.erase(last, v.end());            // {1, 2, 3, 5, 8, 9}
    cout << "After unique: ";
    for (int x : v) cout << x << " ";
    cout << endl;

    // --- Custom sort (descending) ---
    sort(v.begin(), v.end(), greater<int>());  // {9, 8, 5, 3, 2, 1}

    // --- Sort by custom comparator ---
    sort(v.begin(), v.end(), [](int a, int b) {
        return abs(a - 5) < abs(b - 5);  // Sort by distance from 5
    });

    return 0;
}

# Python equivalents of C++ STL algorithms
from bisect import bisect_left, bisect_right

v = [5, 2, 8, 1, 9, 3, 5, 2]

# --- Sorting ---
v.sort()  # [1, 2, 2, 3, 5, 5, 8, 9]

# --- Binary Search (using bisect on sorted list) ---
idx = bisect_left(v, 5)
found = idx < len(v) and v[idx] == 5  # True
print(f"Found 5: {found}")

# --- Lower/Upper Bound ---
lo = bisect_left(v, 5)   # Index of first 5: 4
hi = bisect_right(v, 5)  # Index past last 5: 6
print(f"Number of 5s: {hi - lo}")  # 2

# --- Counting ---
cnt = v.count(2)  # 2
print(f"Count of 2: {cnt}")

# --- Sum ---
total = sum(v)  # 35
print(f"Sum: {total}")

# --- Min/Max ---
print(f"Min: {min(v)}, Max: {max(v)}")  # 1, 9

# --- Reverse ---
v.reverse()  # [9, 8, 5, 5, 3, 2, 2, 1]

# --- Unique (remove duplicates) ---
v = sorted(set(v))  # [1, 2, 3, 5, 8, 9]

# --- Custom sort (descending) ---
v.sort(reverse=True)  # [9, 8, 5, 3, 2, 1]

# --- Sort by custom key ---
v.sort(key=lambda x: abs(x - 5))  # Sort by distance from 5

import java.util.*;
import java.util.stream.*;

public class STLAlgorithms {
    public static void main(String[] args) {
        List<Integer> v = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9, 3, 5, 2));

        // --- Sorting ---
        Collections.sort(v);  // [1, 2, 2, 3, 5, 5, 8, 9]

        // --- Binary Search ---
        int idx = Collections.binarySearch(v, 5);  // Returns index (4 or 5)
        System.out.println("Found 5 at index: " + idx);

        // --- Counting ---
        long cnt = v.stream().filter(x -> x == 2).count();  // 2
        System.out.println("Count of 2: " + cnt);

        // --- Sum ---
        int total = v.stream().mapToInt(Integer::intValue).sum();  // 35
        System.out.println("Sum: " + total);

        // --- Min/Max ---
        int minVal = Collections.min(v);  // 1
        int maxVal = Collections.max(v);  // 9
        System.out.println("Min: " + minVal + ", Max: " + maxVal);

        // --- Reverse ---
        Collections.reverse(v);  // [9, 8, 5, 5, 3, 2, 2, 1]

        // --- Unique (remove duplicates using Set) ---
        List<Integer> unique = new ArrayList<>(new TreeSet<>(v));
        System.out.println("Unique sorted: " + unique);  // [1, 2, 3, 5, 8, 9]

        // --- Custom sort (descending) ---
        v.sort(Collections.reverseOrder());  // [9, 8, 5, 5, 3, 2, 2, 1]

        // --- Sort by custom comparator ---
        v.sort(Comparator.comparingInt(x -> Math.abs(x - 5)));  // By distance from 5
    }
}