"collections" --- 容器資料型態
******************************

**原始碼：**Lib/collections/__init__.py

======================================================================

這個模組實作了一些特別的容器資料型態，用來替代 Python 一般內建的容器，
例如 "dict"（字典）、"list"（串列）、"set"（集合）和 "tuple"（元組）。

+-----------------------+----------------------------------------------------------------------+
| "namedtuple()"        | 用來建立具名欄位的 tuple 子類別的工廠函式                            |
+-----------------------+----------------------------------------------------------------------+
| "deque"               | 一個類似 list 的容器，可以快速的在頭尾加入 (append) 元素與移除 (pop) |
|                       | 元素                                                                 |
+-----------------------+----------------------------------------------------------------------+
| "ChainMap"            | 一個類似 dict 的類別，用來為多個對映 (mapping) 建立單一的視圖 (view) |
+-----------------------+----------------------------------------------------------------------+
| "Counter"             | dict 的子類別，用來計算*可雜湊*物件的數量                            |
+-----------------------+----------------------------------------------------------------------+
| "OrderedDict"         | dict 的子類別，會記錄物件被加入的順序                                |
+-----------------------+----------------------------------------------------------------------+
| "defaultdict"         | dict 的子類別，當值不存在 dict 中時會呼叫一個提供預設值的工廠函式    |
+-----------------------+----------------------------------------------------------------------+
| "UserDict"            | dict 物件的包裝器 (wrapper)，簡化了 dict 的子類別化過程              |
+-----------------------+----------------------------------------------------------------------+
| "UserList"            | list 物件的包裝器，簡化了 list 的子類別化過程                        |
+-----------------------+----------------------------------------------------------------------+
| "UserString"          | 字串物件的包裝器，簡化了字串的子類別化過程                           |
+-----------------------+----------------------------------------------------------------------+


"ChainMap" 物件
===============

在 3.3 版新加入.

"ChainMap"（對映鏈結）類別的目的是快速將數個對映連結在一起，讓它們可以
被當作一個單元來處理。它通常會比建立一個新的字典並多次呼叫 "update()"
來得更快。

這個類別可用於模擬巢狀作用域 (nested scopes)，且在模板化 (templating)
時能派上用場。

class collections.ChainMap(*maps)

   一個 "ChainMap" 將多個 dict 或其他對映組合在一起，建立一個獨立、可
   更新的視圖。如果沒有指定 *maps*，預設會提供一個空字典讓每個新鏈結都
   至少有一個對映。

   底層的對映儲存於一個 list 中，這個 list 是公開的且可透過 *maps* 屬
   性存取或更新，沒有其他狀態 (state)。

   檢索 (lookup) 陸續查詢底層對映，直到鍵被找到，然而讀取、更新和刪除
   就只會對第一個對映操作。

   "ChainMap" 透過參照將底層對映合併，所以當一個底層對映被更新，這些改
   變也會反映到 "ChainMap"。

   所有常見的字典方法都有支援。此外，還有一個 *maps* 屬性 (attribute)
   、一個建立子上下文 (subcontext) 的方法、和一個能夠存取除了第一個以
   外其他所有對映的特性 (property)：

   maps

      一個可被更新的對映列表，這個列表是按照被搜索的順序來排列，在
      ChainMap 中它是唯一被儲存的狀態，可被修改來變換搜索順序。回傳的
      列表都至少包含一個對映。

   new_child(m=None, **kwargs)

      回傳包含一個新對映的 "ChainMap"， 新對映後面接著當前實例的所有現
      存對映。如果有給定 "m"，"m" 會成為那個最前面的新對映；若沒有指定
      ，則會加上一個空 dict，如此一來呼叫 "d.new_child()" 就等同於
      "ChainMap({}, *d.maps)"。這個方法用於建立子上下文，而保持父對映
      的不變。

      在 3.4 版的變更: 加入可選參數 "m"。

      在 3.10 版的變更: 增加了對關鍵字引數的支援。

   parents

      回傳一個包含除了第一個以外所有其他對映的新 "ChainMap" 的特性，可
      用於需要跳過第一個對映的搜索。使用情境類似於在*巢狀作用域*當中使
      用 "nonlocal" 關鍵字，也可與內建函式 "super()" 做類比。引用
      "d.parents" 等同於 "ChainMap(*d.maps[1:])"。

   注意，一個 "ChainMap()" 的疊代順序是透過由後往前掃描對映而定：

      >>> baseline = {'music': 'bach', 'art': 'rembrandt'}
      >>> adjustments = {'art': 'van gogh', 'opera': 'carmen'}
      >>> list(ChainMap(adjustments, baseline))
      ['music', 'art', 'opera']

   這和呼叫 "dict.update()" 結果的順序一樣是從最後一個對映開始：

      >>> combined = baseline.copy()
      >>> combined.update(adjustments)
      >>> list(combined)
      ['music', 'art', 'opera']

   在 3.9 版的變更: 支援 "|" 和 "|=" 運算子，詳見 **PEP 584**。

也參考:

  * Enthought CodeTools package 中的 MultiContext class 支援在鏈中選定
    任意對映寫入。

  * Django 中用於模板的 Context class  是唯讀的對映鏈，也具有加入
    (push) 和移除 (pop) 上下文的功能，與 "new_child()" 方法和
    "parents" 特性類似。

  * Nested Contexts recipe 提供了控制是否只對鏈中第一個或其他對映做寫
    入或其他操作的選項。

  * 一個極度簡化、維讀版本的 Chainmap。


"ChainMap" 範例和用法
---------------------

此章節提供了多種操作 ChainMap 的案例。

模擬 Python 內部檢索鏈結的例子：

   import builtins
   pylookup = ChainMap(locals(), globals(), vars(builtins))

