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