Классы set и multiset: множества

Класс set реализует множество, состоящее из уникальных элементов, а класс multiset — множество, в котором элементы могут повторяться. Прежде чем использовать классы, необходимо в начало программы добавить инструкцию:

#include <set>

Работа с классами производится аналогичным образом, поэтому в этом разделе мы рассмотрим только возможности класса set.

Примечание

Создание объекта

Объявление класса set:

template<typename _Key, typename _Compare = less<_Key>,
         typename _Alloc = allocator<_Key> >
   class set;

Основные псевдонимы для типов:

typedef _Key key_type;
typedef _Key value_type;
typedef _Compare key_compare;
typedef _Compare value_compare;
typedef _Alloc allocator_type;

Создать экземпляр класса set можно следующими способами (полный список конструкторов смотрите в документации):

  • объявить переменную без инициализации. Для этого перед названием переменной указывается название класса, а после названия внутри угловых скобок задается тип данных элемента. В этом случае множество не содержит элементов. Пример объявления без инициализации:
std::set<int> s;
s.insert(1); s.insert(2);
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 1 2

Внутри угловых скобок после типа данных можно дополнительно указать функцию сравнения:

// #include <functional>
std::set<int, std::less<int> > s;
  • указать объект класса set внутри круглых скобок или после оператора = (доступны конструкторы копирования и перемещения):
std::set<int> s1;
s1.insert(1); s1.insert(2);
std::set<int> s2(s1);
for (auto &el : s2) std::cout << el << ' ';
std::cout << std::endl; // 1 2
  • указать диапазон внутри контейнера с помощью итераторов. В первом параметре передается итератор, указывающий на начало диапазона, а во втором параметре — итератор, указывающий на конец диапазона. Пример:
std::set<int> s1;
s1.insert(1); s1.insert(2);
std::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::set<int> s(arr, arr + ARR_SIZE);
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3
  • указать значения внутри списка инициализации:
std::set<int> s = {1, 2, 3};
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Над двумя объектами класса set определены операции ==, !=, <, <=, > и >=. Кроме того, один объект можно присвоить другому объекту. В этом случае выполняется поэлементное копирование (оператор копирования) или перемещение элементов (оператор перемещения). Пример:

std::set<int> s1 = {1, 2, 3}, s2;
s2 = s1;
for (auto &el : s2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Доступно также присваивание элементов из списка инициализации:

std::set<int> s;
s = {1, 2, 3};
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Вставка элементов

Вставить элементы позволяют следующие методы:

  • 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::set<int> s;
std::pair<std::set<int>::iterator, bool> pr;
s.insert(1);
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; // 1 2

Обратите внимание на то, что метод insert() в классе multiset возвращает итератор, а не объект класса pair. Прототипы метода в классе multiset:

iterator insert(const value_type &x);
iterator insert(value_type &&x);

Можно вставить элементы, имеющие одинаковое значение:

std::multiset<int> s;
s.insert(2);
std::multiset<int>::iterator it = s.insert(2);
std::cout << *it << std::endl; // 2

Третий и четвертый прототипы позволяют подсказать позицию вставки с помощью итератора. Эта позиция может быть проигнорирована, т. к. элементы всегда следуют в строгом порядке. В качестве результата возвращается итератор, указывающий на вставленный элемент. Пример:

std::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::set<int> s1 = {1, 2, 3}, s2;
s2.insert(++s1.begin(), s1.end());
for (auto &el : s2) std::cout << el << ' ';
std::cout << std::endl; // 2 3

Шестой прототип вставляет уникальные элементы из списка инициализации:

std::set<int> s = {1, 2, 3};
s.insert({1, 5, 4});
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3 4 5
  • emplace() — создает элемент и вставляет его во множество. Метод возвращает объект класса pair. Через свойство first будет доступен итератор, указывающий на вставленный элемент, а через свойство second — логическое значение true, если элемент вставлен, и false — в противном случае. Обратите внимание на то, что вставить можно только уникальный элемент. Прототип метода:
template<typename... _Args>
   pair<iterator, bool> emplace(_Args &&... args);

Пример:

std::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; // 1 2 3 4

Обратите внимание на то, что метод emplace() в классе multiset возвращает итератор, а не объект класса pair. Прототип метода в классе multiset:

template<typename... _Args>
   iterator emplace(_Args &&... args);

Можно вставить элементы, имеющие одинаковое значение:

std::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::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; // 0 1 2 3 4
  • swap() — меняет элементы двух контейнеров местами. Прототип метода:
void swap(set &x);

Пример:

std::set<int> s1 = {1, 2, 3}, s2 = {4, 5};
s2.swap(s1);
for (auto &el : s1) std::cout << el << ' ';
std::cout << std::endl; // 4 5
for (auto &el : s2) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Вместо метода swap() можно воспользоваться одноименной функцией:

std::swap(s1, s2);

Определение количества элементов

Для определения количества элементов предназначены следующие методы:

  • size() — возвращает количество элементов в контейнере. Прототип метода:
size_type size() const noexcept;

Пример:

std::set<int> s = {1, 2, 3};
std::cout << s.size() << std::endl; // 3
  • empty() — возвращает значение true, если множество не содержит элементов, и false — в противном случае. Прототип метода:
bool empty() const noexcept;

Пример:

std::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::set<int> s;
std::cout << s.max_size() << std::endl;
// 461168601842738790

Удаление элементов

Для удаления элементов предназначены следующие методы:

  • erase() — удаляет один элемент или элементы из диапазона. Прототипы метода:
size_type erase(const key_type &k);
iterator erase(const_iterator pos);
iterator erase(const_iterator first, const_iterator last);

Первый прототип удаляет элемент с указанным значением и возвращает количество удаленных элементов:

std::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; // 2 3

Второй прототип удаляет элемент на который указывает итератор. Удалим последний элемент:

std::set<int> s = {1, 2, 3};
s.erase(--s.end());
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 1 2

Третий прототип удаляет элементы из диапазона, ограниченного итераторами first и last. Удалим все элементы кроме первого и последнего:

std::set<int> s = {1, 2, 3, 4};
s.erase(++s.begin(), --s.end());
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 1 4
  • clear() — удаляет все элементы. Прототип метода:
void clear() noexcept;

Пример:

std::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::set<int> s1 = {1, 2, 3, 4};
std::cout << s1.count(2) << std::endl; // 1
std::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::set<int> s = {1, 2, 3, 4};
std::set<int>::iterator it = s.find(2);
if (it != s.end()) {
   std::cout << *it << std::endl;   // 2
}
  • lower_bound() — возвращает итератор, установленный на элемент, значение которого больше или равно val. Если элемент не найден, то метод возвращает итератор, указывающий на позицию после последнего элемента. Прототипы метода:
iterator lower_bound(const key_type &val);
const_iterator lower_bound(const key_type &val) const;

Пример:

std::set<int> s = {0, 1, 4, 5};
std::set<int>::iterator it = s.lower_bound(2);
if (it != s.end()) {
   std::cout << *it << std::endl;   // 4
}
it = s.lower_bound(1);
if (it != s.end()) {
   std::cout << *it << std::endl;   // 1
}
  • upper_bound() — возвращает итератор, установленный на элемент, значение которого больше val. Если элемент не найден, то метод возвращает итератор, указывающий на позицию после последнего элемента. Прототипы метода:
iterator upper_bound(const key_type &val);
const_iterator upper_bound(const key_type &val) const;

Пример:

std::set<int> s = {0, 1, 4, 5};
std::set<int>::iterator it = s.upper_bound(1);
if (it != s.end()) {
   std::cout << *it << std::endl;   // 4
}
  • equal_range() — возвращает экземпляр класса pair. Через свойство first будет доступен итератор, являющийся результатом выполнения метода lower_bound(), а через свойство second — итератор, являющийся результатом выполнения метода upper_bound(). Прототипы метода:
pair<iterator, iterator> equal_range(const key_type &val);
pair<const_iterator, const_iterator>
     equal_range(const key_type &val) const;

Пример:

typedef std::set<int> Set;
Set s = {0, 1, 4, 5};
std::pair<Set::iterator, Set::iterator> pr;
pr = s.equal_range(1);   // Значение существует
if (pr.first != s.end()) {
   std::cout << *(pr.first) << std::endl;  // 1
}
if (pr.second != s.end()) {
   std::cout << *(pr.second) << std::endl; // 4
}
pr = s.equal_range(2);   // Значение не существует
if (pr.first != s.end()) {
   std::cout << *(pr.first) << std::endl;  // 4
}
if (pr.second != s.end()) {
   std::cout << *(pr.second) << std::endl; // 4
}
  • begin(), end(), cbegin(), cend(), rbegin(), rend(), crbegin() и crend() — возвращают итераторы (см. разд. 16.1.1). Обратите внимание: изменить значение с помощью итераторов нельзя. Выведем значение первого элемента:
std::set<int> s = {1, 2, 3};
std::set<int>::iterator it = s.begin();
std::cout << *it << std::endl; // 1

Обратите внимание: итераторы множеств не поддерживают операторы + и -. Для перемещения итератора нужно использовать операторы ++ и -- или функцию advance(). Пример доступа к третьему элементу:

std::set<int> s = {1, 2, 3, 4};
std::set<int>::iterator it = s.begin();
std::advance(it, 2);
std::cout << *it << std::endl; // 3

Вместо методов begin() и end() можно воспользоваться одноименными функциями. Выведем значение последнего элемента:

std::set<int> s = {1, 2, 3, 4};
std::set<int>::iterator it = std::end(s);
--it;
std::cout << *it << std::endl; // 4

Перебор элементов

Перебрать все элементы можно с помощью цикла for each, итераторов и алгоритма for_each(). Пример использования цикла for each (внутри тела цикла нельзя изменить значение элемента):

std::set<int> s = {1, 2, 3};
for (auto &el : s) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3

Пример перебора элементов с помощью итераторов и цикла for:

std::set<int> s = {1, 2, 3};
std::set<int>::iterator it1, it2;
for (it1 = s.begin(), it2 = s.end(); it1 != it2; ++it1) {
   std::cout << *it1 << ' ';
}
std::cout << std::endl; // 1 2 3

Пример перебора элементов с помощью итераторов и цикла while:

std::set<int> s = {1, 2, 3};
auto it1 = s.begin(), it2 = s.end();
while (it1 != it2) {
   std::cout << *it1++ << ' ';
}
std::cout << std::endl; // 1 2 3

Перебор элементов с помощью алгоритма for_each():

std::set<int> s = {1, 2, 3};
std::for_each( s.begin(), s.end(),
               [](auto &el){ std::cout << el << ' '; } );
std::cout << std::endl; // 1 2 3

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

Помощь сайту

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

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