讓使用者指定的命令列引數優先於環境變數、再優先於預設值的範例：

   import os, argparse

   defaults = {'color': 'red', 'user': 'guest'}

   parser = argparse.ArgumentParser()
   parser.add_argument('-u', '--user')
   parser.add_argument('-c', '--color')
   namespace = parser.parse_args()
   command_line_args = {k: v for k, v in vars(namespace).items() if v is not None}

   combined = ChainMap(command_line_args, os.environ, defaults)
   print(combined['color'])
   print(combined['user'])

用 "ChainMap" 類別模擬巢狀上下文的範例模式：

   c = ChainMap()        # Create root context
   d = c.new_child()     # Create nested child context
   e = c.new_child()     # Child of c, independent from d
   e.maps[0]             # Current context dictionary -- like Python's locals()
   e.maps[-1]            # Root context -- like Python's globals()
   e.parents             # Enclosing context chain -- like Python's nonlocals

   d['x'] = 1            # Set value in current context
   d['x']                # Get first key in the chain of contexts
   del d['x']            # Delete from current context
   list(d)               # All nested values
   k in d                # Check all nested values
   len(d)                # Number of nested values
   d.items()             # All nested items
   dict(d)               # Flatten into a regular dictionary

"ChainMap" 類別只對鏈結中第一個對映來做寫入或刪除，但檢索則會掃過整個
鏈結。但如果需要對更深層的鍵寫入或刪除，透過定義一個子類別來實作也不困
難：

   class DeepChainMap(ChainMap):
       'Variant of ChainMap that allows direct updates to inner scopes'

       def __setitem__(self, key, value):
           for mapping in self.maps:
               if key in mapping:
                   mapping[key] = value
                   return
           self.maps[0][key] = value

       def __delitem__(self, key):
           for mapping in self.maps:
               if key in mapping:
                   del mapping[key]
                   return
           raise KeyError(key)

   >>> d = DeepChainMap({'zebra': 'black'}, {'elephant': 'blue'}, {'lion': 'yellow'})
   >>> d['lion'] = 'orange'         # update an existing key two levels down
   >>> d['snake'] = 'red'           # new keys get added to the topmost dict
   >>> del d['elephant']            # remove an existing key one level down
   >>> d                            # display result
   DeepChainMap({'zebra': 'black', 'snake': 'red'}, {}, {'lion': 'orange'})


"Counter" 物件
==============

提供一個支援方便且快速計數的計數器工具，例如：

   >>> # Tally occurrences of words in a list
   >>> cnt = Counter()
   >>> for word in ['red', 'blue', 'red', 'green', 'blue', 'blue']:
   ...     cnt[word] += 1
   >>> cnt
   Counter({'blue': 3, 'red': 2, 'green': 1})

   >>> # Find the ten most common words in Hamlet
   >>> import re
   >>> words = re.findall(r'\w+', open('hamlet.txt').read().lower())
   >>> Counter(words).most_common(10)
   [('the', 1143), ('and', 966), ('to', 762), ('of', 669), ('i', 631),
    ('you', 554),  ('a', 546), ('my', 514), ('hamlet', 471), ('in', 451)]

class collections.Counter([iterable-or-mapping])

   "Counter" 是 "dict" 的子類別，用來計算*可雜湊*物件的數量。它是將物
   件與其計數作為字典的鍵值對儲存的集合容器。計數可以是包含 0 與負數的
   任何整數值。"Counter" 類別類似其他程式語言中的 bags 或 multisets。

   被計數的元素來自一個 *iterable* 或是被其他的 *mapping*（或 Counter
   ）初始化：

   >>> c = Counter()                           # a new, empty counter
   >>> c = Counter('gallahad')                 # a new counter from an iterable
   >>> c = Counter({'red': 4, 'blue': 2})      # a new counter from a mapping
   >>> c = Counter(cats=4, dogs=8)             # a new counter from keyword args

   Counter 物件擁有一個字典的使用介面，除了遇到 Counter 中沒有的值時會
   回傳計數 0 取代 "KeyError" 這點不同：

   >>> c = Counter(['eggs', 'ham'])
   >>> c['bacon']                              # count of a missing element is zero
   0

   將一個值的計數設為 0 並不會真的從 Counter 中刪除這個元素，要使用
   "del" 來將其刪除：

   >>> c['sausage'] = 0                        # counter entry with a zero count
   >>> del c['sausage']                        # del actually removes the entry

   在 3.1 版新加入.

   在 3.7 版的變更: 作為 "dict" 的子類別，"Counter" 繼承了記憶插入順序
   的功能。對 *Counter* 做數學運算後同樣保留順序性，其結果是依照各個元
   素在運算元左邊出現的時間先後、再按照運算元右邊出現的時間先後來排列
   。

   除了字典原本就有的方法外，Counter 物件額外支援數個新方法：

   elements()

      回傳每個元素都重複出現計算次數的 iterator（疊代器）物件，其中元
      素的回傳順序是依照各元素首次出現的時間先後。如果元素的出現次數小
      於 1，"elements()" 方法會忽略這些元素。

      >>> c = Counter(a=4, b=2, c=0, d=-2)
      >>> sorted(c.elements())
      ['a', 'a', 'a', 'a', 'b', 'b']

   most_common([n])

      回傳一個 list，包含出現最多次的 *n* 個元素及其出現次數，並按照出
      現次數排序。如果 *n* 被省略或者為 "None"，"most_common()" 會回傳
      *所有* counter 中的元素。出現次數相同的元素會按照首次出現的時間
      先後來排列：

      >>> Counter('abracadabra').most_common(3)
      [('a', 5), ('b', 2), ('r', 2)]

   subtract([iterable-or-mapping])

      減去自一個 *iterable* 或另一個*對映*（或 Counter）中的計數元素，
      行為類似 "dict.update()" 但是是為了減去計數而非取代其值。輸入和
      輸出都可以是 0 或是負數。

      >>> c = Counter(a=4, b=2, c=0, d=-2)
      >>> d = Counter(a=1, b=2, c=3, d=4)
      >>> c.subtract(d)
      >>> c
      Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})

      在 3.2 版新加入.

   total()

      計算總計數值。

      >>> c = Counter(a=10, b=5, c=0)
      >>> c.total()
      15

      在 3.10 版新加入.

   通常來說字典方法也可以用於 "Counter" 物件，除了以下兩個作用方式與計
   數器不同。

   fromkeys(iterable)

      此類別方法沒有被實作於 "Counter" 物件中。

   update([iterable-or-mapping])

      加上自一個 *iterable* 計算出的計數或加上另一個 *mapping*（或
      Counter）中的計數，行為類似 "dict.update()" 但是是為了加上計數而
      非取代其值。另外，*iterable* 需要是一串將被計算個數元素的序列，
      而非元素為 "(key, value)" 形式的序列。

Counter 支援相等性、子集和超集關係的 rich comparison 運算子："=="、
"!="、"<"、"<="、">"、">="。這些檢測會將不存在的元素之計數值當作零，因
此 "Counter(a=1) == Counter(a=1, b=0)" 將回傳真值。

在 3.10 版的變更: 增加了 rich comparison 運算。

在 3.10 版的變更: 在相等性運算中，不存在的元素之計數值會被當作零。在此
之前，"Counter(a=3)" 和 "Counter(a=3, b=0)" 被視為不同。

使用 "Counter" 物件的常見使用模式：

   c.total()                       # total of all counts
   c.clear()                       # reset all counts
   list(c)                         # list unique elements
   set(c)                          # convert to a set
   dict(c)                         # convert to a regular dictionary
   c.items()                       # convert to a list of (elem, cnt) pairs
   Counter(dict(list_of_pairs))    # convert from a list of (elem, cnt) pairs
   c.most_common()[:-n-1:-1]       # n least common elements
   +c                              # remove zero and negative counts

為結合多個 "Counter" 物件以產生 multiset（多重集合，擁有大於 0 計數元
素的計數器），有提供了幾種數學操作。加法和減法是根據各個對應元素分別將
Counter 加上和減去計數，交集和聯集分別回傳各個元素最小和最大計數，相等
性與包含性運算則會比較對應的計數。每一個操作都可以接受輸入帶有正負號的
計數，但輸出的 Counter 則會將擁有小於或等於 0 計數的元素剔除。

   >>> c = Counter(a=3, b=1)
   >>> d = Counter(a=1, b=2)
   >>> c + d                       # add two counters together:  c[x] + d[x]
   Counter({'a': 4, 'b': 3})
   >>> c - d                       # subtract (keeping only positive counts)
   Counter({'a': 2})
   >>> c & d                       # intersection:  min(c[x], d[x])
   Counter({'a': 1, 'b': 1})
   >>> c | d                       # union:  max(c[x], d[x])
   Counter({'a': 3, 'b': 2})
   >>> c == d                      # equality:  c[x] == d[x]
   False
   >>> c <= d                      # inclusion:  c[x] <= d[x]
   False

加減法的一元運算子分別是加上空的 Counter 和從空 Counter 減去的簡寫。

>>> c = Counter(a=2, b=-4)
>>> +c
Counter({'a': 2})
>>> -c
Counter({'b': 4})

在 3.3 版新加入: 開始支援加減一元運算子和 multiset 的原地 (in-place)
操作。

備註:

  Counter 主要是被設計來操作正整數以當作使用中的計數，但為了某些會用到
  計數之值為負數或為其他型別的案例中，Counter 也小心地被設計成不會預先
  排除這些特殊元素。為了輔助使用於上述案例，這一小節記錄了最小範圍和型
  別限制。

  * "Counter" 類別本身是字典的子類別，且不限制其鍵與值。值被用來表示計
    數，但實際上你*可以*儲存任何值。

  * 使用 "most_common()" 方法的唯一條件是其值要是可被排序的。

  * 像是 "c[key] += 1" 的原地操作中，其值之型別只必須支援加減，所以分
    數、浮點數、十進位數與其負值都可以使用。同理，"update()" 和
    "subtract()" 也都允許 0 或負值為輸入或輸出。

  * Multiset 相關方法只為了處理正值而設計，其輸入允許是 0 或負值但只有
    正值會被輸出。並無型別限制，但其值的型別須支援加、減及比較運算。

  * "elements()" 方法需要其計數為正值，如為 0 或負值則忽略。

也參考:

  * Smalltalk 中的 Bag class。

  * 維基百科上的多重集合條目。

  * C++ multisets 教學與範例。

  * Multiset 的數學運算及其使用時機，參考 *Knuth, Donald. The Art of
    Computer Programming Volume II, Section 4.6.3, Exercise 19*。

  * 若要根據給定的元素集合來列舉出所有不重複且擁有指定元素數量的
    multiset，請見 "itertools.combinations_with_replacement()"：

       map(Counter, combinations_with_replacement('ABC', 2)) # --> AA AB AC BB BC CC


"deque" 物件
============

class collections.deque([iterable[, maxlen]])

   回傳一個新的 deque（雙端佇列）物件，將 *iterable* 中的資料由左至右
   （使用 "append()"）加入來做初始化。如果 *iterable* 並未給定，回傳的
   則是一個空的 deque。

   Deque 队列是对栈或 queue 队列的泛化（该名称的发音为 "deck"，是
   "double-ended queue" 的简写形式)。 Deque 支持线程安全，高度节省内存
   地从 deque 的任一端添加和弹出条目，在两个方向上的大致性能均为
   *O*(1)。

   虽然 "list" 对象也支持类似的操作，但它们是针对快速的固定长度的操作
   进行优化而 "pop(0)" 和 "insert(0, v)" 操作对下层数据表示的大小和位
   置改变都将产生 *O*(*n*) 的内存移动开销。

   如果 *maxlen* 沒有給定或者為 "None"，deque 可以增長到任意長度；但若
   有給定的話，deque 的最大長度就會被限制。一個被限制長度的 deque 一但
   滿了，若在一端加入數個新元素，則同時會在另一端移除相同數量的元素。
   限定長度的 deque 提供了和 Unix "tail" filter 類似的功能，可用於追蹤
   使用者在意的那些最新執行事項或數據源。

   Deque 物件支援以下方法：

   append(x)

      將 *x* 自 deque 的右側加入。

   appendleft(x)

      將 *x* 自 deque 的左側加入。

   clear()

      將所有元素從 deque 中移除，使其長度為 0。

   copy()

      建立一個 deque 的淺複製 (shallow copy)。

      在 3.5 版新加入.

   count(x)

      計算 deque 內元素為 *x* 的個數。

      在 3.2 版新加入.

   extend(iterable)

      將 iterable 引數加入 deque 的右側。

   extendleft(iterable)

      將 iterable 引數加入 deque 的左側。要注意的是，加入後的元素順序
      和 iterable 參數是相反的。

   index(x[, start[, stop]])

      回傳 deque 中 *x* 的位置（或在索引 *start* 之後、索引 *stop* 之
      前的位置）。回傳第一個匹配的位置，如果沒找到就引發 "ValueError"
      。

      在 3.5 版新加入.

   insert(i, x)

      在 deque 位置 *i* 中插入 *x*。

      如果此插入操作導致 deque 超過其長度上限 *maxlen* 的話，會引發
      "IndexError" 例外。

      在 3.5 版新加入.

   pop()

      移除並回傳 deque 的最右側元素，若本來就沒有任何元素，則會引發
      "IndexError"。

   popleft()

      移除並回傳 deque 的最左側元素，若本來就沒有任何元素，則會引發
      "IndexError"。

   remove(value)

      移除第一個出現的 *value*，如果沒找到的話就引發一個 "ValueError"
      。

   reverse()

      將 deque 中的元素原地 (in-place) 倒序排列並回傳 "None"。

      在 3.2 版新加入.

   rotate(n=1)

      將 deque 向右輪轉 *n* 步。若 *n* 為負值則向左輪轉。

      當 deque 不是空的，向右輪轉一步和 "d.appendleft(d.pop())" 有相同
      意義，而向左輪轉亦等價於 "d.append(d.popleft())"。

   Deque 物件也提供了一個唯讀屬性：

   maxlen

      Deque 的最大長度，如果不限制長度的話則為 "None"。

      在 3.1 版新加入.

在上述操作以外，deque 还支持迭代, 封存, "len(d)", "reversed(d)",
"copy.copy(d)", "copy.deepcopy(d)", 使用 "in" 运算符的成员检测以及下标
引用例如通过 "d[0]" 访问首个元素等。 索引访问在两端的时间复杂度均为
*O*(1) 但在中间则会低至 *O*(*n*)。 对于快速随机访问，请改用列表。

自從 3.5 版本起，deque 開始支援 "__add__()"、"__mul__()" 和
"__imul__()"。

範例：

   >>> from collections import deque
   >>> d = deque('ghi')                 # make a new deque with three items
   >>> for elem in d:                   # iterate over the deque's elements
   ...     print(elem.upper())
   G
   H
   I

   >>> d.append('j')                    # add a new entry to the right side
   >>> d.appendleft('f')                # add a new entry to the left side
   >>> d                                # show the representation of the deque
   deque(['f', 'g', 'h', 'i', 'j'])

   >>> d.pop()                          # return and remove the rightmost item
   'j'
   >>> d.popleft()                      # return and remove the leftmost item
   'f'
   >>> list(d)                          # list the contents of the deque
   ['g', 'h', 'i']
   >>> d[0]                             # peek at leftmost item
   'g'
   >>> d[-1]                            # peek at rightmost item
   'i'

   >>> list(reversed(d))                # list the contents of a deque in reverse
   ['i', 'h', 'g']
   >>> 'h' in d                         # search the deque
   True
   >>> d.extend('jkl')                  # add multiple elements at once
   >>> d
   deque(['g', 'h', 'i', 'j', 'k', 'l'])
   >>> d.rotate(1)                      # right rotation
   >>> d
   deque(['l', 'g', 'h', 'i', 'j', 'k'])
   >>> d.rotate(-1)                     # left rotation
   >>> d
   deque(['g', 'h', 'i', 'j', 'k', 'l'])

   >>> deque(reversed(d))               # make a new deque in reverse order
   deque(['l', 'k', 'j', 'i', 'h', 'g'])
   >>> d.clear()                        # empty the deque
   >>> d.pop()                          # cannot pop from an empty deque
   Traceback (most recent call last):
       File "<pyshell#6>", line 1, in -toplevel-
           d.pop()
   IndexError: pop from an empty deque

   >>> d.extendleft('abc')              # extendleft() reverses the input order
   >>> d
   deque(['c', 'b', 'a'])


"deque" 用法
------------

這一章節提供了多種操作 deque 的案例。

被限制長度的 deque 功能類似 Unix 中的 "tail" filter：

   def tail(filename, n=10):
       'Return the last n lines of a file'
       with open(filename) as f:
           return deque(f, n)

另一用法是透過從右邊加入、從左邊移除來維護最近加入元素的 list：

   def moving_average(iterable, n=3):
       # moving_average([40, 30, 50, 46, 39, 44]) --> 40.0 42.0 45.0 43.0
       # https://en.wikipedia.org/wiki/Moving_average
       it = iter(iterable)
       d = deque(itertools.islice(it, n-1))
       d.appendleft(0)
       s = sum(d)
       for elem in it:
           s += elem - d.popleft()
           d.append(elem)
           yield s / n

一個輪詢調度器可以透過在 "deque" 中放入 iterator 來實現，值自當前
iterator 的位置 0 取出，如果 iterator 已經消耗完畢就用 "popleft()" 將
其從佇列中移除，否則利用 "rotate()" 來將其移至佇列尾端：

   def roundrobin(*iterables):
       "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
       iterators = deque(map(iter, iterables))
       while iterators:
           try:
               while True:
                   yield next(iterators[0])
                   iterators.rotate(-1)
           except StopIteration:
               # Remove an exhausted iterator.
               iterators.popleft()

