Standard Library Algorithms - Забони барномасозии C++ барои барномасозии рақобатӣ

Week 8Pairs and Structs, Sorting and Searching, Standard Library Algorithms

Standard Library Algorithms

min_element, max_element, count, find, accumulate, reverse and swap; lower_bound and upper_bound and counting with them; unique after sort; next_permutation.

Назария
Дарси 10 аз 12
Хониш: 11 дақиқа
Саволҳо: 5

sort and binary_search are two of a family. The C++ library has a shelf of small, fast, well-tested functions for the things you keep writing loops for: the smallest element, how many sevens, the sum, the first zero. Knowing them saves time and, more importantly, bugs. They all take the same two arguments you already know: where to start and where to stop.

The toolbox

For 4 7 -2 9 0 7 -2 3 it prints min -2 at 2, max 9 at 3, sevens 2, sum 26 and first zero at 4. Three things to notice:

min_element, max_element and find return a position, not a value — the same kind of thing as a.begin(). *low reads the value at that position, and low - a.begin() turns it into an index. auto lets the compiler name the type, which is long and never worth typing.
When find finds nothing, it returns a.end(), the position past the last element. Compare with a.end() before reading *it.
accumulate(a.begin(), a.end(), 0LL) adds everything to a starting value — and the sum has the type of that value. With a plain 0 the sum is an int, and 10⁵ numbers of 10⁵ overflow it. 0LL makes it a long long.

Function	Gives
`min_element(b, e)`, `max_element(b, e)`	the position of the smallest / largest (the first one, if equal)
`count(b, e, x)`	how many elements equal `x`
`find(b, e, x)`	the position of the first , or

навбатӣ

Practice: Standard Library Algorithms

Eleven problems for the toolbox: counts, extremes, distinct values, frequency tables, ranks by lower_bound, triangular sums, anagram groups and valid triangles.

Дарси навбатӣ

Дарси пешина Ба харитаи курс

x

e

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) {
        cin >> x;
    }
    auto low = min_element(a.begin(), a.end());    // a position, not a value
    auto high = max_element(a.begin(), a.end());
    cout << "min " << *low << " at " << low - a.begin() << "\n";
    cout << "max " << *high << " at " << high - a.begin() << "\n";
    cout << "sevens " << count(a.begin(), a.end(), 7) << "\n";
    cout << "sum " << accumulate(a.begin(), a.end(), 0LL) << "\n";
    auto it = find(a.begin(), a.end(), 0);
    if (it == a.end()) {
        cout << "no zero\n";
    } else {
        cout << "first zero at " << it - a.begin() << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int &x : a) {
        cin >> x;
    }
    sort(a.begin(), a.end());             // the bounds need a sorted vector
    while (q--) {
        int lo, hi;
        cin >> lo >> hi;
        int from = lower_bound(a.begin(), a.end(), lo) - a.begin();  // first >= lo
        int to = upper_bound(a.begin(), a.end(), hi) - a.begin();    // first > hi
        cout << to - from << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) {
        cin >> x;
    }
    sort(a.begin(), a.end());             // equal values become neighbours
    // each run of equal values: from i up to j - 1
    for (int i = 0; i < n; ) {
        int j = i;
        while (j < n && a[j] == a[i]) {
            j++;
        }
        cout << a[i] << " x" << j - i << "\n";
        i = j;
    }
    a.erase(unique(a.begin(), a.end()), a.end());
    cout << a.size() << " different\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;
    sort(s.begin(), s.end());             // start from the smallest order
    int k = 0;
    do {
        cout << s << "\n";
        k++;
    } while (next_permutation(s.begin(), s.end()));
    cout << k << " orders\n";
    return 0;
}