- set или множество это контейнер для хранения сортированных уникальных значений. Подключается через #include <set>.
- Записи должны быть уникальны. При добавлении записи с существующим значением, операция будет проигнорирована.
- Для использования сортированных неуникальных записей, используйте контейнер std::multiset.
- Для использования несортированных уникальных записей, используйте контейнер std::unordered_set.
- Для использования несортированных неуникальных записей, используйте контейнер std::unordered_multiset.
Метод | Описание | Пример | Сложность |
---|---|---|---|
begin() | Возвращает итератор на первый элемент. | auto i =st.begin(); | O(1) |
clear() | Удаляет все элементы множества. | st.clear(); | O(n) |
count(const T& value) | Возвращает число элементов со значением value (0 или 1) | size_t cnt = st.count(20); | O(logN) |
emplace(T value) | Вставляет в множество значение value | st.emplace(100); | O(1) |
empty() | Возвращает пустой ли список. | if(!st.empty()); | O(1) |
end() | Возвращает итератор на место после последнего элемента списка. | auto i = st.end(); | O(1) |
erase(iterator pos) erase(iterator it_begin, iterator it_end) erase(const T& key) | Удаляет элемент из заданной позиции. Удаляет элементы заданные диапазоном итераторов Удаляет элемент c заданным значением | st.erase(++st.begin()); st.erase(++st.begin(), --st.end()); st.erase(3); | O(1) O(n) O(log(n)) |
equal_range(const T& value) | Возвращает пару (std::pair) итераторов lower_bound() и upper_bound() | auto p = st.equal_range(30); | O(logN) |
find(const T& value) | Возвращает итератор на элемент со значением или st.end() | auto i = st.find(10); | O(logN) |
insert(T value ) | Вставляет элемент. Вставляет элементы из диапазона итераторов контейнера Вставляет элементы списковой инициализацией | st.insert(10); st.insert(ls.begin(), ls.end()); st.insert({3, 4, 2}); | O(Nlog(N+size)) |
lower_bound(const T& value) | Возвращает итератор на элемент не меньше value или st.end() | auto p = st.lower_bound(30); | O(logN) |
set | Конструктор без аргументов. Создает новое пустое множество. | set<int> ls; | O(1) |
set({initializer_list | Конструктор с инициализацией | set<int> st({1, 9, 4, 25, 16}); | O(N*logN) |
set(const set st1) | Конструктор копирования. Создает множество со значениями множества st1 | set<int> st(st1); | O(n) |
set(iterator it_begin, iterator it_end) | Конструктор. Создает множество из диапазона итераторов другого контейнера. | set<int> st(++v.begin(), --v.end()); | O(N*logN) |
max_size() | Возвращает максимально возможный размер множества. | size_t msize = st.max_size(); //230584300921369395 | O(1) |
merge(set& st1) | Слияние текущего множества и st1 | st.merge(st1); | O(N*log(size()+N))) |
rbegin() | Возвращает реверсивный итератор на конец множества. | auto i = st.rbegin(); | O(1) |
rend() | Возвращает реверсивный итератор на начало множества. | auto i = st.rend(); | O(1) |
size() | Возвращает размер множества. | size_t size = st.size(); | O(n) С++98 O(1) С++11 |
sort() | Сортирует элементы множества по возрастанию | st.sort(); | O(n*log(n)) |
swap(set& st1) | Обменивает содержимое множеств | st.swap(st1); | O(1) |
upper_bound(const T& value) | Возвращает итератор на первый элемент больше value или st.end() | auto p = st.upper_bound(30); | O(logN) |