Algoritmi → Strukture podataka → Skupovi i mape: set, multiset, map

Skupovi i mape: set, multiset, map

set: skup različitih elemenata

set čuva svaki element najviše jednom, uvek sortirano. Dodavanje postojećeg elementa ne menja ništa.

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(5);
    s.insert(1);
    s.insert(9);
    s.insert(5);                           // 5 već postoji – ništa se ne menja
    cout << "veličina: " << s.size() << endl;

    for (int x : s) cout << x << " ";      // uvek rastuće
    cout << endl;

    cout << "ima li 9? " << s.count(9) << endl;   // 1 ili 0
    s.erase(9);
    cout << "ima li 9? " << s.count(9) << endl;

    cout << "najmanji: " << *s.begin() << endl;
    cout << "najveći: " << *s.rbegin() << endl;
    return 0;
}

Traženje najbližeg u skupu koji se menja

Sortiran niz i lower_bound rade dok se niz ne menja. Ako se elementi dodaju između upita, koristimo metodu s.lower_bound(x) skupa. Primer: parking mesta se zauzimaju jedno po jedno, a za svako novo vozilo tražimo prvo slobodno mesto sa brojem >= x.

#include <iostream>
#include <set>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;                      // mesta 1..n, q vozila
    set<int> slobodna;
    for (int i = 1; i <= n; i++) slobodna.insert(i);

    while (q--) {
        int x;
        cin >> x;                       // vozač želi mesto x ili prvo veće
        auto it = slobodna.lower_bound(x);
        if (it == slobodna.end()) {
            cout << "nema" << endl;
        } else {
            cout << *it << endl;
            slobodna.erase(it);         // mesto je sada zauzeto
        }
    }
    return 0;
}

multiset: skup sa ponavljanjem

multiset dozvoljava više jednakih elemenata, a i dalje je sortiran. Pažnja: ms.erase(x) briše sve kopije broja x; jednu kopiju brišemo preko iteratora: ms.erase(ms.find(x)).

#include <iostream>
#include <set>
using namespace std;

int main() {
    multiset<int> ms = {4, 1, 4, 7, 4};
    cout << "četvorki: " << ms.count(4) << endl;
    ms.erase(ms.find(4));                // briše samo jednu četvorku
    cout << "četvorki: " << ms.count(4) << endl;
    for (int x : ms) cout << x << " ";
    cout << endl;
    return 0;
}

Multiset je zgodan kada treba stalno znati najmanji i najveći od trenutnih elemenata, a elementi se i dodaju i brišu (na primer, cene u prodavnici koje se menjaju).

map: parovi ključ – vrednost

map<K, V> svakom ključu pridružuje vrednost. Osnove su opisane u lekciji Rečnik podataka – mape u C++; ovde je najvažnija primena – brojanje pojavljivanja kada su vrednosti prevelike za običan niz brojača (do 10⁹, negativne, ili reči).

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    map<string, int> br;                // reč -> broj pojavljivanja
    for (int i = 0; i < n; i++) {
        string rec;
        cin >> rec;
        br[rec]++;                      // nova reč automatski dobija 0, pa se uveća
    }
    for (auto &par : br)                // ključevi su sortirani abecedno
        cout << par.first << " " << par.second << endl;
    return 0;
}

unordered_set i unordered_map

Verzije bez uređenja koriste heš tabelu: dodavanje i traženje su u proseku O(1), ali elementi nisu sortirani i nema lower_bound. Koriste se kada redosled nije bitan, a operacija ima mnogo.

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