# `collections` --- コンテナデータ型

ソースコード: Lib/collections/__init__.py

このモジュールは、汎用の Python 組み込みコンテナ `dict`, `list`, `set`, および `tuple` に代わる、特殊なコンテナデータ型を実装しています。

`namedtuple()` | 名前付きフィールドを持つタプルのサブクラスを作成するファクトリ関数
`deque` | 両端における append や pop を高速に行えるリスト風のコンテナ
`ChainMap` | 複数のマッピングの一つのビューを作成する辞書風のクラス
`Counter` | ハッシュ可能 なオブジェクトを数え上げる辞書のサブクラス
`OrderedDict` | 項目が追加された順序を記憶する辞書のサブクラス
`defaultdict` | ファクトリ関数を呼び出して存在しない値を供給する辞書のサブクラス
`UserDict` | 辞書のサブクラス化を簡単にする辞書オブジェクトのラッパ
`UserList` | リストのサブクラス化を簡単にするリストオブジェクトのラッパ
`UserString` | 文字列のサブクラス化を簡単にする文字列オブジェクトのラッパ

## `ChainMap` オブジェクト

Added in version 3.3.

`ChainMap` クラスは、複数のマッピングを素早く連結し、一つの単位として扱うために提供されています。これはたいてい、新しい辞書を作成して `update()` を繰り返すよりも早いです。

このクラスはネストされたスコープをシミュレートするのに使え、テンプレート化に便利です。

class collections.ChainMap(*maps)

  `ChainMap` は、複数の辞書やその他のマッピングをまとめて、一つの、更新可能なビューを作成します。 maps が指定されないなら、一つの空辞書が与えられますから、新しいチェーンは必ず一つ以上のマッピングをもちます。

  根底のマッピングはリストに保存されます。このリストはパブリックで、 maps 属性を使ってアクセスや更新できます。それ以外に状態はありません。

  探索は、根底のマッピングをキーが見つかるまで引き続き探します。対して、書き込み、更新、削除は、最初のマッピングのみ操作します。

  `ChainMap` は、根底のマッピングを参照によって組み込みます。ですから、根底のマッピングの一つが更新されると、その変更は `ChainMap` に反映されます。

  通常の辞書のメソッドすべてがサポートされています。さらに、maps 属性、新しいサブコンテキストを作成するメソッド、最初のマッピング以外のすべてにアクセスするためのプロパティがあります:

  maps

    マッピングのユーザがアップデートできるリストです。このリストは最初に探されるものから最後に探されるものの順に並んでいます。これが唯一のソートされた状態であり、変更してマッピングが探される順番を変更できます。このリストは常に一つ以上のマッピングを含んでいなければなりません。

  new_child(m=None, **kwargs)

    新しいマッピングに現在のインスタンスが持つ全てのマッピングを追加したものを持つ新しい `ChainMap` インスタンスを返します。 `m` が指定された場合、新しいマッピングのリストの先頭部分になります; 指定されない場合は空の辞書が使われます。すなわち `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 パッケージ に含まれる MultiContext クラス は、チェーン内のすべてのマッピングへの書き込みをサポートするオプションを持ちます。

- Django のテンプレート用の Context class は、読み出し専用のマッピングのチェーンです。 `new_child()` メソッドや `parents` プロパティに似た push や pop の機能もあります。

- Nested Contexts recipe は、書き込み・その他の変更が最初のマッピングにのみ適用されるか、チェーンのすべてのマッピングに適用されるか、制御するオプションを持ちます。

- 非常に単純化した読み出し専用バージョンの 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` クラスは、他の言語のバッグや多重集合のようなものです。

  要素は、 iterable から数え上げられたり、他の mapping (やカウンタ) から初期化されます:

      >>> 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

  カウンタオブジェクトは辞書のインターフェースを持ちますが、存在しない要素に対して `KeyError` を送出する代わりに 0 を返すという違いがあります:

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

  カウントを 0 に設定しても、要素はカウンタから取り除かれません。完全に取り除くには、 `del` を使ってください:

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

  Added in version 3.1.

  バージョン 3.7 で変更: `Counter` は `dict` のサブクラスとして要素の挿入順を維持する機能を継承しました。 Counter オブジェクトに対する数学演算も順序を維持します。結果の順序はまず左の被演算子における要素の出現順に従い、その後右の被演算子において要素が出現する順序になります。

  カウンタオブジェクトは全ての辞書で利用できるメソッドに加えて、以下に示す追加のメソッドをサポートしています。

  elements()

    それぞれの要素を、そのカウント分の回数だけ繰り返すイテレータを返します。要素は挿入した順番で返されます。ある要素のカウントが 1 未満なら、 `elements()` はそれを無視します。

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

  most_common([n])

    最も多い n 要素を、カウントが多いものから少ないものまで順に並べたリストを返します。 n が省略されるか `None` であれば、 `most_common()` はカウンタの すべての 要素を返します。等しいカウントの要素は挿入順に並べられます:

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

  subtract([iterable-or-mapping])

    要素から iterable の要素または mapping の要素が引かれます。 `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})

    Added in version 3.2.

  total()

    カウントの合計を計算します。

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

    Added in version 3.10.

  普通の辞書のメソッドは、以下の 2 つのメソッドがカウンタに対して異なる振る舞いをするのを除き、 `Counter` オブジェクトにも利用できます。

  fromkeys(iterable)

    このクラスメソッドは `Counter` オブジェクトには実装されていません。

  update([iterable-or-mapping])

    要素が iterable からカウントされるか、別の mapping (やカウンタ) が追加されます。 `dict.update()` に似ていますが、カウントを置き換えるのではなく追加します。また、 iterable には `(key, value)` 対のシーケンスではなく、要素のシーケンスが求められます。

カウンタオブジェクトは等価、部分集合、上位集合のための次の拡張比較 (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()                       # access the (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` オブジェクトを組み合わせて多重集合 (0より大きいカウントを持つカウンタ) を作るためのいくつかの数学演算が提供されています。加算と減算はそれぞれの要素のカウンタを加算または減算することによりカウンタオブジェクトを組み合わせます。積集合と和集合は、それぞれのカウントの最大値と最小値を返します。等価と包含はそれぞれのカウントを比較します。それぞれの演算は符号付きカウントを持った入力を受け付けますが、カウントが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

単項加算および減算は、空カウンタの加算や空カウンタからの減算へのショートカットです。

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

Added in version 3.3: 単項加算、単項減算、in-place の多重集合操作のサポートが追加されました。

注釈

カウンタはもともと、推移するカウントを正の整数で表すために設計されました。しかし、他の型や負の値を必要とするユースケースを不必要に排除することがないように配慮されています。このようなユースケースの助けになるように、この節で最低限の範囲と型の制限について記述します。

- `Counter` クラス自体は辞書のサブクラスで、キーと値に制限はありません。値はカウントを表す数であることを意図していますが、値フィールドに任意のものを保存 できます 。

- `most_common()` メソッドが要求するのは、値が順序付け可能なことだけです。

- `c[key] += 1` のようなインプレース演算では、値の型に必要なのは 足し算と引き算ができることだけです。よって分数、浮動小数点数、 小数も使え、負の値がサポートされています。これと同じことが、 負や 0 の値を入力と出力に許す `update()` と `subtract()` メソッド にも言えます。

- 多重集合メソッドは正の値を扱うユースケースに対してのみ設計されています。入力は負や 0 に出来ますが、正の値の出力のみが生成されます。型の制限はありませんが、値の型は足し算、引き算、比較をサポートしている必要があります。

- `elements()` メソッドは整数のカウントを要求します。これは 0 と負のカウントを無視します。

参考

- Smalltalk の Bag class 。

- Wikipedia の Multisets の項目。

- C++ multisets の例を交えたチュートリアル。

- 数学的な多重集合の演算とそのユースケースは、 Knuth, Donald. The Art of Computer Programming Volume II, Section 4.6.3, Exercise 19 を参照してください。

