Standard Template Library (STL)

Hey! Welcome back. Today, we’re unlocking the ultimate superpower of C++: the Standard Template Library (STL).

If you’ve ever spent hours writing custom code for a resizable array, a doubly-linked list, or a complex sorting algorithm, you’ll love the STL. It’s C++‘s built-in toolbox of highly optimized data structures and algorithms, allowing you to build clean, efficient programs without reinventing the wheel.

---

What is the STL?

The Standard Template Library (STL) consists of four primary components:

1. Containers: Objects that store and manage collections of data (e.g., arrays, lists, maps).
2. Algorithms: Out-of-the-box functions for operating on collections (e.g., sorting, searching, reversing).
3. Iterators: Pointer-like objects that bridge containers and algorithms, allowing us to traverse elements.
4. Functors (Function Objects): Objects that behave like functions, letting us customize algorithm behaviors.

graph TD
    STL[STL Core Components]
    STL --> Containers[Containers <br/> 'Where data lives']
    STL --> Iterators[Iterators <br/> 'The bridges/pointers']
    STL --> Algorithms[Algorithms <br/> 'How data is manipulated']
    
    Containers --> Sequence[Sequence: vector, list, deque, stack, queue]
    Containers --> Associative[Associative: set, map, unordered_set, unordered_map]

---

Sequence Containers

Sequence containers store elements sequentially in a linear arrangement.

graph TD
    subgraph Memory Representation
        direction LR
        subgraph Vector Contiguous Slots
            v0[Idx 0: Val 10 <br/> Addr: 0x10] --- v1[Idx 1: Val 20 <br/> Addr: 0x14] --- v2[Idx 2: Val 30 <br/> Addr: 0x18]
        end
        subgraph List Doubly-Linked Nodes
            l0[Val 10 <br/> Addr: 0x5a] <--> l1[Val 20 <br/> Addr: 0xa8] <--> l2[Val 30 <br/> Addr: 0xf2]
        end
    end

1. Vector (Dynamic Array)

A vector is a dynamic array. It stores elements in contiguous memory locations, meaning elements are right next to each other in RAM. If it runs out of space, it automatically reallocates a larger block of memory and moves its elements.

• Pros: Random access is super fast ($O(1)$) using the [] operator; adding elements to the end (push_back) is fast ($O(1)$ amortized).
• Cons: Inserting or removing elements in the middle is slow ($O(N)$) because it requires shifting all subsequent elements.

Example:

#include <iostream>
#include <vector>

int main() {
    // Declaring and initializing a vector
    std::vector<int> v = {10, 20, 30};

    // Adding elements
    v.push_back(40);
    v.push_back(50);

    std::cout << "First Element: " << v.front() << std::endl;
    std::cout << "Last Element: " << v.back() << std::endl;
    std::cout << "Vector Size: " << v.size() << std::endl;

    // Modifying elements and reading via index
    v[1] = 99;
    std::cout << "Element at index 1: " << v[1] << std::endl;

    // Removing the last element
    v.pop_back();

    // Traversing a vector
    std::cout << "All elements: ";
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Clearing all elements
    v.clear();
    std::cout << "Size after clear: " << v.size() << std::endl;

    return 0;
}

Output:

First Element: 10
Last Element: 50
Vector Size: 5
Element at index 1: 99
All elements: 10 99 30 40 
Size after clear: 0

---

2. List (Doubly-Linked List)

A list stores elements in non-contiguous memory locations. Each element (node) contains a value and pointers to the previous and next nodes.

• Pros: Constant time ($O(1)$) insertion and deletion at any position once you have an iterator pointing to it.
• Cons: No random access. You cannot do lst[3]. To find the 4th element, you must start at the beginning and walk through the pointers sequentially ($O(N)$ lookup).

Example:

#include <iostream>
#include <list>

