C++та std::set жана std::unordered_set качан колдонуш керек?

std::set жана std::unordered_set уникалдуу элементтерди сактоо үчүн колдонулат. Алардын ортосунда тандоо артыкчылыктарга көз каранды: тартиптүүлүк же жеткиликтүүлүк/кошуу/ажыратуу ылдамдыгы.

std::set тең салмактуу бинардык издөө дарагына негизделген (жылдамыраак кызыл-кара дарак).

std::set өзгөчөлүктөрү:

• Элементтер сорттолгон тартипте сакталат.
• Элементтерди кошуу, өчүрүү жана издөө убактысы O(log N), анда N — элементтердин саны.
• Эгер элементтердин сорттолгон тартиби маанилүү болсо же белгилүү бир диапазондо алуу керек болсо ылайыктуу.

std::unordered_set хеш-таблицага негизделген.

std::unordered_set өзгөчөлүктөрү:

• Элементтер сорттолгон эмес.
• Элементтерди кошуу, өчүрүү жана издөө орто эсеп менен O(1), бирок эң жаман учурларда (хеш-функциянын көп коллизиясы болсо) O(N) жетиши мүмкүн.
• Элементтин түрү std::hash функциясы жана operator== салыштыруу оператору болушу керек.
• Эң тез кошуу, өчүрүү жана издөө керек болсо жана элементтердин тартиби маанилүү эмес болсо ылайыктуу.

Таблица:

Критерий	std::set	std::unordered_set
Ички түзүм	Балансталган дарак	Хеш-таблица
Элементтердин тартиби	Сорттолгон	Сорттолбогон
Орто убакыт издөө/кошуу/ажыратуу	O(log N)	O(1)
Эң жаман убакыт	O(log N)	O(N)
Талаптар	< оператору	std::hash, operator==

std::set колдонуу мисалы:

#include <iostream>
#include <set>

int main() {
    std::set<int> тартиптелген_жыйнак;
    тартиптелген_жыйнак.insert(5);
    тартиптелген_жыйнак.insert(2);
    тартиптелген_жыйнак.insert(8);

    // Элементтер сорттолгон тартипте чыгат: 2 5 8
    for (int маанилүү : тартиптелген_жыйнак) {
        std::cout << маанилүү << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::unordered_set колдонуу мисалы:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> сорттобогон_жыйнак;
    сорттобогон_жыйнак.insert(5);
    сорттобогон_жыйнак.insert(2);
    сорттобогон_жыйнак.insert(8);

    // Чыгуу тартиби айырмаланышы мүмкүн
    for (int маанилүү : сорттобогон_жыйнак) {
        std::cout << маанилүү << " ";
    }
    std::cout << std::endl;

    return 0;
}