"rotate()" 提供了可以用來實作 "deque" 切片和刪除的方法。舉例來說，用純
Python 實作 "del d[n]" 需要用 "rotate()" 來定位要被移除的元素：

   def delete_nth(d, n):
       d.rotate(-n)
       d.popleft()
       d.rotate(n)

要實現 "deque" 切片，可使用近似以下方法：使用 "rotate()" 來將目標元素
移動到 deque 最左側，用 "popleft()" 移除舊元素並用 "extend()" 加入新元
素，最後再反向 rotate。在這個方法上做小小的更動就能簡單地實現 Forth 風
格的 stack 操作，例如 "dup"、"drop"、"swap"、"over"、"pick"、"rot" 和
"roll"。


"defaultdict" 物件
==================

class collections.defaultdict(default_factory=None, /[, ...])

   回傳一個新的類似字典的物件。"defaultdict" 是內建類別 "dict" 的子類
   別。它覆蓋掉了一個方法並添加了一個可寫入的實例變數。其餘功能與
   "dict" 相同，此文件不再複述。

   第一個引數為 "default_factory" 屬性提供了初始值，他被預設為 "None"
   ，所有其他的引數（包括關鍵字引數）都會被傳遞給 "dict" 的建構函式
   (constructor)。

   "defaultdict" 物件支援以下 "dict" 所沒有的方法：

   __missing__(key)

      如果 "default_factory" 屬性為 "None"，呼叫此方法會引發一個附帶引
      數 *key* 的 "KeyError" 例外。

      如果 "default_factory" 不為 "None"，它會不帶引數地被呼叫來為給定
      的 *key* 提供一個預設值，這個值和 *key* 被作為鍵值對來插入到字典
      中，並且被此方法所回傳。

      如果呼叫 "default_factory" 時發生例外，則該例外將會保持不變地向
      外傳遞。

      当请求的键未找到时本方法会被 "dict" 类的 "__getitem__()" 方法调
      用；它返回或引发的任何对象都会被 "__getitem__()" 返回或引发。

      请注意除了 "__getitem__()" 之外 "__missing__()" *不会* 被调用进
      行任何操作。 这意味着 "get()" 会像普通字典一样返回 "None" 作为默
      认值而不是使用 "default_factory"。

   "defaultdict" 物件支援以下實例變數：

   default_factory

      此屬性為 "__missing__()" 方法所使用。如果有引數被傳入建構函式，
      則此屬性會被初始化成第一個引數，如未提供引數則被初始化為 "None"
      。

   在 3.9 版的變更: 新增合併 ("|") 和更新 ("|=") 運算子，請見 **PEP
   584**。


"defaultdict" 範例
------------------

使用 "list" 作為 "default_factory" 可以很輕鬆地將鍵值對序列轉換為包含
list 之字典：

>>> s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
>>> d = defaultdict(list)
>>> for k, v in s:
...     d[k].append(v)
...
>>> sorted(d.items())
[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

當每個鍵第一次被存取時，它還沒有存在於對映中，所以會自動呼叫
"default_factory" 方法來回傳一個空的 "list" 以建立一個條目，
"list.append()" 操作後續會再新增值到這個新的列表裡。當再次存取該鍵時，
就如普通字典般操作（回傳該鍵所對應到的 list），"list.append()" 也會新
增另一個值到 list 中。和使用與其等價的 "dict.setdefault()" 相比，這個
技巧更加快速和簡單：

>>> d = {}
>>> for k, v in s:
...     d.setdefault(k, []).append(v)
...
>>> sorted(d.items())
[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

設定 "default_factory" 為 "int" 使得 "defaultdict" 可被用於計數（類似
其他語言中的 bag 或 multiset）：

>>> s = 'mississippi'
>>> d = defaultdict(int)
>>> for k in s:
...     d[k] += 1
...
>>> sorted(d.items())
[('i', 4), ('m', 1), ('p', 2), ('s', 4)]

當一個字母首次被存取時，它並不存在於對映中，則 "default_factory" 函式
會呼叫 "int()" 來提供一個整數 0 作為預設值。後續的增加操作繼續對每個字
母做計數。

函式 "int()" 總是回傳 0，這是常數函式的特殊情況。一個更快、更有彈性的
方法是使用 lambda 函式來提供任何常數值（不用一定要是 0）：

>>> def constant_factory(value):
...     return lambda: value
>>> d = defaultdict(constant_factory('<missing>'))
>>> d.update(name='John', action='ran')
>>> '%(name)s %(action)s to %(object)s' % d
'John ran to <missing>'

將 "default_factory" 設為 "set" 使 "defaultdict" 可用於構建一個值為
set 的字典：

>>> s = [('red', 1), ('blue', 2), ('red', 3), ('blue', 4), ('red', 1), ('blue', 4)]
>>> d = defaultdict(set)
>>> for k, v in s:
...     d[k].add(v)
...
>>> sorted(d.items())
[('blue', {2, 4}), ('red', {1, 3})]


"namedtuple()" 擁有具名欄位之 tuple 的工廠函式
==============================================

Named tuple（具名元組）賦予 tuple 中各個位置意義，使程式碼更有可讀性與
自我文件性。它們可以用於任何普通 tuple 可使用的場合，賦予其透過名稱（
而非位置索引）來存取欄位的能力。

collections.namedtuple(typename, field_names, *, rename=False, defaults=None, module=None)

   回傳一個名為 *typename* 的新 tuple 子類別。這個新的子類別被用於建立
   類似 tuple 的物件，可以透過屬性名稱來存取欄位，它同時也是可索引
   (indexable) 和可疊代的 (iterable)。子類別實例同樣有文件字串
   (docstring)（有類別名 typename 和欄位名 field_names）和一個好用的
   "__repr__()" 方法，可將 tuple 內容以 "name=value" 格式列出。

   *field_names* 是一個像 "['x', 'y']" 一樣的字串序列。*field_names*
   也可以是一個用空白或逗號分隔各個欄位名稱的字串，比如 "'x y'" 或者
   "'x, y'"。

   除了底線開頭以外的其他任何有效 Python 識別字 (identifier) 都可以作
   為欄位名稱，有效識別字由字母、數字、底線所組成，但不能是數字或底線
   開頭，也不能是關鍵詞 "keyword"，例如 *class*、*for*、*return*、
   *global*、*pass* 或 *raise*。

   如果 *rename* 為真值，無效的欄位名稱會自動被位置名稱取代。比如
   "['abc', 'def', 'ghi', 'abc']" 會被轉換成 "['abc', '_1', 'ghi',
   '_3']"，移除了關鍵字 "def" 和重複欄位名 "abc"。

   *defaults* 可以為 "None" 或者是一個預設值的 *iterable*。因為有預設
   值的欄位必須出現在那些沒有預設值的欄位之後，*defaults* 是被應用在右
   側的引數。例如 fieldnames 為 "['x', 'y', 'z']" 且 defaults 為 "(1,
   2)"，那麼 "x" 就必須被給定一個引數，"y" 被預設為 "1"，"z" 則被預設
   為 "2"。

   如果 *module* 值有被定義，named tuple 的 "__module__" 屬性就被設定
   為該值。

   Named tuple 實例中沒有字典，所以它們更加輕量，且和一般 tuple 相比佔
   用更少記憶體。

   要支援 pickle，應將 named tuple 類別賦值給一個符合 *typename* 的變
   數。

   在 3.1 版的變更: 新增對於 *rename* 的支援。

   在 3.6 版的變更: *verbose* 和 *rename* 參數成為僅限關鍵字引數。

   在 3.6 版的變更: 新增 *module* 參數。

   在 3.7 版的變更: 移除 *verbose* 參數和 "_source" 屬性。

   在 3.7 版的變更: 新增 *defaults* 參數和 "_field_defaults" 屬性。

   >>> # Basic example
   >>> Point = namedtuple('Point', ['x', 'y'])
   >>> p = Point(11, y=22)     # instantiate with positional or keyword arguments
   >>> p[0] + p[1]             # indexable like the plain tuple (11, 22)
   33
   >>> x, y = p                # unpack like a regular tuple
   >>> x, y
   (11, 22)
   >>> p.x + p.y               # fields also accessible by name
   33
   >>> p                       # readable __repr__ with a name=value style
   Point(x=11, y=22)

