Пособие по практике программирования

         

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-версией.


Содержание раздела