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