cpp

Классы 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
Примечание

Учебник C++ (Qt Creator и MinGW)
Учебник C++ (Qt Creator и MinGW) в формате PDF

Реквизиты

ЮMoney (Yandex-деньги): 410011140483022

ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов

cpp