ꦫꦣꦺꦤ꧀ꦄꦤ꧀ꦠꦱꦺꦤ

PATH: usr / share / doc / python-docs-2.7.5 / html / _sources / library

:mod:`sets` --- Unordered collections of unique elements
========================================================

.. module:: sets
   :synopsis: Implementation of sets of unique elements.
   :deprecated:
.. moduleauthor:: Greg V. Wilson <gvwilson@nevex.com>
.. moduleauthor:: Alex Martelli <aleax@aleax.it>
.. moduleauthor:: Guido van Rossum <guido@python.org>
.. sectionauthor:: Raymond D. Hettinger <python@rcn.com>

.. versionadded:: 2.3

.. deprecated:: 2.6
   The built-in :class:`set`/:class:`frozenset` types replace this module.

The :mod:`sets` module provides classes for constructing and manipulating
unordered collections of unique elements.  Common uses include membership
testing, removing duplicates from a sequence, and computing standard math
operations on sets such as intersection, union, difference, and symmetric
difference.

Like other collections, sets support ``x in set``, ``len(set)``, and ``for x in
set``.  Being an unordered collection, sets do not record element position or
order of insertion.  Accordingly, sets do not support indexing, slicing, or
other sequence-like behavior.

Most set applications use the :class:`Set` class which provides every set method
except for :meth:`__hash__`. For advanced applications requiring a hash method,
the :class:`ImmutableSet` class adds a :meth:`__hash__` method but omits methods
which alter the contents of the set. Both :class:`Set` and :class:`ImmutableSet`
derive from :class:`BaseSet`, an abstract class useful for determining whether
something is a set: ``isinstance(obj, BaseSet)``.

The set classes are implemented using dictionaries.  Accordingly, the
requirements for set elements are the same as those for dictionary keys; namely,
that the element defines both :meth:`__eq__` and :meth:`__hash__`. As a result,
sets cannot contain mutable elements such as lists or dictionaries. However,
they can contain immutable collections such as tuples or instances of
:class:`ImmutableSet`.  For convenience in implementing sets of sets, inner sets
are automatically converted to immutable form, for example,
``Set([Set(['dog'])])`` is transformed to ``Set([ImmutableSet(['dog'])])``.

.. class:: Set([iterable])

Constructs a new empty :class:`Set` object.  If the optional *iterable*
   parameter is supplied, updates the set with elements obtained from iteration.
   All of the elements in *iterable* should be immutable or be transformable to an
   immutable using the protocol described in section :ref:`immutable-transforms`.

.. class:: ImmutableSet([iterable])

Constructs a new empty :class:`ImmutableSet` object.  If the optional *iterable*
   parameter is supplied, updates the set with elements obtained from iteration.
   All of the elements in *iterable* should be immutable or be transformable to an
   immutable using the protocol described in section :ref:`immutable-transforms`.

Because :class:`ImmutableSet` objects provide a :meth:`__hash__` method, they
   can be used as set elements or as dictionary keys.  :class:`ImmutableSet`
   objects do not have methods for adding or removing elements, so all of the
   elements must be known when the constructor is called.

.. _set-objects:

Set Objects
-----------

Instances of :class:`Set` and :class:`ImmutableSet` both provide the following
operations:

+-------------------------------+------------+---------------------------------+
| Operation                     | Equivalent | Result                          |
+===============================+============+=================================+
| ``len(s)``                    |            | cardinality of set *s*          |
+-------------------------------+------------+---------------------------------+
| ``x in s``                    |            | test *x* for membership in *s*  |
+-------------------------------+------------+---------------------------------+
| ``x not in s``                |            | test *x* for non-membership in  |
|                               |            | *s*                             |
+-------------------------------+------------+---------------------------------+
| ``s.issubset(t)``             | ``s <= t`` | test whether every element in   |
|                               |            | *s* is in *t*                   |
+-------------------------------+------------+---------------------------------+
| ``s.issuperset(t)``           | ``s >= t`` | test whether every element in   |
|                               |            | *t* is in *s*                   |
+-------------------------------+------------+---------------------------------+
| ``s.union(t)``                | ``s | t``  | new set with elements from both |
|                               |            | *s* and *t*                     |
+-------------------------------+------------+---------------------------------+
| ``s.intersection(t)``         | ``s & t``  | new set with elements common to |
|                               |            | *s* and *t*                     |
+-------------------------------+------------+---------------------------------+
| ``s.difference(t)``           | ``s - t``  | new set with elements in *s*    |
|                               |            | but not in *t*                  |
+-------------------------------+------------+---------------------------------+
| ``s.symmetric_difference(t)`` | ``s ^ t``  | new set with elements in either |
|                               |            | *s* or *t* but not both         |
+-------------------------------+------------+---------------------------------+
| ``s.copy()``                  |            | new set with a shallow copy of  |
|                               |            | *s*                             |
+-------------------------------+------------+---------------------------------+