Named tuple 在賦予欄位名稱於 "csv" 或 "sqlite3" 模組回傳之 tuple 時相
當有用：

   EmployeeRecord = namedtuple('EmployeeRecord', 'name, age, title, department, paygrade')

   import csv
   for emp in map(EmployeeRecord._make, csv.reader(open("employees.csv", "rb"))):
       print(emp.name, emp.title)

   import sqlite3
   conn = sqlite3.connect('/companydata')
   cursor = conn.cursor()
   cursor.execute('SELECT name, age, title, department, paygrade FROM employees')
   for emp in map(EmployeeRecord._make, cursor.fetchall()):
       print(emp.name, emp.title)

除了繼承自 tuple 的方法，named tuple 還支援三個額外的方法和兩個屬性。
為了防止欄位名稱有衝突，方法和屬性的名稱以底線開頭。

classmethod somenamedtuple._make(iterable)

   從已存在的序列或可疊代物件建立一個新實例的類別方法。

      >>> t = [11, 22]
      >>> Point._make(t)
      Point(x=11, y=22)

somenamedtuple._asdict()

   回傳一個將欄位名稱對映至對應值的 "dict"：

      >>> p = Point(x=11, y=22)
      >>> p._asdict()
      {'x': 11, 'y': 22}

   在 3.1 版的變更: 回傳一個 "OrderedDict" 而非 "dict"。

   在 3.8 版的變更: 回傳一個常規 "dict" 而非 "OrderedDict"，自從
   Python 3.7 開始，dict 已經保證有順序性，如果需要 "OrderedDict" 所專
   屬的特性，推薦的解法是將結果專換成所需的類型：
   "OrderedDict(nt._asdict())"。

somenamedtuple._replace(**kwargs)

   回傳一個新的 named tuple 實例，並將指定欄位替換為新的值：

      >>> p = Point(x=11, y=22)
      >>> p._replace(x=33)
      Point(x=33, y=22)

      >>> for partnum, record in inventory.items():
      ...     inventory[partnum] = record._replace(price=newprices[partnum], timestamp=time.now())

somenamedtuple._fields

   列出 tuple 欄位名稱的字串，用於自我檢查或是從現有 named tuple 建立
   一個新的 named tuple 型別。

      >>> p._fields            # view the field names
      ('x', 'y')

      >>> Color = namedtuple('Color', 'red green blue')
      >>> Pixel = namedtuple('Pixel', Point._fields + Color._fields)
      >>> Pixel(11, 22, 128, 255, 0)
      Pixel(x=11, y=22, red=128, green=255, blue=0)

somenamedtuple._field_defaults

   將欄位名稱對映至預設值的字典。

      >>> Account = namedtuple('Account', ['type', 'balance'], defaults=[0])
      >>> Account._field_defaults
      {'balance': 0}
      >>> Account('premium')
      Account(type='premium', balance=0)

要取得這個名稱存於字串的欄位，要使用 "getattr()" 函式：

>>> getattr(p, 'x')
11

（如拆解引數列表（Unpacking Argument Lists）所述）將一個字典轉換成
named tuple，要使用 ** 雙星號運算子：

>>> d = {'x': 11, 'y': 22}
>>> Point(**d)
Point(x=11, y=22)

