Kada naudoti std::set ir kada std::unordered_set C++?

std::set ir std::unordered_set naudojami saugoti unikalius elementus. Pasirinkimas tarp jų priklauso nuo prioritetų: tvarkos ar našumo prieigos/pridėjimo/ištrynimo.

std::set pagrįstas subalansuotu dvejetainiu paieškos medžiu (dažniausiai raudonai-juodu medžiu).

std::set ypatybės:

• Elementai saugomi surūšiuotoje tvarkoje.
• Pridėjimas, ištrynimas ir paieška trunka O(log N) laiką, kur N yra elementų skaičius.
• Tinka, kai svarbu surūšiuota elementų tvarka arba kai reikia gauti elementus tam tikrame intervale.

std::unordered_set pagrįstas maišų lentele.

std::unordered_set ypatybės:

• Elementai nėra saugomi surūšiuotoje tvarkoje.
• Pridėjimas, ištrynimas ir paieška vidutiniškai trunka O(1), bet blogiausiu atveju (kai yra daug kolizijų) gali pasiekti O(N).
• Reikalaujama, kad elemento tipas turėtų apibrėžtą maišų funkciją (std::hash) ir lyginimo operatorių (operator==).
• Tinka, kai reikalingas maksimalus greitis pridėjimui, ištrynimui ir paieškai, o tvarka nėra svarbi.

Lentelė:

Kriterijus	std::set	std::unordered_set
Vidinė struktūra	Subalansuotas medis	Maišų lentelė
Elementų tvarka	Surūšiuota	Nesurūšiuota
Laikas paieškai/pridėjimui/ištrynimui (vidutinis)	O(log N)	O(1)
Laikas paieškai/pridėjimui/ištrynimui (blogiausias)	O(log N)	O(N)
Reikalavimai tipui	< operatorius	std::hash, operator==

Pavyzdys std::set naudojimui:

#include <iostream>
#include <set>

int main() {
    std::set<int> surūšiuotas_set;
    surūšiuotas_set.insert(5);
    surūšiuotas_set.insert(2);
    surūšiuotas_set.insert(8);

    // Elementai išvedami surūšiuotoje tvarkoje: 2 5 8
    for (int reikšmė : surūšiuotas_set) {
        std::cout << reikšmė << " ";
    }
    std::cout << std::endl;

    return 0;
}

Pavyzdys std::unordered_set naudojimui:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> nesurūšiuotas_set;
    nesurūšiuotas_set.insert(5);
    nesurūšiuotas_set.insert(2);
    nesurūšiuotas_set.insert(8);

    // Išvedimo tvarka gali būti kitokia
    for (int reikšmė : nesurūšiuotas_set) {
        std::cout << reikšmė << " ";
    }
    std::cout << std::endl;

    return 0;
}