Note, the non-operator versions of :meth:`union`, :meth:`intersection`,
:meth:`difference`, and :meth:`symmetric_difference` will accept any iterable as
an argument. In contrast, their operator based counterparts require their
arguments to be sets.  This precludes error-prone constructions like
``Set('abc') & 'cbs'`` in favor of the more readable
``Set('abc').intersection('cbs')``.

.. versionchanged:: 2.3.1
   Formerly all arguments were required to be sets.

In addition, both :class:`Set` and :class:`ImmutableSet` support set to set
comparisons.  Two sets are equal if and only if every element of each set is
contained in the other (each is a subset of the other). A set is less than
another set if and only if the first set is a proper subset of the second set
(is a subset, but is not equal). A set is greater than another set if and only
if the first set is a proper superset of the second set (is a superset, but is
not equal).

The subset and equality comparisons do not generalize to a complete ordering
function.  For example, any two disjoint sets are not equal and are not subsets
of each other, so *all* of the following return ``False``:  ``a<b``, ``a==b``,
or ``a>b``. Accordingly, sets do not implement the :meth:`__cmp__` method.

Since sets only define partial ordering (subset relationships), the output of
the :meth:`list.sort` method is undefined for lists of sets.

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

+-------------+------------------------------+
| Operation   | Result                       |
+=============+==============================+
| ``hash(s)`` | returns a hash value for *s* |
+-------------+------------------------------+

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

Note, the non-operator versions of :meth:`update`, :meth:`intersection_update`,
:meth:`difference_update`, and :meth:`symmetric_difference_update` will accept
any iterable as an argument.

.. versionchanged:: 2.3.1
   Formerly all arguments were required to be sets.

Also note, the module also includes a :meth:`union_update` method which is an
alias for :meth:`update`.  The method is included for backwards compatibility.
Programmers should prefer the :meth:`update` method because it is supported by
the built-in :class:`set()` and :class:`frozenset()` types.

.. _set-example:

Example
-------

>>> from sets import Set
   >>> engineers = Set(['John', 'Jane', 'Jack', 'Janice'])
   >>> programmers = Set(['Jack', 'Sam', 'Susan', 'Janice'])
   >>> managers = Set(['Jane', 'Jack', 'Susan', 'Zack'])
   >>> employees = engineers | programmers | managers           # union
   >>> engineering_management = engineers & managers            # intersection
   >>> fulltime_management = managers - engineers - programmers # difference
   >>> engineers.add('Marvin')                                  # add element
   >>> print engineers # doctest: +SKIP
   Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack'])
   >>> employees.issuperset(engineers)     # superset test
   False
   >>> employees.update(engineers)         # update from another set
   >>> employees.issuperset(engineers)
   True
   >>> for group in [engineers, programmers, managers, employees]: # doctest: +SKIP
   ...     group.discard('Susan')          # unconditionally remove element
   ...     print group
   ...
   Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack'])
   Set(['Janice', 'Jack', 'Sam'])
   Set(['Jane', 'Zack', 'Jack'])
   Set(['Jack', 'Sam', 'Jane', 'Marvin', 'Janice', 'John', 'Zack'])

.. _immutable-transforms:

Protocol for automatic conversion to immutable
----------------------------------------------

Sets can only contain immutable elements.  For convenience, mutable :class:`Set`
objects are automatically copied to an :class:`ImmutableSet` before being added
as a set element.

The mechanism is to always add a :term:`hashable` element, or if it is not
hashable, the element is checked to see if it has an :meth:`__as_immutable__`
method which returns an immutable equivalent.

Since :class:`Set` objects have a :meth:`__as_immutable__` method returning an
instance of :class:`ImmutableSet`, it is possible to construct sets of sets.

A similar mechanism is needed by the :meth:`__contains__` and :meth:`remove`
methods which need to hash an element to check for membership in a set.  Those
methods check an element for hashability and, if not, check for a
:meth:`__as_temporarily_immutable__` method which returns the element wrapped by
a class that provides temporary methods for :meth:`__hash__`, :meth:`__eq__`,
and :meth:`__ne__`.

