Algorithms

Overview

The `<algorithm>` library contains optimized functions for sorting, searching, reversing, counting, and modifying data. Using these prevents you from reinventing the wheel.

Syntax

cpp

#include <algorithm>
#include <vector>

std::vector<int> v = {4, 1, 3, 5, 2};

// Sort (O(N log N))
std::sort(v.begin(), v.end()); 

// Reverse
std::reverse(v.begin(), v.end());

// Binary Search (Returns true/false, MUST be sorted first)
bool found = std::binary_search(v.begin(), v.end(), 3);

// Max Element (Returns an iterator)
auto maxIt = std::max_element(v.begin(), v.end());
int maxVal = *maxIt;

Common Pitfalls

Using `std::binary_search` on an unsorted container. It will silently fail and return incorrect results.

Interview Tips

Know that `std::sort` typically uses IntroSort (a hybrid of QuickSort, HeapSort, and InsertionSort) making it extremely fast and immune to O(N^2) worst-case scenarios.

Real-World Example

Sorting with a custom comparator.

example

cpp

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

bool descending(int a, int b) {
    return a > b;
}

int main() {
    vector<int> nums = {1, 5, 2, 8, 3};
    
    // Sort using custom function
    sort(nums.begin(), nums.end(), descending);
    
    for (int n : nums) cout << n << " "; // 8 5 3 2 1
    return 0;
}

Take C++ Quiz