| \section{\module{sets} --- |
| Unordered collections of unique elements} |
| |
| \declaremodule{standard}{sets} |
| \modulesynopsis{Implementation of sets of unique elements.} |
| \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} |
| |
| The \module{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 \code{\var{x} in \var{set}}, |
| \code{len(\var{set})}, and \code{for \var{x} in \var{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 \method{__hash__()}. For advanced applications requiring |
| a hash method, the \class{ImmutableSet} class adds a \method{__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: |
| \code{isinstance(\var{obj}, BaseSet)}. |
| |
| The set classes are implemented using dictionaries. 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, \code{Set([Set(['dog'])])} is transformed to |
| \code{Set([ImmutableSet(['dog'])])}. |
| |
| \begin{classdesc}{Set}{\optional{iterable}} |
| Constructs a new empty \class{Set} object. If the optional \var{iterable} |
| parameter is supplied, updates the set with elements obtained from iteration. |
| All of the elements in \var{iterable} should be immutable or be transformable |
| to an immutable using the protocol described in |
| section~\ref{immutable-transforms}. |
| \end{classdesc} |
| |
| \begin{classdesc}{ImmutableSet}{\optional{iterable}} |
| Constructs a new empty \class{ImmutableSet} object. If the optional |
| \var{iterable} parameter is supplied, updates the set with elements obtained |
| from iteration. All of the elements in \var{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 \method{__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. |
| \end{classdesc} |
| |
| |
| \subsection{Set Objects \label{set-objects}} |
| |
| Instances of \class{Set} and \class{ImmutableSet} both provide |
| the following operations: |
| |
| \begin{tableii}{c|l}{code}{Operation}{Result} |
| \lineii{len(\var{s})}{cardinality of set \var{s}} |
| |
| \hline |
| \lineii{\var{x} in \var{s}} |
| {test \var{x} for membership in \var{s}} |
| \lineii{\var{x} not in \var{s}} |
| {test \var{x} for non-membership in \var{s}} |
| \lineii{\var{s}.issubset(\var{t})} |
| {test whether every element in \var{s} is in \var{t}; |
| \code{\var{s} <= \var{t}} is equivalent} |
| \lineii{\var{s}.issuperset(\var{t})} |
| {test whether every element in \var{t} is in \var{s}; |
| \code{\var{s} >= \var{t}} is equivalent} |
| |
| \hline |
| \lineii{\var{s} | \var{t}} |
| {new set with elements from both \var{s} and \var{t}} |
| \lineii{\var{s}.union(\var{t})} |
| {new set with elements from both \var{s} and \var{t}} |
| \lineii{\var{s} \&\ \var{t}} |
| {new set with elements common to \var{s} and \var{t}} |
| \lineii{\var{s}.intersection(\var{t})} |
| {new set with elements common to \var{s} and \var{t}} |
| \lineii{\var{s} - \var{t}} |
| {new set with elements in \var{s} but not in \var{t}} |
| \lineii{\var{s}.difference(\var{t})} |
| {new set with elements in \var{s} but not in \var{t}} |
| \lineii{\var{s} \textasciicircum\ \var{t}} |
| {new set with elements in either \var{s} or \var{t} but not both} |
| \lineii{\var{s}.symmetric_difference(\var{t})} |
| {new set with elements in either \var{s} or \var{t} but not both} |
| \lineii{\var{s}.copy()} |
| {new set with a shallow copy of \var{s}} |
| \end{tableii} |
| |
| 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 \emph{none} of the following are true: |
| \code{\var{a}<\var{b}}, \code{\var{a}==\var{b}}, or \code{\var{a}>\var{b}}. |
| Accordingly, sets do not implement the \method{__cmp__} method. |
| |
| Since sets only define partial ordering (subset relationships), the output |
| of the \method{list.sort()} method is undefined for lists of sets. |
| |
| The following table lists operations available in \class{ImmutableSet} |
| but not found in \class{Set}: |
| |
| \begin{tableii}{c|l|c}{code}{Operation}{Result} |
| \lineii{hash(\var{s})}{returns a hash value for \var{s}} |
| \end{tableii} |
| |
| The following table lists operations available in \class{Set} |
| but not found in \class{ImmutableSet}: |
| |
| \begin{tableii}{c|l}{code}{Operation}{Result} |
| \lineii{\var{s} |= \var{t}} |
| {return set \var{s} with elements added from \var{t}} |
| \lineii{\var{s}.union_update(\var{t})} |
| {return set \var{s} with elements added from \var{t}} |
| \lineii{\var{s} \&= \var{t}} |
| {return set \var{s} keeping only elements also found in \var{t}} |
| \lineii{\var{s}.intersection_update(\var{t})} |
| {return set \var{s} keeping only elements also found in \var{t}} |
| \lineii{\var{s} -= \var{t}} |
| {return set \var{s} after removing elements found in \var{t}} |
| \lineii{\var{s}.difference_update(\var{t})} |
| {return set \var{s} after removing elements found in \var{t}} |
| \lineii{\var{s} \textasciicircum= \var{t}} |
| {return set \var{s} with elements from \var{s} or \var{t} |
| but not both} |
| \lineii{\var{s}.symmetric_difference_update(\var{t})} |
| {return set \var{s} with elements from \var{s} or \var{t} |
| but not both} |
| |
| \hline |
| \lineii{\var{s}.add(\var{x})} |
| {add element \var{x} to set \var{s}} |
| \lineii{\var{s}.remove(\var{x})} |
| {remove \var{x} from set \var{s}} |
| \lineii{\var{s}.discard(\var{x})} |
| {removes \var{x} from set \var{s} if present} |
| \lineii{\var{s}.pop()} |
| {remove and return an arbitrary element from \var{s}} |
| \lineii{\var{s}.update(\var{t})} |
| {add elements from \var{t} to set \var{s}} |
| \lineii{\var{s}.clear()} |
| {remove all elements from set \var{s}} |
| \end{tableii} |
| |
| |
| \subsection{Example \label{set-example}} |
| |
| \begin{verbatim} |
| >>> from sets import Set |
| >>> engineers = Set(['John', 'Jane', 'Jack', 'Janice']) |
| >>> programmers = Set(['Jack', 'Sam', 'Susan', 'Janice']) |
| >>> management = Set(['Jane', 'Jack', 'Susan', 'Zack']) |
| >>> employees = engineers | programmers | management # union |
| >>> engineering_management = engineers & programmers # intersection |
| >>> fulltime_management = management - engineers - programmers # difference |
| >>> engineers.add('Marvin') # add element |
| >>> print engineers |
| 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, management, employees]: |
| ... 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']) |
| \end{verbatim} |
| |
| |
| \subsection{Protocol for automatic conversion to immutable |
| \label{immutable-transforms}} |
| |
| 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 hashable element, or if it is not |
| hashable, the element is checked to see if it has an |
| \method{_as_immutable()} method which returns an immutable equivalent. |
| |
| Since \class{Set} objects have a \method{_as_immutable()} method |
| returning an instance of \class{ImmutableSet}, it is possible to |
| construct sets of sets. |
| |
| A similar mechanism is needed by the \method{__contains__()} and |
| \method{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 \method{_as_temporarily_immutable()} method |
| which returns the element wrapped by a class that provides temporary |
| methods for \method{__hash__()}, \method{__eq__()}, and \method{__ne__()}. |
| |
| The alternate mechanism spares the need to build a separate copy of |
| the original mutable object. |
| |
| \class{Set} objects implement the \method{_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. |