STL, Templates, OOAD & C++ Miscellaneous: STL Containers, Algorithms, Iterators, Templates, OOAD Basics

Standard Template Library (STL): The Swiss Army Knife of C++

STL is a powerful library in C++ that provides reusable, efficient components for common programming tasks. It consists of three main parts:

1. Containers (data structures like vector, list, map).
2. Iterators (generalized pointers to traverse containers).
3. Algorithms (functions like sort, find, copy).

Why Use STL?

• Reusability: Pre-built, tested components save time.
• Efficiency: Optimized implementations (e.g., std::vector uses dynamic arrays).
• Consistency: Uniform interface across containers.

1. STL Containers: Data Structures Made Easy

Containers store and organize data. Here are the key ones:

A. Sequence Containers (Ordered Elements)

B. Associative Containers (Key-Value Pairs)

C. Container Adapters (Specialized Interfaces)

Visual: How a std::vector Grows

When a vector runs out of space, it reallocates and copies elements. Here’s what happens during insertion:

Trace of push_back(50) in a vector of capacity 4:

Code Example:

#include <vector>
int main() {
    std::vector<int> vec = {10, 20, 30, 40};
    vec.push_back(50); // Triggers reallocation
    return 0;
}

2. STL Iterators: Generalized Pointers

Iterators allow traversal of containers without knowing their internal structure. Types:

• Input iterator (read-only, single pass): istream_iterator
• Output iterator (write-only): ostream_iterator
• Forward iterator (multiple reads): list::iterator
• Bidirectional iterator: list::reverse_iterator
• Random-access iterator: vector::iterator (like pointers)

Example: Using std::find with iterators

#include <vector>
#include <algorithm>
int main() {
    std::vector<int> nums = {10, 20, 30, 40};
    auto it = std::find(nums.begin(), nums.end(), 30);
    if (it != nums.end()) {
        std::cout << "Found: " << *it; // Output: 30
    }
    return 0;
}

Trace:

3. STL Algorithms: Reusable Functions

Algorithms operate on containers via iterators. Examples:

• Non-modifying: std::find, std::count
• Modifying: std::sort, std::copy
• Numeric: std::accumulate, std::inner_product

Example: Sorting a vector

#include <vector>
#include <algorithm>
int main() {
    std::vector<int> vec = {30, 10, 50, 20};
    std::sort(vec.begin(), vec.end());
    // vec is now [10, 20, 30, 50]
    return 0;
}

Trace of std::sort (simplified):

In the Real World

1. eSewa (Nepal):

   • Uses std::map to store user profiles (ID → User object) for fast lookups.
   • Example: When you pay a bill, eSewa checks your balance in a map in O(log n) time.

2. Khalti’s Transaction Queue:

   • Uses std::queue to manage pending transactions (FIFO ensures fairness).
   • Example: If 100 users request a transfer simultaneously, Khalti processes them in order.

3. Daraz’s Search Algorithm:

   • Uses std::multimap to store product categories (multiple products per category).
   • Example: Searching for "shoes" returns all entries under the "Footwear" category.

4. Ncell’s Call Routing:

   • Uses std::priority_queue to prioritize emergency calls (911) over regular calls.

4. Generic Programming with Templates

Templates allow writing type-agnostic code. Two types:

• Function templates: Generic functions (e.g., std::max).
• Class templates: Generic containers (e.g., std::vector<T>).

How Templates Work

template <typename T>
T max(T a, T b) {
    return (a > b) ? a : b;
}

Trace for max(3.5, 2.1):

Example: std::vector Template

std::vector<std::string> names = {"Alice", "Bob"};
std::vector<int> scores = {90, 85};

Here, T is std::string or int depending on usage.

Advantages of Templates

5. Object-Oriented Analysis and Design (OOAD)

OOAD is the process of designing systems using OOP principles before coding. Key steps:

1. Requirements Analysis: Identify actors and use cases.
2. System Design: Define classes, relationships (inheritance, composition).
3. Implementation: Write code based on the design.

Example: OOAD for a Bank ATM System

Use Case Diagram:

flowchart TD
    A["Customer"] -->|"Withdraw"| B["ATM"]
    A -->|"Check Balance"| B
    A -->|"Transfer"| B
    B -->|"Process"| C["Bank Database"]

Class Diagram:

classDiagram
    class Account {
        +String accountNumber
        +double balance
        +withdraw(amount: double): void
        +deposit(amount: double): void
        +getBalance(): double
    }
    class ATM {
        +processTransaction(customer: Customer, amount: double): bool
        +displayMenu()
    }
    class Customer {
        +String name
        +String id
        +Account account
        +String pin
    }
    Customer "1" --> "1" Account : owns
    ATM --> Customer : interacts
    ATM --> Account : accesses
    note for ATM "Methods:
    - processTransaction()
    - displayMenu()
    - validatePin()"

6. Miscellaneous Topics

A. this Pointer

• Points to the current object’s address.
• Used to resolve name conflicts (e.g., member variable vs. parameter).

Example:

class Person {
public:
    void setAge(int age) {
        this->age = age; // 'this->age' refers to member variable
    }
private:
    int age;
};

B. Exception Handling

C++ uses try, catch, and throw to handle errors gracefully.

Example: Divide by Zero

#include <stdexcept>
int main() {
    int a = 10, b = 0;
    try {
        if (b == 0) throw std::runtime_error("Division by zero!");
        int c = a / b;
    }
    catch (const std::exception& e) {
        std::cerr << "Error: " << e.what();
    }
    return 0;
}

Trace:

Exam Tip

1. STL Questions:

   • Know the time complexity of operations (e.g., map::insert is O(log n)).
   • Differentiate between sequence (vector, list) and associative (map, set) containers.
   • Common pitfalls:
     • Forgetting to #include <vector> or <algorithm>.
     • Using == to compare iterators (use it1 == it2 instead of *it1 == *it2).

2. Templates:

   • Explain the difference between function templates and class templates.
   • Common exam question: Write a template function to swap two variables.

3. OOAD:

   • Draw use case diagrams or class diagrams for given scenarios (e.g., library management system).
   • Key terms: Inheritance, polymorphism, encapsulation.

4. Miscellaneous:

   • For this pointer: Explain its use in constructor chaining.
   • For exceptions: Know the hierarchy (std::exception → std::runtime_error).

Practice Questions

1. Write a program to merge two std::vector<int> into one using std::merge.
2. Explain how std::priority_queue implements a max-heap. Draw its state after inserting {3, 1, 4, 2}.
3. Design an OOAD for a hospital management system (classes: Doctor, Patient, Appointment).
4. Write a template function to find the minimum of three values of any type.