STL Algorithms

Search algorithms help you find elements or patterns in containers. They range from simple linear searches to more sophisticated pattern matching algorithms. Understanding when to use each algorithm can greatly improve your code's performance, especially the difference between O(n) linear search and O(log n) binary search.

Basic Linear Search

Linear search algorithms examine elements one by one until they find what they're looking for. These work on any sequence, sorted or unsorted, but have O(n) time complexity. The most fundamental search algorithms are std::find and std::find_if.

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

int main() {
    vector<int> numbers = {64, 34, 25, 12, 22, 11, 90};
    
    // find - search for exact value
    auto found = find(numbers.begin(), numbers.end(), 25);
    if (found != numbers.end()) {
        cout << "Found 25 at index: " << distance(numbers.begin(), found) << endl;
    }
    // Output: Found 25 at index: 2
    
    // find_if - search with custom condition
    auto large = find_if(numbers.begin(), numbers.end(), 
                         [](int x) { return x > 50; });
    if (large != numbers.end()) {
        cout << "First number > 50: " << *large << endl;
    }
    // Output: First number > 50: 64
    
    // find_if_not - search for element that doesn't match condition
    auto small = find_if_not(numbers.begin(), numbers.end(), 
                             [](int x) { return x > 50; });
    if (small != numbers.end()) {
        cout << "First number <= 50: " << *small << endl;
    }
    // Output: First number <= 50: 34
    
    return 0;
}

Binary Search (Sorted Sequences)

When your data is sorted, binary search algorithms provide O(log n) performance - dramatically faster than linear search for large datasets. The STL provides several binary search variants for different use cases. Remember: these require sorted input!

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

int main() {
    vector<int> sorted = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    
    // binary_search - returns true/false
    bool exists = binary_search(sorted.begin(), sorted.end(), 7);
    cout << "7 exists: " << (exists ? "Yes" : "No") << endl;
    // Output: 7 exists: Yes
    
    // lower_bound - first position where value could be inserted
    auto lower = lower_bound(sorted.begin(), sorted.end(), 8);
    cout << "8 could be inserted at index: " << distance(sorted.begin(), lower) << endl;
    cout << "Value there: " << *lower << endl;
    // Output: 8 could be inserted at index: 4
    // Value there: 9
    
    // upper_bound - first position after the value
    auto upper = upper_bound(sorted.begin(), sorted.end(), 7);
    cout << "After 7, next position has: " << *upper << endl;
    // Output: After 7, next position has: 9
    
    // equal_range - range of all equal elements
    auto range = equal_range(sorted.begin(), sorted.end(), 7);
    cout << "Range for 7: [" << distance(sorted.begin(), range.first) 
         << ", " << distance(sorted.begin(), range.second) << ")" << endl;
    // Output: Range for 7: [3, 4)
    
    return 0;
}

Subsequence Search

Sometimes you need to find patterns or subsequences within sequences. The std::search family of algorithms specializes in finding one sequence within another. These are particularly useful for text processing and pattern matching.

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

int main() {
    string text = "The quick brown fox jumps over the lazy dog";
    string pattern = "brown fox";
    
    // search - find one sequence in another
    auto found = search(text.begin(), text.end(), 
                        pattern.begin(), pattern.end());
    if (found != text.end()) {
        cout << "Found pattern at position: " << distance(text.begin(), found) << endl;
        cout << "Context: '" << string(found, found + pattern.length()) << "'" << endl;
    }
    // Output: Found pattern at position: 10
    // Context: 'brown fox'
    
    // search_n - find n consecutive occurrences
    vector<int> numbers = {1, 2, 3, 3, 3, 4, 5, 3, 3, 6};
    auto triple = search_n(numbers.begin(), numbers.end(), 3, 3);
    if (triple != numbers.end()) {
        cout << "Found 3 consecutive 3s at index: " << distance(numbers.begin(), triple) << endl;
    }
    // Output: Found 3 consecutive 3s at index: 2
    
    // find_end - find last occurrence of subsequence
    vector<int> data = {1, 2, 1, 2, 3, 4, 1, 2};
    vector<int> sub = {1, 2};
    auto last = find_end(data.begin(), data.end(), sub.begin(), sub.end());
    if (last != data.end()) {
        cout << "Last occurrence of [1,2] at index: " << distance(data.begin(), last) << endl;
    }
    // Output: Last occurrence of [1,2] at index: 6
    
    return 0;
}

