> For the complete documentation index, see [llms.txt](https://lintcode-solutions.gitbook.io/project/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lintcode-solutions.gitbook.io/project/oj-review/oct-28-2018.md).

# Oct 28, 2018

## Python `collections`

### `defaultdict`

dict subclass that calls a factory function to supply missing values

Returns a new dictionary-like object. [`defaultdict`](https://docs.python.org/2/library/collections.html#collections.defaultdict) is a subclass of the built-in [`dict`](https://docs.python.org/2/library/stdtypes.html#dict) class. It overrides one method and adds one writable instance variable. The remaining functionality is the same as for the [`dict`](https://docs.python.org/2/library/stdtypes.html#dict) class and is not documented here.

### `OrderedDict`

dict subclass that remembers the order entries were added

Return an instance of a dict subclass, supporting the usual [`dict`](https://docs.python.org/2/library/stdtypes.html#dict) methods. An `OrderedDict` is a dict that remembers the order that keys were first inserted. If a new entry overwrites an existing entry, the original insertion position is left unchanged. Deleting an entry and reinserting it will move it to the end.

### `deque`

Returns a new `deque` object initialized left-to-right (using [`append()`](https://docs.python.org/2/library/collections.html#collections.deque.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.

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

`count`(*x*)

Count the number of deque elements equal to *x*.

`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 an [`IndexError`](https://docs.python.org/2/library/exceptions.html#exceptions.IndexError).

`popleft`()

Remove and return an element from the left side of the deque. If no elements are present, raises an [`IndexError`](https://docs.python.org/2/library/exceptions.html#exceptions.IndexError).

`remove`(*value*)

Remove the first occurrence of *value*. If not found, raises a [`ValueError`](https://docs.python.org/2/library/exceptions.html#exceptions.ValueError).

`reverse`()

Reverse the elements of the deque in-place and then return `None`.

`rotate`(*n=1*)

Rotate the deque *n* steps to the right. If *n* is negative, rotate to the left.

When the deque is not empty, rotating one step to the right is equivalent to `d.appendleft(d.pop())`, and rotating one step to the left is equivalent to `d.append(d.popleft())`.

Deque objects also provide one read-only attribute:`maxlen`

Maximum size of a deque or `None` if unbounded.

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