Implementing Sets
Another commonly used data structure is the set, a collection of objects that support operations such as:
- Intersection
Make a new set with all items in common.
- Union
Make a new set with all items in either operand.
- Membership
Test whether an item exists in a set.
And there are others, depending on the intended use. Sets come in handy for dealing with more abstract group combinations. For instance, given a set of engineers and a set of writers, you can pick out individuals who do both activities by intersecting the two sets. A union of such sets would contain either type of individual, but would include any given individual only once.
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 add operations not directly supported by Python
sequences. The idea is that 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 20-8).
Example 20-8. PP3E\Dstruct\Basic\inter.py
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: ...