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