- 与えられた要素の集まりからなる与えられた大きさの相違なる多重集合をすべて数え上げるには、 `itertools.combinations_with_replacement()` を参照してください:

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

## `deque` オブジェクト

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

  iterable で与えられるデータから、新しい deque オブジェクトを (`append()` をつかって) 左から右に初期化して返します。 iterable が指定されない場合、新しい deque オブジェクトは空になります。

  Deque とは、スタックとキューを一般化したものです (この名前は「デック」と発音され、これは「double-ended queue」の省略形です)。Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からもおよそ O(1) のパフォーマンスで実行できます。

  `list` オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、基礎のデータ表現形式のサイズと位置を両方変えるような `pop(0)` や `insert(0, v)` などの操作ではメモリ移動のために O(n) のコストを必要とします。

  maxlen が指定されなかったり `None` だった場合、 deque は任意のサイズまで大きくなります。 そうでない場合、 deque のサイズは指定された最大長に制限されます。 長さが制限された deque がいっぱいになると、新しい要素を追加するときに追加した要素数分だけ追加したのと反対側から要素が捨てられます。 長さが制限された deque は Unix における `tail` フィルタと似た機能を提供します。 トランザクションの tracking や最近使った要素だけを残したいデータプール (pool of data) などにも便利です。

  Deque オブジェクトは以下のようなメソッドをサポートしています:

  append(x)

    x を deque の右側につけ加えます。

  appendleft(x)

    x を deque の左側につけ加えます。

  clear()

    deque からすべての要素を削除し、長さを 0 にします。

  copy()

    deque の浅いコピーを作成します。

    Added in version 3.5.

  count(x)

    deque の x に等しい要素を数え上げます。

    Added in version 3.2.

  extend(iterable)

    イテラブルな引数 iterable から得られる要素を deque の右側に追加し拡張します。

  extendleft(iterable)

    イテラブルな引数 iterable から得られる要素を deque の左側に追加し拡張します。注意: 左から追加した結果は、イテラブルな引数の順序とは逆になります。

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

    deque 内の x の位置を返します (インデックス start からインデックス stop の両端を含む範囲で)。最初のマッチを返すか、見つからない場合には `ValueError` を発生させます。

    Added in version 3.5.

  insert(i, x)

    x を deque の位置 i に挿入します。

    挿入によって、長さに制限のある deque の長さが maxlen を超える場合、`IndexError` が発生します。

    Added in version 3.5.

  pop()

    deque の右側から要素をひとつ削除し、その要素を返します。要素がひとつも存在しない場合は `IndexError` を発生させます。

  popleft()

    deque の左側から要素をひとつ削除し、その要素を返します。要素がひとつも存在しない場合は `IndexError` を発生させます。

  remove(value)

    value の最初に現れるものを削除します。要素が見付からないない場合は `ValueError` を送出します。

  reverse()

    deque の要素をインプレースに反転し、`None` を返します。

    Added in version 3.2.

  rotate(n=1)

    deque の要素を全体で n ステップだけ右にローテートします。n が負の値の場合は、左にローテートします。

    deque が空でないときは、 deque をひとつ右にローテートすることは `d.appendleft(d.pop())` と同じで、 deque をひとつ左にローテートすることは `d.append(d.popleft())` と同じです。

  deque オブジェクトは読み出し専用属性も 1 つ提供しています:

  maxlen

    deque の最大長で、制限されていなければ `None` です。

    Added in version 3.1.

上記に加え、 deque はイテレーション, pickle 化, `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` フィルタに相当する機能を提供します:

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

deque を使用する別のアプローチは、右に要素を追加し左から要素を取り出すことで最近追加した要素のシーケンスを保持することです:

    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` に格納することで実装できます。 値は、位置0にある選択中のイテレータから取り出されます。 そのイテレータが値を出し切った場合は、 `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()` メソッドを頼りに、pop される要素の位置を割り出します:

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

`deque` のスライスの実装でも、同様のアプローチを使います。まず対象となる要素を `rotate()` によって deque の左端まで移動させてから、 `popleft()` で古い要素を削除します。そして、 `extend()` で新しい要素を追加したのち、循環を逆にします。このアプローチをやや変えたものとして、Forth スタイルのスタック操作、つまり `dup`, `drop`, `swap`, `over`, `pick`, `rot`, および `roll` を実装するのも簡単です。

## `defaultdict` オブジェクト

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

  新しい辞書に似たオブジェクトを返します。 `defaultdict` は組み込みの `dict` クラスのサブクラスです。これはメソッドをひとつオーバーライドし、書き込み可能なインスタンス変数をひとつ追加しています。それ以外の機能は `dict` クラスと同じですので、ここでは説明しません。

  1つ目の引数は `default_factory` 属性の初期値です。デフォルトは `None` です。残りの引数はキーワード引数も含め、 `dict` のコンストラクタに与えられた場合と同様に扱われます。

  `defaultdict` オブジェクトは標準の `dict` に加えて、以下のメソッドを実装しています:

  __missing__(key)

    もし `default_factory` 属性が `None` であれば、このメソッドは `KeyError` 例外を、 key を引数として発生させます。

    もし `default_factory` 属性が `None` でない場合、このメソッドは引数なしで呼び出され、与えらえた key に対応するデフォルト値を提供します。この値は、辞書内に key に対応して登録され、最後に返されます。

    もし `default_factory` の呼出が例外を発生させた場合には、変更せずそのまま例外を投げます。

    このメソッドは `dict` クラスの `__getitem__()` メソッドで、キーが存在しなかった場合によびだされます。値を返すか例外を発生させるのどちらにしても、 `__getitem__()` からもそのまま値が返るか例外が発生します。

    Note that `__missing__()` is not called for any operations besides `__getitem__()`. This means that `get()` will, like normal dictionaries, return `None` as a default rather than using `default_factory`.

  `defaultdict` オブジェクトは以下のインスタンス変数をサポートしています:

  default_factory

    この属性は `__missing__()` メソッドによって使われます。これは存在すればコンストラクタの第1引数によって初期化され、そうでなければ `None` になります。

  バージョン 3.9 で変更: PEP 584 で規定されている合成演算子 (`|`) と更新演算子 (`|=`)が追加されました。

### `defaultdict` の使用例

`list` を `default_factory` とすることで、キー=値ペアのシーケンスをリストの辞書へ簡単にグループ化できます。:

    >>> 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])]

When each key is encountered for the first time, it is not already in the mapping; so an entry is automatically created using the `default_factory` function which returns an empty `list`. The `list.append()` operation then attaches the value to the new list. When keys are encountered again, the look-up proceeds normally (returning the list for that key) and the `list.append()` operation adds another value to the list. This technique is simpler and faster than an equivalent technique using `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を生成します。インクリメント操作が各文字を数え上げます。

常に0を返す `int()` は特殊な関数でした。定数を生成するより速くて柔軟な方法は、 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` をセットの辞書を作るために利用することができます:

    >>> 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()` 名前付きフィールドを持つタプルのファクトリ関数

