База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C++

std::set — подредена колекция от уникални ключове

std::set от <set> съхранява уникални ключове в реда на компаратора. Научете за вмъкването и търсенето, разликите между find, contains, count и equal_range, както и за безопасната проверка на end().

Версия: C++23; repository compiler flag, production runtime not attested

Синтаксис

#include <set>
std::set<Key> values;
auto [it, inserted] = values.insert(key);
auto found = values.find(key);
bool present = found != values.end();
bool exists = values.contains(key);
auto occurrences = values.count(key);
auto [first, last] = values.equal_range(key);

std::set<Key> от <set> е подреден асоциативен контейнер. Всеки елемент е и ключ; компараторът по подразбиране std::less<Key> подрежда целите числа във възходящ ред. Уникалност означава еквивалентност според компаратора: !comp(a, b) && !comp(b, a), а не непременно a == b. Компараторът трябва да задава строг слаб ред.

Обичайното претоварване на std::set::insert(key) за една стойност връща двойка: итератор към вмъкнатия или вече съществуващия елемент и bool, който показва дали е извършено вмъкване. Еквивалентен ключ не се добавя повторно. std::set::find(key) връща итератор към еквивалентен елемент или std::set::end(). end() сочи след последния елемент: проверете it != values.end(), преди да разименувате резултата от търсенето.

std::set::contains(key) връща булева стойност, която показва дали ключът присъства. std::set::count(key) връща броя на еквивалентните елементи, тук винаги 0 или 1. std::set::equal_range(key) връща два итератора, описващи полуотворения диапазон [first, last) от еквивалентни елементи: празен или съдържащ един елемент. Празен диапазон означава first == last, но не непременно first == values.end().

Обичайното вмъкване на една стойност и изброените операции за търсене имат сложност O(log n); end() отнема постоянно време. Ключовете не могат да се променят чрез итератори. Примерът е предназначен за компилация с -std=c++23. Предоставеният документ е развиваща се чернова, а не окончателна публикация на C++23; флагът на компилатора в хранилището не удостоверява поддръжка по време на изпълнение в производствена среда.

Примери

#include <iostream>
#include <set>

int main() {
    std::set<int> values{3, 1, 3};
    auto [it, inserted] = values.insert(2);
    auto duplicate = values.insert(3);

    std::cout << std::boolalpha;
    std::cout << "insert: " << *it << ' ' << inserted << '\n';
    std::cout << "duplicate: " << duplicate.second << '\n';
    std::cout << "ordered:";
    for (int value : values) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';

    auto found = values.find(2);
    if (found != values.end()) {
        std::cout << "find: " << *found << '\n';
    }
    std::cout << "contains 4: " << values.contains(4) << '\n';
    std::cout << "count 3: " << values.count(3) << '\n';

    auto [first, last] = values.equal_range(2);
    std::cout << "equal_range 2:";
    for (auto current = first; current != last; ++current) {
        std::cout << ' ' << *current;
    }
    std::cout << '\n';
}

Резултат

insert: 2 true
duplicate: false
ordered: 1 2 3
find: 2
contains 4: false
count 3: 1
equal_range 2: 2

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници