C++17 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 сохранены в древоподобной структуре. В этом случае одинаковыми являются слова hi how, а затем предложения различаются и разветвляются, как дерево.

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

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

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

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

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

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

template class trie

{

  map tries;