名前付きタプルは、タプルの中のすべての場所に意味を割り当てて、より読みやすく自己解説的なコードを書けるようにします。通常のタプルが利用される場所ならどこでも利用でき、場所に対するインデックスの代わりに名前を使ってフィールドにアクセスできるようになります。

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

  Returns a new tuple subclass named typename. The new subclass is used to create tuple-like objects that have fields accessible by attribute lookup as well as being indexable and iterable. Instances of the subclass also have a helpful docstring (with typename and field_names) and a helpful `__repr__()` method which lists the tuple contents in a `name=value` format.

  field_names は `['x', 'y']` のような文字列のシーケンスです。 field_names には、代わりに各属性名を空白文字 (whitespace) および/またはカンマ (,) で区切った文字列を渡すこともできます。例えば、 `'x y'` や `'x, y'` です。

  アンダースコア (_) で始まる名前を除いて、 Python の正しい識別子 (identifier) ならなんでも属性名として使うことができます。正しい識別子とはアルファベット(letters), 数字(digits), アンダースコア(_) を含みますが、数字やアンダースコアで始まる名前や、 class, for, return, global, pass, raise などといった `keyword` は使えません。

  rename が真の場合、不適切なフィールド名は自動的に位置を示す名前に置き換えられます。例えば `['abc', 'def', 'ghi', 'abc']` は、予約語の `def` と、重複しているフィールド名の `abc` が除去され、`['abc', '_1', 'ghi', '_3']` に変換されます。

  defaults には `None` あるいはデフォルト値の iterable が指定できます。 デフォルト値を持つフィールドはデフォルト値を持たないフィールドより後ろに来なければならないので、 defaults は最も右にある変数に適用されます。 例えば、 field_names が `['x', 'y', 'z']` で defaults が `(1, 2)` の場合、 `x` は必須の引数、 `y` は `1` がデフォルト、 `z` は `2` がデフォルトとなります。

  If module is defined, the `__module__` attribute of the named tuple is set to that value.

  名前付きタプルのインスタンスはインスタンスごとの辞書を持たないので、軽量で、普通のタプル以上のメモリを使用しません。

  pickle 化をサポートするには、名前付きタプルのクラス定義は typename と同じ名前の変数に割り当てなければなりません。

  バージョン 3.1 で変更: rename のサポートが追加されました。

  バージョン 3.6 で変更: verbose と rename 引数が キーワード専用引数 になりました.

  バージョン 3.6 で変更: module 引数が追加されました。

  バージョン 3.7 で変更: Removed the verbose parameter and the `_source` attribute.

  バージョン 3.7 で変更: Added the defaults parameter and the `_field_defaults` attribute.

    >>> # 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)

名前付きタプルは `csv` や `sqlite3` モジュールが返すタプルのフィールドに名前を付けるときにとても便利です:

    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)

タプルから継承したメソッドに加えて、名前付きタプルは3つの追加メソッドと2つの属性をサポートしています。フィールド名との衝突を避けるために、メソッド名と属性名はアンダースコアで始まります。

classmethod somenamedtuple._make(iterable)

  既存の sequence や 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 で変更: 通常の `dict` の代わりに `OrderedDict` を返すようになりました。

  バージョン 3.8 で変更: `collections.OrderedDict` ではなく `dict` を返すようになりました。Python 3.7以降は、通常の辞書で順番が保証されています。 `OrderedDict` 特有の機能を使いたい場合は、結果を `OrderedDict(nt._asdict())` 型にキャストして使用することを推奨します。

somenamedtuple._replace(**kwargs)

  指定されたフィールドを新しい値で置き換えた、新しい名前付きタプルを作って返します:

      >>> 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())

  名前付きタプルは汎用的な関数 `copy.replace()` にもサポートされています。

  バージョン 3.13 で変更: キーワード引数が無効な場合は `ValueError` のかわりに `TypeError` が発生します。

somenamedtuple._fields

  フィールド名をリストにしたタプルです。内省 (introspection) したり、既存の名前付きタプルをもとに新しい名前つきタプルを作成する時に便利です。

      >>> 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

辞書を名前付きタプルに変換するには、 `**` 演算子 (double-star-operator, 引数リストのアンパック で説明しています) を使います。:

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