The alternate mechanism spares the need to build a separate copy of the original
mutable object.

:class:`Set` objects implement the :meth:`__as_temporarily_immutable__` method
which returns the :class:`Set` object wrapped by a new class
:class:`_TemporarilyImmutableSet`.

The two mechanisms for adding hashability are normally invisible to the user;
however, a conflict can arise in a multi-threaded environment where one thread
is updating a set while another has temporarily wrapped it in
:class:`_TemporarilyImmutableSet`.  In other words, sets of mutable sets are not
thread-safe.

.. _comparison-to-builtin-set:

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

The built-in :class:`set` and :class:`frozenset` types were designed based on
lessons learned from the :mod:`sets` module.  The key differences are:

* :class:`Set` and :class:`ImmutableSet` were renamed to :class:`set` and
  :class:`frozenset`.

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

* The hash algorithm for the built-ins performs significantly better (fewer
  collisions) for most datasets.

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

* The built-in versions do not have a :meth:`union_update` method. Instead, use
  the :meth:`update` method which is equivalent.

* The built-in versions do not have a ``_repr(sorted=True)`` method.
  Instead, use the built-in :func:`repr` and :func:`sorted` functions:
  ``repr(sorted(s))``.

* The built-in version does not have a protocol for automatic conversion to
  immutable.  Many found this feature to be confusing and no one in the community
  reported having found real uses for it.

