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. Accordingly, the
34 requirements for set elements are the same as those for dictionary keys;
35 namely, that the element defines both
\method{__eq__
} and
\method{__hash__
}.
37 cannot contain mutable elements such as lists or dictionaries.
38 However, they can contain immutable collections such as tuples or
39 instances of
\class{ImmutableSet
}. For convenience in implementing
40 sets of sets, inner sets are automatically converted to immutable
41 form, for example,
\code{Set(
[Set(
['dog'
])
])
} is transformed to
42 \code{Set(
[ImmutableSet(
['dog'
])
])
}.
44 \begin{classdesc
}{Set
}{\optional{iterable
}}
45 Constructs a new empty
\class{Set
} object. If the optional
\var{iterable
}
46 parameter is supplied, updates the set with elements obtained from iteration.
47 All of the elements in
\var{iterable
} should be immutable or be transformable
48 to an immutable using the protocol described in
49 section~
\ref{immutable-transforms
}.
52 \begin{classdesc
}{ImmutableSet
}{\optional{iterable
}}
53 Constructs a new empty
\class{ImmutableSet
} object. If the optional
54 \var{iterable
} parameter is supplied, updates the set with elements obtained
55 from iteration. All of the elements in
\var{iterable
} should be immutable or
56 be transformable to an immutable using the protocol described in
57 section~
\ref{immutable-transforms
}.
59 Because
\class{ImmutableSet
} objects provide a
\method{__hash__()
} method,
60 they can be used as set elements or as dictionary keys.
\class{ImmutableSet
}
61 objects do not have methods for adding or removing elements, so all of the
62 elements must be known when the constructor is called.
66 \subsection{Set Objects
\label{set-objects
}}
68 Instances of
\class{Set
} and
\class{ImmutableSet
} both provide
69 the following operations:
71 \begin{tableiii
}{c|c|l
}{code
}{Operation
}{Equivalent
}{Result
}
72 \lineiii{len(
\var{s
})
}{}{cardinality of set
\var{s
}}
75 \lineiii{\var{x
} in
\var{s
}}{}
76 {test
\var{x
} for membership in
\var{s
}}
77 \lineiii{\var{x
} not in
\var{s
}}{}
78 {test
\var{x
} for non-membership in
\var{s
}}
79 \lineiii{\var{s
}.issubset(
\var{t
})
}{\code{\var{s
} <=
\var{t
}}}
80 {test whether every element in
\var{s
} is in
\var{t
}}
81 \lineiii{\var{s
}.issuperset(
\var{t
})
}{\code{\var{s
} >=
\var{t
}}}
82 {test whether every element in
\var{t
} is in
\var{s
}}
85 \lineiii{\var{s
}.union(
\var{t
})
}{\var{s
} \textbar{} \var{t
}}
86 {new set with elements from both
\var{s
} and
\var{t
}}
87 \lineiii{\var{s
}.intersection(
\var{t
})
}{\var{s
} \&\
\var{t
}}
88 {new set with elements common to
\var{s
} and
\var{t
}}
89 \lineiii{\var{s
}.difference(
\var{t
})
}{\var{s
} -
\var{t
}}
90 {new set with elements in
\var{s
} but not in
\var{t
}}
91 \lineiii{\var{s
}.symmetric_difference(
\var{t
})
}{\var{s
} \^\
\var{t
}}
92 {new set with elements in either
\var{s
} or
\var{t
} but not both
}
93 \lineiii{\var{s
}.copy()
}{}
94 {new set with a shallow copy of
\var{s
}}
97 Note, the non-operator versions of
\method{union()
},
98 \method{intersection()
},
\method{difference()
}, and
99 \method{symmetric_difference()
} will accept any iterable as an argument.
100 In contrast, their operator based counterparts require their arguments to
101 be sets. This precludes error-prone constructions like
102 \code{Set('abc') \&\ 'cbs'
} in favor of the more readable
103 \code{Set('abc').intersection('cbs')
}.
104 \versionchanged[Formerly all arguments were required to be sets
]{2.3.1}
106 In addition, both
\class{Set
} and
\class{ImmutableSet
}
107 support set to set comparisons. Two sets are equal if and only if
108 every element of each set is contained in the other (each is a subset
110 A set is less than another set if and only if the first set is a proper
111 subset of the second set (is a subset, but is not equal).
112 A set is greater than another set if and only if the first set is a proper
113 superset of the second set (is a superset, but is not equal).
115 The subset and equality comparisons do not generalize to a complete
116 ordering function. For example, any two disjoint sets are not equal and
117 are not subsets of each other, so
\emph{all
} of the following return
118 \code{False
}:
\code{\var{a
}<
\var{b
}},
\code{\var{a
}==
\var{b
}}, or
119 \code{\var{a
}>
\var{b
}}.
120 Accordingly, sets do not implement the
\method{__cmp__
} method.
122 Since sets only define partial ordering (subset relationships), the output
123 of the
\method{list.sort()
} method is undefined for lists of sets.
125 The following table lists operations available in
\class{ImmutableSet
}
126 but not found in
\class{Set
}:
128 \begin{tableii
}{c|l
}{code
}{Operation
}{Result
}
129 \lineii{hash(
\var{s
})
}{returns a hash value for
\var{s
}}
132 The following table lists operations available in
\class{Set
}
133 but not found in
\class{ImmutableSet
}:
135 \begin{tableiii
}{c|c|l
}{code
}{Operation
}{Equivalent
}{Result
}
136 \lineiii{\var{s
}.update(
\var{t
})
}
137 {\var{s
} \textbar=
\var{t
}}
138 {return set
\var{s
} with elements added from
\var{t
}}
139 \lineiii{\var{s
}.intersection_update(
\var{t
})
}
140 {\var{s
} \&=
\var{t
}}
141 {return set
\var{s
} keeping only elements also found in
\var{t
}}
142 \lineiii{\var{s
}.difference_update(
\var{t
})
}
144 {return set
\var{s
} after removing elements found in
\var{t
}}
145 \lineiii{\var{s
}.symmetric_difference_update(
\var{t
})
}
146 {\var{s
} \textasciicircum=
\var{t
}}
147 {return set
\var{s
} with elements from
\var{s
} or
\var{t
}
151 \lineiii{\var{s
}.add(
\var{x
})
}{}
152 {add element
\var{x
} to set
\var{s
}}
153 \lineiii{\var{s
}.remove(
\var{x
})
}{}
154 {remove
\var{x
} from set
\var{s
}; raises KeyError if not present
}
155 \lineiii{\var{s
}.discard(
\var{x
})
}{}
156 {removes
\var{x
} from set
\var{s
} if present
}
157 \lineiii{\var{s
}.pop()
}{}
158 {remove and return an arbitrary element from
\var{s
}; raises
160 \lineiii{\var{s
}.clear()
}{}
161 {remove all elements from set
\var{s
}}
164 Note, the non-operator versions of
\method{update()
},
165 \method{intersection_update()
},
\method{difference_update()
}, and
166 \method{symmetric_difference_update()
} will accept any iterable as
168 \versionchanged[Formerly all arguments were required to be sets
]{2.3.1}
170 Also note, the module also includes a
\method{union_update()
} method
171 which is an alias for
\method{update()
}. The method is included for
172 backwards compatibility. Programmers should prefer the
173 \method{update()
} method because it is supported by the builtin
174 \class{set()
} and
\class{frozenset()
} types.
176 \subsection{Example
\label{set-example
}}
179 >>> from sets import Set
180 >>> engineers = Set(
['John', 'Jane', 'Jack', 'Janice'
])
181 >>> programmers = Set(
['Jack', 'Sam', 'Susan', 'Janice'
])
182 >>> managers = Set(
['Jane', 'Jack', 'Susan', 'Zack'
])
183 >>> employees = engineers | programmers | managers # union
184 >>> engineering_management = engineers & managers # intersection
185 >>> fulltime_management = managers - engineers - programmers # difference
186 >>> engineers.add('Marvin') # add element
188 Set(
['Jane', 'Marvin', 'Janice', 'John', 'Jack'
])
189 >>> employees.issuperset(engineers) # superset test
191 >>> employees.union_update(engineers) # update from another set
192 >>> employees.issuperset(engineers)
194 >>> for group in
[engineers, programmers, managers, employees
]:
195 ... group.discard('Susan') # unconditionally remove element
198 Set(
['Jane', 'Marvin', 'Janice', 'John', 'Jack'
])
199 Set(
['Janice', 'Jack', 'Sam'
])
200 Set(
['Jane', 'Zack', 'Jack'
])
201 Set(
['Jack', 'Sam', 'Jane', 'Marvin', 'Janice', 'John', 'Zack'
])
205 \subsection{Protocol for automatic conversion to immutable
206 \label{immutable-transforms
}}
208 Sets can only contain immutable elements. For convenience, mutable
209 \class{Set
} objects are automatically copied to an
\class{ImmutableSet
}
210 before being added as a set element.
212 The mechanism is to always add a hashable element, or if it is not
213 hashable, the element is checked to see if it has an
214 \method{__as_immutable__()
} method which returns an immutable equivalent.
216 Since
\class{Set
} objects have a
\method{__as_immutable__()
} method
217 returning an instance of
\class{ImmutableSet
}, it is possible to
218 construct sets of sets.
220 A similar mechanism is needed by the
\method{__contains__()
} and
221 \method{remove()
} methods which need to hash an element to check
222 for membership in a set. Those methods check an element for hashability
223 and, if not, check for a
\method{__as_temporarily_immutable__()
} method
224 which returns the element wrapped by a class that provides temporary
225 methods for
\method{__hash__()
},
\method{__eq__()
}, and
\method{__ne__()
}.
227 The alternate mechanism spares the need to build a separate copy of
228 the original mutable object.
230 \class{Set
} objects implement the
\method{__as_temporarily_immutable__()
}
231 method which returns the
\class{Set
} object wrapped by a new class
232 \class{_TemporarilyImmutableSet
}.
234 The two mechanisms for adding hashability are normally invisible to the
235 user; however, a conflict can arise in a multi-threaded environment
236 where one thread is updating a set while another has temporarily wrapped it
237 in
\class{_TemporarilyImmutableSet
}. In other words, sets of mutable sets
241 \subsection{Comparison to the built-in
\class{set
} types
242 \label{comparison-to-builtin-set
}}
244 The built-in
\class{set
} and
\class{frozenset
} types were designed based
245 on lessons learned from the
\module{sets
} module. The key differences are:
248 \item \class{Set
} and
\class{ImmutableSet
} were renamed to
\class{set
} and
250 \item There is no equivalent to
\class{BaseSet
}. Instead, use
251 \code{isinstance(x, (set, frozenset))
}.
252 \item The hash algorithm for the built-ins performs significantly better
253 (fewer collisions) for most datasets.
254 \item The built-in versions have more space efficient pickles.
255 \item The built-in versions do not have a
\method{union_update()
} method.
256 Instead, use the
\method{update()
} method which is equivalent.
257 \item The built-in versions do not have a
\method{_repr(sorted=True)
} method.
258 Instead, use the built-in
\function{repr()
} and
\function{sorted()
}
259 functions:
\code{repr(sorted(s))
}.
260 \item The built-in version does not have a protocol for automatic conversion
261 to immutable. Many found this feature to be confusing and no one
262 in the community reported having found real uses for it.
