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
484 Deque objects support the following methods:
485
486 .. method:: append(item, /)
487
488 Add *item* to the right side of the deque.
489
490
491 .. method:: appendleft(item, /)
492
493 Add *item* to the left side of the deque.
494
495
496 .. method:: clear()
497
498 Remove all elements from the deque leaving it with length 0.
499
500
501 .. method:: copy()
502
503 Create a shallow copy of the deque.
504
505 .. versionadded:: 3.5
506
507
508 .. method:: count(value, /)
509
510 Count the number of deque elements equal to *value*.
511
512 .. versionadded:: 3.2
513
514
515 .. method:: extend(iterable, /)
516
517 Extend the right side of the deque by appending elements from the iterable
518 argument.
519
520
521 .. method:: extendleft(iterable, /)
522
523 Extend the left side of the deque by appending elements from *iterable*.
524 Note, the series of left appends results in reversing the order of
525 elements in the iterable argument.
526
527
528 .. method:: index(value[, start[, stop]])
529
530 Return the position of *value* in the deque (at or after index *start*
531 and before index *stop*). Returns the first match or raises
532 :exc:`ValueError` if not found.
533
534 .. versionadded:: 3.5
535
536
537 .. method:: insert(index, value, /)
538
539 Insert *value* into the deque at position *index*.
540
541 If the insertion would cause a bounded deque to grow beyond *maxlen*,
542 an :exc:`IndexError` is raised.
543
544 .. versionadded:: 3.5
545
546
547 .. method:: pop()
548
549 Remove and return an element from the right side of the deque. If no
550 elements are present, raises an :exc:`IndexError`.
551
552
553 .. method:: popleft()
554
555 Remove and return an element from the left side of the deque. If no
556 elements are present, raises an :exc:`IndexError`.
557
558
559 .. method:: remove(value, /)
560
561 Remove the first occurrence of *value*. If not found, raises a
562 :exc:`ValueError`.
563
564
565 .. method:: reverse()
566
567 Reverse the elements of the deque in-place and then return ``None``.
568
569 .. versionadded:: 3.2
570
571
572 .. method:: rotate(n=1, /)
573
574 Rotate the deque *n* steps to the right. If *n* is negative, rotate
575 to the left.
576
577 When the deque is not empty, rotating one step to the right is equivalent
578 to ``d.appendleft(d.pop())``, and rotating one step to the left is
579 equivalent to ``d.append(d.popleft())``.
580
581
582 Deque objects also provide one read-only attribute:
583
584 .. attribute:: maxlen
585
586 Maximum size of a deque or ``None`` if unbounded.
587
588 .. versionadded:: 3.1
589
590
591 In addition to the above, deques support iteration, pickling, ``len(d)``,
592 ``reversed(d)``, ``copy.copy(d)``, ``copy.deepcopy(d)``, membership testing with
593 the :keyword:`in` operator, and subscript references such as ``d[0]`` to access
594 the first element. Indexed access is *O*\ (1) at both ends but slows to *O*\ (*n*) in
595 the middle. For fast random access, use lists instead.
596
597 Starting in version 3.5, deques support ``__add__()``, ``__mul__()``,
598 and ``__imul__()``.
599
600 Example:
601
602 .. doctest::
603
604 >>> from collections import deque
605 >>> d = deque('ghi') # make a new deque with three items
606 >>> for elem in d: # iterate over the deque's elements
607 ... print(elem.upper())
608 G
609 H
610 I
611
612 >>> d.append('j') # add a new entry to the right side
613 >>> d.appendleft('f') # add a new entry to the left side
614 >>> d # show the representation of the deque
615 deque(['f', 'g', 'h', 'i', 'j'])
616
617 >>> d.pop() # return and remove the rightmost item
618 'j'
619 >>> d.popleft() # return and remove the leftmost item
620 'f'
621 >>> list(d) # list the contents of the deque
622 ['g', 'h', 'i']
623 >>> d[0] # peek at leftmost item
624 'g'
625 >>> d[-1] # peek at rightmost item
626 'i'
627
628 >>> list(reversed(d)) # list the contents of a deque in reverse
629 ['i', 'h', 'g']
630 >>> 'h' in d # search the deque
631 True
632 >>> d.extend('jkl') # add multiple elements at once
633 >>> d
634 deque(['g', 'h', 'i', 'j', 'k', 'l'])
635 >>> d.rotate(1) # right rotation
636 >>> d
637 deque(['l', 'g', 'h', 'i', 'j', 'k'])
638 >>> d.rotate(-1) # left rotation
639 >>> d
640 deque(['g', 'h', 'i', 'j', 'k', 'l'])
641
642 >>> deque(reversed(d)) # make a new deque in reverse order
643 deque(['l', 'k', 'j', 'i', 'h', 'g'])
644 >>> d.clear() # empty the deque
645 >>> d.pop() # cannot pop from an empty deque
646 Traceback (most recent call last):
647 File "<pyshell#6>", line 1, in -toplevel-
648 d.pop()
649 IndexError: pop from an empty deque
650
651 >>> d.extendleft('abc') # extendleft() reverses the input order
652 >>> d
653 deque(['c', 'b', 'a'])
654
655
656 :class:`deque` Recipes
657 ^^^^^^^^^^^^^^^^^^^^^^
658
659 This section shows various approaches to working with deques.
660
661 Bounded length deques provide functionality similar to the ``tail`` filter
662 in Unix::
663
664 def tail(filename, n=10):
665 'Return the last n lines of a file'
666 with open(filename) as f:
667 return deque(f, n)
668
669 Another approach to using deques is to maintain a sequence of recently
670 added elements by appending to the right and popping to the left::
671
672 def moving_average(iterable, n=3):
673 # moving_average([40, 30, 50, 46, 39, 44]) --> 40.0 42.0 45.0 43.0
674 # https://en.wikipedia.org/wiki/Moving_average
675 it = iter(iterable)
676 d = deque(itertools.islice(it, n-1))
677 d.appendleft(0)
678 s = sum(d)
679 for elem in it:
680 s += elem - d.popleft()
681 d.append(elem)
682 yield s / n
683
684 A `round-robin scheduler
685 <https://en.wikipedia.org/wiki/Round-robin_scheduling>`_ can be implemented with
686 input iterators stored in a :class:`deque`. Values are yielded from the active
687 iterator in position zero. If that iterator is exhausted, it can be removed
688 with :meth:`~deque.popleft`; otherwise, it can be cycled back to the end with
689 the :meth:`~deque.rotate` method::
690
691 def roundrobin(*iterables):
692 "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
693 iterators = deque(map(iter, iterables))
694 while iterators:
695 try:
696 while True:
697 yield next(iterators[0])
698 iterators.rotate(-1)
699 except StopIteration:
700 # Remove an exhausted iterator.
701 iterators.popleft()
702
703 The :meth:`~deque.rotate` method provides a way to implement :class:`deque` slicing and
704 deletion. For example, a pure Python implementation of ``del d[n]`` relies on
705 the ``rotate()`` method to position elements to be popped::
706
707 def delete_nth(d, n):
708 d.rotate(-n)
709 d.popleft()
710 d.rotate(n)
711
712 To implement :class:`deque` slicing, use a similar approach applying
713 :meth:`~deque.rotate` to bring a target element to the left side of the deque. Remove
714 old entries with :meth:`~deque.popleft`, add new entries with :meth:`~deque.extend`, and then
715 reverse the rotation.
716 With minor variations on that approach, it is easy to implement Forth style
717 stack manipulations such as ``dup``, ``drop``, ``swap``, ``over``, ``pick``,
718 ``rot``, and ``roll``.
719
720
721 :class:`defaultdict` objects
722 ----------------------------
723
724 .. class:: defaultdict(default_factory=None, /, **kwargs)
725 defaultdict(default_factory, mapping, /, **kwargs)
726 defaultdict(default_factory, iterable, /, **kwargs)
727
728 Return a new dictionary-like object. :class:`defaultdict` is a subclass of the
729 built-in :class:`dict` class. It overrides one method and adds one writable
730 instance variable. The remaining functionality is the same as for the
731 :class:`dict` class and is not documented here.
732
733 The first argument provides the initial value for the :attr:`default_factory`
734 attribute; it defaults to ``None``. All remaining arguments are treated the same
735 as if they were passed to the :class:`dict` constructor, including keyword
736 arguments.
737
738
739 :class:`defaultdict` objects support the following method in addition to the
740 standard :class:`dict` operations:
741
742 .. method:: __missing__(key, /)
743
744 If the :attr:`default_factory` attribute is ``None``, this raises a
745 :exc:`KeyError` exception with the *key* as argument.
746
747 If :attr:`default_factory` is not ``None``, it is called without arguments
748 to provide a default value for the given *key*, this value is inserted in
749 the dictionary for the *key*, and returned.
750
751 If calling :attr:`default_factory` raises an exception this exception is
752 propagated unchanged.
753
754 This method is called by the :meth:`~object.__getitem__` method of the
755 :class:`dict` class when the requested key is not found; whatever it
756 returns or raises is then returned or raised by :meth:`~object.__getitem__`.
757
758 Note that :meth:`__missing__` is *not* called for any operations besides
759 :meth:`~object.__getitem__`. This means that :meth:`~dict.get` will, like
760 normal dictionaries, return ``None`` as a default rather than using
761 :attr:`default_factory`.
762
763
764 :class:`defaultdict` objects support the following instance variable:
765
766
767 .. attribute:: default_factory
768
769 This attribute is used by the :meth:`~defaultdict.__missing__` method;
770 it is initialized from the first argument to the constructor, if present,
771 or to ``None``, if absent.
772
773 .. versionchanged:: 3.9
774 Added merge (``|``) and update (``|=``) operators, specified in
775 :pep:`584`.
776
777
778 :class:`defaultdict` Examples
779 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
780
781 Using :class:`list` as the :attr:`~defaultdict.default_factory`, it is easy to group a
782 sequence of key-value pairs into a dictionary of lists:
783
784 >>> s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
785 >>> d = defaultdict(list)
786 >>> for k, v in s:
787 ... d[k].append(v)
788 ...
789 >>> sorted(d.items())
790 [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]
791
792 When each key is encountered for the first time, it is not already in the
793 mapping; so an entry is automatically created using the :attr:`~defaultdict.default_factory`
794 function which returns an empty :class:`list`. The :meth:`list.append`
795 operation then attaches the value to the new list. When keys are encountered
796 again, the look-up proceeds normally (returning the list for that key) and the
797 :meth:`list.append` operation adds another value to the list. This technique is
798 simpler and faster than an equivalent technique using :meth:`dict.setdefault`:
799
800 >>> d = {}
801 >>> for k, v in s:
802 ... d.setdefault(k, []).append(v)
803 ...
804 >>> sorted(d.items())
805 [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]
806
807 Setting the :attr:`~defaultdict.default_factory` to :class:`int` makes the
808 :class:`defaultdict` useful for counting (like a bag or multiset in other
809 languages):
810
811 >>> s = 'mississippi'
812 >>> d = defaultdict(int)
813 >>> for k in s:
814 ... d[k] += 1
815 ...
816 >>> sorted(d.items())
817 [('i', 4), ('m', 1), ('p', 2), ('s', 4)]
818
819 When a letter is first encountered, it is missing from the mapping, so the
820 :attr:`~defaultdict.default_factory` function calls :func:`int` to supply a default count of
821 zero. The increment operation then builds up the count for each letter.
822
823 The function :func:`int` which always returns zero is just a special case of
824 constant functions. A faster and more flexible way to create constant functions
825 is to use a lambda function which can supply any constant value (not just
826 zero):
827
828 >>> def constant_factory(value):
829 ... return lambda: value
830 ...
831 >>> d = defaultdict(constant_factory('<missing>'))
832 >>> d.update(name='John', action='ran')
833 >>> '%(name)s %(action)s to %(object)s' % d
834 'John ran to <missing>'
835
836 Setting the :attr:`~defaultdict.default_factory` to :class:`set` makes the
837 :class:`defaultdict` useful for building a dictionary of sets:
838
839 >>> s = [('red', 1), ('blue', 2), ('red', 3), ('blue', 4), ('red', 1), ('blue', 4)]
840 >>> d = defaultdict(set)
841 >>> for k, v in s:
842 ... d[k].add(v)
843 ...
844 >>> sorted(d.items())
845 [('blue', {2, 4}), ('red', {1, 3})]
846
847
848 :func:`namedtuple` Factory Function for Tuples with Named Fields
849 ----------------------------------------------------------------
850
851 Named tuples assign meaning to each position in a tuple and allow for more readable,
852 self-documenting code. They can be used wherever regular tuples are used, and
853 they add the ability to access fields by name instead of position index.
854
855 .. function:: namedtuple(typename, field_names, *, rename=False, defaults=None, module=None)
856
857 Returns a new tuple subclass named *typename*. The new subclass is used to
858 create tuple-like objects that have fields accessible by attribute lookup as
859 well as being indexable and iterable. Instances of the subclass also have a
860 helpful docstring (with *typename* and *field_names*) and a helpful
861 :meth:`~object.__repr__` method which lists the tuple contents in a ``name=value``
862 format.
863
864 The *field_names* are a sequence of strings such as ``['x', 'y']``.
865 Alternatively, *field_names* can be a single string with each fieldname
866 separated by whitespace and/or commas, for example ``'x y'`` or ``'x, y'``.
867
868 Any valid Python identifier may be used for a fieldname except for names
869 starting with an underscore. Valid identifiers consist of letters, digits,
870 and underscores but do not start with a digit or underscore and cannot be
871 a :mod:`keyword` such as *class*, *for*, *return*, *global*, *pass*,
872 or *raise*.
873
874 If *rename* is true, invalid fieldnames are automatically replaced
875 with positional names. For example, ``['abc', 'def', 'ghi', 'abc']`` is
876 converted to ``['abc', '_1', 'ghi', '_3']``, eliminating the keyword
877 ``def`` and the duplicate fieldname ``abc``.
878
879 *defaults* can be ``None`` or an :term:`iterable` of default values.
880 Since fields with a default value must come after any fields without a
881 default, the *defaults* are applied to the rightmost parameters. For
882 example, if the fieldnames are ``['x', 'y', 'z']`` and the defaults are
883 ``(1, 2)``, then ``x`` will be a required argument, ``y`` will default to
884 ``1``, and ``z`` will default to ``2``.
885
886 If *module* is defined, the :attr:`~type.__module__` attribute of the
887 named tuple is set to that value.
888
889 Named tuple instances do not have per-instance dictionaries, so they are
890 lightweight and require no more memory than regular tuples.
891
892 To support pickling, the named tuple class should be assigned to a variable
893 that matches *typename*.
894
895 .. versionchanged:: 3.1
896 Added support for *rename*.
897
898 .. versionchanged:: 3.6
899 The *verbose* and *rename* parameters became
900 :ref:`keyword-only arguments <keyword-only_parameter>`.
901
902 .. versionchanged:: 3.6
903 Added the *module* parameter.
904
905 .. versionchanged:: 3.7
906 Removed the *verbose* parameter and the :attr:`!_source` attribute.
907
908 .. versionchanged:: 3.7
909 Added the *defaults* parameter and the :attr:`~somenamedtuple._field_defaults`
910 attribute.
911
912 .. doctest::
913 :options: +NORMALIZE_WHITESPACE
914
915 >>> # Basic example
916 >>> Point = namedtuple('Point', ['x', 'y'])
917 >>> p = Point(11, y=22) # instantiate with positional or keyword arguments
918 >>> p[0] + p[1] # indexable like the plain tuple (11, 22)
919 33
920 >>> x, y = p # unpack like a regular tuple
921 >>> x, y
922 (11, 22)
923 >>> p.x + p.y # fields also accessible by name
924 33
925 >>> p # readable __repr__ with a name=value style
926 Point(x=11, y=22)
927
928 Named tuples are especially useful for assigning field names to result tuples returned
929 by the :mod:`csv` or :mod:`sqlite3` modules::
930
931 EmployeeRecord = namedtuple('EmployeeRecord', 'name, age, title, department, paygrade')
932
933 import csv
934 for emp in map(EmployeeRecord._make, csv.reader(open("employees.csv", "rb"))):
935 print(emp.name, emp.title)
936
937 import sqlite3
938 conn = sqlite3.connect('/companydata')
939 cursor = conn.cursor()
940 cursor.execute('SELECT name, age, title, department, paygrade FROM employees')
941 for emp in map(EmployeeRecord._make, cursor.fetchall()):
942 print(emp.name, emp.title)
943
944 In addition to the methods inherited from tuples, named tuples support
945 three additional methods and two attributes. To prevent conflicts with
946 field names, the method and attribute names start with an underscore.
947
948 .. classmethod:: somenamedtuple._make(iterable, /)
949
950 Class method that makes a new instance from an existing sequence or iterable.
951
952 .. doctest::
953
954 >>> t = [11, 22]
955 >>> Point._make(t)
956 Point(x=11, y=22)
957
958 .. method:: somenamedtuple._asdict()
959
960 Return a new :class:`dict` which maps field names to their corresponding
961 values:
962
963 .. doctest::
964
965 >>> p = Point(x=11, y=22)
966 >>> p._asdict()
967 {'x': 11, 'y': 22}
968
969 .. versionchanged:: 3.1
970 Returns an :class:`OrderedDict` instead of a regular :class:`dict`.
971
972 .. versionchanged:: 3.8
973 Returns a regular :class:`dict` instead of an :class:`OrderedDict`.
974 As of Python 3.7, regular dicts are guaranteed to be ordered. If the
975 extra features of :class:`OrderedDict` are required, the suggested
976 remediation is to cast the result to the desired type:
977 ``OrderedDict(nt._asdict())``.
978
979 .. method:: somenamedtuple._replace(**kwargs)
980
981 Return a new instance of the named tuple replacing specified fields with new
982 values::
983
984 >>> p = Point(x=11, y=22)
985 >>> p._replace(x=33)
986 Point(x=33, y=22)
987
988 >>> for partnum, record in inventory.items():
989 ... inventory[partnum] = record._replace(price=newprices[partnum], timestamp=time.now())
990
991 Named tuples are also supported by generic function :func:`copy.replace`.
992
993 .. versionchanged:: 3.13
994 Raise :exc:`TypeError` instead of :exc:`ValueError` for invalid
995 keyword arguments.
996
997 .. attribute:: somenamedtuple._fields
998
999 Tuple of strings listing the field names. Useful for introspection
1000 and for creating new named tuple types from existing named tuples.
1001
1002 .. doctest::
1003
1004 >>> p._fields # view the field names
1005 ('x', 'y')
1006
1007 >>> Color = namedtuple('Color', 'red green blue')
1008 >>> Pixel = namedtuple('Pixel', Point._fields + Color._fields)
1009 >>> Pixel(11, 22, 128, 255, 0)
1010 Pixel(x=11, y=22, red=128, green=255, blue=0)
1011
1012 .. attribute:: somenamedtuple._field_defaults
1013
1014 Dictionary mapping field names to default values.
1015
1016 .. doctest::
1017
1018 >>> Account = namedtuple('Account', ['type', 'balance'], defaults=[0])
1019 >>> Account._field_defaults
1020 {'balance': 0}
1021 >>> Account('premium')
1022 Account(type='premium', balance=0)
1023
1024 To retrieve a field whose name is stored in a string, use the :func:`getattr`
1025 function:
1026
1027 >>> getattr(p, 'x')
1028 11
1029
1030 To convert a dictionary to a named tuple, use the double-star-operator
1031 (as described in :ref:`tut-unpacking-arguments`):
1032
1033 >>> d = {'x': 11, 'y': 22}
1034 >>> Point(**d)
1035 Point(x=11, y=22)
1036
1037 Since a named tuple is a regular Python class, it is easy to add or change
1038 functionality with a subclass. Here is how to add a calculated field and
1039 a fixed-width print format:
1040
1041 .. doctest::
1042
1043 >>> class Point(namedtuple('Point', ['x', 'y'])):
1044 ... __slots__ = ()
1045 ... @property
1046 ... def hypot(self):
1047 ... return (self.x ** 2 + self.y ** 2) ** 0.5
1048 ... def __str__(self):
1049 ... return 'Point: x=%6.3f y=%6.3f hypot=%6.3f' % (self.x, self.y, self.hypot)
1050
1051 >>> for p in Point(3, 4), Point(14, 5/7):
1052 ... print(p)
1053 Point: x= 3.000 y= 4.000 hypot= 5.000
1054 Point: x=14.000 y= 0.714 hypot=14.018
1055
1056 The subclass shown above sets ``__slots__`` to an empty tuple. This helps
1057 keep memory requirements low by preventing the creation of instance dictionaries.
1058
1059 Subclassing is not useful for adding new, stored fields. Instead, simply
1060 create a new named tuple type from the :attr:`~somenamedtuple._fields` attribute:
1061
1062 >>> Point3D = namedtuple('Point3D', Point._fields + ('z',))
1063
1064 Docstrings can be customized by making direct assignments to the ``__doc__``
1065 fields:
1066
1067 >>> Book = namedtuple('Book', ['id', 'title', 'authors'])
1068 >>> Book.__doc__ += ': Hardcover book in active collection'
1069 >>> Book.id.__doc__ = '13-digit ISBN'
1070 >>> Book.title.__doc__ = 'Title of first printing'
1071 >>> Book.authors.__doc__ = 'List of authors sorted by last name'
1072
1073 .. versionchanged:: 3.5
1074 Property docstrings became writeable.
1075
1076 .. seealso::
1077
1078 * See :class:`typing.NamedTuple` for a way to add type hints for named
1079 tuples. It also provides an elegant notation using the :keyword:`class`
1080 keyword::
1081
1082 class Component(NamedTuple):
1083 part_number: int
1084 weight: float
1085 description: Optional[str] = None
1086
1087 * See :meth:`types.SimpleNamespace` for a mutable namespace based on an
1088 underlying dictionary instead of a tuple.
1089
1090 * The :mod:`dataclasses` module provides a decorator and functions for
1091 automatically adding generated special methods to user-defined classes.
1092
1093
1094 :class:`OrderedDict` objects
1095 ----------------------------
1096
1097 Ordered dictionaries are just like regular dictionaries but have some extra
1098 capabilities relating to ordering operations. They have become less
1099 important now that the built-in :class:`dict` class gained the ability
1100 to remember insertion order (this new behavior became guaranteed in
1101 Python 3.7).
1102
1103 Some differences from :class:`dict` still remain:
1104
1105 * The regular :class:`dict` was designed to be very good at mapping
1106 operations. Tracking insertion order was secondary.
1107
1108 * The :class:`OrderedDict` was designed to be good at reordering operations.
1109 Space efficiency, iteration speed, and the performance of update
1110 operations were secondary.
1111
1112 * The :class:`OrderedDict` algorithm can handle frequent reordering operations
1113 better than :class:`dict`. As shown in the recipes below, this makes it
1114 suitable for implementing various kinds of LRU caches.
1115
1116 * The equality operation for :class:`OrderedDict` checks for matching order.
1117
1118 A regular :class:`dict` can emulate the order sensitive equality test with
1119 ``p == q and all(k1 == k2 for k1, k2 in zip(p, q))``.
1120
1121 * The :meth:`~OrderedDict.popitem` method of :class:`OrderedDict` has a different
1122 signature. It accepts an optional argument to specify which item is popped.
1123
1124 A regular :class:`dict` can emulate OrderedDict's ``od.popitem(last=True)``
1125 with ``d.popitem()`` which is guaranteed to pop the rightmost (last) item.
1126
1127 A regular :class:`dict` can emulate OrderedDict's ``od.popitem(last=False)``
1128 with ``(k := next(iter(d)), d.pop(k))`` which will return and remove the
1129 leftmost (first) item if it exists.
1130
1131 * :class:`OrderedDict` has a :meth:`~OrderedDict.move_to_end` method to efficiently
1132 reposition an element to an endpoint.
1133
1134 A regular :class:`dict` can emulate OrderedDict's ``od.move_to_end(k,
1135 last=True)`` with ``d[k] = d.pop(k)`` which will move the key and its
1136 associated value to the rightmost (last) position.
1137
1138 A regular :class:`dict` does not have an efficient equivalent for
1139 OrderedDict's ``od.move_to_end(k, last=False)`` which moves the key
1140 and its associated value to the leftmost (first) position.
1141
1142 * Until Python 3.8, :class:`dict` lacked a :meth:`~object.__reversed__` method.
1143
1144
1145 .. class:: OrderedDict(**kwargs)
1146 OrderedDict(mapping, /, **kwargs)
1147 OrderedDict(iterable, /, **kwargs)
1148
1149 Return an instance of a :class:`dict` subclass that has methods
1150 specialized for rearranging dictionary order.
1151
1152 .. versionadded:: 3.1
1153
1154 .. method:: popitem(last=True)
1155
1156 The :meth:`popitem` method for ordered dictionaries returns and removes a
1157 (key, value) pair. The pairs are returned in
1158 :abbr:`LIFO (last-in, first-out)` order if *last* is true
1159 or :abbr:`FIFO (first-in, first-out)` order if false.
1160
1161 .. method:: move_to_end(key, last=True)
1162
1163 Move an existing *key* to either end of an ordered dictionary. The item
1164 is moved to the right end if *last* is true (the default) or to the
1165 beginning if *last* is false. Raises :exc:`KeyError` if the *key* does
1166 not exist:
1167
1168 .. doctest::
1169
1170 >>> d = OrderedDict.fromkeys('abcde')
1171 >>> d.move_to_end('b')
1172 >>> ''.join(d)
1173 'acdeb'
1174 >>> d.move_to_end('b', last=False)
1175 >>> ''.join(d)
1176 'bacde'
1177
1178 .. versionadded:: 3.2
1179
1180 In addition to the usual mapping methods, ordered dictionaries also support
1181 reverse iteration using :func:`reversed`.
1182
1183 .. _collections_OrderedDict__eq__:
1184
1185 Equality tests between :class:`OrderedDict` objects are order-sensitive
1186 and are roughly equivalent to ``list(od1.items())==list(od2.items())``.
1187
1188 Equality tests between :class:`OrderedDict` objects and other
1189 :class:`~collections.abc.Mapping` objects are order-insensitive like regular
1190 dictionaries. This allows :class:`OrderedDict` objects to be substituted
1191 anywhere a regular dictionary is used.
1192
1193 .. versionchanged:: 3.5
1194 The items, keys, and values :term:`views <dictionary view>`
1195 of :class:`OrderedDict` now support reverse iteration using :func:`reversed`.
1196
1197 .. versionchanged:: 3.6
1198 With the acceptance of :pep:`468`, order is retained for keyword arguments
1199 passed to the :class:`OrderedDict` constructor and its :meth:`~dict.update`
1200 method.
1201
1202 .. versionchanged:: 3.9
1203 Added merge (``|``) and update (``|=``) operators, specified in :pep:`584`.
1204
1205
1206 :class:`OrderedDict` Examples and Recipes
1207 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1208
1209 It is straightforward to create an ordered dictionary variant
1210 that remembers the order the keys were *last* inserted.
1211 If a new entry overwrites an existing entry, the
1212 original insertion position is changed and moved to the end::
1213
1214 class LastUpdatedOrderedDict(OrderedDict):
1215 'Store items in the order the keys were last added'
1216
1217 def __setitem__(self, key, value):
1218 super().__setitem__(key, value)
1219 self.move_to_end(key)
1220
1221 An :class:`OrderedDict` would also be useful for implementing
1222 variants of :func:`functools.lru_cache`:
1223
1224 .. testcode::
1225
1226 from collections import OrderedDict
1227 from time import time
1228
1229 class TimeBoundedLRU:
1230 "LRU Cache that invalidates and refreshes old entries."
1231
1232 def __init__(self, func, maxsize=128, maxage=30):
1233 self.cache = OrderedDict() # { args : (timestamp, result)}
1234 self.func = func
1235 self.maxsize = maxsize
1236 self.maxage = maxage
1237
1238 def __call__(self, *args):
1239 if args in self.cache:
1240 self.cache.move_to_end(args)
1241 timestamp, result = self.cache[args]
1242 if time() - timestamp <= self.maxage:
1243 return result
1244 result = self.func(*args)
1245 self.cache[args] = time(), result
1246 if len(self.cache) > self.maxsize:
1247 self.cache.popitem(last=False)
1248 return result
1249
1250
1251 .. testcode::
1252
1253 class MultiHitLRUCache:
1254 """ LRU cache that defers caching a result until
1255 it has been requested multiple times.
1256
1257 To avoid flushing the LRU cache with one-time requests,
1258 we don't cache until a request has been made more than once.
1259
1260 """
1261
1262 def __init__(self, func, maxsize=128, maxrequests=4096, cache_after=1):
1263 self.requests = OrderedDict() # { uncached_key : request_count }
1264 self.cache = OrderedDict() # { cached_key : function_result }
1265 self.func = func
1266 self.maxrequests = maxrequests # max number of uncached requests
1267 self.maxsize = maxsize # max number of stored return values
1268 self.cache_after = cache_after
1269
1270 def __call__(self, *args):
1271 if args in self.cache:
1272 self.cache.move_to_end(args)
1273 return self.cache[args]
1274 result = self.func(*args)
1275 self.requests[args] = self.requests.get(args, 0) + 1
1276 if self.requests[args] <= self.cache_after:
1277 self.requests.move_to_end(args)
1278 if len(self.requests) > self.maxrequests:
1279 self.requests.popitem(last=False)
1280 else:
1281 self.requests.pop(args, None)
1282 self.cache[args] = result
1283 if len(self.cache) > self.maxsize:
1284 self.cache.popitem(last=False)
1285 return result
1286
1287 .. doctest::
1288 :hide:
1289
1290 >>> def square(x):
1291 ... return x * x
1292 ...
1293 >>> f = MultiHitLRUCache(square, maxsize=4, maxrequests=6)
1294 >>> list(map(f, range(10))) # First requests, don't cache
1295 [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
1296 >>> f(4) # Cache the second request
1297 16
1298 >>> f(6) # Cache the second request
1299 36
1300 >>> f(2) # The first request aged out, so don't cache
1301 4
1302 >>> f(6) # Cache hit
1303 36
1304 >>> f(4) # Cache hit and move to front
1305 16
1306 >>> list(f.cache.values())
1307 [36, 16]
1308 >>> set(f.requests).isdisjoint(f.cache)
1309 True
1310 >>> list(map(f, [9, 8, 7])) # Cache these second requests
1311 [81, 64, 49]
1312 >>> list(map(f, [7, 9])) # Cache hits
1313 [49, 81]
1314 >>> list(f.cache.values())
1315 [16, 64, 49, 81]
1316 >>> set(f.requests).isdisjoint(f.cache)
1317 True
1318
1319 :class:`UserDict` objects
1320 -------------------------
1321
1322 The class, :class:`UserDict` acts as a wrapper around dictionary objects.
1323 The need for this class has been partially supplanted by the ability to
1324 subclass directly from :class:`dict`; however, this class can be easier
1325 to work with because the underlying dictionary is accessible as an
1326 attribute.
1327
1328 .. class:: UserDict(**kwargs)
1329 UserDict(mapping, /, **kwargs)
1330 UserDict(iterable, /, **kwargs)
1331
1332 Class that simulates a dictionary. The instance's contents are kept in a
1333 regular dictionary, which is accessible via the :attr:`data` attribute of
1334 :class:`!UserDict` instances. If arguments are provided, they are used to
1335 initialize :attr:`data`, like a regular dictionary.
1336
1337 In addition to supporting the methods and operations of mappings,
1338 :class:`!UserDict` instances provide the following attribute:
1339
1340 .. attribute:: data
1341
1342 A real dictionary used to store the contents of the :class:`UserDict`
1343 class.
1344
1345
1346
1347 :class:`UserList` objects
1348 -------------------------
1349
1350 This class acts as a wrapper around list objects. It is a useful base class
1351 for your own list-like classes which can inherit from them and override
1352 existing methods or add new ones. In this way, one can add new behaviors to
1353 lists.
1354
1355 The need for this class has been partially supplanted by the ability to
1356 subclass directly from :class:`list`; however, this class can be easier
1357 to work with because the underlying list is accessible as an attribute.
1358
1359 .. class:: UserList([list])
1360
1361 Class that simulates a list. The instance's contents are kept in a regular
1362 list, which is accessible via the :attr:`data` attribute of :class:`UserList`
1363 instances. The instance's contents are initially set to a copy of *list*,
1364 defaulting to the empty list ``[]``. *list* can be any iterable, for
1365 example a real Python list or a :class:`UserList` object.
1366
1367 In addition to supporting the methods and operations of mutable sequences,
1368 :class:`UserList` instances provide the following attribute:
1369
1370 .. attribute:: data
1371
1372 A real :class:`list` object used to store the contents of the
1373 :class:`UserList` class.
1374
1375 **Subclassing requirements:** Subclasses of :class:`UserList` are expected to
1376 offer a constructor which can be called with either no arguments or one
1377 argument. List operations which return a new sequence attempt to create an
1378 instance of the actual implementation class. To do so, it assumes that the
1379 constructor can be called with a single parameter, which is a sequence object
1380 used as a data source.
1381
1382 If a derived class does not wish to comply with this requirement, all of the
1383 special methods supported by this class will need to be overridden; please
1384 consult the sources for information about the methods which need to be provided
1385 in that case.
1386
1387 :class:`UserString` objects
1388 ---------------------------
1389
1390 The class, :class:`UserString` acts as a wrapper around string objects.
1391 The need for this class has been partially supplanted by the ability to
1392 subclass directly from :class:`str`; however, this class can be easier
1393 to work with because the underlying string is accessible as an
1394 attribute.
1395
1396 .. class:: UserString(seq)
1397
1398 Class that simulates a string object. The instance's
1399 content is kept in a regular string object, which is accessible via the
1400 :attr:`data` attribute of :class:`UserString` instances. The instance's
1401 contents are initially set to a copy of *seq*. The *seq* argument can
1402 be any object which can be converted into a string using the built-in
1403 :func:`str` function.
1404
1405 In addition to supporting the methods and operations of strings,
1406 :class:`UserString` instances provide the following attribute:
1407
1408 .. attribute:: data
1409
1410 A real :class:`str` object used to store the contents of the
1411 :class:`UserString` class.
1412
1413 .. versionchanged:: 3.5
1414 New methods ``__getnewargs__``, ``__rmod__``, ``casefold``,
1415 ``format_map``, ``isprintable``, and ``maketrans``.