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

В этой главе:

□ реализация класса префиксного дерева с использованием алгоритмов STL;

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

□ реализация формулы преобразования Фурье с применением численных алгоритмов STL;

□ определение ошибки суммы двух векторов;

□ реализация отрисовщика множества Мандельброта в ASCII;

□ создание собственного алгоритма

split

□ создание полезных алгоритмов на основе стандартных —

gather

□ удаление лишних пробельных символов между словами;

□ компрессия и декомпрессия строк.

Введение

В предыдущей главе мы рассмотрели базовые алгоритмы STL и выполнили с их помощью простые задания, чтобы понять, как работать с типичным интерфейсом библиотеки: большая часть ее алгоритмов в качестве входных и выходных параметров принимает один или более диапазонов данных в виде пар итераторов. Они зачастую также принимают функции-предикаты, пользовательские функции сравнения или же функции преобразования. В конечном счете они в основном возвращают итераторы, поскольку их можно передать другим алгоритмам.

Хотя программисты стремятся делать алгоритмы STL минимального размера, в то же время интерфейсы они стараются разрабатывать максимально обобщенными. Это позволяет использовать код повторно, но он не всегда хорошо выглядит. Опытный разработчик С++, знающий все алгоритмы, быстрее прочитает код других людей, если они пытались выразить большинство своих идей с помощью алгоритмов STL. Мозг программиста скорее проанализирует название хорошо известного алгоритма, чем поймет сложный цикл, выполняющий ту же задачу несколько иным образом.

К этому моменту вы уже научились использовать структуры данных STL настолько интуитивно, что можете обходиться без указателей, необработанных массивов и других устаревших структур. Следующим шагом будет более глубокое изучение алгоритмов STL, чтобы вы поняли, как обойтись без сложных циклов, выражая их в терминах популярных алгоритмов STL. Это позволит значительно повысить ваш уровень, поскольку код станет более коротким, удобочитаемым и обобщенным, а также не будет привязан к структурам данных. Вы практически всегда можете избежать написания циклов вручную и взять код алгоритма из пространства имен и std, но иногда это приводит к тому, что ваш код начинает выглядеть странно. Мы не станем разбираться, какой код выглядит странно, а какой — нет, просто рассмотрим возможные варианты.

В этой главе мы применим алгоритмы STL необычным способом, чтобы исследовать новые горизонты и увидеть, как решать отдельные задачи с помощью современного С++. Кроме того, мы реализуем собственные алгоритмы, которые можно будет легко объединить с существующими структурами данных и другими алгоритмами, разработанными аналогичным способом. Затем мы объединим имеющиеся алгоритмы STL, чтобы получить новые алгоритмы, которых еще не существует. Такие объединенные алгоритмы позволяют создавать более сложные алгоритмы, но при этом они остаются относительно короткими и читабельными. Еще мы узнаем, почему именно алгоритмы STL считаются «аккуратными» и пригодными для многократного использования. Мы сможем принимать наилучшие решения, только рассмотрев все варианты.

Реализуем класс префиксного дерева с использованием алгоритмов STL

Так называемая структура данных префиксного дерева представляет собой интересный способ хранить данные так, чтобы по ним было легко выполнить поиск. При разбиении предложений на списки слов вы зачастую можете объединить первые несколько слов, одинаковых в каждом предложении.

Взглянем на рис. 6.1, где предложения

hi how are you

hi how do you do

Поскольку структура данных префиксного дерева объединяет общие префиксы, она также называется деревом префиксов. Такую структуру нетрудно реализовать с помощью средств, предлагаемых библиотекой STL. Этот раздел посвящен реализации собственного класса префиксного дерева.

Как это делается

В данном примере мы реализуем собственное дерево префиксов с помощью структур данных и алгоритмов, предлагаемых в библиотеке STL.

1. Включим все заголовочные файлы применяемых частей библиотеки STL, а также объявим об использовании пространства имен

std

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

using namespace std;

2. Вся программа посвящена префиксному дереву, для которого нужно реализовать собственный класс. В нашей реализации данное дерево, по сути, является рекурсивным ассоциативным массивом, содержащим ассоциативные массивы. Каждый узел дерева содержит подобный массив, в котором соотносятся объект, имеющий тип

T

template  class trie

