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