Counting and Existence

Sometimes you don't need to find where something is, just whether it exists or how many times it appears. The counting and existence algorithms provide efficient ways to answer these questions without manually iterating through containers.

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

int main() {
    vector<int> grades = {85, 92, 76, 85, 88, 95, 85, 79, 91};
    
    // count - count exact matches
    int count_85 = count(grades.begin(), grades.end(), 85);
    cout << "Number of 85s: " << count_85 << endl;
    // Output: Number of 85s: 3
    
    // count_if - count with condition
    int high_grades = count_if(grades.begin(), grades.end(), 
                               [](int grade) { return grade >= 90; });
    cout << "Grades >= 90: " << high_grades << endl;
    // Output: Grades >= 90: 3
    
    // any_of - check if any element matches
    bool has_perfect = any_of(grades.begin(), grades.end(), 
                              [](int grade) { return grade == 100; });
    cout << "Has perfect score: " << (has_perfect ? "Yes" : "No") << endl;
    // Output: Has perfect score: No
    
    // all_of - check if all elements match
    bool all_passing = all_of(grades.begin(), grades.end(), 
                              [](int grade) { return grade >= 70; });
    cout << "All passing (>=70): " << (all_passing ? "Yes" : "No") << endl;
    // Output: All passing (>=70): Yes
    
    // none_of - check if no elements match
    bool no_failing = none_of(grades.begin(), grades.end(), 
                              [](int grade) { return grade < 60; });
    cout << "No failing grades: " << (no_failing ? "Yes" : "No") << endl;
    // Output: No failing grades: Yes
    
    return 0;
}

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

int main() {
    vector<double> numbers = {1.5, 2.3, 8.7, 4.1, 6.2, 9.8, 3.4};
    
    // 1. First number > 5.0
    auto large = find_if(numbers.begin(), numbers.end(), 
                         [](double x) { return x > 5.0; });
    if (large != numbers.end()) {
        cout << "First number > 5.0: " << *large << endl;
    }
    // Output: First number > 5.0: 8.7
    
    // 2. First number between 3.0 and 4.0
    auto between = find_if(numbers.begin(), numbers.end(), 
                           [](double x) { return x >= 3.0 && x <= 4.0; });
    if (between != numbers.end()) {
        cout << "First number between 3.0-4.0: " << *between << endl;
    }
    // Output: First number between 3.0-4.0: 3.4
    
    // 3. First number with fractional part > 0.5
    auto high_frac = find_if(numbers.begin(), numbers.end(), 
                             [](double x) { 
                                 double frac = x - floor(x);
                                 return frac > 0.5; 
                             });
    if (high_frac != numbers.end()) {
        cout << "First with fractional part > 0.5: " << *high_frac << endl;
    }
    // Output: First with fractional part > 0.5: 8.7
    
    return 0;
}

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

int main() {
    vector<int> sorted = {2, 4, 6, 8, 10, 12, 14, 16};
    
    // 1. Check if 6 and 7 exist
    bool has_6 = binary_search(sorted.begin(), sorted.end(), 6);
    bool has_7 = binary_search(sorted.begin(), sorted.end(), 7);
    cout << "6 exists: " << (has_6 ? "Yes" : "No") << endl;
    cout << "7 exists: " << (has_7 ? "Yes" : "No") << endl;
    // Output: 6 exists: Yes
    // Output: 7 exists: No
    
    // 2. Find insertion points for 5 and 15
    auto pos_5 = lower_bound(sorted.begin(), sorted.end(), 5);
    auto pos_15 = lower_bound(sorted.begin(), sorted.end(), 15);
    
    cout << "5 could be inserted at index: " << distance(sorted.begin(), pos_5) << endl;
    cout << "15 could be inserted at index: " << distance(sorted.begin(), pos_15) << endl;
    // Output: 5 could be inserted at index: 2
    // Output: 15 could be inserted at index: 7
    
    // 3. Find range for 8
    auto range = equal_range(sorted.begin(), sorted.end(), 8);
    cout << "8 appears in range [" << distance(sorted.begin(), range.first) 
         << ", " << distance(sorted.begin(), range.second) << ")" << endl;
    // Output: 8 appears in range [3, 4)
    
    return 0;
}

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