{

  map tries;

3. Код для добавления новых последовательностей элементов выглядит довольно просто. Пользователь предоставляет пару итераторов (начальный и конечный), и мы проходим по ним рекурсивно. Если он ввел данные

{1, 2, 3}

1

2

3

[]

std::map

public:

  template 

  void insert(It it, It end_it) {

   if (it == end_it) { return; }

   tries[*it].insert(next(it), end_it);

  }

4. Для удобства определим также отдельные функции, они дают пользователю возможность получить контейнер элементов, которые будут автоматически опрошены на предмет итераторов:

  template 

  void insert(const C &container) {

   insert(begin(container), end(container));

  }

5. Чтобы позволить пользователю написать конструкцию

my_trie.insert({"a", "b", "c"});

initializer_list

  void insert(const initializer_list &il) {

   insert(begin(il), end(il));

  }

6. Мы также хотим видеть содержимое дерева, поэтому нужна функция

print

tries.empty()

true

print

  void print(vector &v) const {

   if (tries.empty()) {

    copy(begin(v), end(v), ostream

      _iterator{cout, " "});

   cout << '\n';

   }

   for (const auto &p : tries) {

    v.push_back(p.first);

    p.second.print(v);

    v.pop_back();

   }

  }

7. Рекурсивная функция

print

print

  void print() const {

   vector v;

   print(v);

  }

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

{a,b,c} {a,b,d,e}

{a,b}

{c}

{d, e}

const

std::optional

  template 

  optional>

  subtrie(It it, It end_it) const {

    if (it == end_it) { return ref(*this); }

   auto found (tries.find(*it));

    if (found == end(tries)) { return {}; }

    return found->second.subtrie(next(it), end_it);

  }

9. Аналогично методу

insert

subtrie

  template 

 auto subtrie(const C &c) {

   return subtrie(begin(c), end(c));

  }

};

10. На этом все. Воспользуемся нашим новым классом

trie

main

trie

std::string

int main()

{

  trie t;

  t.insert({"hi", "how", "are", "you"});

  t.insert({"hi", "i", "am", "great", "thanks"});

  t.insert({"what", "are", "you", "doing"});

  t.insert({"i", "am", "watching", "a", "movie"});

11. Сначала выведем на экран все дерево:

  cout << "recorded sentences:\n";

 t.print();

12. Затем получим поддерево для всех входных предложений, которые начинаются со слова

"hi"

  cout << "\npossible suggestions after \"hi\":\n";

  if (auto st (t.subtrie(initializer_list{"hi"}));

   st) {

     st->get().print();

   }

  }

13. Компиляция и запуск программы покажет, что мы действительно получим всего два предложения, начинающихся со слова

"hi "

$ ./trie

recorded sentences:

hi how are you

hi i am great thanks

i am watching a movie

what are you doing

possible suggestions after "hi":

how are you

i am great thanks

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

Что интересно, код для вставки последовательности слов выглядит короче и проще, чем код поиска заданного слова в поддереве. Поэтому сначала рассмотрим код вставки:

template 

void trie::insert(It it, It end_it) {

 if (it == end_it) { return; }

 tries[*it].insert(next(it), end_it);

}

Пара итераторов

it

end_it

tries[*it]

.insert(next(it), end_it)

if (it == end_it) { return; }

return

tries[*it]

[]

std::map

trie

Поиск в поддереве выглядит более сложным, поскольку мы не можем выразить многие функции неявно:

template 

optional>

subtrie(It it, It end_it) const {

  if (it == end_it) { return ref(*this); }

   auto found (tries.find(*it));

   if (found == end(tries)) { return {}; }

  return found->second.subtrie(next(it), end_it);

}

Данный код, по сути, строится вокруг выражения

auto found (tries.find(*it));

