C++ Standard Template Library (STL) - A Professional Guide

1. Standard Template Library (STL)

Q: What is the STL in C++?

The Standard Template Library (STL) is a powerful set of C++ template-based libraries providing generic containers, algorithms, iterators, and function objects. It enables efficient, reusable, and type-safe implementations of data structures and algorithms, making it a cornerstone for DSA tasks like sorting, searching, and graph processing.

Q: What are the main components of the STL?

• Containers: Data structures to store and manage data (e.g., vector, list, map).
• Algorithms: Generic functions for operations like sorting, searching, and transforming (e.g., std::sort, std::find).
• Iterators: Objects that traverse containers, acting as a bridge between containers and algorithms.
• Functors (Function Objects): Classes that define operator() for use in algorithms (e.g., comparators).

Q: What are the types of STL containers?

• Sequence Containers: Store elements in a linear order.
• vector: Dynamic array with fast random access.
• list: Doubly-linked list with fast insertion/deletion.
• deque: Double-ended queue with fast insertion at both ends.
• array (C++11): Fixed-size array with STL integration.
• Associative Containers: Store key-value pairs or sorted elements.
• set: Sorted unique elements.
• map: Sorted key-value pairs (unique keys).
• multiset, multimap: Allow duplicate elements/keys.
• Unordered Associative Containers (C++11): Hash-based, unsorted.
• unordered_set, unordered_map, unordered_multiset, unordered_multimap.
• Container Adapters: Modified interfaces for specific use cases.
• stack: LIFO structure.
• queue: FIFO structure.
• priority_queue: Priority-based queue.

Q: What are iterators and their types in the STL?

Iterators are objects that traverse containers, providing a uniform way to access elements. Types include:

• Input Iterator: Read-only, forward movement (e.g., istream_iterator).
• Output Iterator: Write-only, forward movement (e.g., ostream_iterator).
• Forward Iterator: Read/write, forward movement (e.g., forward_list).
• Bidirectional Iterator: Read/write, forward/backward movement (e.g., list, map).
• Random Access Iterator: Read/write, random access (e.g., vector, array).

Q: What are some common STL algorithms?

From <algorithm>:

• Sorting: std::sort, std::stable_sort.
• Searching: std::find, std::binary_search.
• Manipulation: std::copy, std::reverse, std::remove.
• Numeric: std::accumulate, std::min_element, std::max_element.

Q: Can you give an example of using STL containers and algorithms?

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

int main() {
    vector<int> vec = {5, 2, 9, 1, 5, 6};

    cout << "Original vector: ";
    for (int x : vec) cout << x << " ";
    cout << endl;

    sort(vec.begin(), vec.end());
    cout << "Sorted vector: ";
    for (int x : vec) cout << x << " ";
    cout << endl;

    auto it = find(vec.begin(), vec.end(), 5);
    if (it != vec.end())
        cout << "Found 5 at position: " << distance(vec.begin(), it) << endl;

    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    cout << "After removing duplicates: ";
    for (int x : vec) cout << x << " ";
    cout << endl;

    return 0;
}

Output:

Original vector: 5 2 9 1 5 6
Sorted vector: 1 2 5 5 6 9
Found 5 at position: 2
After removing duplicates: 1 2 5 6 9

Q: How is the STL used in DSA?

• Containers: Efficiently store data for algorithms (e.g., vector for arrays, map for key-value lookups).
• Algorithms: Implement common DSA operations like sorting (std::sort), searching (std::binary_search), or graph traversal utilities.
• Iterators: Enable generic traversal of data structures, decoupling algorithms from container types.
• Performance: STL provides optimized, tested implementations, reducing development time for competitive programming and DSA.

Q: Can you give a DSA-related example using the STL?

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

class Graph {
private:
    int vertices;
    vector<vector<int>> adjList;
public:
    Graph(int v) : vertices(v), adjList(v) {}

    void addEdge(int src, int dest) {
        adjList[src].push_back(dest);
        adjList[dest].push_back(src);
    }

    void bfs(int start) {
        vector<bool> visited(vertices, false);
        queue<int> q;
        visited[start] = true;
        q.push(start);
        cout << "BFS Traversal: ";
        while (!q.empty()) {
            int vertex = q.front(); q.pop();
            cout << vertex << " ";
            for (int neighbor : adjList[vertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        cout << endl;
    }

    bool hasEdge(int src, int dest) {
        auto it = find(adjList[src].begin(), adjList[src].end(), dest);
        return it != adjList[src].end();
    }
};

int main() {
    Graph g(4);
    g.addEdge(0, 1); g.addEdge(0, 2);
    g.addEdge(1, 2); g.addEdge(2, 3);
    g.bfs(0);
    cout << "Edge (1,2): " << (g.hasEdge(1,2) ? "Yes" : "No") << endl;
    cout << "Edge (1,3): " << (g.hasEdge(1,3) ? "Yes" : "No") << endl;
    return 0;
}

Output:

BFS Traversal: 0 1 2 3
Edge (1,2): Yes
Edge (1,3): No

Q: How does the STL differ from C?

• C++ STL: Provides template-based containers, algorithms, and iterators for generic, type-safe programming.
• C: Lacks STL; data structures and algorithms must be implemented manually.
• C++ Advantage: STL simplifies DSA with optimized, reusable components, reducing coding errors and development time.

Q: What are common mistakes with the STL?

• Invalid iterator usage (e.g., dereferencing end() or invalidated iterators after container modification).
• Forgetting to include necessary headers (e.g., <vector>, <algorithm>).
• Using operator[] instead of at() for bounds checking in vector or map.
• Misusing container adapters (e.g., expecting random access in stack).
• Not handling exceptions thrown by STL (e.g., std::out_of_range from vector::at).

Q: What are best practices for using the STL in C++?

• Use appropriate containers for the task (e.g., vector for random access, list for frequent insertions).
• Leverage STL algorithms over manual loops for clarity and efficiency.
• Use iterators correctly and avoid invalidation (e.g., after erase in vector).
• Prefer auto for iterator declarations to simplify code (C++11).
• Use const and references to avoid copying (e.g., const vector<int>&).
• Handle STL exceptions with try-catch blocks for robustness.
• Use std:: explicitly or specific using declarations instead of using namespace std;.

Q: How do functors work in the STL?

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

struct CompareDescending {
    bool operator()(int a, int b) const {
        return a > b;
    }
};

int main() {
    vector<int> vec = {5, 2, 9, 1, 5, 6};
    sort(vec.begin(), vec.end(), CompareDescending());
    cout << "Sorted (descending): ";
    for (int x : vec) cout << x << " ";
    cout << endl;
    return 0;
}

Output:

Sorted (descending): 9 6 5 5 2 1