C++ STL: Complete Guide to Standard Template Library

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

void demonstrateVector() {
    cout << "=== vector (Dynamic Array) ===" << endl;
    
    // 1. Creation and initialization
    vector<int> v1;                     // Empty vector
    vector<int> v2(5, 10);              // 5 elements, each 10
    vector<int> v3 = {1, 2, 3, 4, 5};   // Initializer list
    vector<int> v4(v3.begin(), v3.end()); // From iterator range
    
    // 2. Basic operations
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    
    cout << "Size: " << v1.size() << endl;
    cout << "Capacity: " << v1.capacity() << endl;
    cout << "Empty? " << (v1.empty() ? "Yes" : "No") << endl;
    
    // 3. Access elements
    cout << "Elements: ";
    for (int i = 0; i < v1.size(); i++) {
        cout << v1[i] << " ";          // No bounds checking
    }
    cout << endl;
    
    cout << "Using at(): ";
    for (int i = 0; i < v1.size(); i++) {
        cout << v1.at(i) << " ";       // With bounds checking
    }
    cout << endl;
    
    cout << "Front: " << v1.front() << endl;
    cout << "Back: " << v1.back() << endl;
    
    // 4. Modifying vector
    v1.pop_back();                     // Remove last element
    v1.insert(v1.begin() + 1, 15);     // Insert at position
    v1.erase(v1.begin() + 1);          // Remove at position
    v1.clear();                        // Remove all elements
    
    // 5. Reserve and shrink
    vector<int> v5;
    v5.reserve(100);                   // Pre-allocate memory
    for (int i = 0; i < 50; i++) {
        v5.push_back(i);
    }
    v5.shrink_to_fit();                // Reduce capacity to size
    
    cout << endl;
}

