1 :mod:`collections` --- Container datatypes 2 ========================================== 3 4 .. module:: collections 5 :synopsis: Container datatypes 6 7 .. moduleauthor:: Raymond Hettinger <python (a] rcn.com> 8 .. sectionauthor:: Raymond Hettinger <python (a] rcn.com> 9 10 **Source code:** :source:`Lib/collections/__init__.py` 11 12 .. testsetup:: * 13 14 from collections import * 15 import itertools 16 __name__ = '<doctest>' 17 18 -------------- 19 20 This module implements specialized container datatypes providing alternatives to 21 Python's general purpose built-in containers, :class:`dict`, :class:`list`, 22 :class:`set`, and :class:`tuple`. 23 24 ===================== ==================================================================== 25 :func:`namedtuple` factory function for creating tuple subclasses with named fields 26 :class:`deque` list-like container with fast appends and pops on either end 27 :class:`ChainMap` dict-like class for creating a single view of multiple mappings 28 :class:`Counter` dict subclass for counting hashable objects 29 :class:`OrderedDict` dict subclass that remembers the order entries were added 30 :class:`defaultdict` dict subclass that calls a factory function to supply missing values 31 :class:`UserDict` wrapper around dictionary objects for easier dict subclassing 32 :class:`UserList` wrapper around list objects for easier list subclassing 33 :class:`UserString` wrapper around string objects for easier string subclassing 34 ===================== ==================================================================== 35 36 .. versionchanged:: 3.3 37 Moved :ref:`collections-abstract-base-classes` to the :mod:`collections.abc` module. 38 For backwards compatibility, they continue to be visible in this module 39 as well. 40 41 42 :class:`ChainMap` objects 43 ------------------------- 44 45 .. versionadded:: 3.3 46 47 A :class:`ChainMap` class is provided for quickly linking a number of mappings 48 so they can be treated as a single unit. It is often much faster than creating 49 a new dictionary and running multiple :meth:`~dict.update` calls. 50 51 The class can be used to simulate nested scopes and is useful in templating. 52 53 .. class:: ChainMap(*maps) 54 55 A :class:`ChainMap` groups multiple dicts or other mappings together to 56 create a single, updateable view. If no *maps* are specified, a single empty 57 dictionary is provided so that a new chain always has at least one mapping. 58 59 The underlying mappings are stored in a list. That list is public and can 60 be accessed or updated using the *maps* attribute. There is no other state. 61 62 Lookups search the underlying mappings successively until a key is found. In 63 contrast, writes, updates, and deletions only operate on the first mapping. 64 65 A :class:`ChainMap` incorporates the underlying mappings by reference. So, if 66 one of the underlying mappings gets updated, those changes will be reflected 67 in :class:`ChainMap`. 68 69 All of the usual dictionary methods are supported. In addition, there is a 70 *maps* attribute, a method for creating new subcontexts, and a property for 71 accessing all but the first mapping: 72 73 .. attribute:: maps 74 75 A user updateable list of mappings. The list is ordered from 76 first-searched to last-searched. It is the only stored state and can 77 be modified to change which mappings are searched. The list should 78 always contain at least one mapping. 79 80 .. method:: new_child(m=None) 81 82 Returns a new :class:`ChainMap` containing a new map followed by 83 all of the maps in the current instance. If ``m`` is specified, 84 it becomes the new map at the front of the list of mappings; if not 85 specified, an empty dict is used, so that a call to ``d.new_child()`` 86 is equivalent to: ``ChainMap({}, *d.maps)``. This method is used for 87 creating subcontexts that can be updated without altering values in any 88 of the parent mappings. 89 90 .. versionchanged:: 3.4 91 The optional ``m`` parameter was added. 92 93 .. attribute:: parents 94 95 Property returning a new :class:`ChainMap` containing all of the maps in 96 the current instance except the first one. This is useful for skipping 97 the first map in the search. Use cases are similar to those for the 98 :keyword:`nonlocal` keyword used in :term:`nested scopes <nested 99 scope>`. The use cases also parallel those for the built-in 100 :func:`super` function. A reference to ``d.parents`` is equivalent to: 101 ``ChainMap(*d.maps[1:])``. 102 103 104 .. seealso:: 105 106 * The `MultiContext class 107 <https://github.com/enthought/codetools/blob/4.0.0/codetools/contexts/multi_context.py>`_ 108 in the Enthought `CodeTools package 109 <https://github.com/enthought/codetools>`_ has options to support 110 writing to any mapping in the chain. 111 112 * Django's `Context class 113 <https://github.com/django/django/blob/master/django/template/context.py>`_ 114 for templating is a read-only chain of mappings. It also features 115 pushing and popping of contexts similar to the 116 :meth:`~collections.ChainMap.new_child` method and the 117 :meth:`~collections.ChainMap.parents` property. 118 119 * The `Nested Contexts recipe 120 <https://code.activestate.com/recipes/577434/>`_ has options to control 121 whether writes and other mutations apply only to the first mapping or to 122 any mapping in the chain. 123 124 * A `greatly simplified read-only version of Chainmap 125 <https://code.activestate.com/recipes/305268/>`_. 126 127 128 :class:`ChainMap` Examples and Recipes 129 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 130 131 This section shows various approaches to working with chained maps. 132 133 134 Example of simulating Python's internal lookup chain:: 135 136 import builtins 137 pylookup = ChainMap(locals(), globals(), vars(builtins)) 138 139 Example of letting user specified command-line arguments take precedence over 140 environment variables which in turn take precedence over default values:: 141 142 import os, argparse 143 144 defaults = {'color': 'red', 'user': 'guest'} 145 146 parser = argparse.ArgumentParser() 147 parser.add_argument('-u', '--user') 148 parser.add_argument('-c', '--color') 149 namespace = parser.parse_args() 150 command_line_args = {k:v for k, v in vars(namespace).items() if v} 151 152 combined = ChainMap(command_line_args, os.environ, defaults) 153 print(combined['color']) 154 print(combined['user']) 155 156 Example patterns for using the :class:`ChainMap` class to simulate nested 157 contexts:: 158 159 c = ChainMap() # Create root context 160 d = c.new_child() # Create nested child context 161 e = c.new_child() # Child of c, independent from d 162 e.maps[0] # Current context dictionary -- like Python's locals() 163 e.maps[-1] # Root context -- like Python's globals() 164 e.parents # Enclosing context chain -- like Python's nonlocals 165 166 d['x'] # Get first key in the chain of contexts 167 d['x'] = 1 # Set value in current context 168 del d['x'] # Delete from current context 169 list(d) # All nested values 170 k in d # Check all nested values 171 len(d) # Number of nested values 172 d.items() # All nested items 173 dict(d) # Flatten into a regular dictionary 174 175 The :class:`ChainMap` class only makes updates (writes and deletions) to the 176 first mapping in the chain while lookups will search the full chain. However, 177 if deep writes and deletions are desired, it is easy to make a subclass that 178 updates keys found deeper in the chain:: 179 180 class DeepChainMap(ChainMap): 181 'Variant of ChainMap that allows direct updates to inner scopes' 182 183 def __setitem__(self, key, value): 184 for mapping in self.maps: 185 if key in mapping: 186 mapping[key] = value 187 return 188 self.maps[0][key] = value 189 190 def __delitem__(self, key): 191 for mapping in self.maps: 192 if key in mapping: 193 del mapping[key] 194 return 195 raise KeyError(key) 196 197 >>> d = DeepChainMap({'zebra': 'black'}, {'elephant': 'blue'}, {'lion': 'yellow'}) 198 >>> d['lion'] = 'orange' # update an existing key two levels down 199 >>> d['snake'] = 'red' # new keys get added to the topmost dict 200 >>> del d['elephant'] # remove an existing key one level down 201 DeepChainMap({'zebra': 'black', 'snake': 'red'}, {}, {'lion': 'orange'}) 202 203 204 :class:`Counter` objects 205 ------------------------ 206 207 A counter tool is provided to support convenient and rapid tallies. 208 For example:: 209 210 >>> # Tally occurrences of words in a list 211 >>> cnt = Counter() 212 >>> for word in ['red', 'blue', 'red', 'green', 'blue', 'blue']: 213 ... cnt[word] += 1 214 >>> cnt 215 Counter({'blue': 3, 'red': 2, 'green': 1}) 216 217 >>> # Find the ten most common words in Hamlet 218 >>> import re 219 >>> words = re.findall(r'\w+', open('hamlet.txt').read().lower()) 220 >>> Counter(words).most_common(10) 221 [('the', 1143), ('and', 966), ('to', 762), ('of', 669), ('i', 631), 222 ('you', 554), ('a', 546), ('my', 514), ('hamlet', 471), ('in', 451)] 223 224 .. class:: Counter([iterable-or-mapping]) 225 226 A :class:`Counter` is a :class:`dict` subclass for counting hashable objects. 227 It is an unordered collection where elements are stored as dictionary keys 228 and their counts are stored as dictionary values. Counts are allowed to be 229 any integer value including zero or negative counts. The :class:`Counter` 230 class is similar to bags or multisets in other languages. 231 232 Elements are counted from an *iterable* or initialized from another 233 *mapping* (or counter): 234 235 >>> c = Counter() # a new, empty counter 236 >>> c = Counter('gallahad') # a new counter from an iterable 237 >>> c = Counter({'red': 4, 'blue': 2}) # a new counter from a mapping 238 >>> c = Counter(cats=4, dogs=8) # a new counter from keyword args 239 240 Counter objects have a dictionary interface except that they return a zero 241 count for missing items instead of raising a :exc:`KeyError`: 242 243 >>> c = Counter(['eggs', 'ham']) 244 >>> c['bacon'] # count of a missing element is zero 245 0 246 247 Setting a count to zero does not remove an element from a counter. 248 Use ``del`` to remove it entirely: 249 250 >>> c['sausage'] = 0 # counter entry with a zero count 251 >>> del c['sausage'] # del actually removes the entry 252 253 .. versionadded:: 3.1 254 255 256 Counter objects support three methods beyond those available for all 257 dictionaries: 258 259 .. method:: elements() 260 261 Return an iterator over elements repeating each as many times as its 262 count. Elements are returned in arbitrary order. If an element's count 263 is less than one, :meth:`elements` will ignore it. 264 265 >>> c = Counter(a=4, b=2, c=0, d=-2) 266 >>> sorted(c.elements()) 267 ['a', 'a', 'a', 'a', 'b', 'b'] 268 269 .. method:: most_common([n]) 270 271 Return a list of the *n* most common elements and their counts from the 272 most common to the least. If *n* is omitted or ``None``, 273 :func:`most_common` returns *all* elements in the counter. 274 Elements with equal counts are ordered arbitrarily: 275 276 >>> Counter('abracadabra').most_common(3) # doctest: +SKIP 277 [('a', 5), ('r', 2), ('b', 2)] 278 279 .. method:: subtract([iterable-or-mapping]) 280 281 Elements are subtracted from an *iterable* or from another *mapping* 282 (or counter). Like :meth:`dict.update` but subtracts counts instead 283 of replacing them. Both inputs and outputs may be zero or negative. 284 285 >>> c = Counter(a=4, b=2, c=0, d=-2) 286 >>> d = Counter(a=1, b=2, c=3, d=4) 287 >>> c.subtract(d) 288 >>> c 289 Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6}) 290 291 .. versionadded:: 3.2 292 293 The usual dictionary methods are available for :class:`Counter` objects 294 except for two which work differently for counters. 295 296 .. method:: fromkeys(iterable) 297 298 This class method is not implemented for :class:`Counter` objects. 299 300 .. method:: update([iterable-or-mapping]) 301 302 Elements are counted from an *iterable* or added-in from another 303 *mapping* (or counter). Like :meth:`dict.update` but adds counts 304 instead of replacing them. Also, the *iterable* is expected to be a 305 sequence of elements, not a sequence of ``(key, value)`` pairs. 306 307 Common patterns for working with :class:`Counter` objects:: 308 309 sum(c.values()) # total of all counts 310 c.clear() # reset all counts 311 list(c) # list unique elements 312 set(c) # convert to a set 313 dict(c) # convert to a regular dictionary 314 c.items() # convert to a list of (elem, cnt) pairs 315 Counter(dict(list_of_pairs)) # convert from a list of (elem, cnt) pairs 316 c.most_common()[:-n-1:-1] # n least common elements 317 +c # remove zero and negative counts 318 319 Several mathematical operations are provided for combining :class:`Counter` 320 objects to produce multisets (counters that have counts greater than zero). 321 Addition and subtraction combine counters by adding or subtracting the counts 322 of corresponding elements. Intersection and union return the minimum and 323 maximum of corresponding counts. Each operation can accept inputs with signed 324 counts, but the output will exclude results with counts of zero or less. 325 326 >>> c = Counter(a=3, b=1) 327 >>> d = Counter(a=1, b=2) 328 >>> c + d # add two counters together: c[x] + d[x] 329 Counter({'a': 4, 'b': 3}) 330 >>> c - d # subtract (keeping only positive counts) 331 Counter({'a': 2}) 332 >>> c & d # intersection: min(c[x], d[x]) # doctest: +SKIP 333 Counter({'a': 1, 'b': 1}) 334 >>> c | d # union: max(c[x], d[x]) 335 Counter({'a': 3, 'b': 2}) 336 337 Unary addition and subtraction are shortcuts for adding an empty counter 338 or subtracting from an empty counter. 339 340 >>> c = Counter(a=2, b=-4) 341 >>> +c 342 Counter({'a': 2}) 343 >>> -c 344 Counter({'b': 4}) 345 346 .. versionadded:: 3.3 347 Added support for unary plus, unary minus, and in-place multiset operations. 348 349 .. note:: 350 351 Counters were primarily designed to work with positive integers to represent 352 running counts; however, care was taken to not unnecessarily preclude use 353 cases needing other types or negative values. To help with those use cases, 354 this section documents the minimum range and type restrictions. 355 356 * The :class:`Counter` class itself is a dictionary subclass with no 357 restrictions on its keys and values. The values are intended to be numbers 358 representing counts, but you *could* store anything in the value field. 359 360 * The :meth:`most_common` method requires only that the values be orderable. 361 362 * For in-place operations such as ``c[key] += 1``, the value type need only 363 support addition and subtraction. So fractions, floats, and decimals would 364 work and negative values are supported. The same is also true for 365 :meth:`update` and :meth:`subtract` which allow negative and zero values 366 for both inputs and outputs. 367 368 * The multiset methods are designed only for use cases with positive values. 369 The inputs may be negative or zero, but only outputs with positive values 370 are created. There are no type restrictions, but the value type needs to 371 support addition, subtraction, and comparison. 372 373 * The :meth:`elements` method requires integer counts. It ignores zero and 374 negative counts. 375 376 .. seealso:: 377 378 * `Bag class <https://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html>`_ 379 in Smalltalk. 380 381 * Wikipedia entry for `Multisets <https://en.wikipedia.org/wiki/Multiset>`_. 382 383 * `C++ multisets <http://www.java2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm>`_ 384 tutorial with examples. 385 386 * For mathematical operations on multisets and their use cases, see 387 *Knuth, Donald. The Art of Computer Programming Volume II, 388 Section 4.6.3, Exercise 19*. 389 390 * To enumerate all distinct multisets of a given size over a given set of 391 elements, see :func:`itertools.combinations_with_replacement`: 392 393 map(Counter, combinations_with_replacement('ABC', 2)) --> AA AB AC BB BC CC 394 395 396 :class:`deque` objects 397 ---------------------- 398 399 .. class:: deque([iterable, [maxlen]]) 400 401 Returns a new deque object initialized left-to-right (using :meth:`append`) with 402 data from *iterable*. If *iterable* is not specified, the new deque is empty. 403 404 Deques are a generalization of stacks and queues (the name is pronounced "deck" 405 and is short for "double-ended queue"). Deques support thread-safe, memory 406 efficient appends and pops from either side of the deque with approximately the 407 same O(1) performance in either direction. 408 409 Though :class:`list` objects support similar operations, they are optimized for 410 fast fixed-length operations and incur O(n) memory movement costs for 411 ``pop(0)`` and ``insert(0, v)`` operations which change both the size and 412 position of the underlying data representation. 413 414 415 If *maxlen* is not specified or is ``None``, deques may grow to an 416 arbitrary length. Otherwise, the deque is bounded to the specified maximum 417 length. Once a bounded length deque is full, when new items are added, a 418 corresponding number of items are discarded from the opposite end. Bounded 419 length deques provide functionality similar to the ``tail`` filter in 420 Unix. They are also useful for tracking transactions and other pools of data 421 where only the most recent activity is of interest. 422 423 424 Deque objects support the following methods: 425 426 .. method:: append(x) 427 428 Add *x* to the right side of the deque. 429 430 431 .. method:: appendleft(x) 432 433 Add *x* to the left side of the deque. 434 435 436 .. method:: clear() 437 438 Remove all elements from the deque leaving it with length 0. 439 440 441 .. method:: copy() 442 443 Create a shallow copy of the deque. 444 445 .. versionadded:: 3.5 446 447 448 .. method:: count(x) 449 450 Count the number of deque elements equal to *x*. 451 452 .. versionadded:: 3.2 453 454 455 .. method:: extend(iterable) 456 457 Extend the right side of the deque by appending elements from the iterable 458 argument. 459 460 461 .. method:: extendleft(iterable) 462 463 Extend the left side of the deque by appending elements from *iterable*. 464 Note, the series of left appends results in reversing the order of 465 elements in the iterable argument. 466 467 468 .. method:: index(x[, start[, stop]]) 469 470 Return the position of *x* in the deque (at or after index *start* 471 and before index *stop*). Returns the first match or raises 472 :exc:`ValueError` if not found. 473 474 .. versionadded:: 3.5 475 476 477 .. method:: insert(i, x) 478 479 Insert *x* into the deque at position *i*. 480 481 If the insertion would cause a bounded deque to grow beyond *maxlen*, 482 an :exc:`IndexError` is raised. 483 484 .. versionadded:: 3.5 485 486 487 .. method:: pop() 488 489 Remove and return an element from the right side of the deque. If no 490 elements are present, raises an :exc:`IndexError`. 491 492 493 .. method:: popleft() 494 495 Remove and return an element from the left side of the deque. If no 496 elements are present, raises an :exc:`IndexError`. 497 498 499 .. method:: remove(value) 500 501 Remove the first occurrence of *value*. If not found, raises a 502 :exc:`ValueError`. 503 504 505 .. method:: reverse() 506 507 Reverse the elements of the deque in-place and then return ``None``. 508 509 .. versionadded:: 3.2 510 511 512 .. method:: rotate(n) 513 514 Rotate the deque *n* steps to the right. If *n* is negative, rotate to 515 the left. Rotating one step to the right is equivalent to: 516 ``d.appendleft(d.pop())``. 517 518 519 Deque objects also provide one read-only attribute: 520 521 .. attribute:: maxlen 522 523 Maximum size of a deque or ``None`` if unbounded. 524 525 .. versionadded:: 3.1 526 527 528 In addition to the above, deques support iteration, pickling, ``len(d)``, 529 ``reversed(d)``, ``copy.copy(d)``, ``copy.deepcopy(d)``, membership testing with 530 the :keyword:`in` operator, and subscript references such as ``d[-1]``. Indexed 531 access is O(1) at both ends but slows to O(n) in the middle. For fast random 532 access, use lists instead. 533 534 Starting in version 3.5, deques support ``__add__()``, ``__mul__()``, 535 and ``__imul__()``. 536 537 Example: 538 539 .. doctest:: 540 541 >>> from collections import deque 542 >>> d = deque('ghi') # make a new deque with three items 543 >>> for elem in d: # iterate over the deque's elements 544 ... print(elem.upper()) 545 G 546 H 547 I 548 549 >>> d.append('j') # add a new entry to the right side 550 >>> d.appendleft('f') # add a new entry to the left side 551 >>> d # show the representation of the deque 552 deque(['f', 'g', 'h', 'i', 'j']) 553 554 >>> d.pop() # return and remove the rightmost item 555 'j' 556 >>> d.popleft() # return and remove the leftmost item 557 'f' 558 >>> list(d) # list the contents of the deque 559 ['g', 'h', 'i'] 560 >>> d[0] # peek at leftmost item 561 'g' 562 >>> d[-1] # peek at rightmost item 563 'i' 564 565 >>> list(reversed(d)) # list the contents of a deque in reverse 566 ['i', 'h', 'g'] 567 >>> 'h' in d # search the deque 568 True 569 >>> d.extend('jkl') # add multiple elements at once 570 >>> d 571 deque(['g', 'h', 'i', 'j', 'k', 'l']) 572 >>> d.rotate(1) # right rotation 573 >>> d 574 deque(['l', 'g', 'h', 'i', 'j', 'k']) 575 >>> d.rotate(-1) # left rotation 576 >>> d 577 deque(['g', 'h', 'i', 'j', 'k', 'l']) 578 579 >>> deque(reversed(d)) # make a new deque in reverse order 580 deque(['l', 'k', 'j', 'i', 'h', 'g']) 581 >>> d.clear() # empty the deque 582 >>> d.pop() # cannot pop from an empty deque 583 Traceback (most recent call last): 584 File "<pyshell#6>", line 1, in -toplevel- 585 d.pop() 586 IndexError: pop from an empty deque 587 588 >>> d.extendleft('abc') # extendleft() reverses the input order 589 >>> d 590 deque(['c', 'b', 'a']) 591 592 593 :class:`deque` Recipes 594 ^^^^^^^^^^^^^^^^^^^^^^ 595 596 This section shows various approaches to working with deques. 597 598 Bounded length deques provide functionality similar to the ``tail`` filter 599 in Unix:: 600 601 def tail(filename, n=10): 602 'Return the last n lines of a file' 603 with open(filename) as f: 604 return deque(f, n) 605 606 Another approach to using deques is to maintain a sequence of recently 607 added elements by appending to the right and popping to the left:: 608 609 def moving_average(iterable, n=3): 610 # moving_average([40, 30, 50, 46, 39, 44]) --> 40.0 42.0 45.0 43.0 611 # http://en.wikipedia.org/wiki/Moving_average 612 it = iter(iterable) 613 d = deque(itertools.islice(it, n-1)) 614 d.appendleft(0) 615 s = sum(d) 616 for elem in it: 617 s += elem - d.popleft() 618 d.append(elem) 619 yield s / n 620 621 The :meth:`rotate` method provides a way to implement :class:`deque` slicing and 622 deletion. For example, a pure Python implementation of ``del d[n]`` relies on 623 the :meth:`rotate` method to position elements to be popped:: 624 625 def delete_nth(d, n): 626 d.rotate(-n) 627 d.popleft() 628 d.rotate(n) 629 630 To implement :class:`deque` slicing, use a similar approach applying 631 :meth:`rotate` to bring a target element to the left side of the deque. Remove 632 old entries with :meth:`popleft`, add new entries with :meth:`extend`, and then 633 reverse the rotation. 634 With minor variations on that approach, it is easy to implement Forth style 635 stack manipulations such as ``dup``, ``drop``, ``swap``, ``over``, ``pick``, 636 ``rot``, and ``roll``. 637 638 639 :class:`defaultdict` objects 640 ---------------------------- 641 642 .. class:: defaultdict([default_factory[, ...]]) 643 644 Returns a new dictionary-like object. :class:`defaultdict` is a subclass of the 645 built-in :class:`dict` class. It overrides one method and adds one writable 646 instance variable. The remaining functionality is the same as for the 647 :class:`dict` class and is not documented here. 648 649 The first argument provides the initial value for the :attr:`default_factory` 650 attribute; it defaults to ``None``. All remaining arguments are treated the same 651 as if they were passed to the :class:`dict` constructor, including keyword 652 arguments. 653 654 655 :class:`defaultdict` objects support the following method in addition to the 656 standard :class:`dict` operations: 657 658 .. method:: __missing__(key) 659 660 If the :attr:`default_factory` attribute is ``None``, this raises a 661 :exc:`KeyError` exception with the *key* as argument. 662 663 If :attr:`default_factory` is not ``None``, it is called without arguments 664 to provide a default value for the given *key*, this value is inserted in 665 the dictionary for the *key*, and returned. 666 667 If calling :attr:`default_factory` raises an exception this exception is 668 propagated unchanged. 669 670 This method is called by the :meth:`__getitem__` method of the 671 :class:`dict` class when the requested key is not found; whatever it 672 returns or raises is then returned or raised by :meth:`__getitem__`. 673 674 Note that :meth:`__missing__` is *not* called for any operations besides 675 :meth:`__getitem__`. This means that :meth:`get` will, like normal 676 dictionaries, return ``None`` as a default rather than using 677 :attr:`default_factory`. 678 679 680 :class:`defaultdict` objects support the following instance variable: 681 682 683 .. attribute:: default_factory 684 685 This attribute is used by the :meth:`__missing__` method; it is 686 initialized from the first argument to the constructor, if present, or to 687 ``None``, if absent. 688 689 690 :class:`defaultdict` Examples 691 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 692 693 Using :class:`list` as the :attr:`default_factory`, it is easy to group a 694 sequence of key-value pairs into a dictionary of lists: 695 696 >>> s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)] 697 >>> d = defaultdict(list) 698 >>> for k, v in s: 699 ... d[k].append(v) 700 ... 701 >>> sorted(d.items()) 702 [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])] 703 704 When each key is encountered for the first time, it is not already in the 705 mapping; so an entry is automatically created using the :attr:`default_factory` 706 function which returns an empty :class:`list`. The :meth:`list.append` 707 operation then attaches the value to the new list. When keys are encountered 708 again, the look-up proceeds normally (returning the list for that key) and the 709 :meth:`list.append` operation adds another value to the list. This technique is 710 simpler and faster than an equivalent technique using :meth:`dict.setdefault`: 711 712 >>> d = {} 713 >>> for k, v in s: 714 ... d.setdefault(k, []).append(v) 715 ... 716 >>> sorted(d.items()) 717 [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])] 718 719 Setting the :attr:`default_factory` to :class:`int` makes the 720 :class:`defaultdict` useful for counting (like a bag or multiset in other 721 languages): 722 723 >>> s = 'mississippi' 724 >>> d = defaultdict(int) 725 >>> for k in s: 726 ... d[k] += 1 727 ... 728 >>> sorted(d.items()) 729 [('i', 4), ('m', 1), ('p', 2), ('s', 4)] 730 731 When a letter is first encountered, it is missing from the mapping, so the 732 :attr:`default_factory` function calls :func:`int` to supply a default count of 733 zero. The increment operation then builds up the count for each letter. 734 735 The function :func:`int` which always returns zero is just a special case of 736 constant functions. A faster and more flexible way to create constant functions 737 is to use a lambda function which can supply any constant value (not just 738 zero): 739 740 >>> def constant_factory(value): 741 ... return lambda: value 742 >>> d = defaultdict(constant_factory('<missing>')) 743 >>> d.update(name='John', action='ran') 744 >>> '%(name)s %(action)s to %(object)s' % d 745 'John ran to <missing>' 746 747 Setting the :attr:`default_factory` to :class:`set` makes the 748 :class:`defaultdict` useful for building a dictionary of sets: 749 750 >>> s = [('red', 1), ('blue', 2), ('red', 3), ('blue', 4), ('red', 1), ('blue', 4)] 751 >>> d = defaultdict(set) 752 >>> for k, v in s: 753 ... d[k].add(v) 754 ... 755 >>> sorted(d.items()) 756 [('blue', {2, 4}), ('red', {1, 3})] 757 758 759 :func:`namedtuple` Factory Function for Tuples with Named Fields 760 ---------------------------------------------------------------- 761 762 Named tuples assign meaning to each position in a tuple and allow for more readable, 763 self-documenting code. They can be used wherever regular tuples are used, and 764 they add the ability to access fields by name instead of position index. 765 766 .. function:: namedtuple(typename, field_names, *, verbose=False, rename=False, module=None) 767 768 Returns a new tuple subclass named *typename*. The new subclass is used to 769 create tuple-like objects that have fields accessible by attribute lookup as 770 well as being indexable and iterable. Instances of the subclass also have a 771 helpful docstring (with typename and field_names) and a helpful :meth:`__repr__` 772 method which lists the tuple contents in a ``name=value`` format. 773 774 The *field_names* are a single string with each fieldname separated by whitespace 775 and/or commas, for example ``'x y'`` or ``'x, y'``. Alternatively, *field_names* 776 can be a sequence of strings such as ``['x', 'y']``. 777 778 Any valid Python identifier may be used for a fieldname except for names 779 starting with an underscore. Valid identifiers consist of letters, digits, 780 and underscores but do not start with a digit or underscore and cannot be 781 a :mod:`keyword` such as *class*, *for*, *return*, *global*, *pass*, 782 or *raise*. 783 784 If *rename* is true, invalid fieldnames are automatically replaced 785 with positional names. For example, ``['abc', 'def', 'ghi', 'abc']`` is 786 converted to ``['abc', '_1', 'ghi', '_3']``, eliminating the keyword 787 ``def`` and the duplicate fieldname ``abc``. 788 789 If *verbose* is true, the class definition is printed after it is 790 built. This option is outdated; instead, it is simpler to print the 791 :attr:`_source` attribute. 792 793 If *module* is defined, the ``__module__`` attribute of the named tuple is 794 set to that value. 795 796 Named tuple instances do not have per-instance dictionaries, so they are 797 lightweight and require no more memory than regular tuples. 798 799 .. versionchanged:: 3.1 800 Added support for *rename*. 801 802 .. versionchanged:: 3.6 803 The *verbose* and *rename* parameters became 804 :ref:`keyword-only arguments <keyword-only_parameter>`. 805 806 .. versionchanged:: 3.6 807 Added the *module* parameter. 808 809 .. doctest:: 810 :options: +NORMALIZE_WHITESPACE 811 812 >>> # Basic example 813 >>> Point = namedtuple('Point', ['x', 'y']) 814 >>> p = Point(11, y=22) # instantiate with positional or keyword arguments 815 >>> p[0] + p[1] # indexable like the plain tuple (11, 22) 816 33 817 >>> x, y = p # unpack like a regular tuple 818 >>> x, y 819 (11, 22) 820 >>> p.x + p.y # fields also accessible by name 821 33 822 >>> p # readable __repr__ with a name=value style 823 Point(x=11, y=22) 824 825 Named tuples are especially useful for assigning field names to result tuples returned 826 by the :mod:`csv` or :mod:`sqlite3` modules:: 827 828 EmployeeRecord = namedtuple('EmployeeRecord', 'name, age, title, department, paygrade') 829 830 import csv 831 for emp in map(EmployeeRecord._make, csv.reader(open("employees.csv", "rb"))): 832 print(emp.name, emp.title) 833 834 import sqlite3 835 conn = sqlite3.connect('/companydata') 836 cursor = conn.cursor() 837 cursor.execute('SELECT name, age, title, department, paygrade FROM employees') 838 for emp in map(EmployeeRecord._make, cursor.fetchall()): 839 print(emp.name, emp.title) 840 841 In addition to the methods inherited from tuples, named tuples support 842 three additional methods and two attributes. To prevent conflicts with 843 field names, the method and attribute names start with an underscore. 844 845 .. classmethod:: somenamedtuple._make(iterable) 846 847 Class method that makes a new instance from an existing sequence or iterable. 848 849 .. doctest:: 850 851 >>> t = [11, 22] 852 >>> Point._make(t) 853 Point(x=11, y=22) 854 855 .. method:: somenamedtuple._asdict() 856 857 Return a new :class:`OrderedDict` which maps field names to their corresponding 858 values: 859 860 .. doctest:: 861 862 >>> p = Point(x=11, y=22) 863 >>> p._asdict() 864 OrderedDict([('x', 11), ('y', 22)]) 865 866 .. versionchanged:: 3.1 867 Returns an :class:`OrderedDict` instead of a regular :class:`dict`. 868 869 .. method:: somenamedtuple._replace(kwargs) 870 871 Return a new instance of the named tuple replacing specified fields with new 872 values:: 873 874 >>> p = Point(x=11, y=22) 875 >>> p._replace(x=33) 876 Point(x=33, y=22) 877 878 >>> for partnum, record in inventory.items(): 879 ... inventory[partnum] = record._replace(price=newprices[partnum], timestamp=time.now()) 880 881 .. attribute:: somenamedtuple._source 882 883 A string with the pure Python source code used to create the named 884 tuple class. The source makes the named tuple self-documenting. 885 It can be printed, executed using :func:`exec`, or saved to a file 886 and imported. 887 888 .. versionadded:: 3.3 889 890 .. attribute:: somenamedtuple._fields 891 892 Tuple of strings listing the field names. Useful for introspection 893 and for creating new named tuple types from existing named tuples. 894 895 .. doctest:: 896 897 >>> p._fields # view the field names 898 ('x', 'y') 899 900 >>> Color = namedtuple('Color', 'red green blue') 901 >>> Pixel = namedtuple('Pixel', Point._fields + Color._fields) 902 >>> Pixel(11, 22, 128, 255, 0) 903 Pixel(x=11, y=22, red=128, green=255, blue=0) 904 905 To retrieve a field whose name is stored in a string, use the :func:`getattr` 906 function: 907 908 >>> getattr(p, 'x') 909 11 910 911 To convert a dictionary to a named tuple, use the double-star-operator 912 (as described in :ref:`tut-unpacking-arguments`): 913 914 >>> d = {'x': 11, 'y': 22} 915 >>> Point(**d) 916 Point(x=11, y=22) 917 918 Since a named tuple is a regular Python class, it is easy to add or change 919 functionality with a subclass. Here is how to add a calculated field and 920 a fixed-width print format: 921 922 .. doctest:: 923 924 >>> class Point(namedtuple('Point', ['x', 'y'])): 925 ... __slots__ = () 926 ... @property 927 ... def hypot(self): 928 ... return (self.x ** 2 + self.y ** 2) ** 0.5 929 ... def __str__(self): 930 ... return 'Point: x=%6.3f y=%6.3f hypot=%6.3f' % (self.x, self.y, self.hypot) 931 932 >>> for p in Point(3, 4), Point(14, 5/7): 933 ... print(p) 934 Point: x= 3.000 y= 4.000 hypot= 5.000 935 Point: x=14.000 y= 0.714 hypot=14.018 936 937 The subclass shown above sets ``__slots__`` to an empty tuple. This helps 938 keep memory requirements low by preventing the creation of instance dictionaries. 939 940 Subclassing is not useful for adding new, stored fields. Instead, simply 941 create a new named tuple type from the :attr:`_fields` attribute: 942 943 >>> Point3D = namedtuple('Point3D', Point._fields + ('z',)) 944 945 Docstrings can be customized by making direct assignments to the ``__doc__`` 946 fields: 947 948 >>> Book = namedtuple('Book', ['id', 'title', 'authors']) 949 >>> Book.__doc__ += ': Hardcover book in active collection' 950 >>> Book.id.__doc__ = '13-digit ISBN' 951 >>> Book.title.__doc__ = 'Title of first printing' 952 >>> Book.authors.__doc__ = 'List of authors sorted by last name' 953 954 .. versionchanged:: 3.5 955 Property docstrings became writeable. 956 957 Default values can be implemented by using :meth:`_replace` to 958 customize a prototype instance: 959 960 >>> Account = namedtuple('Account', 'owner balance transaction_count') 961 >>> default_account = Account('<owner name>', 0.0, 0) 962 >>> johns_account = default_account._replace(owner='John') 963 >>> janes_account = default_account._replace(owner='Jane') 964 965 966 .. seealso:: 967 968 * `Recipe for named tuple abstract base class with a metaclass mix-in 969 <https://code.activestate.com/recipes/577629-namedtupleabc-abstract-base-class-mix-in-for-named/>`_ 970 by Jan Kaliszewski. Besides providing an :term:`abstract base class` for 971 named tuples, it also supports an alternate :term:`metaclass`-based 972 constructor that is convenient for use cases where named tuples are being 973 subclassed. 974 975 * See :meth:`types.SimpleNamespace` for a mutable namespace based on an 976 underlying dictionary instead of a tuple. 977 978 * See :meth:`typing.NamedTuple` for a way to add type hints for named tuples. 979 980 981 :class:`OrderedDict` objects 982 ---------------------------- 983 984 Ordered dictionaries are just like regular dictionaries but they remember the 985 order that items were inserted. When iterating over an ordered dictionary, 986 the items are returned in the order their keys were first added. 987 988 .. class:: OrderedDict([items]) 989 990 Return an instance of a dict subclass, supporting the usual :class:`dict` 991 methods. An *OrderedDict* is a dict that remembers the order that keys 992 were first inserted. If a new entry overwrites an existing entry, the 993 original insertion position is left unchanged. Deleting an entry and 994 reinserting it will move it to the end. 995 996 .. versionadded:: 3.1 997 998 .. method:: popitem(last=True) 999 1000 The :meth:`popitem` method for ordered dictionaries returns and removes a 1001 (key, value) pair. The pairs are returned in 1002 :abbr:`LIFO (last-in, first-out)` order if *last* is true 1003 or :abbr:`FIFO (first-in, first-out)` order if false. 1004 1005 .. method:: move_to_end(key, last=True) 1006 1007 Move an existing *key* to either end of an ordered dictionary. The item 1008 is moved to the right end if *last* is true (the default) or to the 1009 beginning if *last* is false. Raises :exc:`KeyError` if the *key* does 1010 not exist:: 1011 1012 >>> d = OrderedDict.fromkeys('abcde') 1013 >>> d.move_to_end('b') 1014 >>> ''.join(d.keys()) 1015 'acdeb' 1016 >>> d.move_to_end('b', last=False) 1017 >>> ''.join(d.keys()) 1018 'bacde' 1019 1020 .. versionadded:: 3.2 1021 1022 In addition to the usual mapping methods, ordered dictionaries also support 1023 reverse iteration using :func:`reversed`. 1024 1025 Equality tests between :class:`OrderedDict` objects are order-sensitive 1026 and are implemented as ``list(od1.items())==list(od2.items())``. 1027 Equality tests between :class:`OrderedDict` objects and other 1028 :class:`~collections.abc.Mapping` objects are order-insensitive like regular 1029 dictionaries. This allows :class:`OrderedDict` objects to be substituted 1030 anywhere a regular dictionary is used. 1031 1032 .. versionchanged:: 3.5 1033 The items, keys, and values :term:`views <dictionary view>` 1034 of :class:`OrderedDict` now support reverse iteration using :func:`reversed`. 1035 1036 .. versionchanged:: 3.6 1037 With the acceptance of :pep:`468`, order is retained for keyword arguments 1038 passed to the :class:`OrderedDict` constructor and its :meth:`update` 1039 method. 1040 1041 :class:`OrderedDict` Examples and Recipes 1042 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 1043 1044 Since an ordered dictionary remembers its insertion order, it can be used 1045 in conjunction with sorting to make a sorted dictionary:: 1046 1047 >>> # regular unsorted dictionary 1048 >>> d = {'banana': 3, 'apple': 4, 'pear': 1, 'orange': 2} 1049 1050 >>> # dictionary sorted by key 1051 >>> OrderedDict(sorted(d.items(), key=lambda t: t[0])) 1052 OrderedDict([('apple', 4), ('banana', 3), ('orange', 2), ('pear', 1)]) 1053 1054 >>> # dictionary sorted by value 1055 >>> OrderedDict(sorted(d.items(), key=lambda t: t[1])) 1056 OrderedDict([('pear', 1), ('orange', 2), ('banana', 3), ('apple', 4)]) 1057 1058 >>> # dictionary sorted by length of the key string 1059 >>> OrderedDict(sorted(d.items(), key=lambda t: len(t[0]))) 1060 OrderedDict([('pear', 1), ('apple', 4), ('orange', 2), ('banana', 3)]) 1061 1062 The new sorted dictionaries maintain their sort order when entries 1063 are deleted. But when new keys are added, the keys are appended 1064 to the end and the sort is not maintained. 1065 1066 It is also straight-forward to create an ordered dictionary variant 1067 that remembers the order the keys were *last* inserted. 1068 If a new entry overwrites an existing entry, the 1069 original insertion position is changed and moved to the end:: 1070 1071 class LastUpdatedOrderedDict(OrderedDict): 1072 'Store items in the order the keys were last added' 1073 1074 def __setitem__(self, key, value): 1075 if key in self: 1076 del self[key] 1077 OrderedDict.__setitem__(self, key, value) 1078 1079 An ordered dictionary can be combined with the :class:`Counter` class 1080 so that the counter remembers the order elements are first encountered:: 1081 1082 class OrderedCounter(Counter, OrderedDict): 1083 'Counter that remembers the order elements are first encountered' 1084 1085 def __repr__(self): 1086 return '%s(%r)' % (self.__class__.__name__, OrderedDict(self)) 1087 1088 def __reduce__(self): 1089 return self.__class__, (OrderedDict(self),) 1090 1091 1092 :class:`UserDict` objects 1093 ------------------------- 1094 1095 The class, :class:`UserDict` acts as a wrapper around dictionary objects. 1096 The need for this class has been partially supplanted by the ability to 1097 subclass directly from :class:`dict`; however, this class can be easier 1098 to work with because the underlying dictionary is accessible as an 1099 attribute. 1100 1101 .. class:: UserDict([initialdata]) 1102 1103 Class that simulates a dictionary. The instance's contents are kept in a 1104 regular dictionary, which is accessible via the :attr:`data` attribute of 1105 :class:`UserDict` instances. If *initialdata* is provided, :attr:`data` is 1106 initialized with its contents; note that a reference to *initialdata* will not 1107 be kept, allowing it be used for other purposes. 1108 1109 In addition to supporting the methods and operations of mappings, 1110 :class:`UserDict` instances provide the following attribute: 1111 1112 .. attribute:: data 1113 1114 A real dictionary used to store the contents of the :class:`UserDict` 1115 class. 1116 1117 1118 1119 :class:`UserList` objects 1120 ------------------------- 1121 1122 This class acts as a wrapper around list objects. It is a useful base class 1123 for your own list-like classes which can inherit from them and override 1124 existing methods or add new ones. In this way, one can add new behaviors to 1125 lists. 1126 1127 The need for this class has been partially supplanted by the ability to 1128 subclass directly from :class:`list`; however, this class can be easier 1129 to work with because the underlying list is accessible as an attribute. 1130 1131 .. class:: UserList([list]) 1132 1133 Class that simulates a list. The instance's contents are kept in a regular 1134 list, which is accessible via the :attr:`data` attribute of :class:`UserList` 1135 instances. The instance's contents are initially set to a copy of *list*, 1136 defaulting to the empty list ``[]``. *list* can be any iterable, for 1137 example a real Python list or a :class:`UserList` object. 1138 1139 In addition to supporting the methods and operations of mutable sequences, 1140 :class:`UserList` instances provide the following attribute: 1141 1142 .. attribute:: data 1143 1144 A real :class:`list` object used to store the contents of the 1145 :class:`UserList` class. 1146 1147 **Subclassing requirements:** Subclasses of :class:`UserList` are expected to 1148 offer a constructor which can be called with either no arguments or one 1149 argument. List operations which return a new sequence attempt to create an 1150 instance of the actual implementation class. To do so, it assumes that the 1151 constructor can be called with a single parameter, which is a sequence object 1152 used as a data source. 1153 1154 If a derived class does not wish to comply with this requirement, all of the 1155 special methods supported by this class will need to be overridden; please 1156 consult the sources for information about the methods which need to be provided 1157 in that case. 1158 1159 :class:`UserString` objects 1160 --------------------------- 1161 1162 The class, :class:`UserString` acts as a wrapper around string objects. 1163 The need for this class has been partially supplanted by the ability to 1164 subclass directly from :class:`str`; however, this class can be easier 1165 to work with because the underlying string is accessible as an 1166 attribute. 1167 1168 .. class:: UserString([sequence]) 1169 1170 Class that simulates a string or a Unicode string object. The instance's 1171 content is kept in a regular string object, which is accessible via the 1172 :attr:`data` attribute of :class:`UserString` instances. The instance's 1173 contents are initially set to a copy of *sequence*. The *sequence* can 1174 be an instance of :class:`bytes`, :class:`str`, :class:`UserString` (or a 1175 subclass) or an arbitrary sequence which can be converted into a string using 1176 the built-in :func:`str` function. 1177 1178 .. versionchanged:: 3.5 1179 New methods ``__getnewargs__``, ``__rmod__``, ``casefold``, 1180 ``format_map``, ``isprintable``, and ``maketrans``. 1181
