испарились. Хотя в этой главе есть и такие примеры, где приходится попотеть, чтобы выразить наши программы в алгоритмах STL, как раз этот алгоритм особенно красив и краток.

Как же работает эта интересная комбинация? Сперва взглянем на возможную реализацию функции std::unique:

template<typename It, typename P>

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, а затем объявим об использовании пространства имен std:

#include <iostream>

#include <string>

#include <algorithm>

#include <sstream>

#include <tuple>

using namespace std;

2. Для нашего дешевого алгоритма сжатия попробуем найти фрагменты текста, содержащие последовательности одинаковых символов, и выполним для них компрессию. Начиная с некой позиции, нужно найти первый символ диапазона, который отличается от текущего. Для этого используем метод std::find. Затем возвращаем кортеж, содержащий итератор, указывающий на этот первый элемент, символьную переменную c, которая содержится в нашем поддиапазоне, и количество ее включений:

template <typename It>

tuple<It, char, size_t> occurrences(It it, It end_it)

{

  if (it == end_it) { return {it, '?', 0}; }

  const char c {*it};

  const auto diff (find_if(it, end_it,

                   [c](char x) { return c != x; }));

  return {diff, c, distance(it, diff)};

}

3. Алгоритм compress постоянно вызывает функцию occurrences. Таким образом, мы переходим от одной группы символов к другой. Строка r<<c<<n помещает символ в поток вывода, следом идет количество включений этого символа в данной части строки. Результатом работы программы является строка, которая автоматически увеличивается по мере работы программы. В конечном счете мы вернем объект типа string, содержащий сжатую строку:

string compress(const string &s)

{

  const auto end_it (end(s));

  stringstream r;

  for (auto it (begin(s)); it != end_it;) {

    const auto [next_diff, c, n] (occurrences(it, end_it));

    r << c << n;

    it = next_diff;

  }

  return r.str();

}

4. Метод decompress работает аналогично, но выглядит гораздо проще. Он постоянно пытается получить символьное значение из потока ввода, а затем и следующее за ним число. Из этих двух значений он может создать строку, содержащую столько включений символов, сколько указано в числе. В конечном счете мы снова вернем строку из выходного потока. Кстати говоря, данная функция декомпрессии небезопасна. Ее можно легко использовать со злым умыслом. Можете ли вы догадаться как? Мы рассмотрим эту проблему позже.

string decompress(const string &s)

{

  stringstream ss{s};

  stringstream r;

  char c;

  size_t n;

  while (ss >> c >> n) { r << string(n, c); }

  return r.str();

}

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

int main()

{

  string s {"aaaaaaaaabbbbbbbbbccccccccccc"};

  cout << compress(s) << 'n';

  cout << decompress(compress(s)) << 'n';

}

6. Компиляция и запуск программы дадут следующий результат:

$ ./compress

a9b9c11

aaaaaaaaabbbbbbbbbccccccccccc

Как это работает

Эта программа, по сути, состоит из двух функций: compress и decompress.

Функция decompress очень проста, поскольку состоит из объявлений переменных, одной строки кода, которая действительно что-то делает, и следующего за ней выражения return. Строка кода, выполняющего некие действия, выглядит так:

while (ss >> c >> n) { r << string(n, c); }

Она постоянно считывает символ