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

Также можно разделить элементы диапазона в соответствии с каким-либо критерием (функтором), и это является предметом обсуждения рецепта 7.7.

Рецепт 7.7.

7.7. Разделение диапазона

Имеется диапазон элементов, которые требуется каким-либо образом разделить на группы. Например, необходимо переместить в начало диапазона все элементы, которые меньше определенного значения.

Для перемещения элементов используйте стандартный алгоритм partition с предикатом-функтором. См. пример 7.7.

Пример 7.7. Разделение диапазона

#include <iostream>

#include <istream>

#include <string>

#include <vector>

#include <algorithm>

#include <functional>

#include <iterator>

#include "utils.h" // Для printContainer(): см. рецепт 7.10

using namespace std;

int main() {

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

 istream_iterator<string> start(cin);

 istream_iterator<string> end; // Здесь создается "маркер"

 vector<string> v(start, end);

 // Реорганизуем элементы в v так, чтобы те, которые меньше,

 // чем "foo", оказались перед остальными.

 vector<string>::iterator p =

  partition(v.begin(), v.end(),

  bind2nd(less<string>(), "foo"));

 printContainer(v);

 cout << "*p = " << *p << endl;

}

Вывод примера 7.7 выглядит примерно так.

Введите набор строк: a d f j k l

^Z

-----

a d f j k l

*p = j

После работы partition итератор p указывает на первый элемент, для которого less(*p, "foo") не равно true.

partition принимает начало и конец диапазона и предикат и перемешает все элементы, для которых предикат равен true, в начало диапазона. Он возвращает итератор, указывающий на первый элемент, для которого предикат не равен true, или на конец диапазона, если все элементы удовлетворяют предикату. Он объявлен вот так.

Bi partition(Bi first, Bi last, Pred pred);

pred — это функтор, который принимает один аргумент и возвращает true или false. Предиката по умолчанию не существует — вы должны указать такой предикат, который удовлетворяет требованию разделения диапазона. При этом можно написать свой предикат, а можно использовать один из предикатов стандартной библиотеки. Например, в примере 7.7 можно видеть, что я для создания функтора использовал less и bind2nd.

vector<string>::iterator p =

partition(v.begin(), v.end(),

bind2nd(less<string>(), "foo"));

Здесь все элементы, которые меньше "foo", перемещаются в начало последовательности. bind2nd здесь необязателен, но он удобен для автоматического создания функтора, который принимает один аргумент и возвращает результат вычисления less<string>(*i, "foo") для каждого i-го элемента последовательности. Если требуется, чтобы одинаковые элементы сохранили свой первоначальный порядок, то следует использовать stable_partition.

partition и другие алгоритмы, которые меняют порядок элементов диапазона, не работают со стандартными ассоциативными контейнерами set, multiset, map и multimap. Причиной этого является то, что ассоциативные контейнеры хранят свои элементы в упорядоченном виде и перемещать и удалять элементы разрешается только самим контейнерам. Использовать partition можно с любым диапазоном, для которого можно получить, по крайней мере, двунаправленный итератор, и это выполняется для всех стандартных последовательных контейнеров, включая 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 << "Объединение: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 — это шаблон функции, определенный в <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, за исключением того, что для добавления элементов в контейнер он использует 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 - а. Другими словами, симметричная разность — это множество всех элементов, которые присутствуют в одном из множеств, но отсутствуют в другом.