Этот сайт использует cookies. Продолжение работы с сайтом означает, что Вы согласны!
Классы unordered_set и unordered_multiset: множества
Класс unordered_set
реализует множество, состоящее из уникальных элементов, а класс unordered_multiset
— множество, в котором элементы могут повторяться. В отличии от класса set
для быстрого поиска элементов используется хеш-таблица, значения которой состоят из целых чисел (тип size_t
). Работа с классами unordered_set
и unordered_multiset
производится аналогичным образом, поэтому в этом разделе мы рассмотрим только возможности класса unordered_set
. Прежде чем использовать классы, необходимо в начало программы добавить инструкцию:
#include <unordered_set>
Создание объекта
Объявление класса unordered_set
:
template<typename _Value, typename _Hash = hash<_Value>,
typename _Pred = equal_to<_Value>,
typename _Alloc = allocator<_Value> >
class unordered_set;
Основные псевдонимы для типов:
typedef typename _Value key_type;
typedef typename _Value value_type;
typedef typename _Hash hasher;
typedef typename _Pred key_equal;
typedef typename _Alloc allocator_type;
Создать экземпляр класса unordered_set
можно следующими способами (полный список конструкторов смотрите в документации):
- объявить переменную без инициализации. Для этого перед названием переменной указывается название класса, а после названия внутри угловых скобок задается тип данных элемента. В этом случае множество не содержит элементов. Пример объявления без инициализации:
std::unordered_set<int> s;
s.insert(1); s.insert(2);
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 2 1
Внутри угловых скобок после типа данных элемента можно дополнительно указать функцию для получения хеша и функцию сравнения для значения:
// #include <functional>
std::unordered_set<int, std::hash<int>,
std::equal_to<int> > s;
- указать объект класса
unordered_set
внутри круглых скобок или после оператора=
(доступны конструкторы копирования и перемещения):
std::unordered_set<int> s1;
s1.insert(1); s1.insert(2);
std::unordered_set<int> s2(s1);
for (auto &el : s2) std::cout << el << ' ';
std::cout << std::endl; // 2 1
- указать диапазон внутри контейнера с помощью итераторов. В первом параметре передается итератор, указывающий на начало диапазона, а во втором параметре — итератор, указывающий на конец диапазона. Пример:
std::unordered_set<int> s1;
s1.insert(1); s1.insert(2);
std::unordered_set<int> s2(s1.begin(), s1.end());
for (auto &el : s2) std::cout << el << ' ';
std::cout << std::endl; // 1 2
Вместо итератора можно передать указатель. Создадим объект на основе обычного массива (будут добавлены только уникальные элементы):
const int ARR_SIZE = 8;
int arr[ARR_SIZE] = {1, 1, 2, 2, 1, 3, 2, 3};
std::unordered_set<int> s(arr, arr + ARR_SIZE);
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 3 2 1
- указать значения внутри списка инициализации:
std::unordered_set<int> s = {1, 2, 3};
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 3 2 1
Над двумя объектами класса unordered_set
определены операции ==
и !=
. Кроме того, один объект можно присвоить другому объекту. В этом случае выполняется поэлементное копирование (оператор копирования) или перемещение элементов (оператор перемещения). Пример:
std::unordered_set<int> s1 = {1, 2, 3}, s2;
s2 = s1;
for (auto &el : s2) std::cout << el << ' ';
std::cout << std::endl; // 3 2 1
Доступно также присваивание элементов из списка инициализации:
std::unordered_set<int> s;
s = {1, 2, 3};
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 3 2 1
Вставка элементов
Вставить элементы позволяют следующие методы:
insert()
— вставляет один или несколько элементов. Прототипы метода:
pair<iterator, bool> insert(const value_type &x);
pair<iterator, bool> insert(value_type &&x);
iterator insert(const_iterator pos, const value_type &x);
iterator insert(const_iterator pos, value_type &&x);
template<typename _InputIterator>
void insert(_InputIterator first, _InputIterator last);
void insert(initializer_list<value_type> list);
Первые два прототипа вставляют значение и возвращают объект класса pair
. Через свойство first
будет доступен итератор, указывающий на вставленный элемент, а через свойство second
— логическое значение true
, если элемент вставлен, и false
— в противном случае. Обратите внимание на то, что вставить можно только элемент, который не содержится во множестве. Пример:
std::unordered_set<int> s;
s.insert(1);
std::pair<std::unordered_set<int>::iterator, bool> pr;
pr = s.insert(2);
if (pr.second) { // Проверка успешности вставки
std::cout << *(pr.first) << std::endl; // 2
}
else std::cout << "No" << std::endl;
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 2 1
Обратите внимание на то, что метод insert()
в классе unordered_multiset
возвращает итератор, а не объект класса pair
. Прототипы метода в классе unordered_multiset
:
iterator insert(const value_type &x);
iterator insert(value_type &&x);
Можно вставить элементы, имеющие одинаковое значение:
std::unordered_multiset<int> s;
s.insert(2);
std::unordered_multiset<int>::iterator it = s.insert(2);
std::cout << *it << std::endl; // 2
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 2 2
Третий и четвертый прототипы позволяют подсказать позицию вставки с помощью итератора. Эта позиция может быть проигнорирована, т. к. элементы всегда следуют в строгом порядке. В качестве результата возвращается итератор, указывающий на вставленный элемент. Пример:
std::unordered_set<int> s = {1, 2};
s.insert(s.begin(), 0);
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 0 1 2
Пятый прототип вставляет элементы из диапазона, ограниченного итераторами first
и last
:
std::unordered_set<int> s1 = {1, 2, 3}, s2;
s2.insert(s1.begin(), s1.end());
for (auto &el : s2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
Шестой прототип вставляет уникальные элементы из списка инициализации:
std::unordered_set<int> s = {1, 2, 3};
s.insert({1, 5, 4});
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 4 5 1 2 3
emplace()
— создает элемент и вставляет его во множество. Метод возвращает объект классаpair
. Через свойствоfirst
будет доступен итератор, указывающий на вставленный элемент, а через свойствоsecond
— логическое значениеtrue
, если элемент вставлен, иfalse
— в противном случае. Обратите внимание на то, что вставить можно только уникальный элемент. Прототип метода:
template<typename... _Args>
pair<iterator, bool> emplace(_Args &&... args);
Пример:
std::unordered_set<int> s = {1, 2, 3};
s.emplace(4);
auto pr = s.emplace(2); // Элемент вставлен не будет
std::cout << std::boolalpha;
std::cout << pr.second << std::endl; // false
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 4 3 2 1
Обратите внимание на то, что метод emplace()
в классе unordered_multiset
возвращает итератор, а не объект класса pair
. Прототип метода в классе unordered_multiset
:
template<typename... _Args>
iterator emplace(_Args &&... args);
Можно вставить элементы, имеющие одинаковое значение:
std::unordered_multiset<int> s = {1, 2, 3};
s.emplace(4);
auto it = s.emplace(2); // OK
std::cout << *it << std::endl; // 2
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 1 2 2 3 4
emplace_hint()
— аналогичен методуemplace()
, но дополнительно позволяет подсказать позицию вставки с помощью итератора. Метод возвращает итератор на вставленный элемент или на существующий элемент (вставить элемент с одинаковым значением нельзя). Прототип метода:
template<typename... _Args>
iterator emplace_hint(const_iterator pos, _Args &&... args);
Пример:
std::unordered_set<int> s = {1, 2, 3};
s.emplace_hint(s.begin(), 0);
s.emplace_hint(s.end(), 4);
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 4 1 2 3 0
swap()
— меняет элементы двух контейнеров местами. Прототип метода:
void swap(unordered_set &x);
Пример:
std::unordered_set<int> s1 = {1, 2, 3}, s2 = {4, 5};
s2.swap(s1);
for (auto &el : s1) std::cout << el << ' ';
std::cout << std::endl; // 5 4
for (auto &el : s2) std::cout << el << ' ';
std::cout << std::endl; // 3 2 1
Вместо метода swap()
можно воспользоваться одноименной функцией:
std::swap(s1, s2);
Определение количества элементов
Для определения количества элементов предназначены следующие методы:
size()
— возвращает количество элементов в контейнере. Прототип метода:
size_type size() const noexcept;
Пример:
std::unordered_set<int> s = {1, 2, 3};
std::cout << s.size() << std::endl; // 3
empty()
— возвращает значениеtrue
, если множество не содержит элементов, иfalse
— в противном случае. Прототип метода:
bool empty() const noexcept;
Пример:
std::unordered_set<int> s1 = {1, 2, 3}, s2;
std::cout << std::boolalpha;
std::cout << s1.empty() << std::endl; // false
std::cout << s2.empty() << std::endl; // true
max_size()
— возвращает максимальное количество элементов, которое теоретически может содержаться в контейнере. Прототип метода:
size_type max_size() const noexcept;
Пример:
std::unordered_set<int> s;
std::cout << s.max_size() << std::endl;
// 1152921504606846975
Удаление элементов
Для удаления элементов предназначены следующие методы:
erase()
— удаляет один элемент или элементы из диапазона. Прототипы метода:
size_type erase(const key_type &k);
iterator erase(const_iterator pos);
iterator erase(const_iterator first, const_iterator last);
Первый прототип удаляет элемент с указанным значением и возвращает количество удаленных элементов:
std::unordered_set<int> s = {1, 2, 3};
std::cout << s.erase(1) << std::endl; // 1
std::cout << s.erase(1) << std::endl; // 0
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 3 2
Второй прототип удаляет элемент на который указывает итератор:
std::unordered_set<int> s = {1, 2, 3};
s.erase(s.begin());
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 2 1
Третий прототип удаляет элементы из диапазона, ограниченного итераторами first
и last
. Удалим все элементы:
std::unordered_set<int> s = {1, 2, 3, 4};
s.erase(s.begin(), s.end());
std::cout << s.size() << std::endl; // 0
clear()
— удаляет все элементы. Прототип метода:
void clear() noexcept;
Пример:
std::unordered_set<int> s = {1, 2, 3, 4};
s.clear();
std::cout << s.size() << std::endl; // 0
Доступ к элементам
Для доступа к элементам предназначены следующие методы:
count()
— возвращает количество элементов со значениемval
. Прототип метода:
size_type count(const key_type &val) const;
Пример:
std::unordered_set<int> s1 = {1, 2, 3, 4};
std::cout << s1.count(2) << std::endl; // 1
std::unordered_multiset<int> s2 = {1, 2, 3, 4, 2, 2};
std::cout << s2.count(2) << std::endl; // 3
find()
— возвращает итератор, установленный на элемент со значениемval
. Если элемент не найден, то метод возвращает итератор, указывающий на позицию после последнего элемента. Прототипы метода:
iterator find(const key_type &val);
const_iterator find(const key_type &val) const;
Пример:
std::unordered_set<int> s = {1, 2, 3, 4};
std::unordered_set<int>::iterator it = s.find(2);
if (it != s.end()) {
std::cout << *it << std::endl; // 2
}
equal_range()
— возвращает экземпляр классаpair
. Через свойствоfirst
будет доступен итератор, ссылающийся на первый элемент с указанным значением, а через свойствоsecond
— итератор, ссылающийся на позицию после последнего элемента с указанным значением. Если значение отсутствует, то оба итератора будут ссылаться на значение, возвращаемое методомend()
. Прототипы метода:
pair<iterator, iterator> equal_range(const key_type &val);
pair<const_iterator, const_iterator>
equal_range(const key_type &val) const;
Пример:
typedef std::unordered_multiset<int> Set;
Set s = {0, 1, 1, 1, 4, 5};
std::pair<Set::iterator, Set::iterator> pr;
pr = s.equal_range(1); // Значение существует
if (pr.first != s.end()) {
Set::iterator it1, it2;
for (it1 = pr.first, it2 = pr.second; it1 != it2; ++it1) {
std::cout << *it1 << ' ';
}
std::cout << std::endl; // 1 1 1
}
pr = s.equal_range(2); // Значение не существует
if (pr.first == s.end()) {
std::cout << "No" << std::endl; // No
}
begin()
,end()
,cbegin()
иcend()
— возвращают итераторы (см. разд. 16.1.1). Обратите внимание: обратные итераторы не поддерживаются. Перебор возможен только в прямом порядке. Кроме того, изменить значение с помощью итераторов нельзя . Выведем значение первого элемента:
std::unordered_set<int> s = {1, 2, 3};
std::unordered_set<int>::iterator it = s.begin();
std::cout << *it << std::endl; // 3
Обратите внимание: итераторы не поддерживают операторы +
, -
и --
. Для перемещения итератора нужно использовать оператор ++
или функцию advance()
. Пример доступа к третьему элементу:
std::unordered_set<int> s = {1, 2, 3, 4};
std::unordered_set<int>::iterator it = s.begin();
std::advance(it, 2);
std::cout << *it << std::endl; // 2
Вместо методов begin()
и end()
можно воспользоваться одноименными функциями. Выведем значение первого элемента:
std::unordered_set<int> s = {1, 2, 3, 4, 5};
std::unordered_set<int>::iterator it = std::begin(s);
std::cout << *it << std::endl; // 5
Перебор элементов
Перебрать все элементы можно с помощью цикла for each
, итераторов и алгоритма for_each()
. Обратите внимание: перебор элементов возможен только в прямом направлении, кроме того, порядок следования элементов может быть произвольным. Пример использования цикла for each
(внутри тела цикла нельзя изменить значение элемента):
std::unordered_set<int> s = {1, 2, 3};
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 3 2 1
Пример перебора элементов с помощью итераторов и цикла for
:
std::unordered_set<int> s = {1, 2, 3};
std::unordered_set<int>::iterator it1, it2;
for (it1 = s.begin(), it2 = s.end(); it1 != it2; ++it1) {
std::cout << *it1 << ' ';
}
std::cout << std::endl; // 3 2 1
Пример перебора элементов с помощью итераторов и цикла while
:
std::unordered_set<int> s = {1, 2, 3};
auto it1 = s.begin(), it2 = s.end();
while (it1 != it2) {
std::cout << *it1++ << ' ';
}
std::cout << std::endl; // 3 2 1
Перебор элементов с помощью алгоритма for_each()
:
std::unordered_set<int> s = {1, 2, 3};
std::for_each( s.begin(), s.end(),
[](auto &el){ std::cout << el << ' '; } );
std::cout << std::endl; // 3 2 1
Реквизиты
ЮMoney (Yandex-деньги): 410011140483022
ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов