C++
Третий вариант программы мы напишем на C++. Поскольку C+ + является почти что расширением С, на нем можно писать как на С (с некоторыми новыми удобствами в обозначениях), а наша изначальная С-версия будет вполне нормальной программой и для C++. Однако при использовании C++ было бы более естественно определить классы для объектов программы — что-то вроде того, что мы сделали на Java — это позволит скрыть некоторые детали реализации. Мы решили пойти даже дальше и использовать библиотеку стандартных шаблонов STL (Standard Template Library), поскольку в ней есть некоторые встроенные механизмы, которые могут выполнить значительную часть необходимой работы. ISO-стандарт C++ включает в себя STL как часть описания языка.
STL предоставляет такие контейнеры, как векторы, списки и множества,
а также ряд основных алгоритмов для поиска, сортировки, добавления и удаления
элементов данных. Благодаря использованию шаблонов C++ каждый алгоритм
STL работает со всевозможными видами контейнеров, включая как типы, описанные
пользователем, так и встроенные типы данных. Контейнеры реализованы как
шаблоны C++, которые инстанцируются для конкретных типов данных; например,
контейнер vector может использоваться для создания конкретных типов vector<int>
или vector<string>. Все операции, описанные в библиотеке для vector, включая стандартные алгоритмы сортировки, можно использовать для таких "производных" типов данных.
В дополнение к контейнеру vector, который схож с Vector в Java, STL предоставляет контейнер deque (дек, гибрид очереди и стека). Дек — это двусторонняя очередь, которая как раз подходит нам для работы с пре-_ фиксами: в ней содержится NPREF элементов, и мы можем выкидывать первый элемент и добавлять в конец новый, обе операции — за время О(1). Дек STL — более общая структура, чем требуется нам, поскольку она позволяет выкидывать и добавлять элементы с обоих концов, но характеристики производительности указывают на то, что нам следует использовать именно ее.
В STL существует также в явном виде и основанный на сбалансированных деревьях контейнер тар, который хранит пары ключ-значение и осуществляет поиск значения, ассоциированного с любым ключом, за 0(log n). Отображения, возможно, не столь эффективны, как О(1) кэш-таблицы, но приятно то, что для их использования не надо писать вообще никакого кода. (Некоторые библиотеки, не входящие в стандарт C++, содержат контейнеры hash или hash_map — они бы подошли просто идеально.)
Кроме всего прочего, мы будем использовать и встроенные функции сравнения, в данном случае они будут сравнивать строки, используя отдельные строки префикса (в которых мы храним отдельные слова!).
Имея в своем распоряжении все перечисленные компоненты, мы пишем код совсем гладко. Вот как выглядят объявления:
typedef deque<string> Prefix;
map<Prefix, vector<string> > statetab;// prefix-> suffixes
Как мы уже говорили, STL предоставляет шаблон дека; запись deque<string> обозначает дек, элементами которого являются строки. Поскольку этот тип встретится в программе несколько раз, мы использовали typedef для присвоения ему осмысленного имени Prefix. А вот тип тар, хранящий префиксы и суффиксы, появится лишь единожды, так что мы не стали давать ему уникального имени; объявление тар описывает переменную statetab, которая является отображением префиксов на векторы строк. Это более удобно, чем в С или Java, поскольку нам не потребуется писать хэш-функцию или метод equals.
В основном блоке инициализируется префикс, считывается вводимый текст (из стандартного потока ввода, который в библиотеке C++ lost ream называется cin), добавляется метка конца ввода и генерируется выходной текст — совсем как в предыдущих версиях:
Функция build использует библиотеку lost ream для ввода слов по одному:
Строка buf будет расти по мере надобности, чтобы в ней помещались вводимые
слова произвольной длины.
В функции add более явно видны преимущества использования STL:
Как вы видите, выражения выглядят совсем не сложно; происходящее "за
кулисами" тоже вполне доступно пониманию простого смертного. Контейнер
тар переопределяет доступ по индексу (операцию[ ]) для того, чтобы он
работал как операция поиска. Выражение statetab[prefix] осуществляет поиск
в statetab по ключу prefix и возвращает ссылку на искомое значение; если
вектора еще не существует, то создается новый. Функция push_back — такая
функция-член класса имеется и в vector, и в deque — добавляет новую строку
в конец вектора или дека; pop^f ront удаляет ("выталкивает")
первый элемент из дека.
Генерация результирующего текста осуществляется практически так же, как и в предыдущих версиях:
Итак, в результате именно эта версия выглядит наиболее понятно и элегантно
— код компактен, структура данных ясно видна, а алгоритм абсолютно прозрачен.
Но, как и за все хорошее в жизни, за это надо платить — данная версия
работает гораздо медленнее, чем версия, написанная на С; правда, это все
же не самый медленный вариант. Вопросы измерения производительности мы
вскоре обсудим.
Упражнение 3-5
Одно из главных преимуществ использования STL состоит в той простоте, благодаря которой можно экспериментировать с различными структурами данных. Попробуйте изменить эту версию, используя различные структуры данных для префиксов, списка суффиксов и таблицы состояний. Посмотрите, как при этом изменяется производительность.
Упражнение 3-6
Перепишите программу на C++ так, чтобы в ней использовались только классы и тип данных string — без каких-либо дополнительных библиотечных средств. Сравните то, что у вас получится, по стилю кода и скорости работы с нашей STL-версией.