Millal kasutada std::set ja millal std::unordered_set C++-is?

std::set ja std::unordered_set kasutatakse unikaalsete elementide salvestamiseks. Nende valik sõltub prioriteetidest: järjekord või jõudlus juurdepääsul/sisestamisel/kustutamisel.

std::set põhineb tasakaalustatud binaarsel otsingupuu (tavaliselt punane-must puu).

std::set omadused:

• Elemente hoitakse sorteeritud järjekorras.
• Sisestamine, kustutamine ja otsing kestab O(log N) aega, kus N on elementide arv.
• Sobib, kui oluline on elementide sorteeritud järjekord või kui on vaja saada elemente teatud vahemikus.

std::unordered_set põhineb hajemälu tabelil.

std::unordered_set omadused:

• Elemente hoitakse mitte-sorteeritud järjekorras.
• Sisestamine, kustutamine ja otsing kestab keskmiselt O(1), kuid halvimatel juhtudel (kui on palju kolleege hajufunktsioonis) võib jõuda O(N).
• Nõuab, et elemendi tüüp omab määratletud hajufunktsiooni (std::hash) ja võrdlusoperaatorit (operator==).
• Sobib, kui on vaja maksimaalset kiirust sisestamisel, kustutamisel ja otsingul ning elementide järjekord ei ole oluline.

Tabel:

Kriteerium	std::set	std::unordered_set
Sise-struktuur	Tasakaalustatud puu	Hajemälu tabel
Elementide järjekord	Sorteeritud	Mitte-sorteeritud
Aeg otsinguks/sisestamiseks/kustutamiseks (keskmine)	O(log N)	O(1)
Aeg otsinguks/sisestamiseks/kustutamiseks (halvim)	O(log N)	O(N)
Nõuded tüübile	< operaator	std::hash, operator==

Näide std::set kasutamisest:

#include <iostream>
#include <set>

int peamine() {
    std::set<int> sorteeritud_set;
    sorteeritud_set.insert(5);
    sorteeritud_set.insert(2);
    sorteeritud_set.insert(8);

    // Elementid väljastatakse sorteeritud järjekorras: 2 5 8
    for (int väärtus : sorteeritud_set) {
        std::cout << väärtus << " ";
    }
    std::cout << std::endl;

    return 0;
}

Näide std::unordered_set kasutamisest:

#include <iostream>
#include <unordered_set>

int peamine() {
    std::unordered_set<int> mitte-sorteeritud_set;
    mitte-sorteeritud_set.insert(5);
    mitte-sorteeritud_set.insert(2);
    mitte-sorteeritud_set.insert(8);

    // Väljundi järjekord võib olla erinev
    for (int väärtus : mitte-sorteeritud_set) {
        std::cout << väärtus << " ";
    }
    std::cout << std::endl;

    return 0;
}