名前付きタプルは通常の Python クラスなので、継承して機能を追加したり変更するのは容易です。次の例では計算済みフィールドと固定幅の print format を追加しています:

    >>> 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__` に空のタプルをセットしています。これにより、インスタンス辞書の作成を抑制してメモリ使用量を低く保つのに役立ちます。

サブクラス化は新しいフィールドを追加するのには適していません。代わりに、新しい名前付きタプルを `_fields` 属性を元に作成してください:

    >>> 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 で変更: 属性ドックストリングが書き込み可能になりました。

参考

- 名前付きタプルに型ヒントを追加する方法については、 `typing.NamedTuple` を参照してください。 `class` キーワードを使った洗練された記法も紹介されています:

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

- タプルではなく、辞書をもとにした変更可能な名前空間を作成するには `types.SimpleNamespace()` を参照してください。

- `dataclasses` モジュールは、生成される特殊メソッドをユーザー定義クラスに自動的に追加するためのデコレータや関数を提供しています。

## `OrderedDict` オブジェクト

順序付き辞書は普通の辞書のようですが、順序操作に関係する追加の機能があります。 組み込みの `dict` クラスが挿入順序を記憶しておく機能 (この新しい振る舞いは Python 3.7 で保証されるようになりました) を獲得した今となっては、順序付き辞書の重要性は薄れました。

いまだ残っている `dict` との差分:

- 通常の `dict` は対応付けに向いているように設計されました。 挿入順序の追跡は二の次です。

- `OrderedDict` は並べ替え操作に向いているように設計されました。 空間効率、反復処理の速度、更新操作のパフォーマンスは二の次です。

- `OrderedDict` のアルゴリズムは、頻繁な並べ替え処理を `dict` よりもうまく扱うことができます。後述のレシピに示されている通り、この性質はさまざまな種類の LRU キャッシュの実装に適しています。

- `OrderedDict` に対する等価演算は突き合わせ順序もチェックします。

  組み込みの `dict` では、順序を考慮した等価演算は `p == q and all(k1 == k2 for k1, k2 in zip(p, q))` で実現することができます。

- The `popitem()` method of `OrderedDict` has a different signature. It accepts an optional argument to specify which item is popped.

  組み込みの `dict` の場合、 OrderedDict の `od.popitem(last=True)` と同じ機能は、最も右側の (最後の) 要素を取り出すことが保証されている `d.popitem()` が果たします。

  組み込みの `dict` の場合、 OrderedDict の `od.popitem(last=False)` は `(k := next(iter(d)), d.pop(k))` で実現できます。これにより、該当する要素のうちで最も左側の (先頭の) ものを辞書から削除して返すことができます。

- `OrderedDict` has a `move_to_end()` method to efficiently reposition an element to an endpoint.

  組み込みの `dict` の場合、キーと値のペアを最も右側 (末尾) に移動する OrderedDict の `od.move_to_end(k, last=True)` は `d[k] = d.pop(k)` で実現できます。

  組み込みの `dict` では、キーと値のペアを最も左側 (先頭) に移動する OrderedDict の `od.move_to_end(k, last=False)` を実現する効率の良い方法はありません。

- Until Python 3.8, `dict` lacked a `__reversed__()` method.

class collections.OrderedDict([items])

  辞書の順序を並べ直すためのメソッドを持つ `dict` のサブクラスのインスタンスを返します。

  Added in version 3.1.

  popitem(last=True)

    順序付き辞書の `popitem()` メソッドは、(key, value) 対を返して消去します。この対は last が真なら LIFO で、偽なら FIFO で返されます。

  move_to_end(key, last=True)

    存在する key を順序付き辞書の先頭または末尾に移動します。要素は 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'

    Added in version 3.2.

通常のマッピングのメソッドに加え、順序付き辞書は `reversed()` による逆順の反復もサポートしています。

Equality tests between `OrderedDict` objects are order-sensitive and are roughly equivalent to `list(od1.items())==list(od2.items())`.

Equality tests between `OrderedDict` objects and other `Mapping` objects are order-insensitive like regular dictionaries. This allows `OrderedDict` objects to be substituted anywhere a regular dictionary is used.

バージョン 3.5 で変更: `OrderedDict` の項目、キー、値の ビュー が `reversed()` による逆順の反復をサポートするようになりました。

バージョン 3.6 で変更: With the acceptance of PEP 468, order is retained for keyword arguments passed to the `OrderedDict` constructor and its `update()` method.

バージョン 3.9 で変更: PEP 584 で規定されている合成演算子 (`|`) と更新演算子 (`|=`)が追加されました。

### `OrderedDict` の例とレシピ

キーが 最後に 追加されたときの順序を記憶する、順序付き辞書の変種を作るのは簡単です。 新しい値が既存の値を上書きする場合、元々の挿入位置が最後尾へ変更されます:

    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 collections import OrderedDict
    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(last=False)
            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(last=False)
            else:
                self.requests.pop(args, None)
                self.cache[args] = result
                if len(self.cache) > self.maxsize:
                    self.cache.popitem(last=False)
            return result

## `UserDict` オブジェクト

クラス `UserDict` は、辞書オブジェクトのラッパとしてはたらきます。このクラスの必要性は、 `dict` から直接的にサブクラス化できる能力に部分的に取って代わられました; しかし、根底の辞書に属性としてアクセスできるので、このクラスを使った方が簡単になることもあります。

class collections.UserDict([initialdata])

  辞書をシミュレートするクラスです。インスタンスの内容は通常の辞書に保存され、 `UserDict` インスタンスの `data` 属性を通してアクセスできます。 initialdata が与えられれば、 `data` はその内容で初期化されます。他の目的のために使えるように、 initialdata への参照が保存されないことに注意してください。

  マッピングのメソッドと演算をサポートするのに加え、 `UserDict` インスタンスは以下の属性を提供します:

  data

    `UserDict` クラスの内容を保存するために使われる実際の辞書です。

## `UserList` オブジェクト

このクラスはリストオブジェクトのラッパとしてはたらきます。これは独自のリスト風クラスの基底クラスとして便利で、既存のメソッドをオーバーライドしたり新しいメソッドを加えたりできます。こうして、リストに新しい振る舞いを加えられます。

このクラスの必要性は、 `list` から直接的にサブクラス化できる能力に部分的に取って代わられました; しかし、根底のリストに属性としてアクセスできるので、このクラスを使った方が簡単になることもあります。

class collections.UserList([list])

  リストをシミュレートするクラスです。インスタンスの内容は通常のリストに保存され、 `UserList` インスタンスの `data` 属性を通してアクセスできます。インスタンスの内容は最初に list のコピーに設定されますが、デフォルトでは空リスト `[]` です。 list は何らかのイテラブル、例えば通常の Python リストや `UserList` オブジェクト、です。

  ミュータブルシーケンスのメソッドと演算をサポートするのに加え、 `UserList` インスタンスは以下の属性を提供します:

  data

    `UserList` クラスの内容を保存するために使われる実際の `list` オブジェクトです。

サブクラス化の要件: `UserList` のサブクラスは引数なしか、あるいは一つの引数のどちらかとともに呼び出せるコンストラクタを提供することが期待されています。新しいシーケンスを返すリスト演算は現在の実装クラスのインスタンスを作成しようとします。そのために、データ元として使われるシーケンスオブジェクトである一つのパラメータとともにコンストラクタを呼び出せると想定しています。

派生クラスがこの要求に従いたくないならば、このクラスがサポートしているすべての特殊メソッドはオーバーライドされる必要があります。その場合に提供される必要のあるメソッドについての情報は、ソースを参考にしてください。

## `UserString` オブジェクト

クラス `UserString` は、文字列オブジェクトのラッパとしてはたらきます。このクラスの必要性は、 `str` から直接的にサブクラス化できる能力に部分的に取って代わられました; しかし、根底の文字列に属性としてアクセスできるので、このクラスを使った方が簡単になることもあります。

class collections.UserString(seq)

  文字列オブジェクトをシミュレートするクラスです。 インスタンスの内容は通常の文字列に保存され、 `UserString` インスタンスの `data` 属性を通してアクセスできます。 インスタンスの内容には最初に seq のコピーが設定されます。 seq 引数は、組み込みの `str()` 関数で文字列に変換できる任意のオブジェクトです。

  文字列のメソッドと演算をサポートするのに加え、 `UserString` インスタンスは次の属性を提供します:

  data

    `UserString` クラスの内容を保存するために使われる実際の `str` オブジェクトです。

  バージョン 3.5 で変更: 新たなメソッド `__getnewargs__`, `__rmod__`, `casefold`, `format_map`, `isprintable`, `maketrans`。