|
ПРИМЕЧАНИЕ
В силу особенностей языка C++ в реализации абстрактного типа на основе статического полиморфизма лучше объявлять имена реализации методов отличными от имен объявлений этих методов в шаблонном интерфейсе. В противном случае, если, по какой-то причине, в классе-реализации не будет метода с вызываемым именем, произойдет рекурсивный вызов метода шаблонного интерфейса и программа войдет в бесконечную рекурсию. Именно по этой причине в вызовах методов добавлены суффиксы «impl».
Теперь достаточно чуть изменить объявление класса ArrayStack, оставив реализацию операций без изменений, только добавив к именам методов суффиксы «_impl», чтобы заработал статический полиморфизм:
class ArrayStack : public Stack {
// Массив реализуется на основе типа std::vector стандартной библиотеки C++
std::vector array_;
public:
void push_impl(unsigned int elem) {
array_.push_back(elem);
}
unsigned int top_impl() {
if (array_.empty()) {
throw std::invalid_argument(“the stack is empty”);
}
return array_.back();
}
void pop_impl() {
if (array_.empty()) {
throw std::invalid_argument(“the stack is empty”);
}
array_.pop_back();
}
bool empty_impl() {
return array_.empty();
}
};
|
Полиморфизм разрешается на этапе компиляции программы, поэтому функция, реализующая подстановку реализации АТД, также должна быть шаблонной:
template
bool CheckFirstAxiom(Stack* stack) {
stack->push(123);
if (stack.top() != 123) {
returnfalse;
}
returntrue;
}
|
В качестве параметра функции по-прежнему передается указатель на объект класса ArrayStack, но разрешение реализации операций производится на этапе компиляции программы.
К сожалению, в языке C++ не реализована эффективным образом возможность связывания реализации АТД с его объявлением на этапе линкования модулей программы. Это полезно при разработке библиотек функций, которые требуют от клиента реализации специфицированного в библиотеке АТД. Например, некая библиотека проводит разбор файлов определенного формата и ожидает от пользователя реализации АТД Interpreter, чтобы вызывать операции этого типа для передачи сведений о результатах анализа. На этапе компиляции библиотеки ее разработчики не знают о том, каким образом информация, предоставляемая разборщиком формата, будет использоваться клиентом. Кроме того, не всегда возможно показывать код библиотеки клиенту, что придется делать при реализации концепции АТД на основе шаблонов. Поэтому связывание на основе шаблонов здесь не годится.
В языках, основанных на парадигмах, отличных от ООП, концепция АТД, очевидно, должна быть реализована по-другому. Рассмотрим, например, как концепция АТД реализуется в языке Haskell. В этом языке АТД можно задавать в модулях. Модуль позволяет описывать типы и набор операций, который виден пользователям модуля. Вот, например, как можно описать абстрактный тип Stack:
module Stack (Stack, create, push, top, pop, empty) where
create :: Stack a
push :: Stack a -> a -> Stack a
top :: Stack a -> a
pop :: Stack a -> Stack a
empty :: Stack a -> Bool
|
Синтаксис языка Haskell позволяет описывать абстрактные типы данных более ясно. Задается модуль Stack, предоставляющий операции, и тип Stack, параметризуемый типом его содержимого. Для операций описывают их арность, типы аргументов и возвращаемых значений. В языке Haskell типы аргументов задаются не в виде декартового произведения соответствующих типов, а с помощью функций, берущих в качестве аргументов другие функции. Соответствие между этими двумя типами описания аргументов называется карированием. Здесь мы на этом не будем подробно останавливаться.
Реализацию АТД Stack также можно задать в модуле Stack следующим образом:
newtype Stack a = StackImpl [a]
create = StackImpl []
push (StackImpl s) x = StackImpl (x:s)
top (StackImpl s) = head s
pop (StackImpl (s:ss)) = StackImpl ss
empty (StackImpl s) = null s
|
Здесь, очевидно, описана реализация АТД Stack на основе списка, причем при помещении элементов в стек они добавляются в начало списка. Таким образом, мы имеем еще один пример реализации АТД стека, но уже на основе списка. Если позже изменить реализацию данного абстрактного типа, заменив ее, например, реализацией на основе конкатенации строкового представления элементов стека, то пользователи данного АТД ничего не заметят, т.к. работают только со спецификацией этого типа, заданной в заголовке модуля.
Do'stlaringiz bilan baham: |