int main() {
    std::list<int> lst = {10, 20, 30};

    // Adding elements to both ends
    lst.push_back(40);
    lst.push_front(5);

    std::cout << "First: " << lst.front() << ", Last: " << lst.back() << std::endl;

    // Removing elements
    lst.pop_front(); // Removes 5
    lst.pop_back();  // Removes 40

    // Iterating through a list (must use iterators, no index allowed!)
    std::cout << "List contents: ";
    for (std::list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

First: 5, Last: 40
List contents: 10 20 30 

---

3. Stack & Queue (Container Adaptors)

These are “adaptors” because they wrap around sequence containers (like vectors or deques) and restrict access to fit specific data patterns.

graph TD
    subgraph Stacks: LIFO
        direction BT
        st_push[Push Elements] --> st1[Element 1] --> st2[Element 2] --> st3[Element 3 - TOP]
        st3 --> st_pop[Pop Top Element]
    end
    subgraph Queues: FIFO
        direction LR
        q_push[Push Back] --> q3[Element 3] --> q2[Element 2] --> q1[Element 1 - FRONT] --> q_pop[Pop Front]
    end

• Stack (LIFO - Last In, First Out): Like a stack of plates. You add to the top (push) and remove from the top (pop).
• Queue (FIFO - First In, First Out): Like a line at a store. You enter at the back (push) and exit from the front (pop).

Stack Example:

#include <iostream>
#include <stack>

int main() {
    std::stack<int> stk;

    stk.push(10);
    stk.push(20);
    stk.push(30); // 30 is at the top

    std::cout << "Stack Size: " << stk.size() << std::endl;
    std::cout << "Top Element: " << stk.top() << std::endl;

    stk.pop(); // Removes 30
    std::cout << "New Top: " << stk.top() << std::endl;

    // Printing and emptying stack
    std::cout << "Popping all: ";
    while (!stk.empty()) {
        std::cout << stk.top() << " ";
        stk.pop();
    }
    std::cout << std::endl;

    return 0;
}

Output:

Stack Size: 3
Top Element: 30
New Top: 20
Popping all: 20 10 

Queue Example:

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    q.push(10);
    q.push(20);
    q.push(30); // 10 is at the front, 30 at the back

    std::cout << "Front Element: " << q.front() << std::endl;
    std::cout << "Back Element: " << q.back() << std::endl;

    q.pop(); // Removes 10
    std::cout << "New Front: " << q.front() << std::endl;

    return 0;
}

Output:

Front Element: 10
Back Element: 30
New Front: 20

---

4. Deque (Double-Ended Queue)

A deque (pronounced “deck”) is a double-ended queue. It allows fast insertion and deletion at both the front and the back. Unlike vectors, it doesn’t store all elements in a single contiguous memory block; instead, it uses a map of multiple contiguous chunks.

• Pros: Fast insertion and deletion at both ends ($O(1)$); supports random index access (dq[i]).
• Cons: Slightly slower element access compared to vectors due to internal pointer redirection.

Example:

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq = {20, 30};

    // Adding elements to both sides
    dq.push_front(10);
    dq.push_back(40);

    // Reading elements
    std::cout << "Front: " << dq.front() << ", Back: " << dq.back() << std::endl;
    std::cout << "Index 2: " << dq[2] << std::endl;

    // Removing elements
    dq.pop_front(); // Removes 10
    dq.pop_back();  // Removes 40

    std::cout << "Size: " << dq.size() << std::endl;
    return 0;
}

Output:

Front: 10, Back: 40
Index 2: 30
Size: 2

---

Associative Containers

Associative containers store elements using key-value or sorted properties.

graph TD
    subgraph Sorted Trees vs Hash Tables
        direction TB
        subgraph Set: Red-Black Tree
            root[Root: 20] --> left[Left: 10]
            root --> right[Right: 30]
        end
        subgraph Unordered Set: Hash Buckets
            bucket0[Bucket 0: empty]
            bucket1[Bucket 1: 10]
            bucket2[Bucket 2: 30 -> 20]
        end
    end

1. Set vs. Unordered Set

• Set: Stores unique elements in sorted order (usually using a Red-Black Tree).
  • Lookup, insertion, and deletion are $O(\log N)$.
• Unordered Set: Stores unique elements in no specific order using a Hash Table.
  • Lookup, insertion, and deletion average $O(1)$ (worst-case is $O(N)$ on hash collisions).

Set Example:

#include <iostream>
#include <set>

int main() {
    std::set<int> s;

    // Inserting values (including duplicate 20)
    s.insert(30);
    s.insert(10);
    s.insert(20);
    s.insert(20); // Ignored since set elements must be unique!

    std::cout << "Set size: " << s.size() << std::endl;

    // Searching for elements
    if (s.find(20) != s.end()) {
        std::cout << "Value 20 exists in set." << std::endl;
    }

    // Elements are printed in sorted ascending order automatically!
    std::cout << "Sorted unique elements: ";
    for (int x : s) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    s.erase(10); // Removes 10
    return 0;
}

Output:

Set size: 3
Value 20 exists in set.
Sorted unique elements: 10 20 30 

