Algorithms · C++ · CodeMIRAI

Many loops you'd write by hand already exist in the standard library, tested and fast. <algorithm> holds dozens of them, and they all work the same way: you give them a range, usually v.begin() to v.end().

Sorting

C++

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

void print(const vector<int>& v) {
    for (int x : v) cout << x << " ";
    cout << endl;
}

int main() {
    vector<int> v = {42, 7, 19, 3, 25};
    sort(v.begin(), v.end());                    // smallest first
    print(v);
    sort(v.begin(), v.end(), greater<int>());    // largest first
    print(v);
    reverse(v.begin(), v.end());
    print(v);
    return 0;
}

Output

3 7 19 25 42 
42 25 19 7 3 
3 7 19 25 42

sort(first, last) puts the range in ascending order. A third argument says how to compare: greater<int>() (from <functional>) sorts largest first. reverse flips the order.

Finding, counting, totalling

C++

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

int main() {
    vector<int> v = {4, 8, 15, 16, 23, 42, 8};

    auto it = find(v.begin(), v.end(), 16);
    if (it != v.end()) cout << "16 is at index " << (it - v.begin()) << endl;

    cout << "8 appears " << count(v.begin(), v.end(), 8) << " times" << endl;
    cout << "min " << *min_element(v.begin(), v.end())
         << ", max " << *max_element(v.begin(), v.end()) << endl;
    cout << "sum " << accumulate(v.begin(), v.end(), 0) << endl;

    int evens = count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
    cout << evens << " even numbers" << endl;
    return 0;
}

Output

16 is at index 3
8 appears 2 times
min 4, max 42
sum 116
5 even numbers

find returns an iterator to the first match, or end() if there's none; subtracting begin() turns it into an index.
min_element and max_element return iterators too, so * reads the value.
accumulate is in <numeric>. Its last argument is the starting total, and its type is the result's type: start from 0.0 to add doubles.

Lambdas: your own rules

[](int x) { return x % 2 == 0; } in the last example is a lambda: a small unnamed function written right where it's needed. Algorithms that take a rule, like count_if and sort, accept one.

C++

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

struct Student {
    string name;
    int score;
};

int main() {
    vector<Student> group = {{"Asha", 88}, {"Leo", 95}, {"Mei", 88}, {"Ravi", 72}};
    sort(group.begin(), group.end(), [](const Student& a, const Student& b) {
        if (a.score != b.score) return a.score > b.score;   // higher scores first
        return a.name < b.name;                             // ties in name order
    });
    for (const auto& s : group) cout << s.name << " " << s.score << endl;

    int pass = 80;
    int passed = count_if(group.begin(), group.end(), [pass](const Student& s) { return s.score >= pass; });
    cout << passed << " scored " << pass << " or more" << endl;
    return 0;
}

Output

Leo 95
Asha 88
Mei 88
Ravi 72
3 scored 80 or more

The comparison lambda answers one question: should a come before b? Sorting by several fields is just a chain of those checks.

The square brackets are the capture list. [pass] lets the lambda use the local variable pass; an empty [] captures nothing.

Removing duplicates and transforming

C++

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

int main() {
    vector<int> v = {3, 1, 3, 2, 1, 3};
    sort(v.begin(), v.end());                          // 1 1 2 3 3 3
    v.erase(unique(v.begin(), v.end()), v.end());      // 1 2 3

    vector<int> squares(v.size());
    transform(v.begin(), v.end(), squares.begin(), [](int x) { return x * x; });
    for (int x : squares) cout << x << " ";
    cout << endl;

    bool allPositive = all_of(v.begin(), v.end(), [](int x) { return x > 0; });
    bool anyBig = any_of(v.begin(), v.end(), [](int x) { return x > 10; });
    cout << allPositive << " " << anyBig << endl;
    return 0;
}

Output

1 4 9 
1 0

unique only removes duplicates that sit next to each other, which is why the vector is sorted first. It moves the kept elements to the front and returns where they end; erase then trims the rest. The pair is a standard idiom.
transform applies a function to every element and writes the results to another range.
all_of, any_of and none_of ask a yes-or-no question about every element.

Searching sorted data

C++

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

int main() {
    vector<int> sorted = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    cout << binary_search(sorted.begin(), sorted.end(), 23) << endl;
    cout << binary_search(sorted.begin(), sorted.end(), 7) << endl;

    auto pos = lower_bound(sorted.begin(), sorted.end(), 20);
    cout << "20 would go at index " << (pos - sorted.begin()) << ", before " << *pos << endl;
    return 0;
}

Output

1
0
20 would go at index 5, before 23

On sorted data, binary_search halves the range at each step instead of checking every element: about 20 steps for a million numbers. lower_bound returns the first position whose value is not less than the one you give, which is where it would be inserted to keep the order.