Д. Стефенс - C++. Сборник рецептов

Рецепт 7.9.

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

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

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

#include

#include

#include

#include

#include

#include "utils.h" // Для printContainer(): см. 7.10

using namespace std;

int main() {

cout << "Введите несколько строк: ";

istream_iterator start(cin);

istream_iterator end;

set s1(start, end);

cin.clear();

cout << "Введите еще несколько строк: ";

set s2(++start, end);

set setUnion;

set setInter;

set 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 << "Объединение:\n";

printContainer(setUnion);

cout << "Различие:\n";

printContainer(setDiff);

cout << "Пересечение:\n";

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

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

list 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, за исключением того, что для добавления элементов в контейнер он использует push_back. Вы не обязаны действовать точно так же. Например, можно изменить размер выходного контейнера так, чтобы он стал достаточно большим

lst3.resize(lst1.size() + lst2.size()),

set_symmetric_difference(lst1.begin(), lst1.end(),

lst2.begin(), lst2.end(), lst3.begin());

Если выходная последовательность будет достаточно большой, то можно просто передать итератор, указывающий на первый элемент последовательности, используя begin.

Если вы не знаете, что такое set_symmetric_difference, я вам расскажу. Это объединение разностей двух множеств, определенных в прямом и обратном порядке. Это значит, что если а и b — это множества, то симметричная разность — это а - b b - а. Другими словами, симметричная разность — это множество всех элементов, которые присутствуют в одном из множеств, но отсутствуют в другом.

Есть еще один момент, который следует знать при работе с операциями над множествами. Так как последовательности не обязаны быть уникальными, можно получить «множество» с повторяющимися значениями. Конечно, строго математически множество не может содержать повторяющиеся значения, так что этот момент может быть не очевиден, Рассмотрим, как будет выглядеть вывод примера 7.8, если вместо setиспользовать list(при запуске примера 7.8 можно вводить повторяющиеся значения, но они не будут добавлены в set, так как set::insertне выполняется для элементов, которые уже присутствуют в set).

Введите несколько строк: a a a b с с

^Z

Введите еще несколько строк: a a b b с

^Z

Объединение a a a b b с с

Различие: a c

Пересечение: a a b с

Здесь операции над множествами перебирают обе последовательности и сравнивают соответствующие значения, определяя, что следует поместить в выходную последовательность.

Наконец, операции над множествами в их оригинальном виде (использующие для сравнения элементов operator<) могут не работать так, как вам требуется, если последовательности содержат указатели. Чтобы обойти эту проблему, напишите функтор, который сравнивает объекты указателей, как в рецепте 7.4.

Рецепт 7.4.

Имеется последовательность элементов, и с каждым элементом требуется выполнить какие-либо действия — либо на месте, либо скопировав их в другую последовательность.

Используйте стандартные алгоритмы transformили for_each. Они оба просты, но позволяют выполнить почти любые действия с элементами последовательностей. Пример 7.9 показывает, как это делается.