Unordered Set Example:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> uset = {40, 10, 30, 20};

    // Elements are printed in arbitrary bucket order!
    std::cout << "Unordered unique elements: ";
    for (int x : uset) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

Unordered unique elements: 20 30 10 40 

---

2. Map vs. Unordered Map

Maps store key-value pairs (std::pair<const Key, Value>). Each key is unique.

• Map: Keys are stored in sorted order ($O(\log N)$ operations).
• Unordered Map: Keys are stored in no specific order using a hash table (average $O(1)$ operations).

Map Example:

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> ageMap;

    // Inserting key-value pairs
    ageMap["Aashutosh"] = 21;
    ageMap["Swagata"] = 22;
    ageMap.insert({"Rhea", 20});

    // Accessing elements
    std::cout << "Aashutosh's age: " << ageMap["Aashutosh"] << std::endl;

    // Iterating (keys are sorted alphabetically by default)
    std::cout << "Map contents:" << std::endl;
    for (std::map<std::string, int>::iterator it = ageMap.begin(); it != ageMap.end(); ++it) {
        // it->first is the key, it->second is the value
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    return 0;
}

Output:

Aashutosh's age: 21
Map contents:
Key: Aashutosh, Value: 21
Key: Rhea, Value: 20
Key: Swagata, Value: 22

Unordered Map Example:

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<std::string, int> umap;

    umap["apple"] = 5;
    umap["banana"] = 12;
    umap["cherry"] = 7;

    // Quick lookup
    if (umap.find("banana") != umap.end()) {
        std::cout << "Found banana! Count: " << umap["banana"] << std::endl;
    }

    return 0;
}

Output:

Found banana! Count: 12

---

Iterators: Bridging Containers and Algorithms

An iterator is a pointer-like object used to navigate and traverse containers. They allow us to access container elements uniformly, regardless of whether the container stores data in contiguous slots or scattered nodes.

graph TD
    subgraph Iterator Capabilities
        direction LR
        in[Input Iterator: Read once, forward]
        out[Output Iterator: Write once, forward]
        fwd[Forward Iterator: Read/Write, forward]
        bi[Bidirectional Iterator: Read/Write, forward & backward]
        rand[Random Access: Read/Write, step arbitrary size offsets]
        
        in --> fwd --> bi --> rand
        out --> fwd
    end

Iterator Operations

Let’s look at a comprehensive example showing iterator declaration, dereferencing (*), pointer arithmetic (it + n), and loop comparisons:

Example:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {100, 200, 300, 400, 500};

    // 1. Explicit iterator declaration
    std::vector<int>::iterator it = v.begin();
    std::cout << "First element (*it): " << *it << std::endl;

    // 2. Incrementing iterators
    it++; 
    std::cout << "Second element after it++: " << *it << std::endl;

    // 3. Random access arithmetic (only for vector/deque/array)
    std::vector<int>::iterator it2 = v.begin() + 3; // Jump to index 3
    std::cout << "Element at index 3 (v.begin() + 3): " << *it2 << std::endl;

    // 4. Using 'auto' keyword to avoid typing long container types
    std::cout << "Traversing with iterator: ";
    for (auto it3 = v.begin(); it3 != v.end(); ++it3) {
        std::cout << *it3 << " ";
    }
    std::cout << std::endl;

    // 5. Iterator comparison
    if (v.begin() < v.end()) {
        std::cout << "v.begin() precedes v.end() in contiguous memory." << std::endl;
    }

    return 0;
}

Output:

First element (*it): 100
Second element after it++: 200
Element at index 3 (v.begin() + 3): 400
Traversing with iterator: 100 200 300 400 500 
v.begin() precedes v.end() in contiguous memory.

---

Core Algorithms

STL provides standard utility functions defined inside the <algorithm> and <numeric> headers. They take iterators defining the start and end of ranges.

Let’s look at the 10 most common algorithms in action:

Example:

#include <iostream>
#include <vector>
#include <algorithm> // for sort, find, count, reverse, unique, bounds
#include <numeric>   // for accumulate

