• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1:mod:`collections` --- High-performance container datatypes
2===========================================================
3
4.. module:: collections
5   :synopsis: High-performance datatypes
6.. moduleauthor:: Raymond Hettinger <python@rcn.com>
7.. sectionauthor:: Raymond Hettinger <python@rcn.com>
8
9.. versionadded:: 2.4
10
11.. testsetup:: *
12
13   from collections import *
14   import itertools
15   __name__ = '<doctest>'
16
17**Source code:** :source:`Lib/collections.py` and :source:`Lib/_abcoll.py`
18
19--------------
20
21This module implements specialized container datatypes providing alternatives to
22Python's general purpose built-in containers, :class:`dict`, :class:`list`,
23:class:`set`, and :class:`tuple`.
24
25=====================   ====================================================================  ===========================
26:func:`namedtuple`      factory function for creating tuple subclasses with named fields      .. versionadded:: 2.6
27:class:`deque`          list-like container with fast appends and pops on either end          .. versionadded:: 2.4
28:class:`Counter`        dict subclass for counting hashable objects                           .. versionadded:: 2.7
29:class:`OrderedDict`    dict subclass that remembers the order entries were added             .. versionadded:: 2.7
30:class:`defaultdict`    dict subclass that calls a factory function to supply missing values  .. versionadded:: 2.5
31=====================   ====================================================================  ===========================
32
33In addition to the concrete container classes, the collections module provides
34:ref:`abstract base classes <collections-abstract-base-classes>` that can be
35used to test whether a class provides a particular interface, for example,
36whether it is hashable or a mapping.
37
38
39:class:`Counter` objects
40------------------------
41
42A counter tool is provided to support convenient and rapid tallies.
43For example::
44
45    >>> # Tally occurrences of words in a list
46    >>> cnt = Counter()
47    >>> for word in ['red', 'blue', 'red', 'green', 'blue', 'blue']:
48    ...     cnt[word] += 1
49    >>> cnt
50    Counter({'blue': 3, 'red': 2, 'green': 1})
51
52    >>> # Find the ten most common words in Hamlet
53    >>> import re
54    >>> words = re.findall(r'\w+', open('hamlet.txt').read().lower())
55    >>> Counter(words).most_common(10)
56    [('the', 1143), ('and', 966), ('to', 762), ('of', 669), ('i', 631),
57     ('you', 554),  ('a', 546), ('my', 514), ('hamlet', 471), ('in', 451)]
58
59.. class:: Counter([iterable-or-mapping])
60
61   A :class:`Counter` is a :class:`dict` subclass for counting hashable objects.
62   It is an unordered collection where elements are stored as dictionary keys
63   and their counts are stored as dictionary values.  Counts are allowed to be
64   any integer value including zero or negative counts.  The :class:`Counter`
65   class is similar to bags or multisets in other languages.
66
67   Elements are counted from an *iterable* or initialized from another
68   *mapping* (or counter):
69
70        >>> c = Counter()                           # a new, empty counter
71        >>> c = Counter('gallahad')                 # a new counter from an iterable
72        >>> c = Counter({'red': 4, 'blue': 2})      # a new counter from a mapping
73        >>> c = Counter(cats=4, dogs=8)             # a new counter from keyword args
74
75   Counter objects have a dictionary interface except that they return a zero
76   count for missing items instead of raising a :exc:`KeyError`:
77
78        >>> c = Counter(['eggs', 'ham'])
79        >>> c['bacon']                              # count of a missing element is zero
80        0
81
82   Setting a count to zero does not remove an element from a counter.
83   Use ``del`` to remove it entirely:
84
85        >>> c['sausage'] = 0                        # counter entry with a zero count
86        >>> del c['sausage']                        # del actually removes the entry
87
88   .. versionadded:: 2.7
89
90
91   Counter objects support three methods beyond those available for all
92   dictionaries:
93
94   .. method:: elements()
95
96      Return an iterator over elements repeating each as many times as its
97      count.  Elements are returned in arbitrary order.  If an element's count
98      is less than one, :meth:`elements` will ignore it.
99
100            >>> c = Counter(a=4, b=2, c=0, d=-2)
101            >>> list(c.elements())
102            ['a', 'a', 'a', 'a', 'b', 'b']
103
104   .. method:: most_common([n])
105
106      Return a list of the *n* most common elements and their counts from the
107      most common to the least.  If *n* is omitted or ``None``,
108      :func:`most_common` returns *all* elements in the counter.
109      Elements with equal counts are ordered arbitrarily:
110
111            >>> Counter('abracadabra').most_common(3)
112            [('a', 5), ('r', 2), ('b', 2)]
113
114   .. method:: subtract([iterable-or-mapping])
115
116      Elements are subtracted from an *iterable* or from another *mapping*
117      (or counter).  Like :meth:`dict.update` but subtracts counts instead
118      of replacing them.  Both inputs and outputs may be zero or negative.
119
120            >>> c = Counter(a=4, b=2, c=0, d=-2)
121            >>> d = Counter(a=1, b=2, c=3, d=4)
122            >>> c.subtract(d)
123            >>> c
124            Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})
125
126   The usual dictionary methods are available for :class:`Counter` objects
127   except for two which work differently for counters.
128
129   .. method:: fromkeys(iterable)
130
131      This class method is not implemented for :class:`Counter` objects.
132
133   .. method:: update([iterable-or-mapping])
134
135      Elements are counted from an *iterable* or added-in from another
136      *mapping* (or counter).  Like :meth:`dict.update` but adds counts
137      instead of replacing them.  Also, the *iterable* is expected to be a
138      sequence of elements, not a sequence of ``(key, value)`` pairs.
139
140Common patterns for working with :class:`Counter` objects::
141
142    sum(c.values())                 # total of all counts
143    c.clear()                       # reset all counts
144    list(c)                         # list unique elements
145    set(c)                          # convert to a set
146    dict(c)                         # convert to a regular dictionary
147    c.items()                       # convert to a list of (elem, cnt) pairs
148    Counter(dict(list_of_pairs))    # convert from a list of (elem, cnt) pairs
149    c.most_common()[:-n-1:-1]       # n least common elements
150    c += Counter()                  # remove zero and negative counts
151
152Several mathematical operations are provided for combining :class:`Counter`
153objects to produce multisets (counters that have counts greater than zero).
154Addition and subtraction combine counters by adding or subtracting the counts
155of corresponding elements.  Intersection and union return the minimum and
156maximum of corresponding counts.  Each operation can accept inputs with signed
157counts, but the output will exclude results with counts of zero or less.
158
159    >>> c = Counter(a=3, b=1)
160    >>> d = Counter(a=1, b=2)
161    >>> c + d                       # add two counters together:  c[x] + d[x]
162    Counter({'a': 4, 'b': 3})
163    >>> c - d                       # subtract (keeping only positive counts)
164    Counter({'a': 2})
165    >>> c & d                       # intersection:  min(c[x], d[x])
166    Counter({'a': 1, 'b': 1})
167    >>> c | d                       # union:  max(c[x], d[x])
168    Counter({'a': 3, 'b': 2})
169
170.. note::
171
172   Counters were primarily designed to work with positive integers to represent
173   running counts; however, care was taken to not unnecessarily preclude use
174   cases needing other types or negative values.  To help with those use cases,
175   this section documents the minimum range and type restrictions.
176
177   * The :class:`Counter` class itself is a dictionary subclass with no
178     restrictions on its keys and values.  The values are intended to be numbers
179     representing counts, but you *could* store anything in the value field.
180
181   * The :meth:`most_common` method requires only that the values be orderable.
182
183   * For in-place operations such as ``c[key] += 1``, the value type need only
184     support addition and subtraction.  So fractions, floats, and decimals would
185     work and negative values are supported.  The same is also true for
186     :meth:`update` and :meth:`subtract` which allow negative and zero values
187     for both inputs and outputs.
188
189   * The multiset methods are designed only for use cases with positive values.
190     The inputs may be negative or zero, but only outputs with positive values
191     are created.  There are no type restrictions, but the value type needs to
192     support addition, subtraction, and comparison.
193
194   * The :meth:`elements` method requires integer counts.  It ignores zero and
195     negative counts.
196
197.. seealso::
198
199    * `Counter class <https://code.activestate.com/recipes/576611/>`_
200      adapted for Python 2.5 and an early `Bag recipe
201      <https://code.activestate.com/recipes/259174/>`_ for Python 2.4.
202
203      in Smalltalk.
204
205    * Wikipedia entry for `Multisets <https://en.wikipedia.org/wiki/Multiset>`_.
206
207    * `C++ multisets <http://www.java2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm>`_
208      tutorial with examples.
209
210    * For mathematical operations on multisets and their use cases, see
211      *Knuth, Donald. The Art of Computer Programming Volume II,
212      Section 4.6.3, Exercise 19*.
213
214    * To enumerate all distinct multisets of a given size over a given set of
215      elements, see :func:`itertools.combinations_with_replacement`.
216
217          map(Counter, combinations_with_replacement('ABC', 2)) --> AA AB AC BB BC CC
218
219
220:class:`deque` objects
221----------------------
222
223.. class:: deque([iterable[, maxlen]])
224
225   Returns a new deque object initialized left-to-right (using :meth:`append`) with
226   data from *iterable*.  If *iterable* is not specified, the new deque is empty.
227
228   Deques are a generalization of stacks and queues (the name is pronounced "deck"
229   and is short for "double-ended queue").  Deques support thread-safe, memory
230   efficient appends and pops from either side of the deque with approximately the
231   same O(1) performance in either direction.
232
233   Though :class:`list` objects support similar operations, they are optimized for
234   fast fixed-length operations and incur O(n) memory movement costs for
235   ``pop(0)`` and ``insert(0, v)`` operations which change both the size and
236   position of the underlying data representation.
237
238   .. versionadded:: 2.4
239
240   If *maxlen* is not specified or is ``None``, deques may grow to an
241   arbitrary length.  Otherwise, the deque is bounded to the specified maximum
242   length.  Once a bounded length deque is full, when new items are added, a
243   corresponding number of items are discarded from the opposite end.  Bounded
244   length deques provide functionality similar to the ``tail`` filter in
245   Unix. They are also useful for tracking transactions and other pools of data
246   where only the most recent activity is of interest.
247
248   .. versionchanged:: 2.6
249      Added *maxlen* parameter.
250
251   Deque objects support the following methods:
252
253
254   .. method:: append(x)
255
256      Add *x* to the right side of the deque.
257
258
259   .. method:: appendleft(x)
260
261      Add *x* to the left side of the deque.
262
263
264   .. method:: clear()
265
266      Remove all elements from the deque leaving it with length 0.
267
268
269   .. method:: count(x)
270
271      Count the number of deque elements equal to *x*.
272
273      .. versionadded:: 2.7
274
275   .. method:: extend(iterable)
276
277      Extend the right side of the deque by appending elements from the iterable
278      argument.
279
280
281   .. method:: extendleft(iterable)
282
283      Extend the left side of the deque by appending elements from *iterable*.
284      Note, the series of left appends results in reversing the order of
285      elements in the iterable argument.
286
287
288   .. method:: pop()
289
290      Remove and return an element from the right side of the deque. If no
291      elements are present, raises an :exc:`IndexError`.
292
293
294   .. method:: popleft()
295
296      Remove and return an element from the left side of the deque. If no
297      elements are present, raises an :exc:`IndexError`.
298
299
300   .. method:: remove(value)
301
302      Removed the first occurrence of *value*.  If not found, raises a
303      :exc:`ValueError`.
304
305      .. versionadded:: 2.5
306
307   .. method:: reverse()
308
309      Reverse the elements of the deque in-place and then return ``None``.
310
311      .. versionadded:: 2.7
312
313   .. method:: rotate(n)
314
315      Rotate the deque *n* steps to the right.  If *n* is negative, rotate to
316      the left.  Rotating one step to the right is equivalent to:
317      ``d.appendleft(d.pop())``.
318
319
320   Deque objects also provide one read-only attribute:
321
322   .. attribute:: maxlen
323
324      Maximum size of a deque or ``None`` if unbounded.
325
326      .. versionadded:: 2.7
327
328
329In addition to the above, deques support iteration, pickling, ``len(d)``,
330``reversed(d)``, ``copy.copy(d)``, ``copy.deepcopy(d)``, membership testing with
331the :keyword:`in` operator, and subscript references such as ``d[-1]``.  Indexed
332access is O(1) at both ends but slows to O(n) in the middle.  For fast random
333access, use lists instead.
334
335Example:
336
337.. doctest::
338
339   >>> from collections import deque
340   >>> d = deque('ghi')                 # make a new deque with three items
341   >>> for elem in d:                   # iterate over the deque's elements
342   ...     print elem.upper()
343   G
344   H
345   I
346
347   >>> d.append('j')                    # add a new entry to the right side
348   >>> d.appendleft('f')                # add a new entry to the left side
349   >>> d                                # show the representation of the deque
350   deque(['f', 'g', 'h', 'i', 'j'])
351
352   >>> d.pop()                          # return and remove the rightmost item
353   'j'
354   >>> d.popleft()                      # return and remove the leftmost item
355   'f'
356   >>> list(d)                          # list the contents of the deque
357   ['g', 'h', 'i']
358   >>> d[0]                             # peek at leftmost item
359   'g'
360   >>> d[-1]                            # peek at rightmost item
361   'i'
362
363   >>> list(reversed(d))                # list the contents of a deque in reverse
364   ['i', 'h', 'g']
365   >>> 'h' in d                         # search the deque
366   True
367   >>> d.extend('jkl')                  # add multiple elements at once
368   >>> d
369   deque(['g', 'h', 'i', 'j', 'k', 'l'])
370   >>> d.rotate(1)                      # right rotation
371   >>> d
372   deque(['l', 'g', 'h', 'i', 'j', 'k'])
373   >>> d.rotate(-1)                     # left rotation
374   >>> d
375   deque(['g', 'h', 'i', 'j', 'k', 'l'])
376
377   >>> deque(reversed(d))               # make a new deque in reverse order
378   deque(['l', 'k', 'j', 'i', 'h', 'g'])
379   >>> d.clear()                        # empty the deque
380   >>> d.pop()                          # cannot pop from an empty deque
381   Traceback (most recent call last):
382     File "<pyshell#6>", line 1, in -toplevel-
383       d.pop()
384   IndexError: pop from an empty deque
385
386   >>> d.extendleft('abc')              # extendleft() reverses the input order
387   >>> d
388   deque(['c', 'b', 'a'])
389
390
391:class:`deque` Recipes
392^^^^^^^^^^^^^^^^^^^^^^
393
394This section shows various approaches to working with deques.
395
396Bounded length deques provide functionality similar to the ``tail`` filter
397in Unix::
398
399   def tail(filename, n=10):
400       'Return the last n lines of a file'
401       return deque(open(filename), n)
402
403Another approach to using deques is to maintain a sequence of recently
404added elements by appending to the right and popping to the left::
405
406    def moving_average(iterable, n=3):
407        # moving_average([40, 30, 50, 46, 39, 44]) --> 40.0 42.0 45.0 43.0
408        # http://en.wikipedia.org/wiki/Moving_average
409        it = iter(iterable)
410        d = deque(itertools.islice(it, n-1))
411        d.appendleft(0)
412        s = sum(d)
413        for elem in it:
414            s += elem - d.popleft()
415            d.append(elem)
416            yield s / float(n)
417
418The :meth:`rotate` method provides a way to implement :class:`deque` slicing and
419deletion.  For example, a pure Python implementation of ``del d[n]`` relies on
420the :meth:`rotate` method to position elements to be popped::
421
422   def delete_nth(d, n):
423       d.rotate(-n)
424       d.popleft()
425       d.rotate(n)
426
427To implement :class:`deque` slicing, use a similar approach applying
428:meth:`rotate` to bring a target element to the left side of the deque. Remove
429old entries with :meth:`popleft`, add new entries with :meth:`extend`, and then
430reverse the rotation.
431With minor variations on that approach, it is easy to implement Forth style
432stack manipulations such as ``dup``, ``drop``, ``swap``, ``over``, ``pick``,
433``rot``, and ``roll``.
434
435
436:class:`defaultdict` objects
437----------------------------
438
439.. class:: defaultdict([default_factory[, ...]])
440
441   Returns a new dictionary-like object.  :class:`defaultdict` is a subclass of the
442   built-in :class:`dict` class.  It overrides one method and adds one writable
443   instance variable.  The remaining functionality is the same as for the
444   :class:`dict` class and is not documented here.
445
446   The first argument provides the initial value for the :attr:`default_factory`
447   attribute; it defaults to ``None``. All remaining arguments are treated the same
448   as if they were passed to the :class:`dict` constructor, including keyword
449   arguments.
450
451   .. versionadded:: 2.5
452
453   :class:`defaultdict` objects support the following method in addition to the
454   standard :class:`dict` operations:
455
456   .. method:: __missing__(key)
457
458      If the :attr:`default_factory` attribute is ``None``, this raises a
459      :exc:`KeyError` exception with the *key* as argument.
460
461      If :attr:`default_factory` is not ``None``, it is called without arguments
462      to provide a default value for the given *key*, this value is inserted in
463      the dictionary for the *key*, and returned.
464
465      If calling :attr:`default_factory` raises an exception this exception is
466      propagated unchanged.
467
468      This method is called by the :meth:`__getitem__` method of the
469      :class:`dict` class when the requested key is not found; whatever it
470      returns or raises is then returned or raised by :meth:`__getitem__`.
471
472      Note that :meth:`__missing__` is *not* called for any operations besides
473      :meth:`__getitem__`. This means that :meth:`get` will, like normal
474      dictionaries, return ``None`` as a default rather than using
475      :attr:`default_factory`.
476
477
478   :class:`defaultdict` objects support the following instance variable:
479
480
481   .. attribute:: default_factory
482
483      This attribute is used by the :meth:`__missing__` method; it is
484      initialized from the first argument to the constructor, if present, or to
485      ``None``, if absent.
486
487
488:class:`defaultdict` Examples
489^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
490
491Using :class:`list` as the :attr:`default_factory`, it is easy to group a
492sequence of key-value pairs into a dictionary of lists:
493
494   >>> s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
495   >>> d = defaultdict(list)
496   >>> for k, v in s:
497   ...     d[k].append(v)
498   ...
499   >>> d.items()
500   [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]
501
502When each key is encountered for the first time, it is not already in the
503mapping; so an entry is automatically created using the :attr:`default_factory`
504function which returns an empty :class:`list`.  The :meth:`list.append`
505operation then attaches the value to the new list.  When keys are encountered
506again, the look-up proceeds normally (returning the list for that key) and the
507:meth:`list.append` operation adds another value to the list. This technique is
508simpler and faster than an equivalent technique using :meth:`dict.setdefault`:
509
510   >>> d = {}
511   >>> for k, v in s:
512   ...     d.setdefault(k, []).append(v)
513   ...
514   >>> d.items()
515   [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]
516
517Setting the :attr:`default_factory` to :class:`int` makes the
518:class:`defaultdict` useful for counting (like a bag or multiset in other
519languages):
520
521   >>> s = 'mississippi'
522   >>> d = defaultdict(int)
523   >>> for k in s:
524   ...     d[k] += 1
525   ...
526   >>> d.items()
527   [('i', 4), ('p', 2), ('s', 4), ('m', 1)]
528
529When a letter is first encountered, it is missing from the mapping, so the
530:attr:`default_factory` function calls :func:`int` to supply a default count of
531zero.  The increment operation then builds up the count for each letter.
532
533The function :func:`int` which always returns zero is just a special case of
534constant functions.  A faster and more flexible way to create constant functions
535is to use :func:`itertools.repeat` which can supply any constant value (not just
536zero):
537
538   >>> def constant_factory(value):
539   ...     return itertools.repeat(value).next
540   >>> d = defaultdict(constant_factory('<missing>'))
541   >>> d.update(name='John', action='ran')
542   >>> '%(name)s %(action)s to %(object)s' % d
543   'John ran to <missing>'
544
545Setting the :attr:`default_factory` to :class:`set` makes the
546:class:`defaultdict` useful for building a dictionary of sets:
547
548   >>> s = [('red', 1), ('blue', 2), ('red', 3), ('blue', 4), ('red', 1), ('blue', 4)]
549   >>> d = defaultdict(set)
550   >>> for k, v in s:
551   ...     d[k].add(v)
552   ...
553   >>> d.items()
554   [('blue', set([2, 4])), ('red', set([1, 3]))]
555
556
557:func:`namedtuple` Factory Function for Tuples with Named Fields
558----------------------------------------------------------------
559
560Named tuples assign meaning to each position in a tuple and allow for more readable,
561self-documenting code.  They can be used wherever regular tuples are used, and
562they add the ability to access fields by name instead of position index.
563
564.. function:: namedtuple(typename, field_names, [verbose=False], [rename=False])
565
566   Returns a new tuple subclass named *typename*.  The new subclass is used to
567   create tuple-like objects that have fields accessible by attribute lookup as
568   well as being indexable and iterable.  Instances of the subclass also have a
569   helpful docstring (with typename and field_names) and a helpful :meth:`__repr__`
570   method which lists the tuple contents in a ``name=value`` format.
571
572   The *field_names* are a sequence of strings such as ``['x', 'y']``.
573   Alternatively, *field_names* can be a single string with each fieldname
574   separated by whitespace and/or commas, for example ``'x y'`` or ``'x, y'``.
575
576   Any valid Python identifier may be used for a fieldname except for names
577   starting with an underscore.  Valid identifiers consist of letters, digits,
578   and underscores but do not start with a digit or underscore and cannot be
579   a :mod:`keyword` such as *class*, *for*, *return*, *global*, *pass*, *print*,
580   or *raise*.
581
582   If *rename* is true, invalid fieldnames are automatically replaced
583   with positional names.  For example, ``['abc', 'def', 'ghi', 'abc']`` is
584   converted to ``['abc', '_1', 'ghi', '_3']``, eliminating the keyword
585   ``def`` and the duplicate fieldname ``abc``.
586
587   If *verbose* is true, the class definition is printed just before being built.
588
589   Named tuple instances do not have per-instance dictionaries, so they are
590   lightweight and require no more memory than regular tuples.
591
592   .. versionadded:: 2.6
593
594   .. versionchanged:: 2.7
595      added support for *rename*.
596
597Example:
598
599.. doctest::
600   :options: +NORMALIZE_WHITESPACE
601
602   >>> Point = namedtuple('Point', ['x', 'y'], verbose=True)
603   class Point(tuple):
604       'Point(x, y)'
605   <BLANKLINE>
606       __slots__ = ()
607   <BLANKLINE>
608       _fields = ('x', 'y')
609   <BLANKLINE>
610       def __new__(_cls, x, y):
611           'Create new instance of Point(x, y)'
612           return _tuple.__new__(_cls, (x, y))
613   <BLANKLINE>
614       @classmethod
615       def _make(cls, iterable, new=tuple.__new__, len=len):
616           'Make a new Point object from a sequence or iterable'
617           result = new(cls, iterable)
618           if len(result) != 2:
619               raise TypeError('Expected 2 arguments, got %d' % len(result))
620           return result
621   <BLANKLINE>
622       def __repr__(self):
623           'Return a nicely formatted representation string'
624           return 'Point(x=%r, y=%r)' % self
625   <BLANKLINE>
626       def _asdict(self):
627           'Return a new OrderedDict which maps field names to their values'
628           return OrderedDict(zip(self._fields, self))
629   <BLANKLINE>
630       def _replace(_self, **kwds):
631           'Return a new Point object replacing specified fields with new values'
632           result = _self._make(map(kwds.pop, ('x', 'y'), _self))
633           if kwds:
634               raise ValueError('Got unexpected field names: %r' % kwds.keys())
635           return result
636   <BLANKLINE>
637       def __getnewargs__(self):
638           'Return self as a plain tuple.  Used by copy and pickle.'
639           return tuple(self)
640   <BLANKLINE>
641       __dict__ = _property(_asdict)
642   <BLANKLINE>
643       def __getstate__(self):
644           'Exclude the OrderedDict from pickling'
645           pass
646   <BLANKLINE>
647       x = _property(_itemgetter(0), doc='Alias for field number 0')
648   <BLANKLINE>
649       y = _property(_itemgetter(1), doc='Alias for field number 1')
650   <BLANKLINE>
651   <BLANKLINE>
652
653   >>> p = Point(11, y=22)     # instantiate with positional or keyword arguments
654   >>> p[0] + p[1]             # indexable like the plain tuple (11, 22)
655   33
656   >>> x, y = p                # unpack like a regular tuple
657   >>> x, y
658   (11, 22)
659   >>> p.x + p.y               # fields also accessible by name
660   33
661   >>> p                       # readable __repr__ with a name=value style
662   Point(x=11, y=22)
663
664Named tuples are especially useful for assigning field names to result tuples returned
665by the :mod:`csv` or :mod:`sqlite3` modules::
666
667   EmployeeRecord = namedtuple('EmployeeRecord', 'name, age, title, department, paygrade')
668
669   import csv
670   for emp in map(EmployeeRecord._make, csv.reader(open("employees.csv", "rb"))):
671       print emp.name, emp.title
672
673   import sqlite3
674   conn = sqlite3.connect('/companydata')
675   cursor = conn.cursor()
676   cursor.execute('SELECT name, age, title, department, paygrade FROM employees')
677   for emp in map(EmployeeRecord._make, cursor.fetchall()):
678       print emp.name, emp.title
679
680In addition to the methods inherited from tuples, named tuples support
681three additional methods and one attribute.  To prevent conflicts with
682field names, the method and attribute names start with an underscore.
683
684.. classmethod:: somenamedtuple._make(iterable)
685
686   Class method that makes a new instance from an existing sequence or iterable.
687
688   .. doctest::
689
690      >>> t = [11, 22]
691      >>> Point._make(t)
692      Point(x=11, y=22)
693
694.. method:: somenamedtuple._asdict()
695
696   Return a new :class:`OrderedDict` which maps field names to their corresponding
697   values::
698
699      >>> p = Point(x=11, y=22)
700      >>> p._asdict()
701      OrderedDict([('x', 11), ('y', 22)])
702
703   .. versionchanged:: 2.7
704      Returns an :class:`OrderedDict` instead of a regular :class:`dict`.
705
706.. method:: somenamedtuple._replace(kwargs)
707
708   Return a new instance of the named tuple replacing specified fields with new
709   values::
710
711      >>> p = Point(x=11, y=22)
712      >>> p._replace(x=33)
713      Point(x=33, y=22)
714
715      >>> for partnum, record in inventory.items():
716      ...     inventory[partnum] = record._replace(price=newprices[partnum], timestamp=time.now())
717
718.. attribute:: somenamedtuple._fields
719
720   Tuple of strings listing the field names.  Useful for introspection
721   and for creating new named tuple types from existing named tuples.
722
723   .. doctest::
724
725      >>> p._fields            # view the field names
726      ('x', 'y')
727
728      >>> Color = namedtuple('Color', 'red green blue')
729      >>> Pixel = namedtuple('Pixel', Point._fields + Color._fields)
730      >>> Pixel(11, 22, 128, 255, 0)
731      Pixel(x=11, y=22, red=128, green=255, blue=0)
732
733To retrieve a field whose name is stored in a string, use the :func:`getattr`
734function:
735
736    >>> getattr(p, 'x')
737    11
738
739To convert a dictionary to a named tuple, use the double-star-operator
740(as described in :ref:`tut-unpacking-arguments`):
741
742   >>> d = {'x': 11, 'y': 22}
743   >>> Point(**d)
744   Point(x=11, y=22)
745
746Since a named tuple is a regular Python class, it is easy to add or change
747functionality with a subclass.  Here is how to add a calculated field and
748a fixed-width print format:
749
750    >>> class Point(namedtuple('Point', 'x y')):
751    ...     __slots__ = ()
752    ...     @property
753    ...     def hypot(self):
754    ...         return (self.x ** 2 + self.y ** 2) ** 0.5
755    ...     def __str__(self):
756    ...         return 'Point: x=%6.3f  y=%6.3f  hypot=%6.3f' % (self.x, self.y, self.hypot)
757    ...
758    >>> for p in Point(3, 4), Point(14, 5/7.):
759    ...     print p
760    Point: x= 3.000  y= 4.000  hypot= 5.000
761    Point: x=14.000  y= 0.714  hypot=14.018
762
763The subclass shown above sets ``__slots__`` to an empty tuple.  This helps
764keep memory requirements low by preventing the creation of instance dictionaries.
765
766Subclassing is not useful for adding new, stored fields.  Instead, simply
767create a new named tuple type from the :attr:`_fields` attribute:
768
769    >>> Point3D = namedtuple('Point3D', Point._fields + ('z',))
770
771Default values can be implemented by using :meth:`_replace` to
772customize a prototype instance:
773
774    >>> Account = namedtuple('Account', 'owner balance transaction_count')
775    >>> default_account = Account('<owner name>', 0.0, 0)
776    >>> johns_account = default_account._replace(owner='John')
777
778Enumerated constants can be implemented with named tuples, but it is simpler
779and more efficient to use a simple class declaration:
780
781    >>> Status = namedtuple('Status', 'open pending closed')._make(range(3))
782    >>> Status.open, Status.pending, Status.closed
783    (0, 1, 2)
784    >>> class Status:
785    ...     open, pending, closed = range(3)
786
787.. seealso::
788
789   `Named tuple recipe <https://code.activestate.com/recipes/500261/>`_
790   adapted for Python 2.4.
791
792
793:class:`OrderedDict` objects
794----------------------------
795
796Ordered dictionaries are just like regular dictionaries but they remember the
797order that items were inserted.  When iterating over an ordered dictionary,
798the items are returned in the order their keys were first added.
799
800.. class:: OrderedDict([items])
801
802   Return an instance of a dict subclass, supporting the usual :class:`dict`
803   methods.  An *OrderedDict* is a dict that remembers the order that keys
804   were first inserted. If a new entry overwrites an existing entry, the
805   original insertion position is left unchanged.  Deleting an entry and
806   reinserting it will move it to the end.
807
808   .. versionadded:: 2.7
809
810.. method:: OrderedDict.popitem(last=True)
811
812   The :meth:`popitem` method for ordered dictionaries returns and removes
813   a (key, value) pair.  The pairs are returned in LIFO order if *last* is
814   true or FIFO order if false.
815
816In addition to the usual mapping methods, ordered dictionaries also support
817reverse iteration using :func:`reversed`.
818
819Equality tests between :class:`OrderedDict` objects are order-sensitive
820and are implemented as ``list(od1.items())==list(od2.items())``.
821Equality tests between :class:`OrderedDict` objects and other
822:class:`Mapping` objects are order-insensitive like regular
823dictionaries.  This allows :class:`OrderedDict` objects to be substituted
824anywhere a regular dictionary is used.
825
826The :class:`OrderedDict` constructor and :meth:`update` method both accept
827keyword arguments, but their order is lost because Python's function call
828semantics pass-in keyword arguments using a regular unordered dictionary.
829
830.. seealso::
831
832   `Equivalent OrderedDict recipe <https://code.activestate.com/recipes/576693/>`_
833   that runs on Python 2.4 or later.
834
835:class:`OrderedDict` Examples and Recipes
836^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
837
838Since an ordered dictionary remembers its insertion order, it can be used
839in conjunction with sorting to make a sorted dictionary::
840
841    >>> # regular unsorted dictionary
842    >>> d = {'banana': 3, 'apple': 4, 'pear': 1, 'orange': 2}
843
844    >>> # dictionary sorted by key
845    >>> OrderedDict(sorted(d.items(), key=lambda t: t[0]))
846    OrderedDict([('apple', 4), ('banana', 3), ('orange', 2), ('pear', 1)])
847
848    >>> # dictionary sorted by value
849    >>> OrderedDict(sorted(d.items(), key=lambda t: t[1]))
850    OrderedDict([('pear', 1), ('orange', 2), ('banana', 3), ('apple', 4)])
851
852    >>> # dictionary sorted by length of the key string
853    >>> OrderedDict(sorted(d.items(), key=lambda t: len(t[0])))
854    OrderedDict([('pear', 1), ('apple', 4), ('orange', 2), ('banana', 3)])
855
856The new sorted dictionaries maintain their sort order when entries
857are deleted.  But when new keys are added, the keys are appended
858to the end and the sort is not maintained.
859
860It is also straight-forward to create an ordered dictionary variant
861that remembers the order the keys were *last* inserted.
862If a new entry overwrites an existing entry, the
863original insertion position is changed and moved to the end::
864
865    class LastUpdatedOrderedDict(OrderedDict):
866        'Store items in the order the keys were last added'
867
868        def __setitem__(self, key, value):
869            if key in self:
870                del self[key]
871            OrderedDict.__setitem__(self, key, value)
872
873An ordered dictionary can be combined with the :class:`Counter` class
874so that the counter remembers the order elements are first encountered::
875
876   class OrderedCounter(Counter, OrderedDict):
877        'Counter that remembers the order elements are first encountered'
878
879        def __repr__(self):
880            return '%s(%r)' % (self.__class__.__name__, OrderedDict(self))
881
882        def __reduce__(self):
883            return self.__class__, (OrderedDict(self),)
884
885
886.. _collections-abstract-base-classes:
887
888Collections Abstract Base Classes
889---------------------------------
890
891The collections module offers the following :term:`ABCs <abstract base class>`:
892
893=========================  =====================  ======================  ====================================================
894ABC                        Inherits from          Abstract Methods        Mixin Methods
895=========================  =====================  ======================  ====================================================
896:class:`Container`                                ``__contains__``
897:class:`Hashable`                                 ``__hash__``
898:class:`Iterable`                                 ``__iter__``
899:class:`Iterator`          :class:`Iterable`      ``next``                ``__iter__``
900:class:`Sized`                                    ``__len__``
901:class:`Callable`                                 ``__call__``
902
903:class:`Sequence`          :class:`Sized`,        ``__getitem__``,        ``__contains__``, ``__iter__``, ``__reversed__``,
904                           :class:`Iterable`,     ``__len__``             ``index``, and ``count``
905                           :class:`Container`
906
907:class:`MutableSequence`   :class:`Sequence`      ``__getitem__``,        Inherited :class:`Sequence` methods and
908                                                  ``__setitem__``,        ``append``, ``reverse``, ``extend``, ``pop``,
909                                                  ``__delitem__``,        ``remove``, and ``__iadd__``
910                                                  ``__len__``,
911                                                  ``insert``
912
913:class:`Set`               :class:`Sized`,        ``__contains__``,       ``__le__``, ``__lt__``, ``__eq__``, ``__ne__``,
914                           :class:`Iterable`,     ``__iter__``,           ``__gt__``, ``__ge__``, ``__and__``, ``__or__``,
915                           :class:`Container`     ``__len__``             ``__sub__``, ``__xor__``, and ``isdisjoint``
916
917:class:`MutableSet`        :class:`Set`           ``__contains__``,       Inherited :class:`Set` methods and
918                                                  ``__iter__``,           ``clear``, ``pop``, ``remove``, ``__ior__``,
919                                                  ``__len__``,            ``__iand__``, ``__ixor__``, and ``__isub__``
920                                                  ``add``,
921                                                  ``discard``
922
923:class:`Mapping`           :class:`Sized`,        ``__getitem__``,        ``__contains__``, ``keys``, ``items``, ``values``,
924                           :class:`Iterable`,     ``__iter__``,           ``get``, ``__eq__``, and ``__ne__``
925                           :class:`Container`     ``__len__``
926
927:class:`MutableMapping`    :class:`Mapping`       ``__getitem__``,        Inherited :class:`Mapping` methods and
928                                                  ``__setitem__``,        ``pop``, ``popitem``, ``clear``, ``update``,
929                                                  ``__delitem__``,        and ``setdefault``
930                                                  ``__iter__``,
931                                                  ``__len__``
932
933
934:class:`MappingView`       :class:`Sized`                                 ``__len__``
935:class:`ItemsView`         :class:`MappingView`,                          ``__contains__``,
936                           :class:`Set`                                   ``__iter__``
937:class:`KeysView`          :class:`MappingView`,                          ``__contains__``,
938                           :class:`Set`                                   ``__iter__``
939:class:`ValuesView`        :class:`MappingView`                           ``__contains__``, ``__iter__``
940=========================  =====================  ======================  ====================================================
941
942
943.. class:: Container
944           Hashable
945           Sized
946           Callable
947
948   ABCs for classes that provide respectively the methods :meth:`__contains__`,
949   :meth:`__hash__`, :meth:`__len__`, and :meth:`__call__`.
950
951.. class:: Iterable
952
953   ABC for classes that provide the :meth:`__iter__` method.
954   See also the definition of :term:`iterable`.
955
956.. class:: Iterator
957
958   ABC for classes that provide the :meth:`~iterator.__iter__` and
959   :meth:`~iterator.next` methods.  See also the definition of :term:`iterator`.
960
961.. class:: Sequence
962           MutableSequence
963
964   ABCs for read-only and mutable :term:`sequences <sequence>`.
965
966.. class:: Set
967           MutableSet
968
969   ABCs for read-only and mutable sets.
970
971.. class:: Mapping
972           MutableMapping
973
974   ABCs for read-only and mutable :term:`mappings <mapping>`.
975
976.. class:: MappingView
977           ItemsView
978           KeysView
979           ValuesView
980
981   ABCs for mapping, items, keys, and values :term:`views <dictionary view>`.
982
983
984These ABCs allow us to ask classes or instances if they provide
985particular functionality, for example::
986
987    size = None
988    if isinstance(myvar, collections.Sized):
989        size = len(myvar)
990
991Several of the ABCs are also useful as mixins that make it easier to develop
992classes supporting container APIs.  For example, to write a class supporting
993the full :class:`Set` API, it only necessary to supply the three underlying
994abstract methods: :meth:`__contains__`, :meth:`__iter__`, and :meth:`__len__`.
995The ABC supplies the remaining methods such as :meth:`__and__` and
996:meth:`isdisjoint` ::
997
998    class ListBasedSet(collections.Set):
999         ''' Alternate set implementation favoring space over speed
1000             and not requiring the set elements to be hashable. '''
1001         def __init__(self, iterable):
1002             self.elements = lst = []
1003             for value in iterable:
1004                 if value not in lst:
1005                     lst.append(value)
1006
1007         def __iter__(self):
1008             return iter(self.elements)
1009
1010         def __contains__(self, value):
1011             return value in self.elements
1012
1013         def __len__(self):
1014             return len(self.elements)
1015
1016    s1 = ListBasedSet('abcdef')
1017    s2 = ListBasedSet('defghi')
1018    overlap = s1 & s2            # The __and__() method is supported automatically
1019
1020Notes on using :class:`Set` and :class:`MutableSet` as a mixin:
1021
1022(1)
1023   Since some set operations create new sets, the default mixin methods need
1024   a way to create new instances from an iterable. The class constructor is
1025   assumed to have a signature in the form ``ClassName(iterable)``.
1026   That assumption is factored-out to an internal classmethod called
1027   :meth:`_from_iterable` which calls ``cls(iterable)`` to produce a new set.
1028   If the :class:`Set` mixin is being used in a class with a different
1029   constructor signature, you will need to override :meth:`_from_iterable`
1030   with a classmethod that can construct new instances from
1031   an iterable argument.
1032
1033(2)
1034   To override the comparisons (presumably for speed, as the
1035   semantics are fixed), redefine :meth:`__le__` and :meth:`__ge__`,
1036   then the other operations will automatically follow suit.
1037
1038(3)
1039   The :class:`Set` mixin provides a :meth:`_hash` method to compute a hash value
1040   for the set; however, :meth:`__hash__` is not defined because not all sets
1041   are hashable or immutable.  To add set hashability using mixins,
1042   inherit from both :meth:`Set` and :meth:`Hashable`, then define
1043   ``__hash__ = Set._hash``.
1044
1045.. seealso::
1046
1047   * `OrderedSet recipe <https://code.activestate.com/recipes/576694/>`_ for an
1048     example built on :class:`MutableSet`.
1049
1050   * For more about ABCs, see the :mod:`abc` module and :pep:`3119`.
1051