9.7.3 Множества

По своей природе, множества находятся скорее ближе к словарям, чем к спискам. Так же, как и словари обеспечивают уникальность ключей, множества гарантируют уникальность входящих в него элементов. С другой стороны, списки обеспечивают порядок следования элементов, что для множеств совсем необязательно. Таким образом, встроенный тип dictionary может служить хорошей базой для реализации множеств. Ниже приведено примерное определение класса, реализующего множество.

class set:

def init (self, seq = ()):

# Атрибут data содержит словарь, ключами

# которого являются элементы множества. Делать

# атрибут частным ( data) нежелательно, так

# как в этом случае будет сложно работать с

# производными от set классами. if isinstance(seq, set):

# Если seq является экземпляром set или

# производного от него класса, можно

# воспользоваться "секретами" реализации self. data = seq. data.copy()

else:

# Иначе мы считаем seq произвольной

# последовательностью self. data = {}

for item in seq:

self. data[item] = None

def items(self):

# Этот метод позволит перебирать элементы

# множества:

# for item in myset.items():

# ...

return self. data.keys()

def tuple key(self):

# Сами множества изменяемые и не могут

# использоваться в качестве ключа в словаре или

# элемента в другом множестве. Для этого их

# нужно преобразовать в кортеж.

В версии 2.0 языка появилась новая встроенная функции zip(), предназначенная специально для параллельного перебора нескольких последовательностей. Ее поведение аналогично приведенному здесь классу parallel , с одним лишь отличием - функция zip() создает полноценный список, в который можно вносить изменения.

items = self. data.keys()

# Сортируя элементы, мы можем гарантировать,

# что порядок следования элементов в двух

# множествах всегда будет одинаковхм. items.sortO

return tuple(items)

def add(self, item):

# Добавление элемента реализуется добавлением в

# словарь пустой записи с соответствующим

# ключем.

self. data[item] = None

def remove(self, item):

if self. data.has key(item):

del self. data[item] else:

# Множество не содержит такого элемента raise ValueError("item doesnt exist")

def copy(self):

return set(self)

def repr (self):

return set(+self.items()+)

def len (self):

# Количество элементов в множестве, вызывается

# функцией len(). Также определяет истинность

# множества.

return len(self. data)

def contains (self, item):

# Операторы in и not in, return self. data.has key(item)

def cmp (self, other):

# Все операции сравнения.

return cmp(self. data, other. data)

def or (self, other):

# Оператор j (объединение). res = set(self) res. data.update(other. data)

return res

def ior (self, other):

# Оператор j=.

self. data.update(other. data) return self

def and (self, other):

# Оператор & (пересечение).

# Будем перебирать элементы того множества,

# которое содержит меньше элементов, if len(other. data) < len(self. data):

self, other = other, self res = set()

for item in self. data.keys():

if other. data.has key(item): res. data[item] = None return res

def iand (self, other):

# Оператор &=.

for item in self. data.keys():

if not other. data.has key(item): del self. data[item] return self

def sub (self, other):

# Оператор - (элементы, которые содержатся в

# первом множестве и не содержатся во втором). res = set()

for item in self. data.keys():

if not other. data.has key(item): res. data[item] = None return res

def isub (self, other):

# Оператор -=.

for item in other. data.keys(): if self. data.has key(item): del self. data[item] return self

# Если мы реализуем вычитание, то для симметрии

# следует также реализовать и сложение

# (объединение). add = or iadd = ior

def xor (self, other):

# Оператор (элементы, содержаш;иеся только в

# одном из множеств).