# 5.12 `collections` -- High-performance container datatypes

New in version 2.4.

This module implements high-performance container datatypes. Currently, the only datatype is a deque. Future additions may include B-trees and Fibonacci heaps.

`deque`( | [iterable])

  Returns a new deque objected initialized left-to-right (using `append()`) with data from iterable. If iterable is not specified, the new deque is empty.

  Deques are a generalization of stacks and queues (the name is pronounced ``deck'' and is short for ``double-ended queue''). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same `O(1)` performance in either direction.

  Though `list` objects support similar operations, they are optimized for fast fixed-length operations and incur `O(n)` memory movement costs for "`pop(0)`" and "`insert(0, v)`" operations which change both the size and position of the underlying data representation. New in version 2.4.

Deque objects support the following methods:

`append`( | x)

  Add x to the right side of the deque.

`appendleft`( | x)

  Add x to the left side of the deque.

`clear`( | )

  Remove all elements from the deque leaving it with length 0.

`extend`( | iterable)

  Extend the right side of the deque by appending elements from the iterable argument.

`extendleft`( | iterable)

  Extend the left side of the deque by appending elements from iterable. Note, the series of left appends results in reversing the order of elements in the iterable argument.

`pop`( | )

  Remove and return an element from the right side of the deque. If no elements are present, raises a `IndexError`.

`popleft`( | )

  Remove and return an element from the left side of the deque. If no elements are present, raises a `IndexError`.

`rotate`( | n)

  Rotate the deque n steps to the right. If n is negative, rotate to the left. Rotating one step to the right is equivalent to: "`d.appendleft(d.pop())`".

In addition to the above, deques support iteration, pickling, "`len(d)`", "`reversed(d)`", "`copy.copy(d)`", "`copy.deepcopy(d)`", membership testing with the `in` operator, and subscript references such as "`d[-1]`".

Example:

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