因為一個 named tuple 是一個常規的 Python 類別，我們可以很容易的透過子
類別來新增或更改功能，以下是如何新增一個計算得到的欄位和固定寬度的輸出
列印格式：

   >>> class Point(namedtuple('Point', ['x', 'y'])):
   ...     __slots__ = ()
   ...     @property
   ...     def hypot(self):
   ...         return (self.x ** 2 + self.y ** 2) ** 0.5
   ...     def __str__(self):
   ...         return 'Point: x=%6.3f  y=%6.3f  hypot=%6.3f' % (self.x, self.y, self.hypot)

   >>> for p in Point(3, 4), Point(14, 5/7):
   ...     print(p)
   Point: x= 3.000  y= 4.000  hypot= 5.000
   Point: x=14.000  y= 0.714  hypot=14.018

上面的子類別將 "__slots__" 設定為空 tuple，這樣一來就防止了字典實例被
建立，因而保持了較低的記憶體用量。

子類別化無法用於增加新的、已被儲存的欄位，應當透過 "_fields" 屬性以建
立一個新的 named tuple 來實現：

>>> Point3D = namedtuple('Point3D', Point._fields + ('z',))

透過直接賦值給 "__doc__"，可以自訂說明文件字串：

>>> Book = namedtuple('Book', ['id', 'title', 'authors'])
>>> Book.__doc__ += ': Hardcover book in active collection'
>>> Book.id.__doc__ = '13-digit ISBN'
>>> Book.title.__doc__ = 'Title of first printing'
>>> Book.authors.__doc__ = 'List of authors sorted by last name'

在 3.5 版的變更: 文件字串屬性變成可寫入。

也參考:

  * 關於為 named tuple 新增型別提示的方法，請參閱 "typing.NamedTuple"
    ，它運用 "class" 關鍵字以提供了一個簡潔的表示法：

       class Component(NamedTuple):
           part_number: int
           weight: float
           description: Optional[str] = None

  * 關於以 dict 而非 tuple 為底層的可變命名空間，請參考
    "types.SimpleNamespace()"。

  * "dataclasses" 模組提供了一個裝飾器和一些函式，用於自動將被生成的特
    殊方法新增到使用者定義的類別中。


"OrderedDict" 物件
==================

Ordered dictionary（有序字典）就像常規字典一樣，但有一些與排序操作相關
的額外功能，但由於內建的 "dict" 類別現在已經有記憶插入順序的能力（
Python 3.7 中確保了這種新行為），它們變得不那麼重要了。

仍存在一些與 "dict" 的不同之處：

* 常規的 "dict" 被設計成非常擅長於對映相關操作，追蹤插入的順序為次要目
  標。

* "OrderedDict" 則被設計成擅長於重新排序相關的操作，空間效率、疊代速度
  和更新操作的效能則為次要設計目標。

* "OrderedDict" 比起 "dict" 更適合處理頻繁的重新排序操作，如在下方用法
  中所示，這讓它適合用於多種 LRU cache 的實作中。

* "OrderedDict" 之相等性運算會檢查順序是否相同。

  一個一般的 "dict" 可以用 "p == q and all(k1 == k2 for k1, k2 in
  zip(p, q))" 來效仿有檢查順序的相等性運算。

* "OrderedDict" 類別的 "popitem()" 方法有不同的函式簽名 (signature)，
  它接受傳入一個選擇性引數來指定要移除哪個元素。

  一個一般的 "dict" 可以用 "d.popitem()" 來效仿 OrderedDict 的
  "od.popitem(last=True)"，這保證會移除最右邊（最後一個）的元素。

  一個一般的 "dict" 可以用 "(k := next(iter(d)), d.pop(k))" 來效仿
  OrderedDict 的 "od.popitem(last=False)"，若最左邊（第一個）的元素存
  在，則將其回傳並移除。

* "OrderedDict" 有個 "move_to_end()" 方法可有效率地將一個元素重新排列
  到任一端。

  一個一般的 "dict" 可以用 "d[k] = d.pop(k)" 來效仿 OrderedDict 的
  "od.move_to_end(k, last=True)"，這會將該鍵與其對應到的值移動至最右（
  最後面）的位置。

  一個一般的 "dict" 沒有和 OrderedDict 的 "od.move_to_end(k,
  last=False)" 等價的有效方式，這是將鍵與其對應到的值移動至最左（最前
  面）位置的方法。

* 在 Python 3.8 之前，"dict" 並沒有 "__reversed__()" 方法。

class collections.OrderedDict([items])

   回傳一個 "dict" 子類別的實例，它具有專門用於重新排列字典順序的方法
   。

   在 3.1 版新加入.

   popitem(last=True)

      Ordered dictionary 的 "popitem()" 方法移除並回傳一個鍵值 (key,
      value) 對。如果 *last* 為真值，則按 LIFO (last-in, first-out) 後
      進先出的順序回傳鍵值對，否則就按 FIFO (first-in, first-out) 先進
      先出的順序回傳鍵值對。

   move_to_end(key, last=True)

      將現有的 *key* 移動到 ordered dictionary 的任一端。如果 *last*
      為真值（此為預設值）則將元素移至右端；如果 *last* 為假值則將元素
      移至左端。如果 *key* 不存在則會引發 "KeyError"：

         >>> d = OrderedDict.fromkeys('abcde')
         >>> d.move_to_end('b')
         >>> ''.join(d)
         'acdeb'
         >>> d.move_to_end('b', last=False)
         >>> ''.join(d)
         'bacde'

      在 3.2 版新加入.

除了普通的對映方法，ordered dictionary 還支援了透過 "reversed()" 來做
倒序疊代。

"OrderedDict" 物件之間的相等性運算是會檢查順序是否相同的，是透過
"list(od1.items())==list(od2.items())" 來實現。"OrderedDict" 物件和其
他 "Mapping" 物件間的相等性運算則像普通字典一樣不考慮順序性，這使得
"OrderedDict" 可於任何字典可使用的時機中被替換掉。