int main() {
    std::vector<int> v = {40, 10, 30, 20, 10, 10, 50};

    // 1. count() - count occurrences of 10
    int c = std::count(v.begin(), v.end(), 10);
    std::cout << "Occurrences of 10: " << c << std::endl;

    // 2. find() - look for 30
    auto it = std::find(v.begin(), v.end(), 30);
    if (it != v.end()) {
        std::cout << "Found 30 at index: " << std::distance(v.begin(), it) << std::endl;
    }

    // 3. accumulate() - sum elements
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "Sum of elements: " << sum << std::endl;

    // 4. reverse() - reverse the vector range
    std::reverse(v.begin(), v.end());
    std::cout << "Reversed elements: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;

    // 5. sort() - sort in ascending order
    std::sort(v.begin(), v.end());
    std::cout << "Sorted elements: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;

    // 6. lower_bound() - first element >= 20
    auto lb = std::lower_bound(v.begin(), v.end(), 20);
    std::cout << "Lower bound for 20 (first element >= 20): " << *lb << " at index " << (lb - v.begin()) << std::endl;

    // 7. upper_bound() - first element > 20
    auto ub = std::upper_bound(v.begin(), v.end(), 20);
    std::cout << "Upper bound for 20 (first element > 20): " << *ub << " at index " << (ub - v.begin()) << std::endl;

    // 8. binary_search() - check if 40 exists
    bool exists = std::binary_search(v.begin(), v.end(), 40);
    std::cout << "Does 40 exist in sorted vector? " << (exists ? "Yes" : "No") << std::endl;

    // 9. unique() - moves consecutive duplicates to the end
    // [10, 10, 10, 20, 30, 40, 50] -> moves extra 10s back
    auto newEnd = std::unique(v.begin(), v.end());
    std::cout << "Elements after std::unique: ";
    for (auto iter = v.begin(); iter != newEnd; ++iter) {
        std::cout << *iter << " ";
    }
    std::cout << std::endl;

    // 10. remove() + erase() idiom - completely deletes value 10
    // std::remove moves matching values to the end and returns a new logical end iterator.
    // v.erase() truncates the vector from that logical end to the physical end.
    v.erase(std::remove(v.begin(), v.end(), 10), v.end());
    std::cout << "Elements after removing all 10s: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;

    return 0;
}

Output:

Occurrences of 10: 3
Found 30 at index: 2
Sum of elements: 170
Reversed elements: 50 10 10 20 30 10 40 
Sorted elements: 10 10 10 20 30 40 50 
Lower bound for 20 (first element >= 20): 20 at index 3
Upper bound for 20 (first element > 20): 30 at index 4
Does 40 exist in sorted vector? Yes
Elements after std::unique: 10 20 30 40 50 
Elements after removing all 10s: 20 30 40 50 

---

Level Up: Extra Practice & Interview Questions

Q1. When would you choose std::set over std::unordered_set?

• Choose std::set when you need your elements kept in sorted order, need to print range traversals (e.g., all values between 10 and 50), or need guaranteed worst-case time complexities of $O(\log N)$.
• Choose std::unordered_set when ordering doesn’t matter, and you want maximum performance with an average time complexity of $O(1)$ for operations.

---

Q2. Write a program to find the second largest element in an array using std::set.

Since sets automatically filter out duplicate values and sort elements in ascending order, we can load the array into a set and read the second element from the end.

Code:

#include <iostream>
#include <set>

int main() {
    int arr[] = {10, 50, 40, 50, 20, 30};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::set<int> uniqueSortedElements(arr, arr + n);

    if (uniqueSortedElements.size() < 2) {
        std::cout << "Not enough unique elements!" << std::endl;
    } else {
        // Set contains: {10, 20, 30, 40, 50}
        // Second largest is at rbegin() + 1
        auto it = uniqueSortedElements.rbegin();
        it++; // Move to second element from end
        std::cout << "Second Largest Element: " << *it << std::endl;
    }

    return 0;
}

Output:

Second Largest Element: 40

---

Q3. Write a program to count the frequency of elements in a vector using std::map and print them in ascending order of keys.

Using std::map lets us count and sort keys alphabetically or numerically at the same time.

Code:

#include <iostream>
#include <vector>
#include <map>
#include <string>

int main() {
    std::vector<std::string> fruits = {"apple", "banana", "apple", "cherry", "banana", "apple"};

    std::map<std::string, int> frequencyMap;

    for (const auto& f : fruits) {
        frequencyMap[f]++; // Increments the key count. Inserts key with default value 0 if not present.
    }

    std::cout << "Fruit Frequencies (Ascending Order):" << std::endl;
    for (const auto& pair : frequencyMap) {
        std::cout << pair.first << " : " << pair.second << std::endl;
    }

    return 0;
}

Output:

Fruit Frequencies (Ascending Order):
apple : 3
banana : 2
cherry : 1