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