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

Здесь все элементы, которые меньше "foo", перемещаются в начало последовательности. bind2nd здесь необязателен, но он удобен для автоматического создания функтора, который принимает один аргумент и возвращает результат вычисления less(*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

#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 выглядят точно так же.