"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
#include
#include
using namespace std;
2. Реализуем новый алгоритм в стиле STL, который называется
remove_multi_ whitespace
. Данный алгоритм удаляет избыточные включения пробелов, но не единичные случаи. Это значит, что строка "a b"
останется неизменной, но строка "a b"
будет сокращена до "a b"
. Для этого мы применим функцию std::unique
с пользовательской бинарной функцией-предикатом. Функция std::unqiue
итерирует по диапазону данных и всегда ищет соседствующие элементы. Затем с помощью функции-предиката она определяет, равны ли искомые элементы. Если да, то удаляет один из них. После вызова этой функции диапазон данных не будет содержать поддиапазонов, в которых одинаковые элементы стоят друг рядом с другом. Функции-предикаты, обычно применяемые в этом контексте, говорят, равны ли два элемента. Мы передадим функции std::unique
предикат, который укажет, стоят ли рядом два пробела, чтобы удалить один из них. Как и в случае std::unique
, мы принимаем начальный и конечный итераторы, а затем возвращаем итератор, указывающий на новый конец диапазона данных:
template
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
, и вуаля, лишние пробелы испарились. Хотя в этой главе есть и такие примеры, где приходится попотеть, чтобы выразить наши программы в алгоритмах STL, как раз этот алгоритм особенно красив и краток.Как же работает эта интересная комбинация? Сперва взглянем на возможную реализацию функции
std::unique
:
template
It unique(It it, It end, P p)
{
if (it == end) { return end; }
It result {it};
while (++it != end) {
if (!p(*result, *it) && ++result != it) {
*result = std::move(*it);
}
}
return ++result;
}
Цикл пошагово проходит по элементам диапазона данных до тех пор, пока они не будут удовлетворять условиям предиката. В момент нахождения такого элемента цикл перемещается на один элемент вперед относительно позиции, где предикат сработал в прошлый раз. Та версия функции
std::unique
, которая не принимает дополнительную функцию-предикат, проверяет, равны ли два соседних элемента.Таким образом, она удаляет повторяющиеся символы, например строка
"abbbbbbc"
преобразуется в "abc"
.Нужно удалить не просто все повторяющиеся символы, но и такие же пробелы. Поэтому наш предикат звучит не как «символы-аргументы равны», а как «символы-аргументы являются пробелами».
Последнее, на что нужно обратить внимание: ни функция
std::unique
, ни алгоритм remove_multi_whitespace
на самом деле не удаляют символы из строки. Они только перемещают символы внутри строки в соответствии с их семантикой и говорят, где находится новый конец строки. Однако нам все еще необходимо выполнить удаление теперь уже ненужных символов, стоящих между новым и старым концом строки. Именно поэтому мы написали следующую строку:
s.erase(remove_multi_whitespace(begin(s), end(s)), end(s));
Это похоже на идиому erase-remove, с которой мы познакомились в теме о векторах и списках.
Компрессия и декомпрессия строк
В этом разделе рассматривается довольно популярная задача, которую предлагают на собеседованиях на должность программиста. Вам нужно написать функцию, которая принимает строку наподобие
"aaaaabbbbbbbccc"
и преобразует ее к виду "a5b7c3"
. Запись "a5"
означает, что в строке присутствует пять символов 'a'
, а "b7"
— что в строке семь символов 'b'
. Это очень простой алгоритм сжатия. Для обычного текста он не очень полезен, поскольку обычная речь не такая избыточная, и при ее изложении в виде текста она не станет гораздо короче, воспользуйся мы этой схемой сжатия. Однако алгоритм относительно просто реализовать даже в том случае, когда у нас под рукой есть только доска и фломастеры. Основная хитрость заключается в том, что вы легко можете написать код с ошибками, если программа изначально плохо структурирована. Работать со строками, как правило, не так сложно, но есть вероятность возникновения переполнения буфера в случае применения старомодных функций форматирования.Попробуем решить эту задачу с помощью средств STL.
Как это делается
В этом примере мы реализуем простые функции
compress
и decompress
для строк.
1. Сначала включим некоторые библиотеки STL, а затем объявим об использовании пространства имен