在 3.5 版的變更: "OrderedDict" 的項 (item)、鍵與值之*視圖*現在可透過
"reversed()" 來倒序疊代。

在 3.6 版的變更: 隨著 **PEP 468** 被核可，被傳入給 "OrderedDict" 建構
函式與其 "update()" 方法的關鍵字引數之順序被保留了下來。

在 3.9 版的變更: 新增合併 ("|") 和更新 ("|=") 運算子，請見 **PEP 584**
。


"OrderedDict" 範例與用法
------------------------

建立一個能夠記住鍵*最後*插入順序的 ordered dictionary 變體很簡單。如果
新條目覆蓋了現有條目，則原本插入位置會被更改並移動至末端：

   class LastUpdatedOrderedDict(OrderedDict):
       'Store items in the order the keys were last added'

       def __setitem__(self, key, value):
           super().__setitem__(key, value)
           self.move_to_end(key)

"OrderedDict" 在實現一個 "functools.lru_cache()" 的變形版本時也非常有
用：

   from time import time

   class TimeBoundedLRU:
       "LRU Cache that invalidates and refreshes old entries."

       def __init__(self, func, maxsize=128, maxage=30):
           self.cache = OrderedDict()      # { args : (timestamp, result)}
           self.func = func
           self.maxsize = maxsize
           self.maxage = maxage

       def __call__(self, *args):
           if args in self.cache:
               self.cache.move_to_end(args)
               timestamp, result = self.cache[args]
               if time() - timestamp <= self.maxage:
                   return result
           result = self.func(*args)
           self.cache[args] = time(), result
           if len(self.cache) > self.maxsize:
               self.cache.popitem(0)
           return result

   class MultiHitLRUCache:
       """ LRU cache that defers caching a result until
           it has been requested multiple times.

           To avoid flushing the LRU cache with one-time requests,
           we don't cache until a request has been made more than once.

       """

       def __init__(self, func, maxsize=128, maxrequests=4096, cache_after=1):
           self.requests = OrderedDict()   # { uncached_key : request_count }
           self.cache = OrderedDict()      # { cached_key : function_result }
           self.func = func
           self.maxrequests = maxrequests  # max number of uncached requests
           self.maxsize = maxsize          # max number of stored return values
           self.cache_after = cache_after

       def __call__(self, *args):
           if args in self.cache:
               self.cache.move_to_end(args)
               return self.cache[args]
           result = self.func(*args)
           self.requests[args] = self.requests.get(args, 0) + 1
           if self.requests[args] <= self.cache_after:
               self.requests.move_to_end(args)
               if len(self.requests) > self.maxrequests:
                   self.requests.popitem(0)
           else:
               self.requests.pop(args, None)
               self.cache[args] = result
               if len(self.cache) > self.maxsize:
                   self.cache.popitem(0)
           return result


"UserDict" 物件
===============

"UserDict" 類別是作為 dict 物件的包裝器。因為已經可以直接自 "dict" 建
立子類別，這個類別的需求已部分被滿足，不過這個類別使用起來更方便，因為
被包裝的字典可以作為其屬性來存取。

class collections.UserDict([initialdata])

   模擬字典的類別。實例的內容被存於一個字典，可透過 "UserDict" 的
   "data" 屬性來做存取。如果有提供 *initialdata*，"data" 屬性會被初始
   化為其值；要注意指到 *initialdata* 的參照不會被保留，使其可被用於其
   他目的。

   除了支援作為對映所需的方法與操作，"UserDict" 實例提供了以下屬性：

   data

      一個真實的字典，用於儲存 "UserDict" 類別的資料內容。


"UserList" 物件
===============

此類別是 list 物件的包裝器。它是個方便的基礎類別，可繼承它並覆寫現有方
法或加入新方法來定義你所需的一個類似於 list 的類別。如此一來，我們可以
為 list 加入新的特性。

因為已經可以直接自 "list" 建立子類別，這個類別的需求已部分被滿足，不過
這個類別使用起來更方便，因為被包裝的 list 可以作為其屬性來存取。

class collections.UserList([list])

   模擬 list 的類別。實例的內容被存於一個 list，可透過 "UserList" 的
   "data" 屬性來做存取。實例內容被初始化為 *list* 的複製，預設為一個空
   的 list "[]"。*list* 可以是任何 iterable，例如一個真實的 Python
   list 或是一個 "UserList" 物件。

   除了支援可變序列的方法與操作，"UserList" 實例提供了以下屬性：

   data

      一個真實的 "list" 物件，用於儲存 "UserList" 類別的資料內容。

**子類別化的條件：**"UserList" 的子類別應該要提供一個不需要引數或一個
引數的建構函式。回傳一個新序列的 list 操作會從那些實作出來的類別建立一
個實例，為了達成上述目的，它假設建構函式可傳入單一參數來呼叫，該參數即
是做為數據來源的一個序列物件。

如果希望一個自此獲得的子類別不遵從上述要求，那所有該類別支援的特殊方法
則必須被覆寫；請參考原始碼來理解在這情況下哪些方法是必須提供的。


"UserString" 物件
=================

"UserString" 類別是字串物件的包裝器，因為已經可以從 "str" 直接建立子類
別，這個類別的需求已經部分被滿足，不過這個類別使用起來更方便，因為被包
裝的字串可以作為其屬性來存取。

class collections.UserString(seq)

   模擬字串物件的類別。實例的內容被存於一個字串物件，可透過
   "UserString" 的 "data" 屬性來做存取。實例內容被初始化為 *seq* 的複
   製，*seq* 引數可以是任何可被內建函式 "str()" 轉換成字串的物件。

   除了支援字串的方法和操作以外，"UserString" 實例也提供了以下屬性：

   data

      一個真實的 "str" 物件，用來儲存 "UserString" 類別的資料內容。

   在 3.5 版的變更: 新增方法 "__getnewargs__"、"__rmod__"、"casefold"
   、"format_map"、"isprintable" 以及 "maketrans"。