int main() {
    vector<int> data = {1, 2, 3, 2, 2, 4, 5, 2, 2, 2, 6};
    vector<int> pattern = {2, 2};
    
    // 1. Find first occurrence of pattern {2, 2}
    auto first = search(data.begin(), data.end(), pattern.begin(), pattern.end());
    if (first != data.end()) {
        cout << "First {2,2} at index: " << distance(data.begin(), first) << endl;
    }
    // Output: First {2,2} at index: 3
    
    // 2. Find 3 consecutive 2s
    auto triple = search_n(data.begin(), data.end(), 3, 2);
    if (triple != data.end()) {
        cout << "Found 3 consecutive 2s at index: " << distance(data.begin(), triple) << endl;
    }
    // Output: Found 3 consecutive 2s at index: 7
    
    // 3. Find last occurrence of pattern {2, 2}
    auto last = find_end(data.begin(), data.end(), pattern.begin(), pattern.end());
    if (last != data.end()) {
        cout << "Last {2,2} at index: " << distance(data.begin(), last) << endl;
    }
    // Output: Last {2,2} at index: 8
    
    return 0;
}

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

int main() {
    vector<int> scores = {88, 92, 76, 85, 94, 67, 89, 91, 78, 95};
    
    // 1. Count A grades (90+)
    int a_grades = count_if(scores.begin(), scores.end(), 
                            [](int score) { return score >= 90; });
    cout << "A grades (90+): " << a_grades << endl;
    // Output: A grades (90+): 4
    
    // 2. Check if all are passing (60+)
    bool all_passing = all_of(scores.begin(), scores.end(), 
                              [](int score) { return score >= 60; });
    cout << "All passing (60+): " << (all_passing ? "Yes" : "No") << endl;
    // Output: All passing (60+): Yes
    
    // 3. Check if any are perfect (100)
    bool has_perfect = any_of(scores.begin(), scores.end(), 
                              [](int score) { return score == 100; });
    cout << "Has perfect score: " << (has_perfect ? "Yes" : "No") << endl;
    // Output: Has perfect score: No
    
    // 4. Check if none are failing (<60)
    bool no_failing = none_of(scores.begin(), scores.end(), 
                              [](int score) { return score < 60; });
    cout << "No failing grades: " << (no_failing ? "Yes" : "No") << endl;
    // Output: No failing grades: Yes
    
    return 0;
}

Modifying algorithms transform, copy, and manipulate elements in containers. These algorithms are powerful tools for data transformation and functional programming patterns. Master these to write clean, expressive code that processes data efficiently without explicit loops.

Transform Algorithms

Transform algorithms apply a function to every element in a range, creating new values. std::transform is the functional programming workhorse of C++, allowing you to convert data elegantly. It can work in-place or create new sequences, and supports both unary and binary operations.

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

int main() {
    // Unary transform: square all numbers
    vector<int> numbers = {1, 2, 3, 4, 5};
    vector<int> squares(numbers.size());
    
    transform(numbers.begin(), numbers.end(), squares.begin(),
              [](int x) { return x * x; });
    
    cout << "Squares: ";
    for (int x : squares) cout << x << " ";
    cout << endl;
    // Output: Squares: 1 4 9 16 25
    
    return 0;
}

Copy Operations

Copy algorithms move data between containers with various conditions and transformations. These operations are safer than manual loops and often more efficient. The STL provides copying with conditions, backward copying for overlapping ranges, and unique copying to filter duplicates.

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

int main() {
    vector<int> source = {1, 5, 2, 8, 3, 9, 4, 6, 7};
    
    // copy_if: copy elements matching condition
    vector<int> evens;
    copy_if(source.begin(), source.end(), back_inserter(evens),
            [](int x) { return x % 2 == 0; });
    
    cout << "Even numbers: ";
    for (int x : evens) cout << x << " ";
    cout << endl;
    // Output: Even numbers: 2 8 4 6
    
    return 0;
}

Replace and Modify

Replacement algorithms modify existing containers by changing specific values or applying conditions. These are particularly useful for data cleaning, value normalization, and conditional updates. The algorithms work in-place or can copy to new containers.

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

int main() {
    // replace: change all occurrences of value
    vector<int> scores = {85, -1, 92, -1, 88, 95, -1, 79};  // -1 = missing
    replace(scores.begin(), scores.end(), -1, 0);  // Replace missing with 0
    
    cout << "After replacing -1 with 0: ";
    for (int x : scores) cout << x << " ";
    cout << endl;
    // Output: After replacing -1 with 0: 85 0 92 0 88 95 0 79
    
    return 0;
}

