1 \section{\module{sets
} ---
2 Unordered collections of unique elements
}
4 \declaremodule{standard
}{sets
}
5 \modulesynopsis{Implementation of sets of unique elements.
}
6 \moduleauthor{Greg V. Wilson
}{gvwilson@nevex.com
}
7 \moduleauthor{Alex Martelli
}{aleax@aleax.it
}
8 \moduleauthor{Guido van Rossum
}{guido@python.org
}
9 \sectionauthor{Raymond D. Hettinger
}{python@rcn.com
}
13 The
\module{sets
} module provides classes for constructing and manipulating
14 unordered collections of unique elements. Common uses include membership
15 testing, removing duplicates from a sequence, and computing standard math
16 operations on sets such as intersection, union, difference, and symmetric
19 Like other collections, sets support
\code{\var{x
} in
\var{set
}},
20 \code{len(
\var{set
})
}, and
\code{for
\var{x
} in
\var{set
}}. Being an
21 unordered collection, sets do not record element position or order of
22 insertion. Accordingly, sets do not support indexing, slicing, or
23 other sequence-like behavior.
25 Most set applications use the
\class{Set
} class which provides every set
26 method except for
\method{__hash__()
}. For advanced applications requiring
27 a hash method, the
\class{ImmutableSet
} class adds a
\method{__hash__()
}
28 method but omits methods which alter the contents of the set. Both
29 \class{Set
} and
\class{ImmutableSet
} derive from
\class{BaseSet
}, an
30 abstract class useful for determining whether something is a set:
31 \code{isinstance(
\var{obj
}, BaseSet)
}.
33 The set classes are implemented using dictionaries. As a result, sets
34 cannot contain mutable elements such as lists or dictionaries.
35 However, they can contain immutable collections such as tuples or
36 instances of
\class{ImmutableSet
}. For convenience in implementing
37 sets of sets, inner sets are automatically converted to immutable
38 form, for example,
\code{Set(
[Set(
['dog'
])
])
} is transformed to
39 \code{Set(
[ImmutableSet(
['dog'
])
])
}.
41 \begin{classdesc
}{Set
}{\optional{iterable
}}
42 Constructs a new empty
\class{Set
} object. If the optional
\var{iterable
}
43 parameter is supplied, updates the set with elements obtained from iteration.
44 All of the elements in
\var{iterable
} should be immutable or be transformable
45 to an immutable using the protocol described in
46 section~
\ref{immutable-transforms
}.
49 \begin{classdesc
}{ImmutableSet
}{\optional{iterable
}}
50 Constructs a new empty
\class{ImmutableSet
} object. If the optional
51 \var{iterable
} parameter is supplied, updates the set with elements obtained
52 from iteration. All of the elements in
\var{iterable
} should be immutable or
53 be transformable to an immutable using the protocol described in
54 section~
\ref{immutable-transforms
}.
56 Because
\class{ImmutableSet
} objects provide a
\method{__hash__()
} method,
57 they can be used as set elements or as dictionary keys.
\class{ImmutableSet
}
58 objects do not have methods for adding or removing elements, so all of the
59 elements must be known when the constructor is called.
63 \subsection{Set Objects
}
65 Instances of
\class{Set
} and
\class{ImmutableSet
} both provide
66 the following operations:
68 \begin{tableii
}{c|l
}{code
}{Operation
}{Result
}
69 \lineii{len(
\var{s
})
}{cardinality of set
\var{s
}}
72 \lineii{\var{x
} in
\var{s
}}
73 {test
\var{x
} for membership in
\var{s
}}
74 \lineii{\var{x
} not in
\var{s
}}
75 {test
\var{x
} for non-membership in
\var{s
}}
76 \lineii{\var{s
}.issubset(
\var{t
})
}
77 {test whether every element in
\var{s
} is in
\var{t
};
78 \code{\var{s
} <=
\var{t
}} is equivalent
}
79 \lineii{\var{s
}.issuperset(
\var{t
})
}
80 {test whether every element in
\var{t
} is in
\var{s
};
81 \code{\var{s
} >=
\var{t
}} is equivalent
}
84 \lineii{\var{s
} |
\var{t
}}
85 {new set with elements from both
\var{s
} and
\var{t
}}
86 \lineii{\var{s
}.union(
\var{t
})
}
87 {new set with elements from both
\var{s
} and
\var{t
}}
88 \lineii{\var{s
} \&\
\var{t
}}
89 {new set with elements common to
\var{s
} and
\var{t
}}
90 \lineii{\var{s
}.intersection(
\var{t
})
}
91 {new set with elements common to
\var{s
} and
\var{t
}}
92 \lineii{\var{s
} -
\var{t
}}
93 {new set with elements in
\var{s
} but not in
\var{t
}}
94 \lineii{\var{s
}.difference(
\var{t
})
}
95 {new set with elements in
\var{s
} but not in
\var{t
}}
96 \lineii{\var{s
} \textasciicircum\
\var{t
}}
97 {new set with elements in either
\var{s
} or
\var{t
} but not both
}
98 \lineii{\var{s
}.symmetric_difference(
\var{t
})
}
99 {new set with elements in either
\var{s
} or
\var{t
} but not both
}
100 \lineii{\var{s
}.copy()
}
101 {new set with a shallow copy of
\var{s
}}
104 In addition, both
\class{Set
} and
\class{ImmutableSet
}
105 support set to set comparisons. Two sets are equal if and only if
106 every element of each set is contained in the other (each is a subset
108 A set is less than another set if and only if the first set is a proper
109 subset of the second set (is a subset, but is not equal).
110 A set is greater than another set if and only if the first set is a proper
111 superset of the second set (is a superset, but is not equal).
113 The following table lists operations available in
\class{ImmutableSet
}
114 but not found in
\class{Set
}:
116 \begin{tableii
}{c|l|c
}{code
}{Operation
}{Result
}
117 \lineii{hash(
\var{s
})
}{returns a hash value for
\var{s
}}
120 The following table lists operations available in
\class{Set
}
121 but not found in
\class{ImmutableSet
}:
123 \begin{tableii
}{c|l
}{code
}{Operation
}{Result
}
124 \lineii{\var{s
} |=
\var{t
}}
125 {return set
\var{s
} with elements added from
\var{t
}}
126 \lineii{\var{s
}.union_update(
\var{t
})
}
127 {return set
\var{s
} with elements added from
\var{t
}}
128 \lineii{\var{s
} \&=
\var{t
}}
129 {return set
\var{s
} keeping only elements also found in
\var{t
}}
130 \lineii{\var{s
}.intersection_update(
\var{t
})
}
131 {return set
\var{s
} keeping only elements also found in
\var{t
}}
132 \lineii{\var{s
} -=
\var{t
}}
133 {return set
\var{s
} after removing elements found in
\var{t
}}
134 \lineii{\var{s
}.difference_update(
\var{t
})
}
135 {return set
\var{s
} after removing elements found in
\var{t
}}
136 \lineii{\var{s
} \textasciicircum=
\var{t
}}
137 {return set
\var{s
} with elements from
\var{s
} or
\var{t
}
139 \lineii{\var{s
}.symmetric_difference_update(
\var{t
})
}
140 {return set
\var{s
} with elements from
\var{s
} or
\var{t
}
144 \lineii{\var{s
}.add(
\var{x
})
}
145 {Add element
\var{x
} to set
\var{s
}}
146 \lineii{\var{s
}.remove(
\var{x
})
}
147 {Remove element
\var{x
} from set
\var{s
}}
148 \lineii{\var{s
}.discard(
\var{x
})
}
149 {Removes element
\var{x
} from set
\var{s
}. Like
\var{s
}.remove(
\var{x
})
150 but does not raise KeyError if
\var{x
} is not in
\var{s
}}
151 \lineii{\var{s
}.pop()
}
152 {Remove and return an element from
\var{s
}; no guarantee is
153 made about which element is removed
}
154 \lineii{\var{s
}.update(
\var{t
})
}
155 {Add elements from
\var{t
} to set
\var{s
}}
156 \lineii{\var{s
}.clear()
}
157 {Remove all elements from set
\var{s
}}
164 >>> from sets import Set
165 >>> engineers = Set(
['John', 'Jane', 'Jack', 'Janice'
])
166 >>> programmers = Set(
['Jack', 'Sam', 'Susan', 'Janice'
])
167 >>> management = Set(
['Jane', 'Jack', 'Susan', 'Zack'
])
168 >>> employees = engineers | programmers | management # union
169 >>> engineering_management = engineers & programmers # intersection
170 >>> fulltime_management = management - engineers - programmers # difference
171 >>> engineers.add('Marvin') # add element
173 Set(
['Jane', 'Marvin', 'Janice', 'John', 'Jack'
])
174 >>> employees.issuperset(engineers) # superset test
176 >>> employees.update(engineers) # update from another set
177 >>> employees.issuperset(engineers)
179 >>> for group in
[engineers, programmers, management, employees
]:
180 group.discard('Susan') # unconditionally remove element
183 Set(
['Jane', 'Marvin', 'Janice', 'John', 'Jack'
])
184 Set(
['Janice', 'Jack', 'Sam'
])
185 Set(
['Jane', 'Zack', 'Jack'
])
186 Set(
['Jack', 'Sam', 'Jane', 'Marvin', 'Janice', 'John', 'Zack'
])
190 \subsection{Protocol for automatic conversion to immutable
191 \label{immutable-transforms
}}
193 Sets can only contain immutable elements. For convenience, mutable
194 \class{Set
} objects are automatically copied to an
\class{ImmutableSet
}
195 before being added as a set element.
197 The mechanism is to always add a hashable element, or if it is not
198 hashable, the element is checked to see if it has an
199 \method{_as_immutable()
} method which returns an immutable equivalent.
201 Since
\class{Set
} objects have a
\method{_as_immutable()
} method
202 returning an instance of
\class{ImmutableSet
}, it is possible to
203 construct sets of sets.
205 A similar mechanism is needed by the
\method{__contains__()
} and
206 \method{remove()
} methods which need to hash an element to check
207 for membership in a set. Those methods check an element for hashability
208 and, if not, check for a
\method{_as_temporarily_immutable()
} method
209 which returns the element wrapped by a class that provides temporary
210 methods for
\method{__hash__()
},
\method{__eq__()
}, and
\method{__ne__()
}.
212 The alternate mechanism spares the need to build a separate copy of
213 the original mutable object.
215 \class{Set
} objects implement the
\method{_as_temporarily_immutable()
}
216 method which returns the
\class{Set
} object wrapped by a new class
217 \class{_TemporarilyImmutableSet
}.
219 The two mechanisms for adding hashability are normally invisible to the
220 user; however, a conflict can arise in a multi-threaded environment
221 where one thread is updating a set while another has temporarily wrapped it
222 in
\class{_TemporarilyImmutableSet
}. In other words, sets of mutable sets
