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

Эта сложная задача была решена без привлечения циклов и сравнения элементов вручную. Мы только предоставили функцию-предикат, указывающую, являются ли заданные два символа пробелами. Затем передали этот предикат в функцию 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, а затем объявим об использовании пространства имен 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)};

}