мы увидим почему:
// Это работает не так, как вы того ожидаете
gather(begin(a), end(a), middle, is_a);
cout << a << 'n';
9. Создадим еще одну строку, содержащую символы подчеркивания и числа. Для этой входной последовательности вызовем функцию gather_sort. Итератор gather_pos находится в середине строки, воспользуемся бинарной функцией сравнения std::less<char>:
string b {"_9_2_4_7_3_8_1_6_5_0_"};
gather_sort(begin(b), end(b), begin(b) + b.size() / 2,
less<char>{});
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) и не получили результат. Почему? На первый взгляд это похоже на баг, но на самом деле все не так.
Представьте, что у нас есть диапазон символов "aabb" и функция-предикат is_character_a, которая возвращает значение true для элементов 'a', — если мы вызовем ее с третьим итератором, указывающим на середину диапазона символов, то увидим такой же баг. Причина заключается в том, что первый вызов stable_ partition будет работать с диапазоном "aa", а второй — с диапазоном "bb". Эта последовательность вызовов не даст получить результат "baab", на который мы наивно надеялись.
Чтобы получить желаемый результат в последнем случае, можно было бы использовать вызов std::rotate(begin, begin + 1, end);
Модификация gather_sort, по сути, аналогична алгоритму gather. Единственное отличие заключается в следующем: она принимает не унарную функцию-предикат, а бинарную функцию сравнения, как и std::sort. И вместо того, чтобы дважды вызывать std::stable_partition, она дважды вызывает std::stable_sort.
Функцию инвертирования сравнения нельзя реализовать с помощью not_fn, как мы это делали для алгоритма gather, поскольку not_fn не работает с бинарными функциями.
Удаляем лишние пробелы между словами
Зачастую полученные от пользователей строки могут иметь самое разное форматирование, и их нужно отредактировать. Например, нужно удалить повторяющиеся пробелы.
В этом разделе мы реализуем быстрый алгоритм удаления таких пробелов, который сохраняет одиночные пробелы. Мы назовем данный алгоритм remove_multi_whitespace, его интерфейс будет похож на интерфейсы алгоритмов STL.
Как это делается
В этом примере мы реализуем алгоритм remove_multi_whitespace и проверим его работоспособность.
1. Как и всегда, сначала приведем несколько директив include и объявим об использовании пространства имен std:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
2. Реализуем новый алгоритм в стиле STL, который называется remove_multi_ whitespace. Данный алгоритм удаляет избыточные включения пробелов, но не единичные случаи. Это значит, что строка "a b" останется неизменной, но строка "a b" будет сокращена до "a b". Для этого мы применим функцию std::unique с пользовательской бинарной функцией-предикатом. Функция std::unqiue итерирует по диапазону данных и всегда ищет соседствующие элементы. Затем с помощью функции-предиката она определяет, равны ли искомые элементы. Если да, то удаляет один из них. После вызова этой функции диапазон данных не будет содержать поддиапазонов, в которых одинаковые элементы стоят друг рядом с другом. Функции-предикаты, обычно применяемые в этом контексте, говорят, равны ли два элемента. Мы передадим функции std::unique предикат, который укажет, стоят ли рядом два пробела, чтобы удалить один из них. Как и в случае std::unique, мы принимаем начальный и конечный итераторы, а затем возвращаем итератор, указывающий на новый конец диапазона данных:
template <typename It>
It remove_multi_whitespace(It it, It end_it)
{
return unique(it, end_it, [](const auto &a, const auto &b) {
return isspace(a) && isspace(b);
});
}
3. На этом все. Создадим строку, которая содержит лишние пробелы.
int main()
{
string s {"fooo bar t baz"}; cout << s << 'n';
4. Теперь воспользуемся идиомой erase-remove, чтобы избавиться от этих пробелов:
s.erase(remove_multi_whitespace(begin(s), end(s)), end(s));
cout << s << 'n';
}
5. Компиляция и запуск программы дадут следующий результат:
$ ./remove_consecutive_whitespace
fooo bar baz
fooo bar baz
Как это работает
Эта сложная задача была решена без привлечения циклов и сравнения элементов вручную. Мы только предоставили функцию-предикат, указывающую, являются ли заданные два символа пробелами. Затем передали этот предикат в функцию std::unique, и вуаля, лишние пробелы