Remove Operations

Remove algorithms eliminate elements from containers based on values or conditions. Important: these algorithms don't actually shrink containers - they move remaining elements forward and return an iterator to the new logical end. Use the erase-remove idiom to actually remove elements from containers.

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

int main() {
    // remove: remove specific value (erase-remove idiom)
    vector<int> numbers = {1, 2, 3, 2, 4, 2, 5};
    auto new_end = remove(numbers.begin(), numbers.end(), 2);
    numbers.erase(new_end, numbers.end());  // Actually remove elements
    
    cout << "After removing 2s: ";
    for (int x : numbers) cout << x << " ";
    cout << endl;
    // Output: After removing 2s: 1 3 4 5
    
    return 0;
}

// Solution shows Celsius to Fahrenheit conversion and temperature categorization

// Solution shows copy_if, copy_n, and unique_copy usage

// Solution shows replace and replace_copy for data cleaning

// Solution shows erase-remove idiom and copy_if for filtering

Sorting is one of the most fundamental operations in computer science. The STL provides multiple sorting algorithms optimized for different use cases. Learn when to use full sorts vs partial sorts, and how to customize sorting behavior with predicates.

Basic Sorting

std::sort is the most commonly used sorting algorithm, providing O(n log n) average performance. It uses an optimized hybrid approach (often Introsort) that combines quicksort, heapsort, and insertion sort for optimal performance across different data patterns.

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

int main() {
    // Basic sort: ascending order
    vector<int> numbers = {64, 34, 25, 12, 22, 11, 90};
    sort(numbers.begin(), numbers.end());
    
    cout << "Ascending: ";
    for (int x : numbers) cout << x << " ";
    cout << endl;
    // Output: Ascending: 11 12 22 25 34 64 90
    
    // Custom comparator: descending order
    vector<int> grades = {85, 92, 76, 88, 95, 79, 91};
    sort(grades.begin(), grades.end(), greater<int>());
    
    cout << "Descending: ";
    for (int x : grades) cout << x << " ";
    cout << endl;
    // Output: Descending: 95 92 91 88 85 79 76
    
    return 0;
}

Partial Sorting

Sometimes you only need the top-k elements or want to find the nth element without fully sorting the entire sequence. Partial sorting algorithms are much faster when you don't need complete ordering, with nth_element providing O(n) average performance.

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

int main() {
    vector<int> scores = {88, 76, 95, 82, 91, 67, 89, 74, 93, 85};
    
    // partial_sort: sort only the first n elements
    partial_sort(scores.begin(), scores.begin() + 3, scores.end(), greater<int>());
    
    cout << "Top 3 scores: ";
    for (int i = 0; i < 3; ++i) cout << scores[i] << " ";
    cout << endl;
    // Output: Top 3 scores: 95 93 91
    
    // Reset for nth_element demo
    scores = {88, 76, 95, 82, 91, 67, 89, 74, 93, 85};
    
    // nth_element: find the median (5th element when sorted)
    nth_element(scores.begin(), scores.begin() + 4, scores.end());
    
    cout << "5th element (median): " << scores[4] << endl;
    cout << "Elements <= median: ";
    for (int i = 0; i < 5; ++i) cout << scores[i] << " ";
    cout << endl;
    // Output: 5th element (median): 85
    // Output: Elements <= median: 76 74 82 67 85
    
    return 0;
}

Sorting Checks

Before performing operations that require sorted data (like binary search), you can verify if a sequence is already sorted. The STL provides efficient checking algorithms that can save unnecessary sorting operations.

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

int main() {
    vector<int> data1 = {1, 3, 5, 7, 9};      // Already sorted
    vector<int> data2 = {1, 5, 3, 7, 9};      // Not sorted
    
    // is_sorted: check if entire sequence is sorted
    bool sorted1 = is_sorted(data1.begin(), data1.end());
    bool sorted2 = is_sorted(data2.begin(), data2.end());
    
    cout << "data1 is sorted: " << (sorted1 ? "Yes" : "No") << endl;
    cout << "data2 is sorted: " << (sorted2 ? "Yes" : "No") << endl;
    // Output: data1 is sorted: Yes
    // Output: data2 is sorted: No
    
    // is_sorted_until: find where sorting breaks
    auto unsorted_pos = is_sorted_until(data2.begin(), data2.end());
    if (unsorted_pos != data2.end()) {
        cout << "First unsorted element: " << *unsorted_pos << endl;
        cout << "At index: " << distance(data2.begin(), unsorted_pos) << endl;
    }
    // Output: First unsorted element: 3
    // Output: At index: 2
    
    return 0;
}

