Kad jālieto std::set un kad std::unordered_set C++?

std::set un std::unordered_set tiek izmantoti, lai glabātu unikālus elementus. Izvēle starp tiem ir atkarīga no prioritātēm: kārtība vai veiktspēja piekļuvei/ievietošanai/izņemšanai.

std::set balstīts uz līdzsvarotu bināro meklēšanas koku (parasti sarkano-melno koku).

std::set īpašības:

• Elementi tiek glabāti sakārtotā secībā.
• Ievietošana, dzēšana un meklēšana ilgst O(log N) laiku, kur N ir elementu skaits.
• Piemērots, ja ir svarīga elementu sakārtotā secība vai ja nepieciešams iegūt elementus noteiktā diapazonā.

std::unordered_set balstīts uz haštabulu.

std::unordered_set īpašības:

• Elementi netiek glabāti sakārtotā secībā.
• Ievietošana, dzēšana un meklēšana vidēji ilgst O(1), bet sliktākajos gadījumos (ja ir daudz kolīziju) var sasniegt O(N).
• Prasība, lai elementa tips būtu definēta ar noteiktu hašfunkciju (std::hash) un vienādojuma operatoru (operator==).
• Piemērots, ja nepieciešama maksimāla ātruma ievietošanai, dzēšanai un meklēšanai, un elementu kārtība nav svarīga.

Salīdzināšanas tabula:

Kritērijs	std::set	std::unordered_set
Iekšējā struktūra	Līdzsvarots koks	Haštabula
Elementu kārtība	Sakārtota	Nesakārtota
Laiks meklēšanai/ievietošanai/izņemšanai (vidēji)	O(log N)	O(1)
Laiks meklēšanai/ievietošanai/izņemšanai (sliktākais)	O(log N)	O(N)
Prasības tipam	< operators	std::hash, operator==

Piemērs std::set izmantošanai:

#include <iostream>
#include <set>

int galvenais() {
    std::set<int> sakārtots_set;
    sakārtots_set.insert(5);
    sakārtots_set.insert(2);
    sakārtots_set.insert(8);

    // Elementi tiks izvadīti sakārtotā secībā: 2 5 8
    for (int vērtība : sakārtots_set) {
        std::cout << vērtība << " ";
    }
    std::cout << std::endl;

    return 0;
}

Piemērs std::unordered_set izmantošanai:

#include <iostream>
#include <unordered_set>

int galvenais() {
    std::unordered_set<int> nesakārtots_set;
    nesakārtots_set.insert(5);
    nesakārtots_set.insert(2);
    nesakārtots_set.insert(8);

    // Izvades secība var atšķirties
    for (int vērtība : nesakārtots_set) {
        std::cout << vērtība << " ";
    }
    std::cout << std::endl;

    return 0;
}