Создаем полезные алгоритмы на основе стандартных алгоритмов gather
Алгоритм
gather
— очень хороший пример компонуемости алгоритмов STL. Шон Пэрент (Sean Parent), будучи старшим научным сотрудником в компании Adobe Systems, популяризировал данный алгоритм, поскольку он полезен и краток. Способ его реализации идеально подчеркивает идею STL-компоновки алгоритмов.Алгоритм
gather
работает для диапазонов данных произвольных типов. Он изменяет порядок элементов так, что конкретные элементы собираются вокруг заданной позиции, выбранной вызывающей стороной.
Как это делается
В данном примере мы реализуем алгоритм
gather
и его дополнительную вариацию. После этого посмотрим, как его можно использовать.
1. Сначала добавим все выражения
include
. Затем объявим об использовании пространства имен std
:
#include
#include
#include
#include
using namespace std;
2. Алгоритм
gather
представляет собой хороший пример компоновки стандартных алгоритмов. Он принимает начальный и конечный итераторы, а также еще один итератор gather_pos
, который указывает на какую-то позицию между ними. Последний параметр — функция-предикат. С ее помощью алгоритм поместит все элементы, соответствующие заданному условию, в позиции рядом с итератором gather_pos
. Реализация перемещения элементов выполняется благодаря std::stable_partition
. Алгоритм gather
возвращает пару итераторов. Они возвращаются вызовом stable_partition
и, таким образом, отмечают начало и конец полученного диапазона:
template
pair gather(It first, It last, It gather_pos, F predicate)
{
return {stable_partition(first, gather_pos, not_fn(predicate)),
stable_partition(gather_pos, last, predicate)};
}
3. Еще одним вариантом реализации является
gather_sort
. Он работает так же, как и gather
, но принимает не унарную функцию-предикат, а бинарную функцию сравнения. Это позволит собрать значения вокруг позиции gather_pos
, они могут быть как самыми маленькими, так и самыми большими:
template
void gather_sort(It first, It last, It gather_pos, F comp_func)
{
auto inv_comp_func ([&](const auto &...ps) {
return !comp_func(ps...);
});
stable_sort(first, gather_pos, inv_comp_func);
stable_sort(gather_pos, last, comp_func);
}
4. Воспользуемся этими алгоритмами. Начнем с предиката, который указывает, является ли заданный символьный аргумент символом
'a'
. Мы создадим строку, состоящую из комбинации символов 'a'
и '_'
:
int main()
{
auto is_a ([](char c) { return c == 'a'; });
string a {"a_a_a_a_a_a_a_a_a_a_a"};
5. Создадим итератор, который указывает на середину нашей новой строки. Вызовем для нее алгоритм
gather
и посмотрим, что произойдет. В результате вызова символы 'a'
будут собраны в середине строки:
auto middle (begin(a) + a.size() / 2);
gather(begin(a), end(a), middle, is_a);
cout << a << '\n';
6. Снова вызовем данный алгоритм, но в этот раз итератор
gather_pos
будет указывать не на середину строки, а на ее начало:
gather(begin(a), end(a), begin(a), is_a);
cout << a << '\n';
7. В третьем вызове соберем элементы вокруг конечного итератора:
gather(begin(a), end(a), end(a), is_a);
cout << a << '\n';
8. При последнем вызове алгоритма
gather
снова попробуем собрать все символы в середине. Этот вызов сработает не так, как нам бы того хотелось, и далее мы увидим почему:
// Это работает не так, как вы того ожидаете
gather(begin(a), end(a), middle, is_a);
cout << a << '\n';
9. Создадим еще одну строку, содержащую символы подчеркивания и числа. Для этой входной последовательности вызовем функцию
gather_sort
. Итератор gather_pos
находится в середине строки, воспользуемся бинарной функцией сравнения std::less
:
string b {"_9_2_4_7_3_8_1_6_5_0_"};
gather_sort(begin(b), end(b), begin(b) + b.size() / 2,
less{});
cout << b << '\n';
}
10. Компиляция и запуск программы даст следующий интересный результат. Первые три строки выглядят так, как мы и ожидали, но четвертая строка — так, будто алгоритм gather не отработал.
В последней строке можно увидеть результат работы функции gather_short. Числа выглядят отсортированными в обоих направлениях.
$ ./gather
_____aaaaaaaaaaa_____
aaaaaaaaaaa__________
__________aaaaaaaaaaa
__________aaaaaaaaaaa
_____9743201568______
Как это работает
Изначально алгоритм
gather
сложно понять, поскольку он очень короткий, но при этом выполняет задачу, которая кажется сложной. Разберем ее по шагам (рис. 6.11).1. В самом начале у нас есть диапазон элементов, для которого мы предоставляем функцию-предикат. На рис. 6.11 все элементы, для которых функция-предикат возвращает значение
true
, окрашены в серый цвет. Итераторы a
и c
отмечают весь диапазон, а
итератор b
указывает на направляющий элемент. Таковым является элемент, вокруг которого мы хотим собрать все серые элементы.2. Алгоритм
gather
вызывает функцию std::stable_partition
для диапазона данных [a, b]
и в то же время использует инвертированную версию предиката. Он инвертирует предикат, поскольку функция std::stable_partition
перемещает все элементы, для которых предикат возвращает значение true
, в переднюю часть диапазона данных. Нужно, чтобы произошло противоположное.3. Выполняется еще один вызов
std::stable_partition
, однако на сей раз для диапазона данных [b, c]
, без
инвертирования предиката. Серые элементы перемещаются в начало входного диапазона данных; это значит, что они перемещаются к направляющему элементу, на который указывает итератор b
.4. Теперь элементы собраны вокруг итератора
b
и алгоритм возвращает итераторы, указывающие на начало и конец диапазона данных, содержащего серые элементы.
Мы несколько раз вызвали алгоритм
gather
для одного диапазона данных. Сначала собрали все элементы в середине диапазона данных. Затем собрали их в begin()
и end()
этих диапазонов. Эти случаи интересны тем, что всегда приводят один из вызовов std::stable_partition
к работе с пустым диапазоном данных, а это влечет бездействие.Для последнего вызова
gather
мы передали параметры (begin, end, middle)
и не получили результат. Почему? На первый взгляд это похоже на баг, но на самом деле все не так.Представьте, что у нас есть диапазон символов