// Solution demonstrates custom comparators for different sorting criteria

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

int main() {
    vector<int> scores = {78, 85, 92, 67, 88, 95, 73, 82, 90, 76};
    
    // Top 3 scores using partial_sort
    vector<int> top_scores = scores;
    partial_sort(top_scores.begin(), top_scores.begin() + 3, 
                 top_scores.end(), greater<int>());
    
    cout << "Top 3 scores: ";
    for (int i = 0; i < 3; ++i) {
        cout << top_scores[i] << " ";
    }
    cout << endl;
    // Output: Top 3 scores: 95 92 90
    
    // Bottom 2 scores using partial_sort
    vector<int> bottom_scores = scores;
    partial_sort(bottom_scores.begin(), bottom_scores.begin() + 2, 
                 bottom_scores.end());
    
    cout << "Bottom 2 scores: ";
    for (int i = 0; i < 2; ++i) {
        cout << bottom_scores[i] << " ";
    }
    cout << endl;
    // Output: Bottom 2 scores: 67 73
    
    // Comparison: partial_sort is O(n log k) where k=3
    // Full sort would be O(n log n) where n=10
    // For large datasets with small k, partial_sort is much faster
    cout << "\nNote: partial_sort is more efficient for top-k problems" << endl;
    
    return 0;
}

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

struct Student {
    string name;
    int grade;
};

int main() {
    vector<Student> students = {
        {"Alice", 85}, {"Bob", 92}, {"Charlie", 85},
        {"David", 92}, {"Eve", 78}, {"Frank", 85}
    };
    
    // First, sort by name (alphabetically)
    stable_sort(students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            return a.name < b.name;
        });
    
    // Then, stable_sort by grade (descending)
    // This preserves alphabetical order for same grades
    stable_sort(students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            return a.grade > b.grade;
        });
    
    cout << "Students sorted by grade (desc), then name:" << endl;
    for (const auto& s : students) {
        cout << s.name << ": " << s.grade << endl;
    }
    // Output:
    // Bob: 92
    // David: 92
    // Alice: 85
    // Charlie: 85
    // Frank: 85
    // Eve: 78
    
    return 0;
}

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

int main() {
    vector<int> data = {45, 12, 78, 34, 89, 23, 56, 67, 90, 11};
    
    // Find median (5th element in 0-indexed array of 10 elements)
    vector<int> temp = data;
    size_t mid = temp.size() / 2;
    nth_element(temp.begin(), temp.begin() + mid, temp.end());
    
    cout << "Median value: " << temp[mid] << endl;
    // Output: Median value: 45 (or 50.5 for even count, but nth_element gives one value)
    
    // Show partition around median
    cout << "Values below median: ";
    for (size_t i = 0; i < mid; ++i) {
        cout << temp[i] << " ";
    }
    cout << "\nValues at/above median: ";
    for (size_t i = mid; i < temp.size(); ++i) {
        cout << temp[i] << " ";
    }
    cout << endl;
    
    // Find 75th percentile (7th element in sorted order, index 7)
    temp = data;
    size_t percentile_75 = (temp.size() * 3) / 4;
    nth_element(temp.begin(), temp.begin() + percentile_75, temp.end());
    
    cout << "\n75th percentile value: " << temp[percentile_75] << endl;
    // Output: 75th percentile value: 78
    
    // Verify by full sort
    vector<int> sorted_data = data;
    sort(sorted_data.begin(), sorted_data.end());
    cout << "Verification (fully sorted): ";
    for (int val : sorted_data) cout << val << " ";
    cout << "\n75th percentile from sorted: " 
         << sorted_data[percentile_75] << endl;
    
    cout << "\nNote: nth_element is O(n) vs sort's O(n log n)" << endl;
    
    return 0;
}

Numeric algorithms perform mathematical operations on sequences of data. From simple accumulation to complex reductions and transformations, these algorithms provide building blocks for statistical analysis and mathematical computations.