[+] ..
[-] fpformat.txt [edit]
[-] string.txt [edit]
[-] aetypes.txt [edit]
[-] textwrap.txt [edit]
[-] codecs.txt [edit]
[-] array.txt [edit]
[-] urllib2.txt [edit]
[-] pickle.txt [edit]
[-] 2to3.txt [edit]
[-] ossaudiodev.txt [edit]
[-] markup.txt [edit]
[-] sha.txt [edit]
[-] stat.txt [edit]
[-] itertools.txt [edit]
[-] numeric.txt [edit]
[-] gzip.txt [edit]
[-] pkgutil.txt [edit]
[-] subprocess.txt [edit]
[-] token.txt [edit]
[-] debug.txt [edit]
[-] dummy_thread.txt [edit]
[-] mimify.txt [edit]
[-] bastion.txt [edit]
[-] popen2.txt [edit]
[-] autogil.txt [edit]
[-] importlib.txt [edit]
[-] io.txt [edit]
[-] msilib.txt [edit]
[-] development.txt [edit]
[-] hotshot.txt [edit]
[-] constants.txt [edit]
[-] curses.ascii.txt [edit]
[-] os.txt [edit]
[-] easydialogs.txt [edit]
[-] mutex.txt [edit]
[-] md5.txt [edit]
[-] stdtypes.txt [edit]
[-] bz2.txt [edit]
[-] imgfile.txt [edit]
[-] aetools.txt [edit]
[-] internet.txt [edit]
[-] xml.dom.pulldom.txt [edit]
[-] cookie.txt [edit]
[-] sunau.txt [edit]
[-] archiving.txt [edit]
[-] modules.txt [edit]
[-] base64.txt [edit]
[-] ttk.txt [edit]
[-] tty.txt [edit]
[-] cookielib.txt [edit]
[-] pydoc.txt [edit]
[-] misc.txt [edit]
[-] fm.txt [edit]
[-] whichdb.txt [edit]
[-] imghdr.txt [edit]
[-] datatypes.txt [edit]
[-] dis.txt [edit]
[-] datetime.txt [edit]
[-] userdict.txt [edit]
[-] py_compile.txt [edit]
[-] imputil.txt [edit]
[-] xml.dom.minidom.txt [edit]
[-] multiprocessing.txt [edit]
[-] functools.txt [edit]
[-] audioop.txt [edit]
[-] language.txt [edit]
[-] miniaeframe.txt [edit]
[-] ssl.txt [edit]
[-] copy_reg.txt [edit]
[-] heapq.txt [edit]
[-] syslog.txt [edit]
[-] fileformats.txt [edit]
[-] simplexmlrpcserver.txt [edit]
[-] numbers.txt [edit]
[-] pipes.txt [edit]
[-] shutil.txt [edit]
[-] zlib.txt [edit]
[-] optparse.txt [edit]
[-] allos.txt [edit]
[-] custominterp.txt [edit]
[-] windows.txt [edit]
[-] dbm.txt [edit]
[-] select.txt [edit]
[-] time.txt [edit]
[-] index.txt [edit]
[-] undoc.txt [edit]
[-] plistlib.txt [edit]
[-] htmllib.txt [edit]
[-] warnings.txt [edit]
[-] functions.txt [edit]
[-] argparse.txt [edit]
[-] distutils.txt [edit]
[-] macpath.txt [edit]
[-] fnmatch.txt [edit]
[-] tabnanny.txt [edit]
[-] calendar.txt [edit]
[-] jpeg.txt [edit]
[-] zipimport.txt [edit]
[-] unix.txt [edit]
[-] chunk.txt [edit]
[-] smtplib.txt [edit]
[-] tokenize.txt [edit]
[-] asynchat.txt [edit]
[-] decimal.txt [edit]
[-] cd.txt [edit]
[-] pickletools.txt [edit]
[-] statvfs.txt [edit]
[-] gettext.txt [edit]
[-] sqlite3.txt [edit]
[-] imageop.txt [edit]
[-] dl.txt [edit]
[-] logging.handlers.txt [edit]
[-] zipfile.txt [edit]
[-] copy.txt [edit]
[-] sched.txt [edit]
[-] nis.txt [edit]
[-] timeit.txt [edit]
[-] weakref.txt [edit]
[-] mailbox.txt [edit]
[-] othergui.txt [edit]
[-] sgmllib.txt [edit]
[-] mimewriter.txt [edit]
[-] email.charset.txt [edit]
[-] mmap.txt [edit]
[-] xmlrpclib.txt [edit]
[-] robotparser.txt [edit]
[-] xml.sax.reader.txt [edit]
[-] hmac.txt [edit]
[-] collections.txt [edit]
[-] mimetools.txt [edit]
[-] aifc.txt [edit]
[-] modulefinder.txt [edit]
[-] socketserver.txt [edit]
[-] grp.txt [edit]
[-] getopt.txt [edit]
[-] __future__.txt [edit]
[-] binascii.txt [edit]
[-] symtable.txt [edit]
[-] crypt.txt [edit]
[-] email.encoders.txt [edit]
[-] imaplib.txt [edit]
[-] spwd.txt [edit]
[-] wsgiref.txt [edit]
[-] errno.txt [edit]
[-] email-examples.txt [edit]
[-] sun.txt [edit]
[-] doctest.txt [edit]
[-] resource.txt [edit]
[-] asyncore.txt [edit]
[-] curses.panel.txt [edit]
[-] imp.txt [edit]
[-] htmlparser.txt [edit]
[-] thread.txt [edit]
[-] posix.txt [edit]
[-] repr.txt [edit]
[-] macostools.txt [edit]
[-] colorsys.txt [edit]
[-] bdb.txt [edit]
[-] stringio.txt [edit]
[-] mm.txt [edit]
[-] cgi.txt [edit]
[-] math.txt [edit]
[-] httplib.txt [edit]
[-] urlparse.txt [edit]
[-] aepack.txt [edit]
[-] colorpicker.txt [edit]
[-] binhex.txt [edit]
[-] tk.txt [edit]
[-] xml.txt [edit]
[-] webbrowser.txt [edit]
[-] contextlib.txt [edit]
[-] types.txt [edit]
[-] shelve.txt [edit]
[-] platform.txt [edit]
[-] readline.txt [edit]
[-] locale.txt [edit]
[-] sets.txt [edit]
[-] macosa.txt [edit]
[-] bisect.txt [edit]
[-] email.parser.txt [edit]
[-] xml.sax.txt [edit]
[-] xml.etree.elementtree.txt [edit]
[-] netrc.txt [edit]
[-] new.txt [edit]
[-] bsddb.txt [edit]
[-] fl.txt [edit]
[-] curses.txt [edit]
[-] hashlib.txt [edit]
[-] tarfile.txt [edit]
[-] ftplib.txt [edit]
[-] telnetlib.txt [edit]
[-] macos.txt [edit]
[-] multifile.txt [edit]
[-] dbhash.txt [edit]
[-] netdata.txt [edit]
[-] fileinput.txt [edit]
[-] python.txt [edit]
[-] mac.txt [edit]
[-] filesys.txt [edit]
[-] scrolledtext.txt [edit]
[-] compiler.txt [edit]
[-] tkinter.txt [edit]
[-] random.txt [edit]
[-] mailcap.txt [edit]
[-] fpectl.txt [edit]
[-] fcntl.txt [edit]
[-] ipc.txt [edit]
[-] formatter.txt [edit]
[-] profile.txt [edit]
[-] xml.dom.txt [edit]
[-] email.iterators.txt [edit]
[-] logging.config.txt [edit]
[-] rlcompleter.txt [edit]
[-] idle.txt [edit]
[-] gdbm.txt [edit]
[-] ast.txt [edit]
[-] someos.txt [edit]
[-] cmd.txt [edit]
[-] re.txt [edit]
[-] docxmlrpcserver.txt [edit]
[-] pdb.txt [edit]
[-] rexec.txt [edit]
[-] commands.txt [edit]
[-] restricted.txt [edit]
[-] crypto.txt [edit]
[-] dumbdbm.txt [edit]
[-] email.txt [edit]
[-] linecache.txt [edit]
[-] os.path.txt [edit]
[-] cgitb.txt [edit]
[-] _winreg.txt [edit]
[-] carbon.txt [edit]
[-] turtle.txt [edit]
[-] xml.sax.handler.txt [edit]
[-] json.txt [edit]
[-] email.generator.txt [edit]
[-] struct.txt [edit]
[-] mhlib.txt [edit]
[-] uuid.txt [edit]
[-] threading.txt [edit]
[-] mimetypes.txt [edit]
[-] traceback.txt [edit]
[-] filecmp.txt [edit]
[-] sndhdr.txt [edit]
[-] logging.txt [edit]
[-] getpass.txt [edit]
[-] dummy_threading.txt [edit]
[-] abc.txt [edit]
[-] shlex.txt [edit]
[-] email.mime.txt [edit]
[-] fractions.txt [edit]
[-] email.header.txt [edit]
[-] marshal.txt [edit]
[-] symbol.txt [edit]
[-] wave.txt [edit]
[-] urllib.txt [edit]
[-] queue.txt [edit]
[-] operator.txt [edit]
[-] compileall.txt [edit]
[-] sysconfig.txt [edit]
[-] quopri.txt [edit]
[-] inspect.txt [edit]
[-] xdrlib.txt [edit]
[-] __builtin__.txt [edit]
[-] ic.txt [edit]
[-] signal.txt [edit]
[-] dircache.txt [edit]
[-] rfc822.txt [edit]
[-] glob.txt [edit]
[-] stringprep.txt [edit]
[-] tix.txt [edit]
[-] i18n.txt [edit]
[-] email.util.txt [edit]
[-] anydbm.txt [edit]
[-] code.txt [edit]
[-] __main__.txt [edit]
[-] difflib.txt [edit]
[-] unicodedata.txt [edit]
[-] sunaudio.txt [edit]
[-] msvcrt.txt [edit]
[-] site.txt [edit]
[-] codeop.txt [edit]
[-] uu.txt [edit]
[-] winsound.txt [edit]
[-] smtpd.txt [edit]
[-] al.txt [edit]
[-] user.txt [edit]
[-] poplib.txt [edit]
[-] nntplib.txt [edit]
[-] keyword.txt [edit]
[-] ctypes.txt [edit]
[-] socket.txt [edit]
[-] simplehttpserver.txt [edit]
[-] sys.txt [edit]
[-] pyexpat.txt [edit]
[-] configparser.txt [edit]
[-] persistence.txt [edit]
[-] trace.txt [edit]
[-] runpy.txt [edit]
[-] csv.txt [edit]
[-] test.txt [edit]
[-] framework.txt [edit]
[-] gc.txt [edit]
[-] cmath.txt [edit]
[-] exceptions.txt [edit]
[-] pyclbr.txt [edit]
[-] sgi.txt [edit]
[-] parser.txt [edit]
[-] future_builtins.txt [edit]
[-] pwd.txt [edit]
[-] strings.txt [edit]
[-] frameworks.txt [edit]
[-] email.message.txt [edit]
[-] cgihttpserver.txt [edit]
[-] intro.txt [edit]
[-] email.errors.txt [edit]
[-] pprint.txt [edit]
[-] pty.txt [edit]
[-] xml.sax.utils.txt [edit]
[-] posixfile.txt [edit]
[-] tempfile.txt [edit]
[-] termios.txt [edit]
[-] gl.txt [edit]
[-] gensuitemodule.txt [edit]
[-] atexit.txt [edit]
[-] basehttpserver.txt [edit]
[-] unittest.txt [edit]