>>> x = set({'spam':[1, 1], 'ham': [2, 2], 'eggs':[3, 3]})
>>> x
{'eggs', 'ham', 'spam'}Plus there are additional operations we won’t illuminate here—see a core language text
such as Learning Python for more details. For instance, built-in sets also support op-
erations such as superset testing, and they come in two flavors: mutable and frozen
(frozen sets are hashable, and thus usable in sets of sets). Moreover, set comprehensions
are more powerful than suggested, and sets are a natural at duplicate removal:
>>> y = {c.upper() * 4 for c in 'spamham'} # set comprehension
>>> y
{'SSSS', 'AAAA', 'MMMM', 'HHHH', 'PPPP'}
>>>
>>> list(set([1, 2, 3, 1, 2])) # remove duplicates from a list
[1, 2, 3]As for stacks, though, the built-in set type might not by itself achieve all our goals.
Moreover, homegrown set implementations turn out to be an ideal vehicle for studying
custom data structure implementations in Python. Although the end result may not
compete with the performance of built-in set objects today, the code can still be in-
structive to read, and fun to experiment with.
Also as for stacks, a custom set implementation will generally be based upon other
built-in types. Python lists, tuples, and strings come close to the notion of a set: the
in operator tests membership, for iterates, and so on. Here, we’ll add operations not
directly supported by Python sequences. In effect, we’re extending built-in types for
unique requirements.
Set Functions
As before, let’s first start out with a function-based set manager. But this time, instead
of managing a shared set object in a module, let’s define functions to implement set
operations on passed-in Python sequences (see Example 18-8).
Example 18-8. PP4E\Dstruct\Basic\inter.py
"set operations for two sequences"
def intersect(seq1, seq2):
res = [] # start with an empty list
for x in seq1: # scan the first sequence
if x in seq2:
res.append(x) # add common items to the end
return res
def union(seq1, seq2):
res = list(seq1) # make a copy of seq1
for x in seq2: # add new items in seq2
if not x in res:
Implementing Sets | 1375