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 существует также в явном виде и основанный на сбалансированных деревьях контейнер тар, который хранит пары ключ-значение и осуществляет поиск значения, ассоциированного с любым ключом, за O(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), добавляется метка конца ввода и генерируется выходной текст – совсем как в предыдущих версиях:
