Programski jezici → C++ → STL u C++-u: pair, sort, set i priority_queue

STL u C++-u: pair, sort, set i priority_queue

pair: dve vrednosti zajedno

pair<A, B> čuva dve vrednosti – npr. ime i bodove, ili koordinate tačke. Poređenje parova ide leksikografski: prvo po first, pa po second.

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

int main() {
    int n;
    cin >> n;
    vector<pair<int, string>> takmicari(n);          // (bodovi, ime)
    for (auto& [bodovi, ime] : takmicari)              // strukturno vezivanje (C++17)
        cin >> ime >> bodovi;

    sort(takmicari.begin(), takmicari.end());         // po bodovima, pa po imenu
    for (auto& [bodovi, ime] : takmicari)
        cout << ime << " " << bodovi << "\n";
    return 0;
}

Iva je pre Marka jer imaju iste bodove, a „Iva“ < „Marko“. make_pair(a, b) ili samo {a, b} pravi par.

sort sa sopstvenim pravilom

sort(v.begin(), v.end()) sortira rastuće u O(n log n). Za drugi redosled daje se funkcija poređenja (komparator) – najčešće lambda koja vraća true ako a treba da bude pre b:

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

int main() {
    int n;
    cin >> n;
    vector<pair<string, int>> v(n);                   // (ime, bodovi)
    for (auto& [ime, bodovi] : v) cin >> ime >> bodovi;

    // više bodova je bolje; kod istih bodova – abecedno po imenu
    sort(v.begin(), v.end(), [](const pair<string, int>& a, const pair<string, int>& b) {
        if (a.second != b.second) return a.second > b.second;
        return a.first < b.first;
    });

    for (int i = 0; i < n; i++)
        cout << i + 1 << ". " << v[i].first << " " << v[i].second << "\n";
    return 0;
}

Binarna pretraga u sortiranom nizu

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

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    sort(a.begin(), a.end());
    while (q--) {
        int x;
        cin >> x;
        // koliko elemenata je < x, a koliko <= x
        int manjih = lower_bound(a.begin(), a.end(), x) - a.begin();
        int najvise = upper_bound(a.begin(), a.end(), x) - a.begin();
        cout << x << ": pojavljuje se " << najvise - manjih << " puta, manjih je " << manjih << "\n";
    }
    return 0;
}

lower_bound vraća prvo mesto gde je element ≥ x, upper_bound prvo mesto gde je > x – obe u O(log n). Detaljno: Binarna pretraga.

set i map: uređeni skup

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

int main() {
    int n;
    cin >> n;
    set<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);                        // duplikati se ne dodaju, O(log n)
    }
    cout << "razlicitih: " << s.size() << "\n";
    cout << "najmanji: " << *s.begin() << ", najveci: " << *s.rbegin() << "\n";
    cout << "ima 7: " << (s.count(7) ? "da" : "ne") << "\n";
    auto it = s.lower_bound(6);             // najmanji element >= 6
    if (it != s.end()) cout << "prvi >= 6: " << *it << "\n";
    s.erase(9);
    for (int x : s) cout << x << " ";       // uvek u rastućem redosledu
    cout << "\n";
    return 0;
}

priority_queue: uvek najveći na vrhu

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

int main() {
    // k najvecih brojeva iz niza: cuvamo k najvecih u "min-hip"-u
    int n, k;
    cin >> n >> k;
    priority_queue<int, vector<int>, greater<int>> pq;   // na vrhu je NAJMANJI
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();               // izbaci najmanjeg
    }
    vector<int> rez;
    while (!pq.empty()) { rez.push_back(pq.top()); pq.pop(); }
    reverse(rez.begin(), rez.end());
    for (int x : rez) cout << x << " ";
    cout << "\n";
    return 0;
}

priority_queue<int> drži najveći element na vrhu (top); push i pop rade u O(log n). Sa greater<int> na vrhu je najmanji. Ovde je složenost O(n log k) umesto O(n log n) za sortiranje celog niza. Red sa prioritetom je osnova Dijkstrinog algoritma: Red sa prioritetom.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje