- multiset ассоциативный контейнер для сортированных неуникальных значений (значения могут повторяться). Подключается через #include <set>;
- Для использования сортированных уникальных записей, используйте контейнер std::set.
- Для использования несортированных уникальных записей, используйте контейнер std::unordered_set.
- Для использования несортированных неуникальных записей, используйте контейнер std::unordered_multiset.
Метод | Описание | Пример | Сложность |
---|---|---|---|
begin() | Возвращает итератор на первый элемент. | auto i =ms.begin(); | O(1) |
clear() | Удаляет все элементы множества. | ms.clear(); | O(n) |
count(const T& value) | Возвращает число элементов со значением value | size_t cnt = ms.count(20); | O(logN) |
emplace(T value) | Вставляет в множество значение value | ms.emplace(100); | O(log(N)) |
emplace_hint(iterator it, T value) | Вставляет в множество значение value используя итератор (подсказку) | ms.emplace_hint(ms.end(), 100); | O(1), O(log(N)) |
empty() | Возвращает пустой ли список. | if(!ms.empty()); | O(1) |
end() | Возвращает итератор на место после последнего элемента списка. | auto i = ms.end(); | O(1) |
equal_range(const value_type& val) | Возвращает пару итераторов включающих искомое значение. | auto it = ms.equal_range(15); | O(log(N)) |
erase(iterator pos) | Удаляет элемент из заданной позиции. | ms.erase(ms.begin()); | O(1) |
erase(const value_type& val) | Удаляет элемент(ы) с заданным значением. | ms.erase(10); | O(log(N)) |
erase(iterator it_begin, iterator it_end) | Удаляет элементы заданные диапазоном итераторов. | ms.erase(++ms.begin(), --ms.end()); | O(n) |
find(const T& value) | Возвращает итератор на элемент со значением или ms.end() | auto i = ms.find(10); | O(logN) |
insert(const T& value) | Вставляет элемент со значением value | ms.insert(500); | O(logN) |
insert(iterator it_hint, const T& value);) | Вставляет элемент со значением value и подсказкой в виде итератора откуда искать место вставки | ms.insert(ms.begin(), 5); | O(logN), O(1) |
insert(iterator it_begin, iterator it_end) | Вставляет элементы из диапазона итераторов контейнера | ms.insert(v.begin(), v.end()); | O(Nlog(size+N)) |
insert(initializer_list<value_type> il) | Вставляет элементы из списка инициализации | ms.insert({3, 5, 2}); | O(Nlog(size+N)) |
key_comp() | Возвращает функцию возвращающую arg1 < arg2 | auto ms_func = ms.key_comp(); | O(1) |
lower_bound(const T& value) | Возвращает итератор на элемент больше или равный value или ms.end() | auto it = ms.lower_bound(30); | O(logN) |
max_size() | Возвращает максимально возможный (текущий) размер массива. | size_t msize = ms.max_size(); //230584300921369395 | O(1) |
multiset | Конструктор без аргументов. Создает новое пустое множество. | multiset<int> ms; | O(1) |
multiset({initializer_list<T> init}) | Конструктор с инициализацией | multiset<int> ms({1, 9, 4, 25, 16}); | O(N*logN) |
multiset(const multiset ms1) | Конструктор копирования. Создает множество со значениями множества st1 | multiset<int> ms(ms1); | O(n) |
multiset(iterator it_begin, iterator it_end) | Конструктор. Создает множество из диапазона итераторов другого контейнера. | multiset<int> ms(++v.begin(), --v.end()); | O(N*logN) |
merge(multiset& ms1) | Слияние текущего множества и ms1 | ms.merge(ms1); | O(N*log(size()+N))) |
rbegin() | Возвращает реверсивный итератор на конец множества. | auto i = ms.rbegin(); | O(1) |
rend() | Возвращает реверсивный итератор на начало множества. | auto i = ms.rend(); | O(1) |
size() | Возвращает размер множества. | size_t size = ms.size(); | O(1) |
swap(set& ms1) | Обменивает содержимое множеств | ms.swap(ms1); | O(1) |
upper_bound(const T& value) | Возвращает итератор на первый элемент больше value или ms.end() | auto p = ms.upper_bound(30); | O(logN) |
value_comp() | Возвращает функцию возвращающую arg1 < arg2 | auto ms_func = ms.value_comp(); | O(1) |
#include <iostream> // cout
#include <set> // multiset
#include <vector> // vector
int main()
{
std::multiset<int> st; // Пустой конструктор
ms.insert(4); //{4} Вставили значение 4
ms.insert(1); //{1, 4} Вставили значение 1
std::multiset<int> sti{5, 10, 3, 7}; //{3, 5, 7, 10} Конструктор с инициализацией
std::vector<int> vec{3, 1, 5, 4, 2}; // Вектор
std::multiset<int> st1(vec.begin(), vec.end() - 2); //{1, 3, 5} Конструктор из итераторов другого контейнера
std::multiset<int> st2(st1); //{1, 3, 5} Конструктор копирования
std::multiset<int> st3(std::move(st2)); //{1, 3, 5} Конструктор перемещения. st2 теперь пустой контейнер
st3.insert(1); //{1, 1, 3, 5} Вставка неуникального значения возможна
for(auto it = st3.begin(); it != st3.end(); it++){
std::cout << *it << " "; //1 1 3 5
}
}