Accumulation and Reduction

std::accumulate is the fundamental reduction algorithm, folding a sequence into a single value. While traditionally used for summing, it's incredibly flexible with custom operations. The newer std::reduce provides parallel execution capabilities for better performance on large datasets.

#include <iostream>
#include <vector>
#include <numeric>
#include <string>
using namespace std;

int main() {
    vector<int> numbers = {1, 2, 3, 4, 5};
    
    // accumulate: sum all elements
    int sum = accumulate(numbers.begin(), numbers.end(), 0);
    cout << "Sum: " << sum << endl;
    // Output: Sum: 15
    
    // accumulate with custom operation: product
    int product = accumulate(numbers.begin(), numbers.end(), 1,
                             [](int a, int b) { return a * b; });
    cout << "Product: " << product << endl;
    // Output: Product: 120
    
    // accumulate on strings: concatenation
    vector<string> words = {"Hello", " ", "World", "!"};
    string sentence = accumulate(words.begin(), words.end(), string(""));
    cout << "Sentence: " << sentence << endl;
    // Output: Sentence: Hello World!
    
    return 0;
}

Transform and Reduce

std::transform_reduce combines transformation and reduction in one step, which can be more efficient than separate transform and accumulate operations. This is particularly powerful for mathematical computations like dot products or computing statistics from transformed data.

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

int main() {
    vector<double> values = {1.0, 2.0, 3.0, 4.0, 5.0};
    
    // transform_reduce: sum of squares
    double sum_of_squares = transform_reduce(
        values.begin(), values.end(), 0.0, plus<>(),
        [](double x) { return x * x; }
    );
    cout << "Sum of squares: " << sum_of_squares << endl;
    // Output: Sum of squares: 55
    
    // Two-range transform_reduce: dot product
    vector<double> vec1 = {1, 2, 3};
    vector<double> vec2 = {4, 5, 6};
    
    double dot_product = transform_reduce(
        vec1.begin(), vec1.end(), vec2.begin(), 0.0
    );
    cout << "Dot product: " << dot_product << endl;
    // Output: Dot product: 32
    
    return 0;
}

Sequence Generation

Numeric algorithms also include sequence generation functions that create patterns or fill containers with computed values. std::iota creates arithmetic sequences, while partial sums can create cumulative totals and running calculations.

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

int main() {
    // iota: generate arithmetic sequence
    vector<int> sequence(10);
    iota(sequence.begin(), sequence.end(), 1);  // Fill with 1, 2, 3, ...
    
    cout << "Sequence: ";
    for (int x : sequence) cout << x << " ";
    cout << endl;
    // Output: Sequence: 1 2 3 4 5 6 7 8 9 10
    
    // partial_sum: cumulative sum
    vector<int> cumulative(sequence.size());
    partial_sum(sequence.begin(), sequence.end(), cumulative.begin());
    
    cout << "Cumulative sum: ";
    for (int x : cumulative) cout << x << " ";
    cout << endl;
    // Output: Cumulative sum: 1 3 6 10 15 21 28 36 45 55
    
    // adjacent_difference: differences between consecutive elements
    vector<int> differences(cumulative.size());
    adjacent_difference(cumulative.begin(), cumulative.end(), differences.begin());
    
    cout << "Adjacent differences: ";
    for (int x : differences) cout << x << " ";
    cout << endl;
    // Output: Adjacent differences: 1 2 3 4 5 6 7 8 9 10
    
    return 0;
}

// Solution demonstrates accumulate for basic statistics

#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>
using namespace std;

int main() {
    vector<int> vec1 = {1, 2, 3};
    vector<int> vec2 = {4, 5, 6};
    
    // Dot product: (1*4) + (2*5) + (3*6) = 4 + 10 + 18 = 32
    int dot_product = transform_reduce(
        vec1.begin(), vec1.end(), vec2.begin(), 0
    );
    cout << "Dot product: " << dot_product << endl;
    // Output: Dot product: 32
    
    // Sum of squared differences: (1-4)^2 + (2-5)^2 + (3-6)^2 = 9 + 9 + 9 = 27
    int sum_squared_diff = transform_reduce(
        vec1.begin(), vec1.end(), vec2.begin(), 0, plus<>(),
        [](int a, int b) { 
            int diff = a - b; 
            return diff * diff; 
        }
    );
    cout << "Sum of squared differences: " << sum_squared_diff << endl;
    // Output: Sum of squared differences: 27
    
    // Manhattan distance: |1-4| + |2-5| + |3-6| = 3 + 3 + 3 = 9
    int manhattan = transform_reduce(
        vec1.begin(), vec1.end(), vec2.begin(), 0, plus<>(),
        [](int a, int b) { return abs(a - b); }
    );
    cout << "Manhattan distance: " << manhattan << endl;
    // Output: Manhattan distance: 9
    
    // Euclidean distance for reference: sqrt(27) ≈ 5.196
    double euclidean = sqrt(static_cast<double>(sum_squared_diff));
    cout << "Euclidean distance: " << euclidean << endl;
    
    return 0;
}

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

