C++. Сборник рецептов - [105]

Рецепт 7.7.

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

Проблема

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

Решение

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

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

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

using namespace std;

int main() {
 cout << "Введите набор строк: ";
 istream_iterator start(cin);
 istream_iterator end; // Здесь создается "маркер"
 vector v(start, end);
 // Реорганизуем элементы в v так, чтобы те, которые меньше,
 // чем "foo", оказались перед остальными.
 vector::iterator p =
  partition(v.begin(), v.end(),
  bind2nd(less(), "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::iterator p =
partition(v.begin(), v.end(),
bind2nd(less(), "foo"));

Здесь все элементы, которые меньше "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

Обсуждение

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