Вместо того чтобы искать следующий по глубине узел дерева с помощью оператора (

[]

find

[]

Еще одной непонятной деталью является возвращаемый тип

optional>

std::optional

"hello my friend"

"goodbye my friend"

{}

reference_wrapper

optional

trie&

reference_wrapper

Создаем генератор поисковых подсказок с помощью префиксных деревьев

Когда вы вводите некие символы в поисковик, интерфейс зачастую пытается определить, как будет выглядеть весь поисковый запрос. Эти догадки зачастую основываются на популярных запросах. Иногда подобные догадки выглядят довольно забавно, поскольку оказывается, что люди вводят в поисковик странные запросы (рис. 6.2).

В этом разделе мы используем класс

trie

Как это делается

В данном примере мы реализуем консольное приложение, которое принимает некие входные данные, а затем пробует определить, что именно пользователь хочет найти, основываясь на небольшой текстовой базе данных.

1. Как и всегда, сначала указываем, что включаем заголовочные файлы, а также объявляем об использовании пространства имен

std

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

using namespace std;

2. Воспользуемся реализацией из предыдущего примера:

template 

class trie

{

  map tries;

public:

  template 

  void insert(It it, It end_it) {

   if (it == end_it) { return; }

   tries[*it].insert(next(it), end_it);

  }

  template 

  void insert(const C &container) {

   insert(begin(container), end(container));

  }

  void insert(const initializer_list 

&il) {

   insert(begin(il), end(il));

  }

  void print(list &l) const {

   if (tries.empty()) {

     copy(begin(l), end(l), ostream_iterator{cout, " "});

     cout << '\n';

   }

   for (const auto &p : tries) {

    l.push_back(p.first);

    p.second.print(l);

    l.pop_back();

   }

  }

  void print() const {

   list l;

   print(l);

  }

  template 

 optional>

  subtrie(It it, It end_it) const {

   if (it == end_it) { return ref(*this); }

   auto found (tries.find(*it));

   if (found == end(tries)) { return {}; }

 return found->second.subtrie(next(it), end_it);

  }

  template 

  auto subtrie(const C &c) const {

   return subtrie(begin(c), end(c));

  }

};

3. Добавим небольшую вспомогательную функцию, которая выводит на экран строку, приглашающую пользователя ввести какой-нибудь текст:

static void prompt()

{

  cout << "Next input please:\n > ";

}

4. В функции

main

int main()

{

  trie t;

  fstream infile {"db.txt"};

  for (string line; getline(infile, line);) {

   istringstream iss {line};

   t.insert(istream_iterator{iss}, {});

  }

5. Теперь, когда мы создали дерево на основе содержимого текстового файла, нужно реализовать интерфейс, который позволит пользователю отправлять запросы. Приглашаем пользователя ввести какой-нибудь текст и ожидаем его действий:

  prompt();

  for (string line; getline(cin, line);) {

   istringstream iss {line};

6. Имея введенный текст, мы делаем запрос к дереву, чтобы получить поддерево. Если у нас есть такая входная последовательность в текстовом файле, то можем вывести на экран возможное продолжение поискового запроса, как делают другие поисковики. При отсутствии соответствующего поддерева просто скажем об этом пользователю:

   if (auto st (t.subtrie(istream_iterator{iss}, {}));

    st) {

     cout << "Suggestions:\n"; st->get().print();

   } else {

    cout << "No suggestions found.\n";

   }

7. Затем снова выведем текст приглашения и подождем следующей строки от пользователя. На этом все.

   cout << "----------------\n";

   prompt();

  }

}

8. Прежде чем запустить программу, следует чем-то заполнить файл

db.txt

do ghosts exist

do goldfish sleep

do guinea pigs bite

how wrong can you be

how could trump become president

how could this happen to me

how did bruce lee die

how did you learn c++

what would aliens look like

what would macgiver do

what would bjarne stroustrup do

...

9. До запуска программы нужно создать файл

db.txt

hi how are you

hi i am great thanks

do ghosts exist

do goldfish sleep

do guinea pigs bite

how wrong can you be

how could trump become president

how could this happen to me

how did bruce lee die

how did you learn c++

what would aliens look like

what would macgiver do

what would bjarne stroustrup do

what would chuck norris do

why do cats like boxes

why does it rain

why is the sky blue

why do cats hate water

why do cats hate dogs

why is c++ so hard

10. Компиляция и запуск программы с последующим вводом некоторых входных данных будут выглядеть так:

$ ./word_suggestion

Next input please:

> what would

Suggestions:

aliens look like

bjarne stroustrup do

chuck norris do

macgiver do

----------------

Next input please:

> why do

Suggestions:

cats hate dogs

cats hate water

cats like boxes

----------------

Next input please:

> 

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

Принцип работы префиксного дерева был показан в предыдущем примере, но способ его заполнения и создания запросов к нему выглядит несколько странно. Давайте подробнее рассмотрим фрагмент кода, который заполняет пустое дерево на основе содержимого текстовой базы данных:

fstream infile {"db.txt"};

for (string line; getline(infile, line);) {

  istringstream iss {line};

 t.insert(istream_iterator{iss}, {});

}

Цикл заполняет строку

line

istringstream

istream_iterator

iss

std::istringstream

std::string

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

std::cin

trie::subtrie

trie::insert

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

Можно добавить в каждый узел дерева переменные-счетчики. Это позволит определить, как часто префикс встречается в некоторых входных данных. На основе этой информации можно отсортировать предположения по частоте их встречаемости, что и делают поисковики. Подсказки, возникающие при наборе текста на смартфоне, также реализованы подобным образом.

Предлагаю вам создать этот вариант генератора подсказок в качестве самостоятельного упражнения.

Реализуем формулу преобразования Фурье с применением численных алгоритмов STL

Преобразование Фурье — это очень важная и очень известная формула в области обработки сигналов. Она была открыта примерно 200 лет назад, но с появлением компьютеров количество вариантов ее использования значительно увеличилось. Она применяется при сжатии аудио/изображений/видео, в аудиофильтрах, медицинских устройствах отображения, приложениях для телефонов, которые определяют, какая песня сейчас играет, и т.д.

Поскольку количество возможных вариантов применения данной формулы довольно велико (и не только преобразования Фурье), STL разрабатывалась так, чтобы приносить пользу и при выполнении вычислений. Преобразование Фурье — лишь один из многих примеров подобных вычислений, при этом не самый простой. Сама формула выглядит так (рис. 6.3):

Преобразование, описываемое этой формулой, по сути, описывает сумму. Каждый элемент суммы является произведением точки графика вектора входного сигнала и выражения

exp(-2*i*...)

N

j

k

csignal fourier_transform(const csignal &s) {

 csignal t(s.size());

  const double pol {-2.0 * M_PI / s.size()};

  for (size_t k {0}; k < s.size(); ++k) {

   for (size_t j {0}; j < s.size(); ++j) {

    t[k] += s[j] * polar(1.0, pol * k * j);

   }

  }

  return t;

}

Тип

csignal

std::complex

std::polar

Эта версия работает хорошо, но давайте реализуем преобразование Фурье с помощью инструментов, доступных в STL.

Как это делается

В данном примере мы реализуем преобразование Фурье, а затем трансформируем с его помощью некоторые сигналы.

1. Сначала включим все необходимые заголовочные файлы и объявим об использовании пространства имен

std

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

using namespace std;

2. Точка графика сигнала представляет собой комплексное число, которое будет выражено с помощью типажа

std::complex

double

cmplx

double

csignal

using cmplx = complex;

using csignal = vector;

3. Чтобы проитерировать по возрастающей численной последовательности, мы возьмем численный итератор из соответствующего примера. Переменные

k

j

class num_iterator {

 size_t i;

public:

  explicit num_iterator(size_t position) : i{position} {}

 size_t operator*() const { return i; }

  num_iterator& operator++() {

   ++i;

   return *this;

  }

  bool operator!=(const num_iterator &other) const {

   return i != other.i;

  }

};

4. Функция преобразования Фурье будет принимать сигнал и возвращать новый. Последний представляет собой преобразование Фурье, выполненное для входного сигнала. Обратное преобразование Фурье выполняется аналогично прямому, поэтому предоставим необязательный параметр булева типа, который указывает на направление преобразования. Обратите внимание: наличие подобных параметров зачастую указывает на плохой стиль программирования, особенно если в сигнатуре функции их несколько. Здесь мы для краткости применили всего один параметр булева типа.

Первое, что нужно сделать, — это выделить память для нового вектора сигналов, имеющего размер исходного сигнала:

csignal fourier_transform(const csignal &s, bool back = false)

{

  csignal t (s.size());

5. В формуле имеются два множителя, которые всегда выглядят одинаково. Поместим их в отдельные переменные:

  const double pol {2.0 * M_PI * (back ? -1.0 : 1.0)};

  const double div {back ? 1.0 : double(s.size())};

6. Алгоритм

std::accumulate

std::accumulat

s

pol

j

accumulate

  auto sum_up ([=, &s] (size_t j) {

   return [=, &s] (cmplx c, size_t k) {

    return c + s[k] *

     polar(1.0, pol * k * j / double(s.size()));

   };

  });

7. Внутренняя часть преобразования Фурье теперь выполняется алгоритмом

std::accumulate

j

  auto to_ft ([=, &s](size_t j){

   return accumulate(num_iterator{0},

            num_iterator{s.size()},

            cmplx{},

           sum_up(j))

   /div;

  });

8. До этого момента мы не выполняли код самого преобразования Фурье. Мы лишь подготовили множество вспомогательного кода, который сейчас и задействуем. Вызов

std::transform

  transform(num_iterator{0}, num_iterator{s.size()},

       begin(t), to_ft);

  return t;

}

9. Реализуем отдельные функции, которые позволяют создать объекты функций для генерации сигналов. Первая из них представляет собой генератор косинусоидального сигнала. Она возвращает лямбда-выражение, способное сгенерировать косинусоидальный сигнал на основе заданной длины периода. Сам сигнал может иметь произвольную длину, но его длина периода будет фиксированной. Длина периода N означает, что сигнал повторит себя спустя N шагов. Лямбда-выражение не принимает никаких параметров. Можно постоянно вызывать его, и для каждого вызова оно будет возвращать точку графика сигнала для следующего момента времени.

static auto gen_cosine (size_t period_len){

 return [period_len, n{0}] () mutable {

   return cos(double(n++) * 2.0 * M_PI / period_len);

  };

}

10. Вторым сигналом будет прямоугольная волна. Она колеблется между значениями

–1

+1

n

+1

–1

period_len

Обратите внимание: в этот раз мы инициализируем n значением, не равным

0

+1

static auto gen_square_wave (size_t period_len)

{

  return [period_len, n{period_len*7/4}] () mutable {

   return ((n++ * 2 / period_len) % 2) * 2 - 1.0;

  };

}

11. Сгенерировать сам сигнал с помощью указанных генераторов можно, выделив память для нового вектора и заполнив его значениями, сгенерированными на основе повторяющихся вызовов функции-генератора. Это делает функция

std::generate

*it = gen()

template 

static csignal signal_from_generator(size_t len, F gen)

{

  csignal r (len);

  generate(begin(r), end(r), gen);

 return r;

}

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

std::transform

static void print_signal (const csignal &s)

{

  auto real_val ([](cmplx c) { return c.real(); });

 transform(begin(s), end(s),

       ostream_iterator{cout, " "}, real_val);

 cout << '\n';

}

13. Мы реализовали формулу Фурье, но у нас еще нет сигналов для преобразования. Создаем их в функции

main

int main()

{

  const size_t sig_len {100};

14. Теперь сгенерируем сигналы, преобразуем их и выведем на экран — это произойдет на трех следующих шагах. Первый шаг — генерация косинусоидального и прямоугольного сигналов. Они имеют одинаковые длину сигнала и длину периода:

  auto cosine (signal_from_generator(sig_len,

       gen_cosine( sig_len / 2)));

  auto square_wave (signal_from_generator(sig_len,

       gen_square_wave(sig_len / 2)));

15. Теперь у нас есть сигналы, представляющие собой косинусоидальную функцию и прямоугольную волну. Чтобы сгенерировать третий сигнал, который будет находиться между ними, возьмем сигнал прямоугольной волны и определим его преобразование Фурье (сохраним его в векторе

trans_sqw

10

(signal_length-10)

0.0

  auto trans_sqw (fourier_transform(square_wave));

  fill (next(begin(trans_sqw), 10), prev(end(trans_sqw), 10), 0);

  auto mid (fourier_transform(trans_sqw, true));

16. Теперь у нас есть три сигнала:

cosine

mid

square_wave

double

 print_signal(cosine);

 print_signal(fourier_transform(cosine));

 print_signal(mid);

 print_signal(trans_sqw);

 print_signal(square_wave);

 print_signal(fourier_transform(square_wave));

17. Компиляция и запуск программы приведут к тому, что экран консоли будет заполнен множеством численных значений. Если мы построим график для полученного результата, то увидим следующее изображение (рис. 6.4).

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

Программа состоит из двух сложных фрагментов. Один из них — само преобразование Фурье, а другой — генерация сигналов с помощью изменяемых лямбда-выражений.

Сначала сконцентрируемся на преобразовании Фурье. Основа реализации формулы, созданной с применением циклов (которой мы не пользовались, а лишь рассмотрели во введении), выглядит так:

for (size_t k {0}; k < s.size(); ++k) {

  for (size_t j {0}; j < s.size(); ++j) {

   t[k] += s[j] * polar(1.0, pol * k * j / double(s.size()));

  }

}

С помощью алгоритмов STL std::transform и std::accumulate мы написали код, который можно подытожить, используя следующий псевдокод:

transform(num_iterator{0}, num_iterator{s.size()}, ...

 accumulate((num_iterator0}, num_iterator{s.size()}, ...

   c + s[k] * polar(1.0, pol * k * j / double(s.size()));

Мы получим точно такой же результат, что и в случае с циклом. Это, вероятно, пример ситуации, когда строгое следование алгоритмам STL не приводит к повышению качества кода. Тем не менее данная реализация алгоритма не знает о выбранной структуре данных. Она также будет работать со списками (однако в нашем случае это не будет иметь особого смысла). Еще одним преимуществом является тот факт, что алгоритмы C++17 STL легко распараллелить (данный вопрос мы рассмотрим в другой главе книги). А вот обычные циклы нужно реструктурировать, чтобы включить поддержку многопроцессорного режима (если только мы не используем внешние библиотеки наподобие OpenMP, в них циклы реструктурируются за нас).

Еще одна сложная часть — генерация сигналов. Еще раз взглянем на

gen_cosine

static auto gen_cosine (size_t period_len)

{

  return [period_len, n{0}] () mutable {

   return cos(double(n++) * 2.0 * M_PI / period_len);

  };

}

Каждый экземпляр лямбда-выражения представляет собой объект функции, который изменяет свое состояние при каждом вызове. Его состояние описывается переменными

period_len

signal_from_generator

template 

static auto signal_from_generator(size_t len, F gen)

{

  csignal r (len);

 generate(begin(r), end(r), gen);

 return r;

}

Эта вспомогательная функция выделяет память для вектора сигнала с заданной длиной и вызывает метод

std::generate

r

gen

gen_cosine

К сожалению, способ решения задачи с помощью STL не позволяет сделать код более элегантным. Ситуация может измениться, если библиотека

ranges

Определяем ошибку суммы двух векторов

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

Существует простая формула для определения этой ошибки между сигналами

a

b

Для каждого значения

i

Как это делается

В этом примере мы создадим два сигнала и посчитаем для них ошибку суммы.

1. Как и обычно, сначала приводим выражения

include

std

#include 

#include 

#include 

#include 

#include 

#include 

using namespace std;

2. Определим ошибку суммы двух сигналов. Таковыми выступят синусоидальная волна и ее копия, только оригинал будет сохранен в векторе, содержащем переменные типа

double

int

double

int

double

as

int

ds

int main()

{

  const size_t sig_len {100};

  vector as (sig_len); // a для аналогового сигнала

 vector ds (sig_len);   // d для цифрового сигнала

3. Чтобы сгенерировать сигнал синусоидальной волны, реализуем небольшое лямбда-выражение, имеющее изменяемое значение счетчика

n

std::generate

std::copy

double

int

  auto sin_gen ([n{0}] () mutable {

   return 5.0 * sin(n++ * 2.0 * M_PI / 100);

  });

  generate(begin(as), end(as), sin_gen);

 copy(begin(as), end(as), begin(ds));

4. Сначала выведем на экран сигналы, чтобы позднее можно было построить для них график:

copy(begin(as), end(as),

 ostream_iterator{cout, " "});

cout << '\n';

copy(begin(ds), end(ds),

  ostream_iterator{cout, " "});

cout << '\n';

5. Теперь перейдем к самой ошибке суммы. Используем метод

std::inner_product

  cout << inner_product(begin(as), end(as), begin(ds),

             0.0, std::plus{},

             [](double a, double b) {

              return pow(a - b, 2);

            })

    << '\n';

}

6. Компиляция и запуск программы приведут к выводу двух длинных строк, содержащих сигналы, и третьей строки, в которой показывается единственное значение — разность сигналов. Эта разность равна

40.889

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

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

std::inner_product

[](double a,double b) { return pow(a-b,2);}

Взглянув на потенциальную реализацию метода

std::inner_product

template

T inner_product(InIt1 it1, InIt1 end1, InIt2 it2, T val,

         F bin_op1, G bin_op2)

{

  while (it1 != end1) {

   val = bin_op1(val, bin_op2(*it1, *it2));

   ++it1;

   ++it2;

  }

  return value;

}

Алгоритм принимает пару итераторов (начальный и конечный) для первого диапазона данных, а также начальный итератор для второго диапазона. В нашем случае они представляют собой векторы, для которых нужно определить ошибку суммы. Следующий символ — исходное значение

val

0.0

bin_op1

bin_op2

К этому моменту мы понимаем, что данный алгоритм очень похож на

std::accumulate

bin_op2(*it1,*it2)

*it

accumulate

std::inner_product

std::accumulate

В нашем случае функция-упаковщик выглядит как

pow(a-b,2)

bin_op1

std::plus

Реализуем отрисовщик множества Мандельброта в ASCII

В 1975 году математик Бенуа Мандельброт (Benoˆt Mandelbrot) придумал термин «фрактал». Это математическое множество с интересными математическими свойствами, которое в конечном счете выглядит как произведение искусства. Фракталы в приближении выглядят так, будто повторяются бесконечно. Одним из самых популярных фракталов является множество Мандельброта, его вы можете увидеть на рис. 6.7.

Рисунок множества Мандельброта можно сгенерировать путем повторения специальной формулы (рис. 6.8).

Переменные

z

c

В STL предусмотрен полезный класс

std::complex

Как это делается

В этом примере мы выведем на консоль такое же изображение, которое было показано на рис. 6.7, в формате ASCII.

1. Сначала включим все заголовочные файлы и объявим об использовании пространства имен

std

#include 

#include 

#include 

#include 

#include 

#include 

using namespace std;

2. Множество Мандельброта и формула работают с комплексными числами. Поэтому определим псевдоним типа

cmplx

double

using cmplx = complex;

3. Вы можете скомпоновать весь код для отрисовки изображения для множества Мандельброта с помощью ASCII примерно за 20 строк кода, но мы реализуем каждый логический шаг отдельно, а затем соберем все воедино. Первый шаг — реализация функции, которая переводит координаты из целых чисел в числа с плавающей точкой. Изначально мы имеем столбцы и строки для всех позиций символов на консоли. Нужно получить координаты с типом

complex

int

double

static auto scaler(int min_from, int max_from,

          double min_to, double max_to)

{

  const int w_from {max_from - min_from};

 const double w_to {max_to - min_to};

 const int mid_from {(max_from - min_from) / 2 + min_from};

 const double mid_to {(max_to - min_to) / 2.0 + min_to};

 return [=] (int from) {

   return double(from - mid_from) / w_from * w_to + mid_to;

  };

}

4. Теперь можно преобразовать точки в одном измерении, но множество Мандельброта существует в двумерной системе координат. Чтобы выполнить преобразование из одной системы координат

(x, y)

scaler_x

scaler_y

cmplx

template 

static auto scaled_cmplx(A scaler_x, B scaler_y)

{

  return [=](int x, int y) {

   return cmplx{scaler_x(x), scaler_y(y)};

  };

}

5. После получения возможности преобразовывать координаты в правильные измерения можно реализовать множество Мандельброта. Функция, которую мы реализуем, сейчас ничего не знает о концепции консольных окон или линейного тангенциального преобразования, поэтому можно сконцентрироваться на математике, описывающей множество Мандельброта. Возводим в квадрат значение

z

2

max_iterations

static auto mandelbrot_iterations(cmplx c)

{

  cmplx z {};

  size_t iterations {0};

  const size_t max_iterations {1000};

  while (abs(z) < 2 && iterations < max_iterations) {

   ++iterations;

   z = pow(z, 2) + c;

  }

  return iterations;

}

6. Теперь можно начать с функции

main

scale

int main()

{

  const size_t w {100};

 const size_t h {40};

 auto scale (scaled_cmplx(

   scaler(0, w, -2.0, 1.0),

   scaler(0, h, -1.0, 1.0)

  ));

7. Чтобы выполнить линейный перебор всего изображения, напишем еще одну функцию преобразования, которая принимает одномерную координату

i

(x, y)

i

scale

  auto i_to_xy ([=](int i) { return scale(i % w, i / w); });

8. Сейчас можно преобразовать одномерные координаты (с типом

int

(int, int)

cmplx

int

  auto to_iteration_count ([=](int i) {

   return mandelbrot_iterations(i_to_xy(i));

  });

9. Теперь подготовим все данные. Предположим, что итоговое изображение ASCII имеет w символов в длину и h символов в ширину. Его можно сохранить в одномерном векторе, который имеет

w*h

std::iota

0...(w*h–1)

to_iteration_count

  vector v (w * h);

 iota(begin(v), end(v), 0);

  transform(begin(v), end(v), begin(v), to_iteration_count);

10. На этом, по сути, все. Теперь у нас есть вектор v, который мы инициализировали одномерными координатами и переписали счетчиком итераций для множества Мандельброта. На его основе можно вывести красивое изображение. Можно сделать окно консоли длиной w символов, чтобы не выводить на экран символ перевода строки. Но мы можем также нестандартно использовать алгоритм

std::accumulate

*

50

n

w

  auto binfunc ([w, n{0}] (auto output_it, int x) mutable {

    *++output_it = (x > 50 ? '*' : ' ');

    if (++n % w == 0) { ++output_it = '\n'; }

     return output_it;

  });

11. Вызывая функцию

std::accumulate

print

ostream_iterator

  accumulate(begin(v), end(v), ostream_iterator{cout},

        binfunc);

}

12. Компиляция и запуск программы приводят к следующему результату, который выглядит как изначальное детализированное множество Мандельброта в упрощенной форме (рис. 6.9).

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

Все расчеты происходят во время вызова

std::transform

vector v (w * h);

iota(begin(v), end(v), 0);

transform(begin(v), end(v), begin(v), to_iteration_count);

Что же произошло и почему это работает именно так? Функция

to_iteration_count

i_to_xy

scale

mandelbrot_iterations

Подобным способом в качестве входного параметра можно использовать индекс одномерного массива и получать количество итераций множества Мандельброта для точки двумерной плоскости, которую представляет точка массива. К счастью, эти три преобразования совершенно не взаимозависимы. Модули подобного кода можно легко протестировать отдельно друг от друга. Таким образом, находить и исправлять ошибки очень легко, как и просто утверждать о корректности кода.

Создаем собственный алгоритм split

В некоторых ситуациях существующих алгоритмов STL недостаточно. Но ничто не запрещает нам реализовать собственный алгоритм. Прежде чем решать конкретную задачу, следует тщательно ее обдумать, чтобы понять: многие задачи можно решить путем обобщения. Если мы будем регулярно добавлять в наши библиотеки новый код по мере решения собственных задач, то можем помочь коллегам-программистам, у которых появятся аналогичные задачи. Идея заключается в том, чтобы знать, когда ваш код является достаточно обобщенным и когда не нужно обобщать его еще больше, в противном случае у нас получится новый язык общего назначения.

В этом примере мы реализуем алгоритм, который назовем

split

Как это делается

В данном примере мы реализуем собственный алгоритм

split

1. Сначала включим некоторые части библиотеки STL и объявим об использовании пространства имен

std

#include 

#include 

#include 

#include 

#include 

using namespace std;

2. Алгоритм, показанный в этом разделе, предназначен для разбиения диапазонов данных. Он принимает начальный и конечный итераторы, а также итератор вывода, что поначалу делает его похожим на алгоритмы

std::copy

std::transform

split_val

bin_func

split_val

bin_func

std::find

split_val

template 

InIt split(InIt it, InIt end_it, OutIt out_it, T split_val,

      F bin_func)

{

  while (it != end_it) {

   auto slice_end (find(it, end_it, split_val));

   *out_it++ = bin_func(it, slice_end);

   if (slice_end == end_it) { return end_it; }

   it = next(slice_end);

  }

  return it;

}

3. Воспользуемся новым алгоритмом. Создадим строку, которую затем разобьем на части. Элементом, отмечающим конец последнего фрагмента и начало следующего, будет дефис

'-'

int main()

{

  const string s {"a-b-c-d-e-f-g"};

4. Когда алгоритм вызывает функцию

bin_func

  auto binfunc ([](auto it_a, auto it_b) {

   return string(it_a, it_b);

  });

5. Выходной диапазон данных представляет собой список строк. Мы вызовем алгоритм

split

  list l;

  split(begin(s), end(s), back_inserter(l), '-', binfunc);

6. Чтобы увидеть полученное, выведем на экран новый список разбитых строк:

  copy(begin(l), end(l), ostream_iterator{cout, "\n"}); 

}

7. Компиляция и запуск программы дадут следующий результат. Он не содержит дефисов и показывает, что включает отдельные слова (которые в нашем примере являются отдельными символами):

$ ./split

a

b

c

d

e

f

g

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

Алгоритм

split

std::transform

split_val

template 

InIt split(InIt it, InIt end_it, OutIt out_it, T split_val, F bin_func)

{

  while (it != end_it) {

   auto slice_end (find(it, end_it, split_val));

   *out_it++ = bin_func(it, slice_end);

   if (slice_end == end_it) { return end_it; }

   it = next(slice_end);

  }

  return it;

}

Цикл требует выполнять перебор до конца входного диапазона данных. Во время каждой итерации вызов

std::find

split_val

'-'

slice_end

it

В данной комбинации итератор

it

slice

slice_end

"foo-bar-baz"

bin_func

split

[](auto it_a, auto it_b) {

 return string(it_a, it_b);

}

Функция

split

bin_func

bin_func

"foo"

"bar"

"baz"

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

Интересной альтернативой реализации нашего алгоритма, разбивающего строки на части, является реализация итератора, который делает то же самое. Мы сейчас не будем реализовывать такой итератор, но кратко рассмотрим подобный сценарий.

Этот итератор должен перескакивать между разделителями при каждом инкременте. При разыменовании ему следует создавать объект строки на основе позиции, на которую он сейчас указывает, что можно сделать с помощью бинарной функции

binfunc

Если бы наш класс итератора назывался

split_iterator

split

string s {"a-b-c-d-e-f-g"};

list l;

auto binfunc ([](auto it_a, auto it_b) {

 return string(it_a, it_b);

});

copy(split_iterator{begin(s), end(s), '-', binfunc},{}, back_inserter(l));

Недостатком описанного подхода служит тот факт, что реализовать итератор сложнее, чем одну функцию. Кроме того, существует множество узких моментов в коде итератора, которые могут привести к появлению ошибок, поэтому такое решение требует более серьезного тестирования. С другой стороны, очень легко объединить подобный итератор с другими алгоритмами библиотеки STL.

Создаем полезные алгоритмы на основе стандартных алгоритмов gather

Алгоритм

gather

Алгоритм

gather

Как это делается

В данном примере мы реализуем алгоритм

gather

1. Сначала добавим все выражения

include

std

#include 

#include 

#include 

#include 

using namespace std;

2. Алгоритм

gather

gather_pos

gather_pos

std::stable_partition

gather

stable_partition

template 

pair gather(It first, It last, It gather_pos, F predicate)

{

  return {stable_partition(first, gather_pos, not_fn(predicate)),

      stable_partition(gather_pos, last, predicate)};

}

3. Еще одним вариантом реализации является

gather_sort

gather

gather_pos

template 

void gather_sort(It first, It last, It gather_pos, F comp_func)

{

  auto inv_comp_func ([&](const auto &...ps) {

   return !comp_func(ps...);

  });

  stable_sort(first, gather_pos, inv_comp_func);

 stable_sort(gather_pos, last, comp_func);

}

4. Воспользуемся этими алгоритмами. Начнем с предиката, который указывает, является ли заданный символьный аргумент символом

'a'

'a'

'_'

int main()

{

  auto is_a ([](char c) { return c == 'a'; });

 string a {"a_a_a_a_a_a_a_a_a_a_a"};

5. Создадим итератор, который указывает на середину нашей новой строки. Вызовем для нее алгоритм

gather

'a'

  auto middle (begin(a) + a.size() / 2);

  gather(begin(a), end(a), middle, is_a);

 cout << a << '\n';

6. Снова вызовем данный алгоритм, но в этот раз итератор

gather_pos

  gather(begin(a), end(a), begin(a), is_a);

 cout << a << '\n';

7. В третьем вызове соберем элементы вокруг конечного итератора:

  gather(begin(a), end(a), end(a), is_a);

 cout << a << '\n';

8. При последнем вызове алгоритма

gather

  // Это работает не так, как вы того ожидаете

  gather(begin(a), end(a), middle, is_a);

 cout << a << '\n';

9. Создадим еще одну строку, содержащую символы подчеркивания и числа. Для этой входной последовательности вызовем функцию

gather_sort

gather_pos

std::less

  string b {"_9_2_4_7_3_8_1_6_5_0_"};

 gather_sort(begin(b), end(b), begin(b) + b.size() / 2,

        less{});

 cout << b << '\n';

}

10. Компиляция и запуск программы даст следующий интересный результат. Первые три строки выглядят так, как мы и ожидали, но четвертая строка — так, будто алгоритм gather не отработал.

В последней строке можно увидеть результат работы функции gather_short. Числа выглядят отсортированными в обоих направлениях.

$ ./gather

_____aaaaaaaaaaa_____

aaaaaaaaaaa__________

__________aaaaaaaaaaa

__________aaaaaaaaaaa

_____9743201568______

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

Изначально алгоритм

gather

1. В самом начале у нас есть диапазон элементов, для которого мы предоставляем функцию-предикат. На рис. 6.11 все элементы, для которых функция-предикат возвращает значение

true

a

c

а

b

2. Алгоритм

gather

std::stable_partition

[a, b]

std::stable_partition

true

3. Выполняется еще один вызов

std::stable_partition

[b, c]

без

b

4. Теперь элементы собраны вокруг итератора

b

Мы несколько раз вызвали алгоритм

gather

begin()

end()

std::stable_partition

Для последнего вызова

gather

(begin, end, middle)

Представьте, что у нас есть диапазон символов

"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

Как это делается

В этом примере мы реализуем алгоритм

remove_multi_whitespace

1. Как и всегда, сначала приведем несколько директив

include

#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

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

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)};

}

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 способен принимать еще одно условное выражение, которое ограничивает максимальный размер итоговой строки. Попробуйте выполнить данное упражнение самостоятельно.