1 :mod:`collections` --- High-performance container datatypes 2 =========================================================== 3 4 .. module:: collections 5 :synopsis: High-performance datatypes 6 .. moduleauthor:: Raymond Hettinger <python (a] rcn.com> 7 .. sectionauthor:: Raymond Hettinger <python (a] rcn.com> 8 9 .. versionadded:: 2.4 10 11 .. testsetup:: * 12 13 from collections import * 14 import itertools 15 __name__ = '<doctest>' 16 17 **Source code:** :source:`Lib/collections.py` and :source:`Lib/_abcoll.py` 18 19 -------------- 20 21 This module implements specialized container datatypes providing alternatives to 22 Python's general purpose built-in containers, :class:`dict`, :class:`list`, 23 :class:`set`, and :class:`tuple`. 24 25 ===================== ==================================================================== =========================== 26 :func:`namedtuple` factory function for creating tuple subclasses with named fields .. versionadded:: 2.6 27 :class:`deque` list-like container with fast appends and pops on either end .. versionadded:: 2.4 28 :class:`Counter` dict subclass for counting hashable objects .. versionadded:: 2.7 29 :class:`OrderedDict` dict subclass that remembers the order entries were added .. versionadded:: 2.7 30 :class:`defaultdict` dict subclass that calls a factory function to supply missing values .. versionadded:: 2.5 31 ===================== ==================================================================== =========================== 32 33 In addition to the concrete container classes, the collections module provides 34 :ref:`abstract base classes <collections-abstract-base-classes>` that can be 35 used to test whether a class provides a particular interface, for example, 36 whether it is hashable or a mapping. 37 38 39 :class:`Counter` objects 40 ------------------------ 41 42 A counter tool is provided to support convenient and rapid tallies. 43 For example:: 44 45 >>> # Tally occurrences of words in a list 46 >>> cnt = Counter() 47 >>> for word in ['red', 'blue', 'red', 'green', 'blue', 'blue']: 48 ... cnt[word] += 1 49 >>> cnt 50 Counter({'blue': 3, 'red': 2, 'green': 1}) 51 52 >>> # Find the ten most common words in Hamlet 53 >>> import re 54 >>> words = re.findall(r'\w+', open('hamlet.txt').read().lower()) 55 >>> Counter(words).most_common(10) 56 [('the', 1143), ('and', 966), ('to', 762), ('of', 669), ('i', 631), 57 ('you', 554), ('a', 546), ('my', 514), ('hamlet', 471), ('in', 451)] 58 59 .. class:: Counter([iterable-or-mapping]) 60 61 A :class:`Counter` is a :class:`dict` subclass for counting hashable objects. 62 It is an unordered collection where elements are stored as dictionary keys 63 and their counts are stored as dictionary values. Counts are allowed to be 64 any integer value including zero or negative counts. The :class:`Counter` 65 class is similar to bags or multisets in other languages. 66 67 Elements are counted from an *iterable* or initialized from another 68 *mapping* (or counter): 69 70 >>> c = Counter() # a new, empty counter 71 >>> c = Counter('gallahad') # a new counter from an iterable 72 >>> c = Counter({'red': 4, 'blue': 2}) # a new counter from a mapping 73 >>> c = Counter(cats=4, dogs=8) # a new counter from keyword args 74 75 Counter objects have a dictionary interface except that they return a zero 76 count for missing items instead of raising a :exc:`KeyError`: 77 78 >>> c = Counter(['eggs', 'ham']) 79 >>> c['bacon'] # count of a missing element is zero 80 0 81 82 Setting a count to zero does not remove an element from a counter. 83 Use ``del`` to remove it entirely: 84 85 >>> c['sausage'] = 0 # counter entry with a zero count 86 >>> del c['sausage'] # del actually removes the entry 87 88 .. versionadded:: 2.7 89 90 91 Counter objects support three methods beyond those available for all 92 dictionaries: 93 94 .. method:: elements() 95 96 Return an iterator over elements repeating each as many times as its 97 count. Elements are returned in arbitrary order. If an element's count 98 is less than one, :meth:`elements` will ignore it. 99 100 >>> c = Counter(a=4, b=2, c=0, d=-2) 101 >>> list(c.elements()) 102 ['a', 'a', 'a', 'a', 'b', 'b'] 103 104 .. method:: most_common([n]) 105 106 Return a list of the *n* most common elements and their counts from the 107 most common to the least. If *n* is omitted or ``None``, 108 :func:`most_common` returns *all* elements in the counter. 109 Elements with equal counts are ordered arbitrarily: 110 111 >>> Counter('abracadabra').most_common(3) 112 [('a', 5), ('r', 2), ('b', 2)] 113 114 .. method:: subtract([iterable-or-mapping]) 115 116 Elements are subtracted from an *iterable* or from another *mapping* 117 (or counter). Like :meth:`dict.update` but subtracts counts instead 118 of replacing them. Both inputs and outputs may be zero or negative. 119 120 >>> c = Counter(a=4, b=2, c=0, d=-2) 121 >>> d = Counter(a=1, b=2, c=3, d=4) 122 >>> c.subtract(d) 123 >>> c 124 Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6}) 125 126 The usual dictionary methods are available for :class:`Counter` objects 127 except for two which work differently for counters. 128 129 .. method:: fromkeys(iterable) 130 131 This class method is not implemented for :class:`Counter` objects. 132 133 .. method:: update([iterable-or-mapping]) 134 135 Elements are counted from an *iterable* or added-in from another 136 *mapping* (or counter). Like :meth:`dict.update` but adds counts 137 instead of replacing them. Also, the *iterable* is expected to be a 138 sequence of elements, not a sequence of ``(key, value)`` pairs. 139 140 Common patterns for working with :class:`Counter` objects:: 141 142 sum(c.values()) # total of all counts 143 c.clear() # reset all counts 144 list(c) # list unique elements 145 set(c) # convert to a set 146 dict(c) # convert to a regular dictionary 147 c.items() # convert to a list of (elem, cnt) pairs 148 Counter(dict(list_of_pairs)) # convert from a list of (elem, cnt) pairs 149 c.most_common()[:-n-1:-1] # n least common elements 150 c += Counter() # remove zero and negative counts 151 152 Several mathematical operations are provided for combining :class:`Counter` 153 objects to produce multisets (counters that have counts greater than zero). 154 Addition and subtraction combine counters by adding or subtracting the counts 155 of corresponding elements. Intersection and union return the minimum and 156 maximum of corresponding counts. Each operation can accept inputs with signed 157 counts, but the output will exclude results with counts of zero or less. 158 159 >>> c = Counter(a=3, b=1) 160 >>> d = Counter(a=1, b=2) 161 >>> c + d # add two counters together: c[x] + d[x] 162 Counter({'a': 4, 'b': 3}) 163 >>> c - d # subtract (keeping only positive counts) 164 Counter({'a': 2}) 165 >>> c & d # intersection: min(c[x], d[x]) 166 Counter({'a': 1, 'b': 1}) 167 >>> c | d # union: max(c[x], d[x]) 168 Counter({'a': 3, 'b': 2}) 169 170 .. note:: 171 172 Counters were primarily designed to work with positive integers to represent 173 running counts; however, care was taken to not unnecessarily preclude use 174 cases needing other types or negative values. To help with those use cases, 175 this section documents the minimum range and type restrictions. 176 177 * The :class:`Counter` class itself is a dictionary subclass with no 178 restrictions on its keys and values. The values are intended to be numbers 179 representing counts, but you *could* store anything in the value field. 180 181 * The :meth:`most_common` method requires only that the values be orderable. 182 183 * For in-place operations such as ``c[key] += 1``, the value type need only 184 support addition and subtraction. So fractions, floats, and decimals would 185 work and negative values are supported. The same is also true for 186 :meth:`update` and :meth:`subtract` which allow negative and zero values 187 for both inputs and outputs. 188 189 * The multiset methods are designed only for use cases with positive values. 190 The inputs may be negative or zero, but only outputs with positive values 191 are created. There are no type restrictions, but the value type needs to 192 support addition, subtraction, and comparison. 193 194 * The :meth:`elements` method requires integer counts. It ignores zero and 195 negative counts. 196 197 .. seealso:: 198 199 * `Counter class <https://code.activestate.com/recipes/576611/>`_ 200 adapted for Python 2.5 and an early `Bag recipe 201 <https://code.activestate.com/recipes/259174/>`_ for Python 2.4. 202 203 in Smalltalk. 204 205 * Wikipedia entry for `Multisets <https://en.wikipedia.org/wiki/Multiset>`_. 206 207 * `C++ multisets <http://www.java2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm>`_ 208 tutorial with examples. 209 210 * For mathematical operations on multisets and their use cases, see 211 *Knuth, Donald. The Art of Computer Programming Volume II, 212 Section 4.6.3, Exercise 19*. 213 214 * To enumerate all distinct multisets of a given size over a given set of 215 elements, see :func:`itertools.combinations_with_replacement`. 216 217 map(Counter, combinations_with_replacement('ABC', 2)) --> AA AB AC BB BC CC 218 219 220 :class:`deque` objects 221 ---------------------- 222 223 .. class:: deque([iterable[, maxlen]]) 224 225 Returns a new deque object initialized left-to-right (using :meth:`append`) with 226 data from *iterable*. If *iterable* is not specified, the new deque is empty. 227 228 Deques are a generalization of stacks and queues (the name is pronounced "deck" 229 and is short for "double-ended queue"). Deques support thread-safe, memory 230 efficient appends and pops from either side of the deque with approximately the 231 same O(1) performance in either direction. 232 233 Though :class:`list` objects support similar operations, they are optimized for 234 fast fixed-length operations and incur O(n) memory movement costs for 235 ``pop(0)`` and ``insert(0, v)`` operations which change both the size and 236 position of the underlying data representation. 237 238 .. versionadded:: 2.4 239 240 If *maxlen* is not specified or is ``None``, deques may grow to an 241 arbitrary length. Otherwise, the deque is bounded to the specified maximum 242 length. Once a bounded length deque is full, when new items are added, a 243 corresponding number of items are discarded from the opposite end. Bounded 244 length deques provide functionality similar to the ``tail`` filter in 245 Unix. They are also useful for tracking transactions and other pools of data 246 where only the most recent activity is of interest. 247 248 .. versionchanged:: 2.6 249 Added *maxlen* parameter. 250 251 Deque objects support the following methods: 252 253 254 .. method:: append(x) 255 256 Add *x* to the right side of the deque. 257 258 259 .. method:: appendleft(x) 260 261 Add *x* to the left side of the deque. 262 263 264 .. method:: clear() 265 266 Remove all elements from the deque leaving it with length 0. 267 268 269 .. method:: count(x) 270 271 Count the number of deque elements equal to *x*. 272 273 .. versionadded:: 2.7 274 275 .. method:: extend(iterable) 276 277 Extend the right side of the deque by appending elements from the iterable 278 argument. 279 280 281 .. method:: extendleft(iterable) 282 283 Extend the left side of the deque by appending elements from *iterable*. 284 Note, the series of left appends results in reversing the order of 285 elements in the iterable argument. 286 287 288 .. method:: pop() 289 290 Remove and return an element from the right side of the deque. If no 291 elements are present, raises an :exc:`IndexError`. 292 293 294 .. method:: popleft() 295 296 Remove and return an element from the left side of the deque. If no 297 elements are present, raises an :exc:`IndexError`. 298 299 300 .. method:: remove(value) 301 302 Removed the first occurrence of *value*. If not found, raises a 303 :exc:`ValueError`. 304 305 .. versionadded:: 2.5 306 307 .. method:: reverse() 308 309 Reverse the elements of the deque in-place and then return ``None``. 310 311 .. versionadded:: 2.7 312 313 .. method:: rotate(n) 314 315 Rotate the deque *n* steps to the right. If *n* is negative, rotate to 316 the left. Rotating one step to the right is equivalent to: 317 ``d.appendleft(d.pop())``. 318 319 320 Deque objects also provide one read-only attribute: 321 322 .. attribute:: maxlen 323 324 Maximum size of a deque or ``None`` if unbounded. 325 326 .. versionadded:: 2.7 327 328 329 In addition to the above, deques support iteration, pickling, ``len(d)``, 330 ``reversed(d)``, ``copy.copy(d)``, ``copy.deepcopy(d)``, membership testing with 331 the :keyword:`in` operator, and subscript references such as ``d[-1]``. Indexed 332 access is O(1) at both ends but slows to O(n) in the middle. For fast random 333 access, use lists instead. 334 335 Example: 336 337 .. doctest:: 338 339 >>> from collections import deque 340 >>> d = deque('ghi') # make a new deque with three items 341 >>> for elem in d: # iterate over the deque's elements 342 ... print elem.upper() 343 G 344 H 345 I 346 347 >>> d.append('j') # add a new entry to the right side 348 >>> d.appendleft('f') # add a new entry to the left side 349 >>> d # show the representation of the deque 350 deque(['f', 'g', 'h', 'i', 'j']) 351 352 >>> d.pop() # return and remove the rightmost item 353 'j' 354 >>> d.popleft() # return and remove the leftmost item 355 'f' 356 >>> list(d) # list the contents of the deque 357 ['g', 'h', 'i'] 358 >>> d[0] # peek at leftmost item 359 'g' 360 >>> d[-1] # peek at rightmost item 361 'i' 362 363 >>> list(reversed(d)) # list the contents of a deque in reverse 364 ['i', 'h', 'g'] 365 >>> 'h' in d # search the deque 366 True 367 >>> d.extend('jkl') # add multiple elements at once 368 >>> d 369 deque(['g', 'h', 'i', 'j', 'k', 'l']) 370 >>> d.rotate(1) # right rotation 371 >>> d 372 deque(['l', 'g', 'h', 'i', 'j', 'k']) 373 >>> d.rotate(-1) # left rotation 374 >>> d 375 deque(['g', 'h', 'i', 'j', 'k', 'l']) 376 377 >>> deque(reversed(d)) # make a new deque in reverse order 378 deque(['l', 'k', 'j', 'i', 'h', 'g']) 379 >>> d.clear() # empty the deque 380 >>> d.pop() # cannot pop from an empty deque 381 Traceback (most recent call last): 382 File "<pyshell#6>", line 1, in -toplevel- 383 d.pop() 384 IndexError: pop from an empty deque 385 386 >>> d.extendleft('abc') # extendleft() reverses the input order 387 >>> d 388 deque(['c', 'b', 'a']) 389 390 391 :class:`deque` Recipes 392 ^^^^^^^^^^^^^^^^^^^^^^ 393 394 This section shows various approaches to working with deques. 395 396 Bounded length deques provide functionality similar to the ``tail`` filter 397 in Unix:: 398 399 def tail(filename, n=10): 400 'Return the last n lines of a file' 401 return deque(open(filename), n) 402 403 Another approach to using deques is to maintain a sequence of recently 404 added elements by appending to the right and popping to the left:: 405 406 def moving_average(iterable, n=3): 407 # moving_average([40, 30, 50, 46, 39, 44]) --> 40.0 42.0 45.0 43.0 408 # http://en.wikipedia.org/wiki/Moving_average 409 it = iter(iterable) 410 d = deque(itertools.islice(it, n-1)) 411 d.appendleft(0) 412 s = sum(d) 413 for elem in it: 414 s += elem - d.popleft() 415 d.append(elem) 416 yield s / float(n) 417 418 The :meth:`rotate` method provides a way to implement :class:`deque` slicing and 419 deletion. For example, a pure Python implementation of ``del d[n]`` relies on 420 the :meth:`rotate` method to position elements to be popped:: 421 422 def delete_nth(d, n): 423 d.rotate(-n) 424 d.popleft() 425 d.rotate(n) 426 427 To implement :class:`deque` slicing, use a similar approach applying 428 :meth:`rotate` to bring a target element to the left side of the deque. Remove 429 old entries with :meth:`popleft`, add new entries with :meth:`extend`, and then 430 reverse the rotation. 431 With minor variations on that approach, it is easy to implement Forth style 432 stack manipulations such as ``dup``, ``drop``, ``swap``, ``over``, ``pick``, 433 ``rot``, and ``roll``. 434 435 436 :class:`defaultdict` objects 437 ---------------------------- 438 439 .. class:: defaultdict([default_factory[, ...]]) 440 441 Returns a new dictionary-like object. :class:`defaultdict` is a subclass of the 442 built-in :class:`dict` class. It overrides one method and adds one writable 443 instance variable. The remaining functionality is the same as for the 444 :class:`dict` class and is not documented here. 445 446 The first argument provides the initial value for the :attr:`default_factory` 447 attribute; it defaults to ``None``. All remaining arguments are treated the same 448 as if they were passed to the :class:`dict` constructor, including keyword 449 arguments. 450 451 .. versionadded:: 2.5 452 453 :class:`defaultdict` objects support the following method in addition to the 454 standard :class:`dict` operations: 455 456 .. method:: __missing__(key) 457 458 If the :attr:`default_factory` attribute is ``None``, this raises a 459 :exc:`KeyError` exception with the *key* as argument. 460 461 If :attr:`default_factory` is not ``None``, it is called without arguments 462 to provide a default value for the given *key*, this value is inserted in 463 the dictionary for the *key*, and returned. 464 465 If calling :attr:`default_factory` raises an exception this exception is 466 propagated unchanged. 467 468 This method is called by the :meth:`__getitem__` method of the 469 :class:`dict` class when the requested key is not found; whatever it 470 returns or raises is then returned or raised by :meth:`__getitem__`. 471 472 Note that :meth:`__missing__` is *not* called for any operations besides 473 :meth:`__getitem__`. This means that :meth:`get` will, like normal 474 dictionaries, return ``None`` as a default rather than using 475 :attr:`default_factory`. 476 477 478 :class:`defaultdict` objects support the following instance variable: 479 480 481 .. attribute:: default_factory 482 483 This attribute is used by the :meth:`__missing__` method; it is 484 initialized from the first argument to the constructor, if present, or to 485 ``None``, if absent. 486 487 488 :class:`defaultdict` Examples 489 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 490 491 Using :class:`list` as the :attr:`default_factory`, it is easy to group a 492 sequence of key-value pairs into a dictionary of lists: 493 494 >>> s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)] 495 >>> d = defaultdict(list) 496 >>> for k, v in s: 497 ... d[k].append(v) 498 ... 499 >>> d.items() 500 [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])] 501 502 When each key is encountered for the first time, it is not already in the 503 mapping; so an entry is automatically created using the :attr:`default_factory` 504 function which returns an empty :class:`list`. The :meth:`list.append` 505 operation then attaches the value to the new list. When keys are encountered 506 again, the look-up proceeds normally (returning the list for that key) and the 507 :meth:`list.append` operation adds another value to the list. This technique is 508 simpler and faster than an equivalent technique using :meth:`dict.setdefault`: 509 510 >>> d = {} 511 >>> for k, v in s: 512 ... d.setdefault(k, []).append(v) 513 ... 514 >>> d.items() 515 [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])] 516 517 Setting the :attr:`default_factory` to :class:`int` makes the 518 :class:`defaultdict` useful for counting (like a bag or multiset in other 519 languages): 520 521 >>> s = 'mississippi' 522 >>> d = defaultdict(int) 523 >>> for k in s: 524 ... d[k] += 1 525 ... 526 >>> d.items() 527 [('i', 4), ('p', 2), ('s', 4), ('m', 1)] 528 529 When a letter is first encountered, it is missing from the mapping, so the 530 :attr:`default_factory` function calls :func:`int` to supply a default count of 531 zero. The increment operation then builds up the count for each letter. 532 533 The function :func:`int` which always returns zero is just a special case of 534 constant functions. A faster and more flexible way to create constant functions 535 is to use :func:`itertools.repeat` which can supply any constant value (not just 536 zero): 537 538 >>> def constant_factory(value): 539 ... return itertools.repeat(value).next 540 >>> d = defaultdict(constant_factory('<missing>')) 541 >>> d.update(name='John', action='ran') 542 >>> '%(name)s %(action)s to %(object)s' % d 543 'John ran to <missing>' 544 545 Setting the :attr:`default_factory` to :class:`set` makes the 546 :class:`defaultdict` useful for building a dictionary of sets: 547 548 >>> s = [('red', 1), ('blue', 2), ('red', 3), ('blue', 4), ('red', 1), ('blue', 4)] 549 >>> d = defaultdict(set) 550 >>> for k, v in s: 551 ... d[k].add(v) 552 ... 553 >>> d.items() 554 [('blue', set([2, 4])), ('red', set([1, 3]))] 555 556 557 :func:`namedtuple` Factory Function for Tuples with Named Fields 558 ---------------------------------------------------------------- 559 560 Named tuples assign meaning to each position in a tuple and allow for more readable, 561 self-documenting code. They can be used wherever regular tuples are used, and 562 they add the ability to access fields by name instead of position index. 563 564 .. function:: namedtuple(typename, field_names, [verbose=False], [rename=False]) 565 566 Returns a new tuple subclass named *typename*. The new subclass is used to 567 create tuple-like objects that have fields accessible by attribute lookup as 568 well as being indexable and iterable. Instances of the subclass also have a 569 helpful docstring (with typename and field_names) and a helpful :meth:`__repr__` 570 method which lists the tuple contents in a ``name=value`` format. 571 572 The *field_names* are a sequence of strings such as ``['x', 'y']``. 573 Alternatively, *field_names* can be a single string with each fieldname 574 separated by whitespace and/or commas, for example ``'x y'`` or ``'x, y'``. 575 576 Any valid Python identifier may be used for a fieldname except for names 577 starting with an underscore. Valid identifiers consist of letters, digits, 578 and underscores but do not start with a digit or underscore and cannot be 579 a :mod:`keyword` such as *class*, *for*, *return*, *global*, *pass*, *print*, 580 or *raise*. 581 582 If *rename* is true, invalid fieldnames are automatically replaced 583 with positional names. For example, ``['abc', 'def', 'ghi', 'abc']`` is 584 converted to ``['abc', '_1', 'ghi', '_3']``, eliminating the keyword 585 ``def`` and the duplicate fieldname ``abc``. 586 587 If *verbose* is true, the class definition is printed just before being built. 588 589 Named tuple instances do not have per-instance dictionaries, so they are 590 lightweight and require no more memory than regular tuples. 591 592 .. versionadded:: 2.6 593 594 .. versionchanged:: 2.7 595 added support for *rename*. 596 597 Example: 598 599 .. doctest:: 600 :options: +NORMALIZE_WHITESPACE 601 602 >>> Point = namedtuple('Point', ['x', 'y'], verbose=True) 603 class Point(tuple): 604 'Point(x, y)' 605 <BLANKLINE> 606 __slots__ = () 607 <BLANKLINE> 608 _fields = ('x', 'y') 609 <BLANKLINE> 610 def __new__(_cls, x, y): 611 'Create new instance of Point(x, y)' 612 return _tuple.__new__(_cls, (x, y)) 613 <BLANKLINE> 614 @classmethod 615 def _make(cls, iterable, new=tuple.__new__, len=len): 616 'Make a new Point object from a sequence or iterable' 617 result = new(cls, iterable) 618 if len(result) != 2: 619 raise TypeError('Expected 2 arguments, got %d' % len(result)) 620 return result 621 <BLANKLINE> 622 def __repr__(self): 623 'Return a nicely formatted representation string' 624 return 'Point(x=%r, y=%r)' % self 625 <BLANKLINE> 626 def _asdict(self): 627 'Return a new OrderedDict which maps field names to their values' 628 return OrderedDict(zip(self._fields, self)) 629 <BLANKLINE> 630 def _replace(_self, **kwds): 631 'Return a new Point object replacing specified fields with new values' 632 result = _self._make(map(kwds.pop, ('x', 'y'), _self)) 633 if kwds: 634 raise ValueError('Got unexpected field names: %r' % kwds.keys()) 635 return result 636 <BLANKLINE> 637 def __getnewargs__(self): 638 'Return self as a plain tuple. Used by copy and pickle.' 639 return tuple(self) 640 <BLANKLINE> 641 __dict__ = _property(_asdict) 642 <BLANKLINE> 643 def __getstate__(self): 644 'Exclude the OrderedDict from pickling' 645 pass 646 <BLANKLINE> 647 x = _property(_itemgetter(0), doc='Alias for field number 0') 648 <BLANKLINE> 649 y = _property(_itemgetter(1), doc='Alias for field number 1') 650 <BLANKLINE> 651 <BLANKLINE> 652 653 >>> p = Point(11, y=22) # instantiate with positional or keyword arguments 654 >>> p[0] + p[1] # indexable like the plain tuple (11, 22) 655 33 656 >>> x, y = p # unpack like a regular tuple 657 >>> x, y 658 (11, 22) 659 >>> p.x + p.y # fields also accessible by name 660 33 661 >>> p # readable __repr__ with a name=value style 662 Point(x=11, y=22) 663 664 Named tuples are especially useful for assigning field names to result tuples returned 665 by the :mod:`csv` or :mod:`sqlite3` modules:: 666 667 EmployeeRecord = namedtuple('EmployeeRecord', 'name, age, title, department, paygrade') 668 669 import csv 670 for emp in map(EmployeeRecord._make, csv.reader(open("employees.csv", "rb"))): 671 print emp.name, emp.title 672 673 import sqlite3 674 conn = sqlite3.connect('/companydata') 675 cursor = conn.cursor() 676 cursor.execute('SELECT name, age, title, department, paygrade FROM employees') 677 for emp in map(EmployeeRecord._make, cursor.fetchall()): 678 print emp.name, emp.title 679 680 In addition to the methods inherited from tuples, named tuples support 681 three additional methods and one attribute. To prevent conflicts with 682 field names, the method and attribute names start with an underscore. 683 684 .. classmethod:: somenamedtuple._make(iterable) 685 686 Class method that makes a new instance from an existing sequence or iterable. 687 688 .. doctest:: 689 690 >>> t = [11, 22] 691 >>> Point._make(t) 692 Point(x=11, y=22) 693 694 .. method:: somenamedtuple._asdict() 695 696 Return a new :class:`OrderedDict` which maps field names to their corresponding 697 values:: 698 699 >>> p = Point(x=11, y=22) 700 >>> p._asdict() 701 OrderedDict([('x', 11), ('y', 22)]) 702 703 .. versionchanged:: 2.7 704 Returns an :class:`OrderedDict` instead of a regular :class:`dict`. 705 706 .. method:: somenamedtuple._replace(kwargs) 707 708 Return a new instance of the named tuple replacing specified fields with new 709 values:: 710 711 >>> p = Point(x=11, y=22) 712 >>> p._replace(x=33) 713 Point(x=33, y=22) 714 715 >>> for partnum, record in inventory.items(): 716 ... inventory[partnum] = record._replace(price=newprices[partnum], timestamp=time.now()) 717 718 .. attribute:: somenamedtuple._fields 719 720 Tuple of strings listing the field names. Useful for introspection 721 and for creating new named tuple types from existing named tuples. 722 723 .. doctest:: 724 725 >>> p._fields # view the field names 726 ('x', 'y') 727 728 >>> Color = namedtuple('Color', 'red green blue') 729 >>> Pixel = namedtuple('Pixel', Point._fields + Color._fields) 730 >>> Pixel(11, 22, 128, 255, 0) 731 Pixel(x=11, y=22, red=128, green=255, blue=0) 732 733 To retrieve a field whose name is stored in a string, use the :func:`getattr` 734 function: 735 736 >>> getattr(p, 'x') 737 11 738 739 To convert a dictionary to a named tuple, use the double-star-operator 740 (as described in :ref:`tut-unpacking-arguments`): 741 742 >>> d = {'x': 11, 'y': 22} 743 >>> Point(**d) 744 Point(x=11, y=22) 745 746 Since a named tuple is a regular Python class, it is easy to add or change 747 functionality with a subclass. Here is how to add a calculated field and 748 a fixed-width print format: 749 750 >>> class Point(namedtuple('Point', 'x y')): 751 ... __slots__ = () 752 ... @property 753 ... def hypot(self): 754 ... return (self.x ** 2 + self.y ** 2) ** 0.5 755 ... def __str__(self): 756 ... return 'Point: x=%6.3f y=%6.3f hypot=%6.3f' % (self.x, self.y, self.hypot) 757 ... 758 >>> for p in Point(3, 4), Point(14, 5/7.): 759 ... print p 760 Point: x= 3.000 y= 4.000 hypot= 5.000 761 Point: x=14.000 y= 0.714 hypot=14.018 762 763 The subclass shown above sets ``__slots__`` to an empty tuple. This helps 764 keep memory requirements low by preventing the creation of instance dictionaries. 765 766 Subclassing is not useful for adding new, stored fields. Instead, simply 767 create a new named tuple type from the :attr:`_fields` attribute: 768 769 >>> Point3D = namedtuple('Point3D', Point._fields + ('z',)) 770 771 Default values can be implemented by using :meth:`_replace` to 772 customize a prototype instance: 773 774 >>> Account = namedtuple('Account', 'owner balance transaction_count') 775 >>> default_account = Account('<owner name>', 0.0, 0) 776 >>> johns_account = default_account._replace(owner='John') 777 778 Enumerated constants can be implemented with named tuples, but it is simpler 779 and more efficient to use a simple class declaration: 780 781 >>> Status = namedtuple('Status', 'open pending closed')._make(range(3)) 782 >>> Status.open, Status.pending, Status.closed 783 (0, 1, 2) 784 >>> class Status: 785 ... open, pending, closed = range(3) 786 787 .. seealso:: 788 789 `Named tuple recipe <https://code.activestate.com/recipes/500261/>`_ 790 adapted for Python 2.4. 791 792 793 :class:`OrderedDict` objects 794 ---------------------------- 795 796 Ordered dictionaries are just like regular dictionaries but they remember the 797 order that items were inserted. When iterating over an ordered dictionary, 798 the items are returned in the order their keys were first added. 799 800 .. class:: OrderedDict([items]) 801 802 Return an instance of a dict subclass, supporting the usual :class:`dict` 803 methods. An *OrderedDict* is a dict that remembers the order that keys 804 were first inserted. If a new entry overwrites an existing entry, the 805 original insertion position is left unchanged. Deleting an entry and 806 reinserting it will move it to the end. 807 808 .. versionadded:: 2.7 809 810 .. method:: OrderedDict.popitem(last=True) 811 812 The :meth:`popitem` method for ordered dictionaries returns and removes 813 a (key, value) pair. The pairs are returned in LIFO order if *last* is 814 true or FIFO order if false. 815 816 In addition to the usual mapping methods, ordered dictionaries also support 817 reverse iteration using :func:`reversed`. 818 819 Equality tests between :class:`OrderedDict` objects are order-sensitive 820 and are implemented as ``list(od1.items())==list(od2.items())``. 821 Equality tests between :class:`OrderedDict` objects and other 822 :class:`Mapping` objects are order-insensitive like regular 823 dictionaries. This allows :class:`OrderedDict` objects to be substituted 824 anywhere a regular dictionary is used. 825 826 The :class:`OrderedDict` constructor and :meth:`update` method both accept 827 keyword arguments, but their order is lost because Python's function call 828 semantics pass-in keyword arguments using a regular unordered dictionary. 829 830 .. seealso:: 831 832 `Equivalent OrderedDict recipe <https://code.activestate.com/recipes/576693/>`_ 833 that runs on Python 2.4 or later. 834 835 :class:`OrderedDict` Examples and Recipes 836 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 837 838 Since an ordered dictionary remembers its insertion order, it can be used 839 in conjunction with sorting to make a sorted dictionary:: 840 841 >>> # regular unsorted dictionary 842 >>> d = {'banana': 3, 'apple': 4, 'pear': 1, 'orange': 2} 843 844 >>> # dictionary sorted by key 845 >>> OrderedDict(sorted(d.items(), key=lambda t: t[0])) 846 OrderedDict([('apple', 4), ('banana', 3), ('orange', 2), ('pear', 1)]) 847 848 >>> # dictionary sorted by value 849 >>> OrderedDict(sorted(d.items(), key=lambda t: t[1])) 850 OrderedDict([('pear', 1), ('orange', 2), ('banana', 3), ('apple', 4)]) 851 852 >>> # dictionary sorted by length of the key string 853 >>> OrderedDict(sorted(d.items(), key=lambda t: len(t[0]))) 854 OrderedDict([('pear', 1), ('apple', 4), ('orange', 2), ('banana', 3)]) 855 856 The new sorted dictionaries maintain their sort order when entries 857 are deleted. But when new keys are added, the keys are appended 858 to the end and the sort is not maintained. 859 860 It is also straight-forward to create an ordered dictionary variant 861 that remembers the order the keys were *last* inserted. 862 If a new entry overwrites an existing entry, the 863 original insertion position is changed and moved to the end:: 864 865 class LastUpdatedOrderedDict(OrderedDict): 866 'Store items in the order the keys were last added' 867 868 def __setitem__(self, key, value): 869 if key in self: 870 del self[key] 871 OrderedDict.__setitem__(self, key, value) 872 873 An ordered dictionary can be combined with the :class:`Counter` class 874 so that the counter remembers the order elements are first encountered:: 875 876 class OrderedCounter(Counter, OrderedDict): 877 'Counter that remembers the order elements are first encountered' 878 879 def __repr__(self): 880 return '%s(%r)' % (self.__class__.__name__, OrderedDict(self)) 881 882 def __reduce__(self): 883 return self.__class__, (OrderedDict(self),) 884 885 886 .. _collections-abstract-base-classes: 887 888 Collections Abstract Base Classes 889 --------------------------------- 890 891 The collections module offers the following :term:`ABCs <abstract base class>`: 892 893 ========================= ===================== ====================== ==================================================== 894 ABC Inherits from Abstract Methods Mixin Methods 895 ========================= ===================== ====================== ==================================================== 896 :class:`Container` ``__contains__`` 897 :class:`Hashable` ``__hash__`` 898 :class:`Iterable` ``__iter__`` 899 :class:`Iterator` :class:`Iterable` ``next`` ``__iter__`` 900 :class:`Sized` ``__len__`` 901 :class:`Callable` ``__call__`` 902 903 :class:`Sequence` :class:`Sized`, ``__getitem__``, ``__contains__``, ``__iter__``, ``__reversed__``, 904 :class:`Iterable`, ``__len__`` ``index``, and ``count`` 905 :class:`Container` 906 907 :class:`MutableSequence` :class:`Sequence` ``__getitem__``, Inherited :class:`Sequence` methods and 908 ``__setitem__``, ``append``, ``reverse``, ``extend``, ``pop``, 909 ``__delitem__``, ``remove``, and ``__iadd__`` 910 ``__len__``, 911 ``insert`` 912 913 :class:`Set` :class:`Sized`, ``__contains__``, ``__le__``, ``__lt__``, ``__eq__``, ``__ne__``, 914 :class:`Iterable`, ``__iter__``, ``__gt__``, ``__ge__``, ``__and__``, ``__or__``, 915 :class:`Container` ``__len__`` ``__sub__``, ``__xor__``, and ``isdisjoint`` 916 917 :class:`MutableSet` :class:`Set` ``__contains__``, Inherited :class:`Set` methods and 918 ``__iter__``, ``clear``, ``pop``, ``remove``, ``__ior__``, 919 ``__len__``, ``__iand__``, ``__ixor__``, and ``__isub__`` 920 ``add``, 921 ``discard`` 922 923 :class:`Mapping` :class:`Sized`, ``__getitem__``, ``__contains__``, ``keys``, ``items``, ``values``, 924 :class:`Iterable`, ``__iter__``, ``get``, ``__eq__``, and ``__ne__`` 925 :class:`Container` ``__len__`` 926 927 :class:`MutableMapping` :class:`Mapping` ``__getitem__``, Inherited :class:`Mapping` methods and 928 ``__setitem__``, ``pop``, ``popitem``, ``clear``, ``update``, 929 ``__delitem__``, and ``setdefault`` 930 ``__iter__``, 931 ``__len__`` 932 933 934 :class:`MappingView` :class:`Sized` ``__len__`` 935 :class:`ItemsView` :class:`MappingView`, ``__contains__``, 936 :class:`Set` ``__iter__`` 937 :class:`KeysView` :class:`MappingView`, ``__contains__``, 938 :class:`Set` ``__iter__`` 939 :class:`ValuesView` :class:`MappingView` ``__contains__``, ``__iter__`` 940 ========================= ===================== ====================== ==================================================== 941 942 943 .. class:: Container 944 Hashable 945 Sized 946 Callable 947 948 ABCs for classes that provide respectively the methods :meth:`__contains__`, 949 :meth:`__hash__`, :meth:`__len__`, and :meth:`__call__`. 950 951 .. class:: Iterable 952 953 ABC for classes that provide the :meth:`__iter__` method. 954 See also the definition of :term:`iterable`. 955 956 .. class:: Iterator 957 958 ABC for classes that provide the :meth:`~iterator.__iter__` and 959 :meth:`~iterator.next` methods. See also the definition of :term:`iterator`. 960 961 .. class:: Sequence 962 MutableSequence 963 964 ABCs for read-only and mutable :term:`sequences <sequence>`. 965 966 .. class:: Set 967 MutableSet 968 969 ABCs for read-only and mutable sets. 970 971 .. class:: Mapping 972 MutableMapping 973 974 ABCs for read-only and mutable :term:`mappings <mapping>`. 975 976 .. class:: MappingView 977 ItemsView 978 KeysView 979 ValuesView 980 981 ABCs for mapping, items, keys, and values :term:`views <dictionary view>`. 982 983 984 These ABCs allow us to ask classes or instances if they provide 985 particular functionality, for example:: 986 987 size = None 988 if isinstance(myvar, collections.Sized): 989 size = len(myvar) 990 991 Several of the ABCs are also useful as mixins that make it easier to develop 992 classes supporting container APIs. For example, to write a class supporting 993 the full :class:`Set` API, it only necessary to supply the three underlying 994 abstract methods: :meth:`__contains__`, :meth:`__iter__`, and :meth:`__len__`. 995 The ABC supplies the remaining methods such as :meth:`__and__` and 996 :meth:`isdisjoint` :: 997 998 class ListBasedSet(collections.Set): 999 ''' Alternate set implementation favoring space over speed 1000 and not requiring the set elements to be hashable. ''' 1001 def __init__(self, iterable): 1002 self.elements = lst = [] 1003 for value in iterable: 1004 if value not in lst: 1005 lst.append(value) 1006 1007 def __iter__(self): 1008 return iter(self.elements) 1009 1010 def __contains__(self, value): 1011 return value in self.elements 1012 1013 def __len__(self): 1014 return len(self.elements) 1015 1016 s1 = ListBasedSet('abcdef') 1017 s2 = ListBasedSet('defghi') 1018 overlap = s1 & s2 # The __and__() method is supported automatically 1019 1020 Notes on using :class:`Set` and :class:`MutableSet` as a mixin: 1021 1022 (1) 1023 Since some set operations create new sets, the default mixin methods need 1024 a way to create new instances from an iterable. The class constructor is 1025 assumed to have a signature in the form ``ClassName(iterable)``. 1026 That assumption is factored-out to an internal classmethod called 1027 :meth:`_from_iterable` which calls ``cls(iterable)`` to produce a new set. 1028 If the :class:`Set` mixin is being used in a class with a different 1029 constructor signature, you will need to override :meth:`_from_iterable` 1030 with a classmethod that can construct new instances from 1031 an iterable argument. 1032 1033 (2) 1034 To override the comparisons (presumably for speed, as the 1035 semantics are fixed), redefine :meth:`__le__` and :meth:`__ge__`, 1036 then the other operations will automatically follow suit. 1037 1038 (3) 1039 The :class:`Set` mixin provides a :meth:`_hash` method to compute a hash value 1040 for the set; however, :meth:`__hash__` is not defined because not all sets 1041 are hashable or immutable. To add set hashability using mixins, 1042 inherit from both :meth:`Set` and :meth:`Hashable`, then define 1043 ``__hash__ = Set._hash``. 1044 1045 .. seealso:: 1046 1047 * `OrderedSet recipe <https://code.activestate.com/recipes/576694/>`_ for an 1048 example built on :class:`MutableSet`. 1049 1050 * For more about ABCs, see the :mod:`abc` module and :pep:`3119`. 1051
