# 11 `collections` -- 高性能なコンテナ・データ型

バージョン 2.4 で 新たに追加 された仕様です。

このモジュールでは高性能なコンテナ・データ型を実装しています。 現在のところ、実装されている型は deque のみです。 将来的に B-tree と Fibonacci heap がふくまれるかもしれません。

`deque`( | [iterable])

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

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

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

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

`append`( | x)

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

`appendleft`( | x)

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

`clear`( | )

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

`extend`( | iterable)

  イテレータ化可能な引数 iterable から得られる要素を deque の右側に 追加し拡張します。

`extendleft`( | iterable)

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

`pop`( | )

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

`popleft`( | )

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

`rotate`( | n)

  Deque の要素を全体で nステップだけ右にローテートします。 n が負の値の場合は、左にローテートします。Deque を ひとつ右にローテートすることは "`d.appendleft(d.pop())`" と同じです。

上記の操作のほかにも、deque は次のような操作をサポートしています: イテレータ化、pickle、"`len(d)`"、"`reversed(d)`"、 "`copy.copy(d)`"、 "`copy.deepcopy(d)`"、 `in` 演算子による 包含検査、そして "`d[-1]`" などの添え字による参照。

例:

    >>> from collections import deque
    >>> d = deque('ghi')                 # 3つの要素からなる新しい deque をつくる。
    >>> for elem in d:                   # deque の要素をひとつずつたどる。
    ...     print elem.upper()
    G
    H
    I

    >>> d.append('j')                    # 新しい要素を右側につけたす。
    >>> d.appendleft('f')                # 新しい要素を左側につけたす。
    >>> d                                # deque の表現形式。
    deque(['f', 'g', 'h', 'i', 'j'])

    >>> d.pop()                          # いちばん右側の要素を削除し返す。
    'j'
    >>> d.popleft()                      # いちばん左側の要素を削除し返す。
    'f'
    >>> list(d)                          # deque の内容をリストにする。
    ['g', 'h', 'i']
    >>> d[0]                             # いちばん左側の要素をのぞく。
    'g'
    >>> d[-1]                            # いちばん右側の要素をのぞく。
    'i'

    >>> list(reversed(d))                # deque の内容を逆順でリストにする。
    ['i', 'h', 'g']
    >>> 'h' in d                         # deque を検索。
    True
    >>> d.extend('jkl')                  # 複数の要素を一度に追加する。
    >>> d
    deque(['g', 'h', 'i', 'j', 'k', 'l'])
    >>> d.rotate(1)                      # 右ローテート
    >>> d
    deque(['l', 'g', 'h', 'i', 'j', 'k'])
    >>> d.rotate(-1)                     # 左ローテート
    >>> d
    deque(['g', 'h', 'i', 'j', 'k', 'l'])

    >>> deque(reversed(d))               # 新しい deque を逆順でつくる。
    deque(['l', 'k', 'j', 'i', 'h', 'g'])
    >>> d.clear()                        # deque を空にする。
    >>> d.pop()                          # 空の deque からは pop できない。
    Traceback (most recent call last):
      File "<pyshell#6>", line 1, in -toplevel-
        d.pop()
    IndexError: pop from an empty deque

    >>> d.extendleft('abc')              # extendleft() は入力を逆順にする。
    >>> d
    deque(['c', 'b', 'a'])