C++17 STL Стандартная библиотека шаблонов — страница 61 из 119

std:

#include 
#include 
#include 
#include 
#include 

using namespace std;

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

template 
tuple 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< помещает символ в поток вывода, следом идет количество включений этого символа в данной части строки. Результатом работы программы является строка, которая автоматически увеличивается по мере работы программы. В конечном счете мы вернем объект типа 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 небезопасна. Более того, ее легко использовать со злым умыслом.

Представьте следующую входную строку: "a00000". Ее сжатие приведет к результату "a1", поскольку в ней содержится только один символ, 'a'. За ним следует пять символов '0', что даст результат "05". Итоговый результат выглядит как "a105". К сожалению, эта сжатая строка гласит: «Символ 'a', повторенный 105 раз». Это не имеет ничего общего с нашей исходной строкой. При ее декомпрессии мы получим строку длиной 105 символов вместо строки, состоящей всего из шести символов. Представьте то же самое для более крупных чисел — пользова тель может легко нарушить использование кучи, поскольку наш алгоритм не готов к таким входным данным.

Чтобы это предотвратить, функция compress может, например, отвергать входные данные, содержащие числа, или особым образом их помечать. А алгоритм decompress способен принимать еще одно условное выражение, которое ограничивает максимальный размер итоговой строки. Попробуйте выполнить данное упражнение самостоятельно. 

Глава 7Строки, классы потоков и регулярные выражения

В этой главе:

□ создание, конкатенация и преобразование строк;

□ удаление пробелов из начала и конца строк;

□ преимущества использования std::string без затрат на создание объектов std::string;

□ чтение значений из пользовательского ввода;

□ подсчет всех слов в файле;

□ форматирование ваших выходных данных с помощью манипуляторов потока ввода/вывода;

□ инициализация сложных объектов из файла вывода;

□ заполнение контейнеров с применением итераторов std::istream;

□ вывод любых данных на экран с помощью итераторов std::ostream;

□ перенаправление выходных данных в файл для конкретных разделов кода;

□ создание пользовательских строковых классов путем наследования std::char_traits;

□ токенизация входных данных с помощью библиотеки для работы с регулярными выражениями;