C++. Сборник рецептов

любым диапазоном, для которого можно получить, по крайней мере, двунаправленный итератор, и это выполняется для всех стандартных последовательных контейнеров, включая deque, vector и list.

Смотри также

Рецепт 7.9.

7.8. Выполнение для последовательностей операций над множествами

Проблема

Имеются последовательности, которые требуется реорганизовать с помощью операций над множествами, таких как объединение (union), различие (difference) или пересечение (intersection).

Решение

Для этой цели используйте специальные функции стандартной библиотеки. set_union, set_difference и set_intersection. Каждая из них выполняет соответствующую операцию над множеством и помещает результат в выходной диапазон. Их использование показано в примере 7.8.

Пример 7.8. Использование операций над множествами

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <iterator>
#include 'utils.h' // Для printContainer(): см. 7.10
using namespace std;
int main() {
 cout << 'Введите несколько строк: ';
 istream_iterator<string> start(cin);
 istream_iterator<string> end;
 set<string> s1(start, end);
 cin.clear();
 cout << 'Введите еще несколько строк: ';
 set<string> s2(++start, end);
 set<string> setUnion;
 set<string> setInter;
 set<string> setDiff;
 set_union(s1.begin(), s1.end(), s2.begin(), s2.end(),
  inserter(setUnion, setUnion.begin()));
 set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
  inserter(setDiff, setDiff.begin()));
 set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
  inserter(setInter,setInter.begin()));
 cout << 'Объединение:
';
 printContainer(setUnion);
 cout << 'Различие:
';
 printContainer(setDiff);
 cout << 'Пересечение:
';
 printContainer(setInter);
}

Вывод этой программы выглядит примерно так (printContainer просто печатает содержимое контейнера).

Введите несколько строк: a b c d
^Z
Введите еще несколько строк: d е f g
^Z
Объединение: a b с d e f g
Различие: a b c
Пересечение: d

Обсуждение

Операции с множествами в стандартной библиотеке выглядят и работают сходным образом. Каждая принимает два диапазона, выполняет свою операцию с ними и помешает результаты в выходной итератор. Вы должны убедиться, что для выходной последовательности имеется достаточно места, или использовать inserter или back_inserter (как использовать back_inserter, рассказывается в рецепте 7.5).

Объявление set_union выглядит вот так.

Out set_union(In first1, In last1, In first2, In last2, Out result);

Объявления set_difference, set_intersection и set_symmetric_difference выглядят точно так же.

Чтобы использовать эти функции, сделайте так, как показано в примере 7.8. Например, чтобы найти пересечение двух множеств, вызовите set_intersection вот так.

set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
 inserter(setInter, setInter.begin()));

Последний аргумент set_intersection требует некоторых пояснений, inserter — это шаблон функции, определенный в <iterator>, который принимает контейнер и итератор и возвращает выходной итератор, который при записи в него значения вызывает для первого аргумента inserter метод insert. При его использовании для последовательного контейнера он вставляет значения перед iterator, переданным в качестве второго аргумента. При его использовании для ассоциативного контейнера, как это делается в показанном выше фрагменте кода, этот итератор игнорируется, и элементы вставляются в соответствии с критерием сортировки контейнера.

set — это удобный пример для наших целей, но операции над множествами работают для любых последовательностей, а не только для set. Например, операции над множествами можно выполнить для list:

list<string> lst1, lst2, lst3;
// Заполняем их данными
lst1.sort(); // Элементы должны быть отсортированы
lst2.sort();
set_symmetric_difference(lst1 begin(), lst1.end(),
lst2.begin(), lst2.end(), back_inserter(lst3));

Однако так как list хранит данные в неотсортированном виде, его вначале требуется отсортировать иначе результаты операций над множествами будут неверными. Также обратите внимание, что в этом примере вместо inserter используется back_inserter. back_inserter работает аналогично inserter, за исключением того, что для