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@nevex.com>

     9 .. moduleauthor:: Alex Martelli <aleax@aleax.it>

    10 .. moduleauthor:: Guido van Rossum <guido@python.org>

    11 .. sectionauthor:: Raymond D. Hettinger <python@rcn.com>

    12 

    13 

    14 .. versionadded:: 2.3

    15 

    16 .. deprecated:: 2.6

    17    The built-in ``set``/``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)``                    |            | cardinality of set *s*          |

    80 +-------------------------------+------------+---------------------------------+

    81 | ``x in s``                    |            | test *x* for membership in *s*  |

    82 +-------------------------------+------------+---------------------------------+

    83 | ``x not in s``                |            | test *x* for non-membership in  |

    84 |                               |            | *s*                             |

    85 +-------------------------------+------------+---------------------------------+

    86 | ``s.issubset(t)``             | ``s <= t`` | test whether every element in   |

    87 |                               |            | *s* is in *t*                   |

    88 +-------------------------------+------------+---------------------------------+

    89 | ``s.issuperset(t)``           | ``s >= t`` | test whether every element in   |

    90 |                               |            | *t* is in *s*                   |

    91 +-------------------------------+------------+---------------------------------+

    92 | ``s.union(t)``                | ``s | t``  | new set with elements from both |

    93 |                               |            | *s* and *t*                     |

    94 +-------------------------------+------------+---------------------------------+

    95 | ``s.intersection(t)``         | ``s & t``  | new set with elements common to |

    96 |                               |            | *s* and *t*                     |

    97 +-------------------------------+------------+---------------------------------+

    98 | ``s.difference(t)``           | ``s - t``  | new set with elements in *s*    |

    99 |                               |            | but not in *t*                  |

   100 +-------------------------------+------------+---------------------------------+

   101 | ``s.symmetric_difference(t)`` | ``s ^ t``  | new set with elements in either |

   102 |                               |            | *s* or *t* but not both         |

   103 +-------------------------------+------------+---------------------------------+

   104 | ``s.copy()``                  |            | new set with a shallow copy of  |

   105 |                               |            | *s*                             |

   106 +-------------------------------+------------+---------------------------------+

   107 

   108 Note, the non-operator versions of :meth:`union`, :meth:`intersection`,

   109 :meth:`difference`, and :meth:`symmetric_difference` will accept any iterable as

   110 an argument. In contrast, their operator based counterparts require their

   111 arguments to be sets.  This precludes error-prone constructions like

   112 ``Set('abc') & 'cbs'`` in favor of the more readable

   113 ``Set('abc').intersection('cbs')``.

   114 

   115 .. versionchanged:: 2.3.1

   116    Formerly all arguments were required to be sets.

   117 

   118 In addition, both :class:`Set` and :class:`ImmutableSet` support set to set

   119 comparisons.  Two sets are equal if and only if every element of each set is

   120 contained in the other (each is a subset of the other). A set is less than

   121 another set if and only if the first set is a proper subset of the second set

   122 (is a subset, but is not equal). A set is greater than another set if and only

   123 if the first set is a proper superset of the second set (is a superset, but is

   124 not equal).

   125 

   126 The subset and equality comparisons do not generalize to a complete ordering

   127 function.  For example, any two disjoint sets are not equal and are not subsets

   128 of each other, so *all* of the following return ``False``:  ``a<b``, ``a==b``,

   129 or ``a>b``. Accordingly, sets do not implement the :meth:`__cmp__` method.

   130 

   131 Since sets only define partial ordering (subset relationships), the output of

   132 the :meth:`list.sort` method is undefined for lists of sets.

   133 

   134 The following table lists operations available in :class:`ImmutableSet` but not

   135 found in :class:`Set`:

   136 

   137 +-------------+------------------------------+

   138 | Operation   | Result                       |

   139 +=============+==============================+

   140 | ``hash(s)`` | returns a hash value for *s* |

   141 +-------------+------------------------------+

   142 

   143 The following table lists operations available in :class:`Set` but not found in

   144 :class:`ImmutableSet`:

   145 

   146 +--------------------------------------+-------------+---------------------------------+

   147 | Operation                            | Equivalent  | Result                          |

   148 +======================================+=============+=================================+

   149 | ``s.update(t)``                      | *s* \|= *t* | return set *s* with elements    |

   150 |                                      |             | added from *t*                  |

   151 +--------------------------------------+-------------+---------------------------------+

   152 | ``s.intersection_update(t)``         | *s* &= *t*  | return set *s* keeping only     |

   153 |                                      |             | elements also found in *t*      |

   154 +--------------------------------------+-------------+---------------------------------+

   155 | ``s.difference_update(t)``           | *s* -= *t*  | return set *s* after removing   |

   156 |                                      |             | elements found in *t*           |

   157 +--------------------------------------+-------------+---------------------------------+

   158 | ``s.symmetric_difference_update(t)`` | *s* ^= *t*  | return set *s* with elements    |

   159 |                                      |             | from *s* or *t* but not both    |

   160 +--------------------------------------+-------------+---------------------------------+

   161 | ``s.add(x)``                         |             | add element *x* to set *s*      |

   162 +--------------------------------------+-------------+---------------------------------+

   163 | ``s.remove(x)``                      |             | remove *x* from set *s*; raises |

   164 |                                      |             | :exc:`KeyError` if not present  |

   165 +--------------------------------------+-------------+---------------------------------+

   166 | ``s.discard(x)``                     |             | removes *x* from set *s* if     |

   167 |                                      |             | present                         |

   168 +--------------------------------------+-------------+---------------------------------+

   169 | ``s.pop()``                          |             | remove and return an arbitrary  |

   170 |                                      |             | element from *s*; raises        |

   171 |                                      |             | :exc:`KeyError` if empty        |

   172 +--------------------------------------+-------------+---------------------------------+

   173 | ``s.clear()``                        |             | remove all elements from set    |

   174 |                                      |             | *s*                             |

   175 +--------------------------------------+-------------+---------------------------------+

   176 

   177 Note, the non-operator versions of :meth:`update`, :meth:`intersection_update`,

   178 :meth:`difference_update`, and :meth:`symmetric_difference_update` will accept

   179 any iterable as an argument.

   180 

   181 .. versionchanged:: 2.3.1

   182    Formerly all arguments were required to be sets.

   183 

   184 Also note, the module also includes a :meth:`union_update` method which is an

   185 alias for :meth:`update`.  The method is included for backwards compatibility.

   186 Programmers should prefer the :meth:`update` method because it is supported by

   187 the builtin :class:`set()` and :class:`frozenset()` types.

   188 

   189 

   190 .. _set-example:

   191 

   192 Example

   193 -------

   194 

   195    >>> from sets import Set

   196    >>> engineers = Set(['John', 'Jane', 'Jack', 'Janice'])

   197    >>> programmers = Set(['Jack', 'Sam', 'Susan', 'Janice'])

   198    >>> managers = Set(['Jane', 'Jack', 'Susan', 'Zack'])

   199    >>> employees = engineers | programmers | managers           # union

   200    >>> engineering_management = engineers & managers            # intersection

   201    >>> fulltime_management = managers - engineers - programmers # difference

   202    >>> engineers.add('Marvin')                                  # add element

   203    >>> print engineers # doctest: +SKIP

   204    Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack'])

   205    >>> employees.issuperset(engineers)     # superset test

   206    False

   207    >>> employees.update(engineers)         # update from another set

   208    >>> employees.issuperset(engineers)

   209    True

   210    >>> for group in [engineers, programmers, managers, employees]: # doctest: +SKIP

   211    ...     group.discard('Susan')          # unconditionally remove element

   212    ...     print group

   213    ...

   214    Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack'])

   215    Set(['Janice', 'Jack', 'Sam'])

   216    Set(['Jane', 'Zack', 'Jack'])

   217    Set(['Jack', 'Sam', 'Jane', 'Marvin', 'Janice', 'John', 'Zack'])

   218 

   219 

   220 .. _immutable-transforms:

   221 

   222 Protocol for automatic conversion to immutable

   223 ----------------------------------------------

   224 

   225 Sets can only contain immutable elements.  For convenience, mutable :class:`Set`

   226 objects are automatically copied to an :class:`ImmutableSet` before being added

   227 as a set element.

   228 

   229 The mechanism is to always add a :term:`hashable` element, or if it is not

   230 hashable, the element is checked to see if it has an :meth:`__as_immutable__`

   231 method which returns an immutable equivalent.

   232 

   233 Since :class:`Set` objects have a :meth:`__as_immutable__` method returning an

   234 instance of :class:`ImmutableSet`, it is possible to construct sets of sets.

   235 

   236 A similar mechanism is needed by the :meth:`__contains__` and :meth:`remove`

   237 methods which need to hash an element to check for membership in a set.  Those

   238 methods check an element for hashability and, if not, check for a

   239 :meth:`__as_temporarily_immutable__` method which returns the element wrapped by

   240 a class that provides temporary methods for :meth:`__hash__`, :meth:`__eq__`,

   241 and :meth:`__ne__`.

   242 

   243 The alternate mechanism spares the need to build a separate copy of the original

   244 mutable object.

   245 

   246 :class:`Set` objects implement the :meth:`__as_temporarily_immutable__` method

   247 which returns the :class:`Set` object wrapped by a new class

   248 :class:`_TemporarilyImmutableSet`.

   249 

   250 The two mechanisms for adding hashability are normally invisible to the user;

   251 however, a conflict can arise in a multi-threaded environment where one thread

   252 is updating a set while another has temporarily wrapped it in

   253 :class:`_TemporarilyImmutableSet`.  In other words, sets of mutable sets are not

   254 thread-safe.

   255 

   256 

   257 .. _comparison-to-builtin-set:

   258 

   259 Comparison to the built-in :class:`set` types

   260 ---------------------------------------------

   261 

   262 The built-in :class:`set` and :class:`frozenset` types were designed based on

   263 lessons learned from the :mod:`sets` module.  The key differences are:

   264 

   265 * :class:`Set` and :class:`ImmutableSet` were renamed to :class:`set` and

   266   :class:`frozenset`.

   267 

   268 * There is no equivalent to :class:`BaseSet`.  Instead, use ``isinstance(x,

   269   (set, frozenset))``.

   270 

   271 * The hash algorithm for the built-ins performs significantly better (fewer

   272   collisions) for most datasets.

   273 

   274 * The built-in versions have more space efficient pickles.

   275 

   276 * The built-in versions do not have a :meth:`union_update` method. Instead, use

   277   the :meth:`update` method which is equivalent.

   278 

   279 * The built-in versions do not have a ``_repr(sorted=True)`` method.

   280   Instead, use the built-in :func:`repr` and :func:`sorted` functions:

   281   ``repr(sorted(s))``.

   282 

   283 * The built-in version does not have a protocol for automatic conversion to

   284   immutable.  Many found this feature to be confusing and no one in the community

   285   reported having found real uses for it.

   286