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