1 2 :mod:`sets` --- Unordered collections of unique elements 3 ======================================================== 4 5 .. module:: sets 6 :synopsis: Implementation of sets of unique elements. 7 :deprecated: 8 .. moduleauthor:: Greg V. Wilson <gvwilson (a] nevex.com> 9 .. moduleauthor:: Alex Martelli <aleax (a] aleax.it> 10 .. moduleauthor:: Guido van Rossum <guido (a] python.org> 11 .. sectionauthor:: Raymond D. Hettinger <python (a] rcn.com> 12 13 14 .. versionadded:: 2.3 15 16 .. deprecated:: 2.6 17 The built-in :class:`set`/:class:`frozenset` types replace this module. 18 19 The :mod:`sets` module provides classes for constructing and manipulating 20 unordered collections of unique elements. Common uses include membership 21 testing, removing duplicates from a sequence, and computing standard math 22 operations on sets such as intersection, union, difference, and symmetric 23 difference. 24 25 Like other collections, sets support ``x in set``, ``len(set)``, and ``for x in 26 set``. Being an unordered collection, sets do not record element position or 27 order of insertion. Accordingly, sets do not support indexing, slicing, or 28 other sequence-like behavior. 29 30 Most set applications use the :class:`Set` class which provides every set method 31 except for :meth:`__hash__`. For advanced applications requiring a hash method, 32 the :class:`ImmutableSet` class adds a :meth:`__hash__` method but omits methods 33 which alter the contents of the set. Both :class:`Set` and :class:`ImmutableSet` 34 derive from :class:`BaseSet`, an abstract class useful for determining whether 35 something is a set: ``isinstance(obj, BaseSet)``. 36 37 The set classes are implemented using dictionaries. Accordingly, the 38 requirements for set elements are the same as those for dictionary keys; namely, 39 that the element defines both :meth:`__eq__` and :meth:`__hash__`. As a result, 40 sets cannot contain mutable elements such as lists or dictionaries. However, 41 they can contain immutable collections such as tuples or instances of 42 :class:`ImmutableSet`. For convenience in implementing sets of sets, inner sets 43 are automatically converted to immutable form, for example, 44 ``Set([Set(['dog'])])`` is transformed to ``Set([ImmutableSet(['dog'])])``. 45 46 47 .. class:: Set([iterable]) 48 49 Constructs a new empty :class:`Set` object. If the optional *iterable* 50 parameter is supplied, updates the set with elements obtained from iteration. 51 All of the elements in *iterable* should be immutable or be transformable to an 52 immutable using the protocol described in section :ref:`immutable-transforms`. 53 54 55 .. class:: ImmutableSet([iterable]) 56 57 Constructs a new empty :class:`ImmutableSet` object. If the optional *iterable* 58 parameter is supplied, updates the set with elements obtained from iteration. 59 All of the elements in *iterable* should be immutable or be transformable to an 60 immutable using the protocol described in section :ref:`immutable-transforms`. 61 62 Because :class:`ImmutableSet` objects provide a :meth:`__hash__` method, they 63 can be used as set elements or as dictionary keys. :class:`ImmutableSet` 64 objects do not have methods for adding or removing elements, so all of the 65 elements must be known when the constructor is called. 66 67 68 .. _set-objects: 69 70 Set Objects 71 ----------- 72 73 Instances of :class:`Set` and :class:`ImmutableSet` both provide the following 74 operations: 75 76 +-------------------------------+------------+---------------------------------+ 77 | Operation | Equivalent | Result | 78 +===============================+============+=================================+ 79 | ``len(s)`` | | number of elements in set *s* | 80 | | | (cardinality) | 81 +-------------------------------+------------+---------------------------------+ 82 | ``x in s`` | | test *x* for membership in *s* | 83 +-------------------------------+------------+---------------------------------+ 84 | ``x not in s`` | | test *x* for non-membership in | 85 | | | *s* | 86 +-------------------------------+------------+---------------------------------+ 87 | ``s.issubset(t)`` | ``s <= t`` | test whether every element in | 88 | | | *s* is in *t* | 89 +-------------------------------+------------+---------------------------------+ 90 | ``s.issuperset(t)`` | ``s >= t`` | test whether every element in | 91 | | | *t* is in *s* | 92 +-------------------------------+------------+---------------------------------+ 93 | ``s.union(t)`` | ``s | t`` | new set with elements from both | 94 | | | *s* and *t* | 95 +-------------------------------+------------+---------------------------------+ 96 | ``s.intersection(t)`` | ``s & t`` | new set with elements common to | 97 | | | *s* and *t* | 98 +-------------------------------+------------+---------------------------------+ 99 | ``s.difference(t)`` | ``s - t`` | new set with elements in *s* | 100 | | | but not in *t* | 101 +-------------------------------+------------+---------------------------------+ 102 | ``s.symmetric_difference(t)`` | ``s ^ t`` | new set with elements in either | 103 | | | *s* or *t* but not both | 104 +-------------------------------+------------+---------------------------------+ 105 | ``s.copy()`` | | new set with a shallow copy of | 106 | | | *s* | 107 +-------------------------------+------------+---------------------------------+ 108 109 Note, the non-operator versions of :meth:`union`, :meth:`intersection`, 110 :meth:`difference`, and :meth:`symmetric_difference` will accept any iterable as 111 an argument. In contrast, their operator based counterparts require their 112 arguments to be sets. This precludes error-prone constructions like 113 ``Set('abc') & 'cbs'`` in favor of the more readable 114 ``Set('abc').intersection('cbs')``. 115 116 .. versionchanged:: 2.3.1 117 Formerly all arguments were required to be sets. 118 119 In addition, both :class:`Set` and :class:`ImmutableSet` support set to set 120 comparisons. Two sets are equal if and only if every element of each set is 121 contained in the other (each is a subset of the other). A set is less than 122 another set if and only if the first set is a proper subset of the second set 123 (is a subset, but is not equal). A set is greater than another set if and only 124 if the first set is a proper superset of the second set (is a superset, but is 125 not equal). 126 127 The subset and equality comparisons do not generalize to a complete ordering 128 function. For example, any two disjoint sets are not equal and are not subsets 129 of each other, so *all* of the following return ``False``: ``a<b``, ``a==b``, 130 or ``a>b``. Accordingly, sets do not implement the :meth:`__cmp__` method. 131 132 Since sets only define partial ordering (subset relationships), the output of 133 the :meth:`list.sort` method is undefined for lists of sets. 134 135 The following table lists operations available in :class:`ImmutableSet` but not 136 found in :class:`Set`: 137 138 +-------------+------------------------------+ 139 | Operation | Result | 140 +=============+==============================+ 141 | ``hash(s)`` | returns a hash value for *s* | 142 +-------------+------------------------------+ 143 144 The following table lists operations available in :class:`Set` but not found in 145 :class:`ImmutableSet`: 146 147 +--------------------------------------+-------------+---------------------------------+ 148 | Operation | Equivalent | Result | 149 +======================================+=============+=================================+ 150 | ``s.update(t)`` | *s* \|= *t* | return set *s* with elements | 151 | | | added from *t* | 152 +--------------------------------------+-------------+---------------------------------+ 153 | ``s.intersection_update(t)`` | *s* &= *t* | return set *s* keeping only | 154 | | | elements also found in *t* | 155 +--------------------------------------+-------------+---------------------------------+ 156 | ``s.difference_update(t)`` | *s* -= *t* | return set *s* after removing | 157 | | | elements found in *t* | 158 +--------------------------------------+-------------+---------------------------------+ 159 | ``s.symmetric_difference_update(t)`` | *s* ^= *t* | return set *s* with elements | 160 | | | from *s* or *t* but not both | 161 +--------------------------------------+-------------+---------------------------------+ 162 | ``s.add(x)`` | | add element *x* to set *s* | 163 +--------------------------------------+-------------+---------------------------------+ 164 | ``s.remove(x)`` | | remove *x* from set *s*; raises | 165 | | | :exc:`KeyError` if not present | 166 +--------------------------------------+-------------+---------------------------------+ 167 | ``s.discard(x)`` | | removes *x* from set *s* if | 168 | | | present | 169 +--------------------------------------+-------------+---------------------------------+ 170 | ``s.pop()`` | | remove and return an arbitrary | 171 | | | element from *s*; raises | 172 | | | :exc:`KeyError` if empty | 173 +--------------------------------------+-------------+---------------------------------+ 174 | ``s.clear()`` | | remove all elements from set | 175 | | | *s* | 176 +--------------------------------------+-------------+---------------------------------+ 177 178 Note, the non-operator versions of :meth:`update`, :meth:`intersection_update`, 179 :meth:`difference_update`, and :meth:`symmetric_difference_update` will accept 180 any iterable as an argument. 181 182 .. versionchanged:: 2.3.1 183 Formerly all arguments were required to be sets. 184 185 Also note, the module also includes a :meth:`union_update` method which is an 186 alias for :meth:`update`. The method is included for backwards compatibility. 187 Programmers should prefer the :meth:`update` method because it is supported by 188 the built-in :class:`set()` and :class:`frozenset()` types. 189 190 191 .. _set-example: 192 193 Example 194 ------- 195 196 >>> from sets import Set 197 >>> engineers = Set(['John', 'Jane', 'Jack', 'Janice']) 198 >>> programmers = Set(['Jack', 'Sam', 'Susan', 'Janice']) 199 >>> managers = Set(['Jane', 'Jack', 'Susan', 'Zack']) 200 >>> employees = engineers | programmers | managers # union 201 >>> engineering_management = engineers & managers # intersection 202 >>> fulltime_management = managers - engineers - programmers # difference 203 >>> engineers.add('Marvin') # add element 204 >>> print engineers # doctest: +SKIP 205 Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack']) 206 >>> employees.issuperset(engineers) # superset test 207 False 208 >>> employees.update(engineers) # update from another set 209 >>> employees.issuperset(engineers) 210 True 211 >>> for group in [engineers, programmers, managers, employees]: # doctest: +SKIP 212 ... group.discard('Susan') # unconditionally remove element 213 ... print group 214 ... 215 Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack']) 216 Set(['Janice', 'Jack', 'Sam']) 217 Set(['Jane', 'Zack', 'Jack']) 218 Set(['Jack', 'Sam', 'Jane', 'Marvin', 'Janice', 'John', 'Zack']) 219 220 221 .. _immutable-transforms: 222 223 Protocol for automatic conversion to immutable 224 ---------------------------------------------- 225 226 Sets can only contain immutable elements. For convenience, mutable :class:`Set` 227 objects are automatically copied to an :class:`ImmutableSet` before being added 228 as a set element. 229 230 The mechanism is to always add a :term:`hashable` element, or if it is not 231 hashable, the element is checked to see if it has an :meth:`__as_immutable__` 232 method which returns an immutable equivalent. 233 234 Since :class:`Set` objects have a :meth:`__as_immutable__` method returning an 235 instance of :class:`ImmutableSet`, it is possible to construct sets of sets. 236 237 A similar mechanism is needed by the :meth:`__contains__` and :meth:`remove` 238 methods which need to hash an element to check for membership in a set. Those 239 methods check an element for hashability and, if not, check for a 240 :meth:`__as_temporarily_immutable__` method which returns the element wrapped by 241 a class that provides temporary methods for :meth:`__hash__`, :meth:`__eq__`, 242 and :meth:`__ne__`. 243 244 The alternate mechanism spares the need to build a separate copy of the original 245 mutable object. 246 247 :class:`Set` objects implement the :meth:`__as_temporarily_immutable__` method 248 which returns the :class:`Set` object wrapped by a new class 249 :class:`_TemporarilyImmutableSet`. 250 251 The two mechanisms for adding hashability are normally invisible to the user; 252 however, a conflict can arise in a multi-threaded environment where one thread 253 is updating a set while another has temporarily wrapped it in 254 :class:`_TemporarilyImmutableSet`. In other words, sets of mutable sets are not 255 thread-safe. 256 257 258 .. _comparison-to-builtin-set: 259 260 Comparison to the built-in :class:`set` types 261 --------------------------------------------- 262 263 The built-in :class:`set` and :class:`frozenset` types were designed based on 264 lessons learned from the :mod:`sets` module. The key differences are: 265 266 * :class:`Set` and :class:`ImmutableSet` were renamed to :class:`set` and 267 :class:`frozenset`. 268 269 * There is no equivalent to :class:`BaseSet`. Instead, use ``isinstance(x, 270 (set, frozenset))``. 271 272 * The hash algorithm for the built-ins performs significantly better (fewer 273 collisions) for most datasets. 274 275 * The built-in versions have more space efficient pickles. 276 277 * The built-in versions do not have a :meth:`union_update` method. Instead, use 278 the :meth:`update` method which is equivalent. 279 280 * The built-in versions do not have a ``_repr(sorted=True)`` method. 281 Instead, use the built-in :func:`repr` and :func:`sorted` functions: 282 ``repr(sorted(s))``. 283 284 * The built-in version does not have a protocol for automatic conversion to 285 immutable. Many found this feature to be confusing and no one in the community 286 reported having found real uses for it. 287 288
