Debian Codegraph @

Doc/library/collections.rst

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