int main() {
    vector<int> sales = {100, 150, 200, 120, 180, 220};
    
    // Running totals (cumulative sum)
    vector<int> cumulative(sales.size());
    partial_sum(sales.begin(), sales.end(), cumulative.begin());
    
    cout << "Running totals: ";
    for (int val : cumulative) cout << val << " ";
    cout << endl;
    // Output: Running totals: 100 250 450 570 750 970
    
    // Running products (compound growth)
    vector<long long> products(sales.size());
    partial_sum(sales.begin(), sales.end(), products.begin(),
        [](long long a, int b) { return a * b; });
    
    cout << "Running products: ";
    for (long long val : products) cout << val << " ";
    cout << endl;
    // Output: Running products: 100 15000 3000000 360000000 ...
    
    // Differences between consecutive months using adjacent_difference
    vector<int> differences(sales.size());
    adjacent_difference(sales.begin(), sales.end(), differences.begin());
    
    cout << "Month-to-month changes: ";
    for (size_t i = 1; i < differences.size(); ++i) {
        cout << (differences[i] >= 0 ? "+" : "") 
             << differences[i] << " ";
    }
    cout << endl;
    // Output: Month-to-month changes: +50 +50 -80 +60 +40
    
    // Calculate average monthly change
    int total_change = accumulate(differences.begin() + 1, 
                                   differences.end(), 0);
    double avg_change = static_cast<double>(total_change) / (sales.size() - 1);
    cout << "Average monthly change: " << avg_change << endl;
    
    return 0;
}

#include <iostream>
#include <vector>
#include <numeric>
#include <iomanip>
using namespace std;

struct InvestmentState {
    double balance;
    double total_interest;
};

int main() {
    vector<double> deposits = {1000, 1000, 1000, 1000, 1000, 1000};
    double monthly_rate = 0.005;  // 0.5% per month
    
    // Calculate final balance with compound interest
    // Each month: add deposit, then apply interest
    InvestmentState final = accumulate(
        deposits.begin(), deposits.end(),
        InvestmentState{0.0, 0.0},
        [monthly_rate](InvestmentState state, double deposit) {
            state.balance += deposit;  // Add deposit
            double interest = state.balance * monthly_rate;
            state.balance += interest;  // Apply interest
            state.total_interest += interest;
            return state;
        }
    );
    
    cout << fixed << setprecision(2);
    cout << "Final balance (compound): $" << final.balance << endl;
    cout << "Total interest earned: $" << final.total_interest << endl;
    // Output: Final balance (compound): $6090.75
    //         Total interest earned: $90.75
    
    // Calculate total deposits
    double total_deposits = accumulate(deposits.begin(), deposits.end(), 0.0);
    cout << "Total deposits: $" << total_deposits << endl;
    
    // Simple interest comparison (interest only on deposits, not compounded)
    double simple_interest = 0.0;
    for (size_t i = 0; i < deposits.size(); ++i) {
        // Each deposit earns interest for remaining months
        int months_earning = deposits.size() - i;
        simple_interest += deposits[i] * monthly_rate * months_earning;
    }
    double simple_final = total_deposits + simple_interest;
    
    cout << "\nSimple interest comparison:" << endl;
    cout << "Final balance (simple): $" << simple_final << endl;
    cout << "Total interest (simple): $" << simple_interest << endl;
    
    // Show compound advantage
    double advantage = final.balance - simple_final;
    cout << "\nCompound interest advantage: $" << advantage << endl;
    
    // Calculate effective return rate
    double return_rate = (final.total_interest / total_deposits) * 100;
    cout << "Effective return: " << return_rate << "%" << endl;
    
    return 0;
}