void demonstrateList() {
    cout << "=== list (Doubly Linked List) ===" << endl;
    
    list<string> names = {"Alice", "Bob", "Charlie"};
    
    // 1. Basic operations
    names.push_back("David");
    names.push_front("Zoe");
    names.pop_back();
    names.pop_front();
    
    // 2. Iteration
    cout << "Names: ";
    for (auto it = names.begin(); it != names.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 3. List-specific operations
    list<int> lst1 = {1, 2, 3, 4, 5};
    list<int> lst2 = {10, 20, 30};
    
    // Splice - move elements from one list to another
    auto it = lst1.begin();
    advance(it, 2);                    // Move iterator to position 2
    lst1.splice(it, lst2);             // Insert lst2 into lst1
    
    cout << "After splice: ";
    for (int num : lst1) {
        cout << num << " ";
    }
    cout << endl;
    
    // Remove elements
    lst1.remove(3);                    // Remove all 3s
    lst1.remove_if([](int n) {         // Remove if condition true
        return n % 2 == 0;             // Remove even numbers
    });
    
    // Sort and unique (list has member functions)
    list<int> lst3 = {5, 3, 1, 4, 2};
    lst3.sort();                       // O(n log n)
    lst3.unique();                     // Remove consecutive duplicates
    
    cout << endl;
}

void demonstrateDeque() {
    cout << "=== deque (Double-Ended Queue) ===" << endl;
    
    deque<int> dq;
    
    // Operations at both ends
    dq.push_back(10);
    dq.push_back(20);
    dq.push_front(5);
    dq.push_front(1);
    
    cout << "Deque: ";
    for (int num : dq) {
        cout << num << " ";
    }
    cout << endl;
    
    cout << "Front: " << dq.front() << endl;
    cout << "Back: " << dq.back() << endl;
    
    dq.pop_front();
    dq.pop_back();
    
    // Random access
    cout << "Element at index 1: " << dq[1] << endl;
    cout << "Element at index 1 (at): " << dq.at(1) << endl;
    
    cout << endl;
}

void demonstrateArray() {
    cout << "=== array (Fixed Size Array) ===" << endl;
    
    array<int, 5> arr = {1, 2, 3, 4, 5};  // Size fixed at compile time
    
    // Similar to vector interface
    cout << "Size: " << arr.size() << endl;
    cout << "Empty? " << (arr.empty() ? "Yes" : "No") << endl;
    cout << "Front: " << arr.front() << endl;
    cout << "Back: " << arr.back() << endl;
    
    // Access elements
    cout << "Elements: ";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    // Fill array
    arr.fill(10);  // All elements become 10
    
    // Swap arrays
    array<int, 5> arr2 = {5, 4, 3, 2, 1};
    arr.swap(arr2);
    
    cout << endl;
}

void demonstrateForwardList() {
    cout << "=== forward_list (Singly Linked List) ===" << endl;
    
    forward_list<int> flist = {1, 2, 3, 4, 5};
    
    // Only forward traversal
    cout << "Forward list: ";
    for (int num : flist) {
        cout << num << " ";
    }
    cout << endl;
    
    // Operations (only front operations are efficient)
    flist.push_front(0);
    flist.pop_front();
    
    // Insert after a position
    auto it = flist.begin();
    advance(it, 2);
    flist.insert_after(it, 99);
    
    // Remove after a position
    flist.erase_after(it);
    
    // Remove elements
    flist.remove(3);                    // Remove all 3s
    flist.remove_if([](int n) {
        return n > 3;                   // Remove numbers > 3
    });
    
    cout << "After modifications: ";
    for (int num : flist) {
        cout << num << " ";
    }
    cout << endl << endl;
}

void performanceComparison() {
    cout << "=== Performance Comparison ===" << endl;
    cout << "Use vector when:" << endl;
    cout << "  - Need random access" << endl;
    cout << "  - Mostly add/remove at end" << endl;
    cout << "  - Memory contiguity important" << endl;
    cout << endl;
    
    cout << "Use list when:" << endl;
    cout << "  - Frequent insertions/deletions in middle" << endl;
    cout << "  - Don't need random access" << endl;
    cout << "  - Need stable iterators (iterators don't invalidate)" << endl;
    cout << endl;
    
    cout << "Use deque when:" << endl;
    cout << "  - Need efficient insertion/removal at both ends" << endl;
    cout << "  - Need random access" << endl;
    cout << "  - Don't need memory contiguity" << endl;
}

int main() {
    demonstrateVector();
    demonstrateList();
    demonstrateDeque();
    demonstrateArray();
    demonstrateForwardList();
    performanceComparison();
    
    return 0;
}

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

void demonstrateSet() {
    cout << "=== set (Sorted Unique Elements) ===" << endl;
    
    // 1. Creation and initialization
    set<int> s1 = {5, 2, 8, 1, 9};
    set<int> s2(s1.begin(), s1.end());
    
    // Elements are automatically sorted
    cout << "Set elements (sorted): ";
    for (int num : s1) {
        cout << num << " ";
    }
    cout << endl;
    
    // 2. Insertion
    auto result = s1.insert(3);        // Returns pair
    if (result.second) {
        cout << "Inserted 3 successfully" << endl;
    }
    
    // Insert duplicate - fails
    result = s1.insert(2);             // 2 already exists
    if (!result.second) {
        cout << "2 already exists in set" << endl;
    }
    
    // 3. Finding elements
    auto it = s1.find(5);
    if (it != s1.end()) {
        cout << "Found 5 in set" << endl;
    }
    
    // count() returns 0 or 1 (since set has unique elements)
    if (s1.count(8) > 0) {
        cout << "8 exists in set" << endl;
    }
    
    // 4. Range operations
    auto lower = s1.lower_bound(3);    // First element >= 3
    auto upper = s1.upper_bound(7);    // First element > 7
    
    cout << "Elements in range [3, 7]: ";
    for (auto it = lower; it != upper; ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 5. Deletion
    s1.erase(2);                       // Erase by value
    it = s1.find(8);
    if (it != s1.end()) {
        s1.erase(it);                  // Erase by iterator
    }
    
    // Erase range
    s1.erase(s1.begin(), s1.find(5));  // Erase elements before 5
    
    cout << "Size after deletions: " << s1.size() << endl;
    cout << endl;
}

void demonstrateMultiset() {
    cout << "=== multiset (Sorted with Duplicates) ===" << endl;
    
    multiset<int> ms = {5, 2, 5, 1, 2, 3};
    
    cout << "Multiset elements: ";
    for (int num : ms) {
        cout << num << " ";
    }
    cout << endl;
    
    // Can insert duplicates
    ms.insert(5);
    ms.insert(5);
    
    cout << "Count of 5: " << ms.count(5) << endl;
    
    // Find all occurrences of a value
    auto range = ms.equal_range(5);    // Returns pair
    cout << "All 5s: ";
    for (auto it = range.first; it != range.second; ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // Erase all occurrences of a value
    ms.erase(5);                       // Erases all 5s
    
    cout << "After erasing all 5s: ";
    for (int num : ms) {
        cout << num << " ";
    }
    cout << endl << endl;
}

void demonstrateMap() {
    cout << "=== map (Sorted Key-Value Pairs) ===" << endl;
    
    // 1. Creation and initialization
    map<string, int> ageMap = {
        {"Alice", 25},
        {"Bob", 30},
        {"Charlie", 35}
    };
    
    // 2. Insertion methods
    ageMap["David"] = 28;              // Using [] operator
    ageMap.insert({"Eve", 22});        // Using insert()
    
    // insert() returns pair
    auto result = ageMap.insert({"Alice", 26}); // Alice already exists
    if (!result.second) {
        cout << "Alice already exists with age " << ageMap["Alice"] << endl;
    }
    
    // 3. Access elements
    cout << "Bob's age: " << ageMap["Bob"] << endl;
    
    // Using at() (throws exception if key doesn't exist)
    try {
        cout << "Charlie's age: " << ageMap.at("Charlie") << endl;
    } catch (const out_of_range& e) {
        cout << "Key not found!" << endl;
    }
    
    // 4. Checking existence
    if (ageMap.find("Frank") == ageMap.end()) {
        cout << "Frank not found in map" << endl;
    }
    
    // 5. Iteration
    cout << "\nAll entries (sorted by key):" << endl;
    for (const auto& pair : ageMap) {
        cout << pair.first << ": " << pair.second << endl;
    }
    
    // 6. Using iterators
    cout << "\nUsing iterators:" << endl;
    for (auto it = ageMap.begin(); it != ageMap.end(); ++it) {
        cout << it->first << ": " << it->second << endl;
    }
    
    // 7. Erasing elements
    ageMap.erase("Bob");               // Erase by key
    auto it = ageMap.find("Charlie");
    if (it != ageMap.end()) {
        ageMap.erase(it);              // Erase by iterator
    }
    
    // 8. Custom comparator
    map<string, int, greater<string>> reverseMap = {
        {"Alice", 25},
        {"Bob", 30},
        {"Charlie", 35}
    };
    
    cout << "\nReverse sorted map:" << endl;
    for (const auto& pair : reverseMap) {
        cout << pair.first << ": " << pair.second << endl;
    }
    
    cout << endl;
}

void demonstrateMultimap() {
    cout << "=== multimap (Multiple Values per Key) ===" << endl;
    
    multimap<string, string> courses;
    
    // Can have multiple values for same key
    courses.insert({"CS101", "Introduction to Programming"});
    courses.insert({"CS101", "Data Structures"});
    courses.insert({"CS101", "Algorithms"});
    courses.insert({"MATH101", "Calculus I"});
    courses.insert({"MATH101", "Linear Algebra"});
    
    // Finding all values for a key
    cout << "Courses for CS101:" << endl;
    auto range = courses.equal_range("CS101");
    for (auto it = range.first; it != range.second; ++it) {
        cout << "  " << it->second << endl;
    }
    
    cout << endl;
}

void demonstrateUnorderedContainers() {
    cout << "=== Unordered Containers (Hash Tables) ===" << endl;
    
    // 1. unordered_set
    unordered_set<string> us = {"apple", "banana", "cherry"};
    
    cout << "unordered_set elements: ";
    for (const string& fruit : us) {
        cout << fruit << " ";
    }
    cout << endl;
    
    // 2. unordered_map
    unordered_map<string, double> priceMap = {
        {"apple", 1.20},
        {"banana", 0.80},
        {"cherry", 3.50}
    };
    
    cout << "\nFruit prices:" << endl;
    for (const auto& pair : priceMap) {
        cout << pair.first << ": $" << pair.second << endl;
    }
    
    // 3. Hash statistics
    cout << "\nHash table statistics:" << endl;
    cout << "Bucket count: " << priceMap.bucket_count() << endl;
    cout << "Load factor: " << priceMap.load_factor() << endl;
    cout << "Max load factor: " << priceMap.max_load_factor() << endl;
    
    // 4. Iterating through buckets
    cout << "\nElements by bucket:" << endl;
    for (size_t i = 0; i < priceMap.bucket_count(); ++i) {
        cout << "Bucket " << i << ": ";
        for (auto it = priceMap.begin(i); it != priceMap.end(i); ++it) {
            cout << it->first << " ";
        }
        cout << endl;
    }
    
    // 5. Custom hash function (for custom types)
    struct Point {
        int x, y;
        
        bool operator==(const Point& other) const {
            return x == other.x && y == other.y;
        }
    };
    
    struct PointHash {
        size_t operator()(const Point& p) const {
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
    
    unordered_set<Point, PointHash> pointSet;
    pointSet.insert({1, 2});
    pointSet.insert({3, 4});
    
    cout << endl;
}

void containerComparison() {
    cout << "=== Ordered vs Unordered Containers ===" << endl;
    cout << "\nUse ordered containers (set/map) when:" << endl;
    cout << "  - Need elements in sorted order" << endl;
    cout << "  - Need to traverse in order" << endl;
    cout << "  - Need range queries (lower_bound, upper_bound)" << endl;
    cout << "  - Memory overhead of hash table is too high" << endl;
    
    cout << "\nUse unordered containers when:" << endl;
    cout << "  - Need faster lookup (O(1) average)" << endl;
    cout << "  - Don't care about order" << endl;
    cout << "  - Have good hash function for your type" << endl;
    cout << "  - Can tolerate O(n) worst-case performance" << endl;
}

int main() {
    demonstrateSet();
    demonstrateMultiset();
    demonstrateMap();
    demonstrateMultimap();
    demonstrateUnorderedContainers();
    containerComparison();
    
    return 0;
}

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <deque>
#include <functional>  // For greater<>
#include <string>
using namespace std;

void demonstrateStack() {
    cout << "=== stack (LIFO - Last In First Out) ===" << endl;
    
    // Default uses deque as underlying container
    stack<int> s1;
    
    // Can specify underlying container
    stack<int, vector<int>> s2;      // Uses vector
    stack<int, list<int>> s3;        // Uses list
    
    // Basic operations
    s1.push(10);
    s1.push(20);
    s1.push(30);
    
    cout << "Top element: " << s1.top() << endl;
    cout << "Size: " << s1.size() << endl;
    cout << "Empty? " << (s1.empty() ? "Yes" : "No") << endl;
    
    // Process stack (LIFO order)
    cout << "Stack elements (LIFO): ";
    while (!s1.empty()) {
        cout << s1.top() << " ";
        s1.pop();
    }
    cout << endl;
    
    // Practical example: Expression evaluation
    cout << "\nExpression Evaluation (Parentheses matching):" << endl;
    string expression = "((a + b) * (c - d))";
    stack<char> parenStack;
    bool balanced = true;
    
    for (char ch : expression) {
        if (ch == '(') {
            parenStack.push(ch);
        } else if (ch == ')') {
            if (parenStack.empty()) {
                balanced = false;
                break;
            }
            parenStack.pop();
        }
    }
    
    if (balanced && parenStack.empty()) {
        cout << "Expression is balanced" << endl;
    } else {
        cout << "Expression is not balanced" << endl;
    }
    
    cout << endl;
}

void demonstrateQueue() {
    cout << "=== queue (FIFO - First In First Out) ===" << endl;
    
    // Default uses deque as underlying container
    queue<string> q1;
    
    // Can specify underlying container
    queue<string, list<string>> q2;  // Uses list
    
    // Basic operations
    q1.push("Task 1");
    q1.push("Task 2");
    q1.push("Task 3");
    
    cout << "Front: " << q1.front() << endl;
    cout << "Back: " << q1.back() << endl;
    cout << "Size: " << q1.size() << endl;
    
    // Process queue (FIFO order)
    cout << "Processing queue (FIFO):" << endl;
    while (!q1.empty()) {
        cout << "Processing: " << q1.front() << endl;
        q1.pop();
    }
    
    // Practical example: BFS simulation
    cout << "\nBFS (Breadth-First Search) Simulation:" << endl;
    queue<int> bfsQueue;
    vector<bool> visited(6, false);
    vector<vector<int>> graph = {
        {1, 2},     // Node 0
        {0, 3, 4},  // Node 1
        {0, 5},     // Node 2
        {1},        // Node 3
        {1},        // Node 4
        {2}         // Node 5
    };
    
    bfsQueue.push(0);
    visited[0] = true;
    
    cout << "BFS traversal: ";
    while (!bfsQueue.empty()) {
        int current = bfsQueue.front();
        bfsQueue.pop();
        cout << current << " ";
        
        for (int neighbor : graph[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                bfsQueue.push(neighbor);
            }
        }
    }
    cout << endl << endl;
}

void demonstratePriorityQueue() {
    cout << "=== priority_queue (Max-Heap by default) ===" << endl;
    
    // Default: max-heap (largest element at top)
    priority_queue<int> maxHeap;
    
    // Min-heap: use greater<> comparator
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    // Basic operations for max-heap
    maxHeap.push(30);
    maxHeap.push(10);
    maxHeap.push(50);
    maxHeap.push(20);
    
    cout << "Max-heap elements (largest at top):" << endl;
    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    cout << endl;
    
    // Min-heap example
    minHeap.push(30);
    minHeap.push(10);
    minHeap.push(50);
    minHeap.push(20);
    
    cout << "\nMin-heap elements (smallest at top):" << endl;
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    cout << endl;
    
    // Custom comparator example
    struct Task {
        string name;
        int priority;  // Higher number = higher priority
        
        bool operator<(const Task& other) const {
            return priority < other.priority;  // For max-heap based on priority
        }
    };
    
    priority_queue<Task> taskQueue;
    taskQueue.push({"Low priority task", 1});
    taskQueue.push({"High priority task", 3});
    taskQueue.push({"Medium priority task", 2});
    
    cout << "\nProcessing tasks by priority:" << endl;
    while (!taskQueue.empty()) {
        Task task = taskQueue.top();
        taskQueue.pop();
        cout << task.name << " (Priority: " << task.priority << ")" << endl;
    }
    
    // Practical example: Merge k sorted arrays
    cout << "\nMerging k sorted arrays using min-heap:" << endl;
    vector<vector<int>> arrays = {
        {1, 4, 7},
        {2, 5, 8},
        {3, 6, 9}
    };
    
    // Element: (value, array_index, element_index)
    priority_queue<pair<int, pair<int, int>>, 
                   vector<pair<int, pair<int, int>>>,
                   greater<pair<int, pair<int, int>>>> minHeap2;
    
    // Push first element of each array
    for (int i = 0; i < arrays.size(); i++) {
        if (!arrays[i].empty()) {
            minHeap2.push({arrays[i][0], {i, 0}});
        }
    }
    
    vector<int> merged;
    while (!minHeap2.empty()) {
        auto current = minHeap2.top();
        minHeap2.pop();
        
        int value = current.first;
        int arrayIdx = current.second.first;
        int elementIdx = current.second.second;
        
        merged.push_back(value);
        
        // Push next element from same array
        if (elementIdx + 1 < arrays[arrayIdx].size()) {
            minHeap2.push({arrays[arrayIdx][elementIdx + 1], {arrayIdx, elementIdx + 1}});
        }
    }
    
    cout << "Merged array: ";
    for (int num : merged) {
        cout << num << " ";
    }
    cout << endl << endl;
}

void adaptorComparison() {
    cout << "=== Container Adaptor Comparison ===" << endl;
    
    cout << "\nstack (LIFO):" << endl;
    cout << "  - Operations: push(), pop(), top()" << endl;
    cout << "  - Underlying: deque (default), vector, list" << endl;
    cout << "  - Use cases: Function calls, undo/redo, parsing" << endl;
    
    cout << "\nqueue (FIFO):" << endl;
    cout << "  - Operations: push(), pop(), front(), back()" << endl;
    cout << "  - Underlying: deque (default), list" << endl;
    cout << "  - Use cases: BFS, task scheduling, buffering" << endl;
    
    cout << "\npriority_queue (Heap):" << endl;
    cout << "  - Operations: push(), pop(), top()" << endl;
    cout << "  - Underlying: vector (default), deque" << endl;
    cout << "  - Use cases: Dijkstra, scheduling, median maintenance" << endl;
}

int main() {
    demonstrateStack();
    demonstrateQueue();
    demonstratePriorityQueue();
    adaptorComparison();
    
    return 0;
}

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <numeric>     // For numeric algorithms
#include <functional>  // For function objects
#include <string>
#include <iterator>    // For back_inserter, etc.
#include <random>      // For random numbers
using namespace std;

void demonstrateNonModifyingAlgorithms() {
    cout << "=== Non-modifying Algorithms ===" << endl;
    
    vector<int> v = {1, 2, 3, 4, 5, 2, 3, 2, 7, 8};
    
    // 1. find() - find element
    auto it = find(v.begin(), v.end(), 3);
    if (it != v.end()) {
        cout << "Found 3 at position: " << distance(v.begin(), it) << endl;
    }
    
    // 2. count() - count occurrences
    int twos = count(v.begin(), v.end(), 2);
    cout << "Number of 2s: " << twos << endl;
    
    // 3. count_if() - count with condition
    int evens = count_if(v.begin(), v.end(), [](int n) {
        return n % 2 == 0;
    });
    cout << "Number of even numbers: " << evens << endl;
    
    // 4. all_of(), any_of(), none_of()
    bool allPositive = all_of(v.begin(), v.end(), [](int n) {
        return n > 0;
    });
    cout << "All positive? " << (allPositive ? "Yes" : "No") << endl;
    
    // 5. for_each() - apply function to each element
    cout << "Elements: ";
    for_each(v.begin(), v.end(), [](int n) {
        cout << n << " ";
    });
    cout << endl;
    
    // 6. search() - find subsequence
    vector<int> sub = {2, 3};
    auto subIt = search(v.begin(), v.end(), sub.begin(), sub.end());
    if (subIt != v.end()) {
        cout << "Found subsequence starting at: " << distance(v.begin(), subIt) << endl;
    }
    
    cout << endl;
}

void demonstrateModifyingAlgorithms() {
    cout << "=== Modifying Algorithms ===" << endl;
    
    vector<int> v = {1, 2, 3, 4, 5};
    
    // 1. copy() - copy elements
    vector<int> dest(5);
    copy(v.begin(), v.end(), dest.begin());
    cout << "Copied vector: ";
    for (int n : dest) cout << n << " ";
    cout << endl;
    
    // 2. copy_if() - copy with condition
    vector<int> evens;
    copy_if(v.begin(), v.end(), back_inserter(evens), [](int n) {
        return n % 2 == 0;
    });
    cout << "Even numbers: ";
    for (int n : evens) cout << n << " ";
    cout << endl;
    
    // 3. transform() - apply function and store result
    vector<int> squared(v.size());
    transform(v.begin(), v.end(), squared.begin(), [](int n) {
        return n * n;
    });
    cout << "Squared: ";
    for (int n : squared) cout << n << " ";
    cout << endl;
    
    // 4. replace() - replace elements
    vector<int> v2 = v;
    replace(v2.begin(), v2.end(), 3, 30);
    cout << "After replacing 3 with 30: ";
    for (int n : v2) cout << n << " ";
    cout << endl;
    
    // 5. fill() - fill with value
    vector<int> v3(5);
    fill(v3.begin(), v3.end(), 42);
    cout << "Filled with 42: ";
    for (int n : v3) cout << n << " ";
    cout << endl;
    
    // 6. generate() - generate using function
    vector<int> v4(5);
    int counter = 1;
    generate(v4.begin(), v4.end(), [&counter]() {
        return counter++ * 10;
    });
    cout << "Generated: ";
    for (int n : v4) cout << n << " ";
    cout << endl;
    
    // 7. remove() and erase-remove idiom
    vector<int> v5 = {1, 2, 3, 2, 4, 2, 5};
    auto newEnd = remove(v5.begin(), v5.end(), 2);
    v5.erase(newEnd, v5.end());
    cout << "After removing all 2s: ";
    for (int n : v5) cout << n << " ";
    cout << endl;
    
    cout << endl;
}

void demonstrateSortingAlgorithms() {
    cout << "=== Sorting Algorithms ===" << endl;
    
    vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // 1. sort() - quick sort (not stable)
    sort(v.begin(), v.end());
    cout << "Sorted: ";
    for (int n : v) cout << n << " ";
    cout << endl;
    
    // 2. stable_sort() - maintains order of equal elements
    vector<pair<int, string>> people = {
        {25, "Alice"},
        {30, "Bob"},
        {25, "Charlie"},
        {30, "David"}
    };
    
    stable_sort(people.begin(), people.end(), [](const auto& a, const auto& b) {
        return a.first < b.first;
    });
    
    cout << "Stable sorted by age: " << endl;
    for (const auto& p : people) {
        cout << p.second << " (" << p.first << ")" << endl;
    }
    
    // 3. partial_sort() - sort first n elements
    vector<int> v2 = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    partial_sort(v2.begin(), v2.begin() + 3, v2.end());
    cout << "First 3 elements sorted: ";
    for (int n : v2) cout << n << " ";
    cout << endl;
    
    // 4. nth_element() - partition around nth element
    vector<int> v3 = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    auto middle = v3.begin() + v3.size() / 2;
    nth_element(v3.begin(), middle, v3.end());
    cout << "Median: " << *middle << endl;
    cout << "After nth_element (left <= median <= right): ";
    for (int n : v3) cout << n << " ";
    cout << endl;
    
    // 5. binary_search() - requires sorted range
    vector<int> sorted = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    bool found = binary_search(sorted.begin(), sorted.end(), 5);
    cout << "5 found in sorted vector? " << (found ? "Yes" : "No") << endl;
    
    // 6. lower_bound(), upper_bound() - find insertion points
    vector<int> v4 = {1, 2, 2, 2, 3, 4, 5};
    auto lb = lower_bound(v4.begin(), v4.end(), 2);  // First element >= 2
    auto ub = upper_bound(v4.begin(), v4.end(), 2);  // First element > 2
    cout << "Range of 2s: [" << distance(v4.begin(), lb) << ", " 
         << distance(v4.begin(), ub) << ")" << endl;
    
    cout << endl;
}

void demonstrateNumericAlgorithms() {
    cout << "=== Numeric Algorithms ===" << endl;
    
    vector<int> v = {1, 2, 3, 4, 5};
    
    // 1. accumulate() - sum of elements
    int sum = accumulate(v.begin(), v.end(), 0);
    cout << "Sum: " << sum << endl;
    
    // accumulate with custom operation (product)
    int product = accumulate(v.begin(), v.end(), 1, multiplies<int>());
    cout << "Product: " << product << endl;
    
    // 2. inner_product() - dot product
    vector<int> v2 = {2, 3, 4, 5, 6};
    int dotProduct = inner_product(v.begin(), v.end(), v2.begin(), 0);
    cout << "Dot product: " << dotProduct << endl;
    
    // 3. partial_sum() - cumulative sum
    vector<int> result(v.size());
    partial_sum(v.begin(), v.end(), result.begin());
    cout << "Partial sums: ";
    for (int n : result) cout << n << " ";
    cout << endl;
    
    // 4. adjacent_difference() - difference between adjacent elements
    vector<int> diff(v.size());
    adjacent_difference(v.begin(), v.end(), diff.begin());
    cout << "Adjacent differences: ";
    for (int n : diff) cout << n << " ";
    cout << endl;
    
    // 5. iota() - fill with increasing values (C++11)
    vector<int> v3(5);
    iota(v3.begin(), v3.end(), 10);  // Start from 10
    cout << "Iota from 10: ";
    for (int n : v3) cout << n << " ";
    cout << endl;
    
    cout << endl;
}

void demonstrateHeapAlgorithms() {
    cout << "=== Heap Algorithms ===" << endl;
    
    vector<int> v = {9, 5, 7, 1, 3, 2, 8};
    
    // 1. make_heap() - create max-heap
    make_heap(v.begin(), v.end());
    cout << "Max-heap: ";
    for (int n : v) cout << n << " ";
    cout << endl;
    cout << "Max element: " << v.front() << endl;
    
    // 2. push_heap() - add element to heap
    v.push_back(10);
    push_heap(v.begin(), v.end());
    cout << "After pushing 10: ";
    for (int n : v) cout << n << " ";
    cout << endl;
    
    // 3. pop_heap() - remove max element
    pop_heap(v.begin(), v.end());
    v.pop_back();
    cout << "After popping max: ";
    for (int n : v) cout << n << " ";
    cout << endl;
    
    // 4. sort_heap() - sort heap
    sort_heap(v.begin(), v.end());
    cout << "Sorted heap: ";
    for (int n : v) cout << n << " ";
    cout << endl;
    
    cout << endl;
}

void demonstrateSetAlgorithms() {
    cout << "=== Set Algorithms ===" << endl;
    
    vector<int> v1 = {1, 2, 3, 4, 5};
    vector<int> v2 = {3, 4, 5, 6, 7};
    vector<int> result;
    
    // Need sorted ranges for set algorithms
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    
    // 1. set_union() - union of two sets
    result.resize(v1.size() + v2.size());
    auto unionEnd = set_union(v1.begin(), v1.end(), 
                              v2.begin(), v2.end(), 
                              result.begin());
    result.erase(unionEnd, result.end());
    cout << "Union: ";
    for (int n : result) cout << n << " ";
    cout << endl;
    
    // 2. set_intersection() - intersection of two sets
    result.clear();
    set_intersection(v1.begin(), v1.end(), 
                     v2.begin(), v2.end(), 
                     back_inserter(result));
    cout << "Intersection: ";
    for (int n : result) cout << n << " ";
    cout << endl;
    
    // 3. set_difference() - elements in first but not second
    result.clear();
    set_difference(v1.begin(), v1.end(), 
                   v2.begin(), v2.end(), 
                   back_inserter(result));
    cout << "Difference (v1 - v2): ";
    for (int n : result) cout << n << " ";
    cout << endl;
    
    // 4. set_symmetric_difference() - elements in either but not both
    result.clear();
    set_symmetric_difference(v1.begin(), v1.end(), 
                             v2.begin(), v2.end(), 
                             back_inserter(result));
    cout << "Symmetric difference: ";
    for (int n : result) cout << n << " ";
    cout << endl;
    
    // 5. includes() - check if one set includes another
    bool includes = std::includes(v1.begin(), v1.end(), 
                                  result.begin(), result.end());
    cout << "v1 includes result? " << (includes ? "Yes" : "No") << endl;
    
    cout << endl;
}

void demonstrateMinMaxAlgorithms() {
    cout << "=== Min/Max Algorithms ===" << endl;
    
    vector<int> v = {5, 2, 8, 1, 9, 3};
    
    // 1. min_element(), max_element()
    auto minIt = min_element(v.begin(), v.end());
    auto maxIt = max_element(v.begin(), v.end());
    cout << "Min: " << *minIt << " at position " << distance(v.begin(), minIt) << endl;
    cout << "Max: " << *maxIt << " at position " << distance(v.begin(), maxIt) << endl;
    
    // 2. minmax_element() - find both min and max in one pass (C++11)
    auto minmax = minmax_element(v.begin(), v.end());
    cout << "Min: " << *minmax.first << ", Max: " << *minmax.second << endl;
    
    // 3. lexicographical_compare() - dictionary comparison
    string s1 = "apple";
    string s2 = "banana";
    bool lexLess = lexicographical_compare(s1.begin(), s1.end(), 
                                          s2.begin(), s2.end());
    cout << s1 << " < " << s2 << "? " << (lexLess ? "Yes" : "No") << endl;
    
    cout << endl;
}

int main() {
    demonstrateNonModifyingAlgorithms();
    demonstrateModifyingAlgorithms();
    demonstrateSortingAlgorithms();
    demonstrateNumericAlgorithms();
    demonstrateHeapAlgorithms();
    demonstrateSetAlgorithms();
    demonstrateMinMaxAlgorithms();
    
    return 0;
}

#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <algorithm>
#include <functional>  // For function objects
#include <iterator>    // For iterator adaptors
#include <numeric>
#include <string>
using namespace std;

void demonstrateIterators() {
    cout << "=== Iterator Types and Operations ===" << endl;
    
    vector<int> v = {1, 2, 3, 4, 5};
    
    // 1. Different iterator types
    vector<int>::iterator it1;          // Read/write iterator
    vector<int>::const_iterator it2;    // Read-only iterator
    vector<int>::reverse_iterator it3;  // Reverse iterator
    
    // 2. Iterator operations
    it1 = v.begin();
    cout << "First element: " << *it1 << endl;
    ++it1;                              // Advance iterator
    cout << "Second element: " << *it1 << endl;
    it1 += 2;                           // Random access
    cout << "Fourth element: " << *it1 << endl;
    
    // 3. Iterator categories demonstration
    list<int> lst = {1, 2, 3, 4, 5};
    list<int>::iterator lit = lst.begin();
    ++lit;                              // OK for bidirectional
    // lit += 2;                        // Error: list iterator not random access
    
    // 4. Reverse iterators
    cout << "Reverse iteration: ";
    for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
        cout << *rit << " ";
    }
    cout << endl;
    
    // 5. Const iterators
    cout << "Const iteration: ";
    for (auto cit = v.cbegin(); cit != v.cend(); ++cit) {
        // *cit = 10;                   // Error: can't modify through const_iterator
        cout << *cit << " ";
    }
    cout << endl;
    
    // 6. Iterator traits
    using iter_type = vector<int>::iterator;
    cout << "Iterator category: ";
    if (is_same<iterator_traits<iter_type>::iterator_category,
                random_access_iterator_tag>::value) {
        cout << "Random Access Iterator" << endl;
    }
    
    // 7. Iterator invalidation
    vector<int> v2 = {1, 2, 3, 4, 5};
    auto invalidIt = v2.begin() + 2;
    v2.push_back(6);                    // May reallocate
    // cout << *invalidIt << endl;     // DANGER: iterator may be invalidated
    
    cout << endl;
}

void demonstrateIteratorAdaptors() {
    cout << "=== Iterator Adaptors ===" << endl;
    
    // 1. back_inserter, front_inserter, inserter
    vector<int> v = {1, 2, 3};
    list<int> lst;
    
    copy(v.begin(), v.end(), back_inserter(lst));      // push_back
    copy(v.begin(), v.end(), front_inserter(lst));     // push_front
    
    set<int> s;
    copy(v.begin(), v.end(), inserter(s, s.begin()));  // insert at position
    
    // 2. istream_iterator - read from input stream
    cout << "Enter numbers (Ctrl+D to end): ";
    vector<int> input;
    copy(istream_iterator<int>(cin), 
         istream_iterator<int>(), 
         back_inserter(input));
    
    cout << "You entered: ";
    copy(input.begin(), input.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    
    // 3. ostream_iterator - write to output stream
    vector<string> words = {"Hello", "World", "C++", "STL"};
    cout << "Words: ";
    copy(words.begin(), words.end(), ostream_iterator<string>(cout, " "));
    cout << endl;
    
    // 4. move_iterator (C++11) - move instead of copy
    vector<string> source = {"one", "two", "three"};
    vector<string> dest;
    
    copy(make_move_iterator(source.begin()),
         make_move_iterator(source.end()),
         back_inserter(dest));
    
    cout << "After move: source size = " << source.size() 
         << ", dest size = " << dest.size() << endl;
    
    cout << endl;
}

void demonstrateFunctionObjects() {
    cout << "=== Function Objects (Functors) ===" << endl;
    
    // 1. Predefined function objects
    vector<int> v = {1, 2, 3, 4, 5};
    
    // Using plus<> functor
    int sum = accumulate(v.begin(), v.end(), 0, plus<int>());
    cout << "Sum using plus: " << sum << endl;
    
    // Using multiplies<> functor
    int product = accumulate(v.begin(), v.end(), 1, multiplies<int>());
    cout << "Product using multiplies: " << product << endl;
    
    // Using greater<> for sorting in descending order
    sort(v.begin(), v.end(), greater<int>());
    cout << "Sorted descending: ";
    for (int n : v) cout << n << " ";
    cout << endl;
    
    // 2. Custom function object
    struct IsEven {
        bool operator()(int n) const {
            return n % 2 == 0;
        }
    };
    
    int evenCount = count_if(v.begin(), v.end(), IsEven());
    cout << "Even numbers: " << evenCount << endl;
    
    // 3. Function object with state
    class RunningAverage {
    private:
        double total = 0;
        int count = 0;
    public:
        double operator()(double value) {
            total += value;
            count++;
            return total / count;
        }
    };
    
    vector<double> values = {1.0, 2.0, 3.0, 4.0, 5.0};
    RunningAverage avg;
    cout << "Running averages: ";
    for (double val : values) {
        cout << avg(val) << " ";
    }
    cout << endl;
    
    cout << endl;
}

void demonstrateLambdas() {
    cout << "=== Lambda Expressions (C++11) ===" << endl;
    
    vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // 1. Basic lambda
    auto isEven = [](int n) { return n % 2 == 0; };
    int evens = count_if(v.begin(), v.end(), isEven);
    cout << "Even numbers: " << evens << endl;
    
    // 2. Lambda with capture by value
    int threshold = 5;
    auto greaterThan = [threshold](int n) { return n > threshold; };
    int aboveThreshold = count_if(v.begin(), v.end(), greaterThan);
    cout << "Numbers > " << threshold << ": " << aboveThreshold << endl;
    
    // 3. Lambda with capture by reference
    int sum = 0;
    for_each(v.begin(), v.end(), [&sum](int n) { sum += n; });
    cout << "Sum: " << sum << endl;
    
    // 4. Lambda with mutable (can modify captured values)
    int counter = 0;
    auto incrementer = [counter]() mutable { return ++counter; };
    cout << "Incrementer: " << incrementer() << " " 
         << incrementer() << " " << incrementer() << endl;
    
    // 5. Lambda as comparator
    sort(v.begin(), v.end(), [](int a, int b) {
        return a > b;  // Sort descending
    });
    cout << "Sorted descending: ";
    for (int n : v) cout << n << " ";
    cout << endl;
    
    // 6. Generic lambda (C++14)
    auto add = [](auto a, auto b) { return a + b; };
    cout << "add(5, 3) = " << add(5, 3) << endl;
    cout << "add(2.5, 3.7) = " << add(2.5, 3.7) << endl;
    cout << "add(string(\"Hello, \"), string(\"World!\")) = " 
         << add(string("Hello, "), string("World!")) << endl;
    
    cout << endl;
}

void demonstrateStdFunction() {
    cout << "=== std::function (Type-erased callable) ===" << endl;
    
    // 1. Storing different callables
    function<int(int, int)> operation;
    
    // Store lambda
    operation = [](int a, int b) { return a + b; };
    cout << "10 + 20 = " << operation(10, 20) << endl;
    
    // Store function pointer
    operation = plus<int>();
    cout << "10 + 20 = " << operation(10, 20) << endl;
    
    // 2. Function with different signatures
    function<void(int)> callback;
    
    callback = [](int x) { 
        cout << "Callback called with: " << x << endl; 
    };
    callback(42);
    
    // 3. Using in algorithms
    vector<function<bool(int)>> predicates;
    predicates.push_back([](int n) { return n % 2 == 0; });
    predicates.push_back([](int n) { return n > 5; });
    predicates.push_back([](int n) { return n < 10; });
    
    vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    for (const auto& pred : predicates) {
        int count = count_if(v.begin(), v.end(), pred);
        cout << "Predicate matches: " << count << " elements" << endl;
    }
    
    // 4. Function with bind
    auto add = [](int a, int b, int c) { return a + b + c; };
    auto add5 = bind(add, placeholders::_1, placeholders::_2, 5);
    cout << "add5(10, 20) = " << add5(10, 20) << endl;
    
    cout << endl;
}

void demonstrateCustomIterators() {
    cout << "=== Custom Iterator Example ===" << endl;
    
    // Simple custom iterator for demonstration
    class Range {
    private:
        int start, end;
    public:
        class Iterator {
        private:
            int current;
        public:
            using iterator_category = input_iterator_tag;
            using value_type = int;
            using difference_type = int;
            using pointer = int*;
            using reference = int&;
            
            Iterator(int pos) : current(pos) {}
            
            int operator*() const { return current; }
            Iterator& operator++() { ++current; return *this; }
            Iterator operator++(int) { Iterator temp = *this; ++current; return temp; }
            bool operator==(const Iterator& other) const { return current == other.current; }
            bool operator!=(const Iterator& other) const { return current != other.current; }
        };
        
        Range(int s, int e) : start(s), end(e) {}
        Iterator begin() const { return Iterator(start); }
        Iterator end() const { return Iterator(end); }
    };
    
    // Using custom iterator
    cout << "Range [1, 10): ";
    for (int n : Range(1, 10)) {
        cout << n << " ";
    }
    cout << endl;
    
    // Use with STL algorithms
    Range r(1, 6);
    int sum = accumulate(r.begin(), r.end(), 0);
    cout << "Sum of range [1, 6) = " << sum << endl;
}

int main() {
    demonstrateIterators();
    demonstrateIteratorAdaptors();
    demonstrateFunctionObjects();
    demonstrateLambdas();
    demonstrateStdFunction();
    demonstrateCustomIterators();
    
    return 0;
}