Kaidzu.com
Таймеры
Си
C++
Миландр- 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)
| |
#include <iostream> // cout
#include <set> // set
using namespace std;
int main() {
set<int> s_empty; // Создание множества
set<string> ss = {"Apple", "Orange", "Nut"}; // Создание множества строк
set<int> si{1, 9, 8, 2}; // Создание множества целочисленных значений
ss.insert("Cherry"); // Добавление элемента
si.insert(7); // Добавление элемента
si.insert(7); // Добавление существующего элемента (не будет добавлен)
si.insert({3, 2, 1}); // Добавление нескольких элементов
ss.erase("Nut"); // Удаление элемента
si.erase(7); // Удаление элемента
si.erase(7); // Удаление несуществующего элемента
cout << ss.count("Cherry") << endl; //1 Элемент найден
cout << ss.count("Chuka") << endl; //0 Элемент не найден
cout << si.count(2) << endl; //1 Элемент найден
for(auto i : si){ // Перебор элементов
cout << i << " "; //1 2 3 8 9 Элементы set всегда отсортированы
}
cout << endl;
}
