C++17 STL Стандартная библиотека шаблонов

3. Алгоритм compress постоянно вызывает функцию occurrences. Таким образом, мы переходим от одной группы символов к другой. Строка r< помещает символ в поток вывода, следом идет количество включений этого символа в данной части строки. Результатом работы программы является строка, которая автоматически увеличивается по мере работы программы. В конечном счете мы вернем объект типа 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); }

Она постоянно считывает символ c и переменную-счетчик n из строкового потока ss. Класс stringstream скрывает от нас возможности, связанные с анализом строки. Отработав успешно, функция возвращает развернутую строку в строковый поток, из которого итоговую строку можно вернуть вызывающей стороне. Если c = 'a' и n = 5, то выражение string(n, c) вернет строку "aaaaa".

Функция compress выглядит более сложно. Мы также написали для нее небольшую вспомогательную функцию. Поэтому сначала взглянем на функцию occurrences. На рис. 6.12 показано, как она работает.

Функция occurences принимает два параметра: итератор, указывающий на начало последовательности символов внутри диапазона данных, и конечный итератор этого набора. С помощью find_if мы находим первый символ, отличный от символа, на который изначально указывал итератор. На рис. 6.12 данный итератор называется diff. Разность между этой новой позицией и старой позицией итератора равна количеству одинаковых элементов (на рис. 6.12 diff-it равно 6). После выполнения подсчетов итератор diff можно использовать повторно для выполнения нового поиска. Так что мы помещаем diff, символ поддиапазона и длину поддиапазона в кортеж и возвращаем его.

Имея подобную информацию, можно переходить от поддиапазона к поддиапазону и помещать промежуточные результаты в сжатую целевую строку:

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

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

  r << c << n;

  it = next_diff;

}

Дополнительная информация

В шаге 4 мы упоминали, что функция decompress небезопасна. Более того, ее легко использовать со злым умыслом.