Прежде чем перейти к другим классическим структурам данных, необходимо коснуться еще одного аспекта, имеющегося в истории со стеками и множествами. В последних версиях Python имеется возможность
создавать подклассы от встроенных типов данных, таких как списки и словари, с целью расширения их возможностей. То есть благодаря тому, что типы данных теперь сами являются классами, доступными для наследования, мы можем создавать уникальные типы данных, являющиеся расширенными версиями встроенных типов, определяя подклассы, наследующие встроенные инструменты. Это особенно верно для Python 3.X, где термины «тип» и «класс» стали настоящим синонимами.
Для демонстрации в примере 18.13 приводится основная часть модуля, содержащего версии наших объектов стека и множества, реализованные в предыдущих разделах, переработанные в списки с дополнительными методами. Для разнообразия здесь был также немного упрощен метод объединения множеств и из него был убран избыточный цикл.
Пример 18.13. PP4E\Dstruct\Basic\typesubclass.py
"расширение встроенных типов вместо создания совершенно новой реализации"
class Stack(list):
"список с дополнительными методами"
def top(self):
return self[-1]
def push(self, item):
list.append(self, item)
def pop(self): if not self:
return None # чтобы избежать исключения
else:
return list.pop(self)
class Set(list):
"список с дополнительными методами и операторами"
def __init__(self, value=[]): # при создании объекта
list.__init__(self)
self.concat(value)
def intersect(self, other): # other — последовательность любого типа
res = [] # self — объект экземпляра
for x in self:
if x in other:
res.append(x)
return Set(res) # вернуть новый объект типа Set
def union(self, other):
res = Set(self) # новое множество с копией своего списка
res.concat(other) # вставить уникальные элементы из other
return res
# value: список, строка, Set.
# отфильтровать дубликаты
if not x in self: self.append(x)
# методы len, getitem, iter унаследованы, используется метод repr списка def __and__(self, other): return self.intersect(other)
def __or__(self, other): return self.union(other)
def __str__(self): return ‘<Set:’ + repr(self) + ‘>’
…программный код самотестирования опущен: смотрите файл в пакете примеров…
Стек и множество здесь реализованы по сути так же, как и прежде, но вместо встраивания списка и управления им эти объекты сами являются расширенными списками. Они добавляют несколько дополнительных методов, но основную функциональность наследуют от списков.
Этот прием позволяет уменьшить объем необходимого обертывающего программного кода, но он также делает доступной функциональность, которая может быть несвойственна некоторым типам. Например, в данной реализации имеется возможность сортировать содержимое стека, вставлять данные в середину и менять порядок следования элементов на обратный, потому что методы, реализующие эти операции, были унаследованы от встроенного списка. В большинстве случаев эти операции не имеют смысла для подобных структур данных, поэтому решение из предыдущих разделов в виде классов-оберток, запрещающих несвойственные операции, может оказаться более предпочтительным.
Подробности, касающиеся классов, наследующих встроенные типы, смотрите в программном коде самопроверки в оставшейся части файла с реализацией и в файле с ожидаемым выводом. Так как эти объекты используются точно так же, как и оригинальные версии стеков и множеств, дальнейшее исследование особенностей их использования я оставляю на роль самостоятельного упражнения.
Наследование встроенных типов может найти другие применения, пожалуй, более полезные, чем было продемонстрировано выше. Представьте, например, очередь или упорядоченный словарь. Очередь могла бы быть реализована как подкласс списка с методами извлечения из очереди и помещения в нее, которые добавляли бы новые элементы в конец и удаляли имеющиеся из начала. Словарь можно было бы реализовать как подкласс словаря с дополнительным списком ключей, который сортируется при вставке новых элементов и по запросу. Такой подход отлично подходит для реализации типов, напоминающих встроенные, но может оказаться непригодным для создания таких радикально отличающихся от них структур данных, как представленные в следующих двух разделах.
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
