# SortedDict

SortedContainers is an Apache2 licensed Python sorted collections library, written in pure-Python, and fast as C-extensions. SortedDict API documentation is detailed below. The introduction is the best way to get started.

class `sortedcontainers.``SortedDict`(*args, **kwargs)

  A `SortedDict` provides the same methods as a `dict`. Additionally, a `SortedDict` efficiently maintains its keys in sorted order. Consequently, the keys method will return the keys in sorted order, the popitem method will remove the item with the highest key, etc.

  An optional key argument defines a callable that, like the key argument to Python’s sorted function, extracts a comparison key from each dict key. If no function is specified, the default compares the dict keys directly. The key argument must be provided as a positional argument and must come before all other arguments.

  An optional load argument defines the load factor of the internal list used to maintain sort order. If present, this argument must come before an iterable. The default load factor of ‘1000’ works well for lists from tens to tens of millions of elements. Good practice is to use a value that is the square or cube root of the list size. With billions of elements, the best load factor depends on your usage. It’s best to leave the load factor at the default until you start benchmarking. See implementation details for more information.

  An optional iterable provides an initial series of items to populate the `SortedDict`. Each item in the series must itself contain two items. The first is used as a key in the new dictionary, and the second as the key’s value. If a given key is seen more than once, the last value associated with it is retained in the new dictionary.

  If keyword arguments are given, the keywords themselves with their associated values are added as items to the dictionary. If a key is specified both in the positional argument and as a keyword argument, the value associated with the keyword is retained in the dictionary. For example, these all return a dictionary equal to `{"one": 2, "two": 3}`:

  - `SortedDict(one=2, two=3)`
  - `SortedDict({'one': 2, 'two': 3})`
  - `SortedDict(zip(('one', 'two'), (2, 3)))`
  - `SortedDict([['two', 3], ['one', 2]])`

  The first example only works for keys that are valid Python identifiers; the others work with any valid keys.

  `SortedDict` inherits from the built-in dict type.

  `x in d`

    Return True if and only if x is a key in the dictionary.

    Return type: | `bool`

  `del d[key]`

    Remove `d[key]` from d. Raises a `KeyError` if key is not in the dictionary.

  `d[key]`

    Return the item of d with key key. Raises a `KeyError` if key is not in the dictionary.

    Return type: | value

  `D == D2, D != D2`

    Test two dictionaries for equality (or inequality). Mappings compare equal if and only if they have the same length, if all of the keys of D may be found in D2, and all of the corresponding values compare equal.

    Return type: | `bool`

  `iter`(d)

    Return an iterator over the sorted keys of the dictionary.

    Iterating the Mapping while adding or deleting keys may raise a RuntimeError or fail to iterate over all entries.

    Return type: | iterator

  `reversed`(d)

    Return a reversed iterator over the sorted keys of the dictionary.

    Iterating the Mapping while adding or deleting keys may raise a RuntimeError or fail to iterate over all entries.

    Return type: | iterator

  `len`(d)

    Return the number of (key, value) pairs in the dictionary.

    Return type: | `int`

  `d[key] = value`

    Set d[key] to value.

  `d.``clear`()

    Remove all elements from the dictionary.

  `d.``copy`()

    Create a shallow copy of the dictionary.

    Return type: | `SortedDict`

  `d.``fromkeys`(seq, value=None)

    Create a new dictionary with keys from seq and values set to value.

    `fromkeys()` is a class method that returns a new dictionary. value defaults to `None`.

    Return type: | `SortedDict`

  `d.``get`(key, default=None)

    Return the value for key if key is in the dictionary, else default. If default is not given, it defaults to `None`, so that this method never raises a `KeyError`.

    Return type: | value

  `d.``items`()

    In Python 2, returns a list of the dictionary’s items (`(key, value)` pairs).

    In Python 3, returns a new `ItemsView` of the dictionary’s items. In addition to the methods provided by the built-in view, the `ItemsView` is indexable (e.g., `d.items()[5]`).

    Return type: | `list` or `ItemsView`

  `d.``keys`()

    In Python 2, return a `SortedSet` of the dictionary’s keys.

    In Python 3, return a new `KeysView` of the dictionary’s keys. In addition to the methods provided by the built-in view, the `KeysView` is indexable (e.g., `d.keys()[5]`).

    Return type: | `SortedSet` or `KeysView`

  `d.``pop`(key[, default])

    If key is in the dictionary, remove it and return its value, else return default. If default is not given and key is not in the dictionary, a `KeyError` is raised.

    Return type: | value

  `d.``popitem`(last=True)

    Remove and return a `(key, value)` pair from the dictionary. If `last=True` (default) then remove the greatest key from the dictionary. Else, remove the least key from the dictionary.

    If the dictionary is empty, calling `popitem()` raises a `KeyError`.

    Return type: | (key, value) tuple

  `d.``peekitem`(index=-1)

    Return `(key, value)` item pair at index.

    Unlike popitem, the sorted dictionary is not modified. Index defaults to -1, the last/greatest key in the dictionary. Specify `index=0` to lookup the first/least key in the dictionary.

    If index is out of range, raise `IndexError`.

    Return type: | (key, value) tuple

  `d.``setdefault`(key, default=None)

    If key is in the dictionary, return its value. If not, insert key with a value of default and return default. default defaults to `None`.

  `d.``update`(other, ...)

    Update the dictionary with the key/value pairs from other, overwriting existing keys.

    `update()` accepts either another dictionary object or an iterable of key/value pairs (as a tuple or other iterable of length two). If keyword arguments are specified, the dictionary is then updated with those key/value pairs: `d.update(red=1, blue=2)`.

  `d.``values`()

    In Python 2, return a list of the dictionary’s values.

    In Python 3, return a new `ValuesView` of the dictionary’s values. In addition to the methods provided by the built-in view, the `ValuesView` is indexable (e.g., `d.values()[5]`).

    Return type: | `list` or `ValuesView`

  `d.``clear`()

    Remove all the elements from the sorted dictionary.

  `d.``has_key`(key)

    Return True iff key is in the dictionary.

    Return type: | `bool`

  `d.``index`(key[, start[, stop]])

    Return the smallest k such that

    System Message: WARNING/2 (`d.iloc[k] == key`)

    latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.17 (TeX Live 2016/Debian) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2016/03/31> patch level 3 Babel <3.9r> and hyphenation patterns for 3 language(s) loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2014/09/29 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty ! LaTeX Error: File `utf8x.def’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: def) Enter file name: ! Emergency stop. <read *> l.158 \endinput ^^M No pages of output. Transcript written on math.log.
    and

    System Message: WARNING/2 (`i <= k < j`)

    latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.17 (TeX Live 2016/Debian) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2016/03/31> patch level 3 Babel <3.9r> and hyphenation patterns for 3 language(s) loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2014/09/29 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty ! LaTeX Error: File `utf8x.def’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: def) Enter file name: ! Emergency stop. <read *> l.158 \endinput ^^M No pages of output. Transcript written on math.log.
    . Raises `ValueError` if key is not present. stop defaults to the end of the set. start defaults to the beginning. Negative indexes are supported, as for slice indices.

    Return type: | `int`

  `d.``bisect_left`(key)

    Similar to the `bisect` module in the standard library, this returns an appropriate index to insert key in SortedDict. If key is already present in SortedDict, the insertion point will be before (to the left of) any existing entries.

    Return type: | `int`

  `d.``bisect`(key)

    Same as bisect_right.

    Return type: | `int`

  `d.``bisect_right`(key)

    Same as bisect_left, but if key is already present in SortedDict, the insertion index will be after (to the right of) any existing entries.

    Return type: | `int`

  `d.``bisect_key_left`(key)

    Similar to the `bisect` module in the standard library, this returns an appropriate index to insert a value with a given key. If values with key are already present, the insertion point will be before (to the left of) any existing entries. This method is present only if the sorted dict was constructed with a key function. In this context, key refers to the result of the key function applied to the dictionary key.

    Return type: | `int`

  `d.``bisect_key`(key)

    Same as bisect_key_right.

    Return type: | `int`

  `d.``bisect_key_right`(key)

    Same as bisect_key_left, but if key is already present, the insertion point will be after (to the right of) any existing entries.

    Return type: | `int`

  `d.iloc[pos]`

    Very efficiently return the key at index pos in iteration. Supports negative indices and slice notation. Raises `IndexError` on invalid pos.

    Return type: | key or `list`

  `del d.iloc[index]`

    Remove the `d[d.iloc[index]]` from d. Supports negative indices and slice notation. Raises `IndexError` on invalid index.

  `d.``islice`(start=None, stop=None, reverse=False)

    Returns an iterator that slices keys from start to stop index, inclusive and exclusive respectively.

    When reverse is True, values are yielded from the iterator in reverse order.

    Both start and stop default to None which is automatically inclusive of the beginning and end.

    Return type: | iterator

  `d.``irange`(minimum=None, maximum=None, inclusive=(True, True), reverse=False)

    Create an iterator of keys between minimum and maximum.

    inclusive is a pair of booleans that indicates whether the minimum and maximum ought to be included in the range, respectively. The default is (True, True) such that the range is inclusive of both minimum and maximum.

    Both minimum and maximum default to None which is automatically inclusive of the start and end of the list, respectively.

    When reverse is True the values are yielded from the iterator in reverse order; reverse defaults to False.

    When initialized with a key-function, an irange_key method is also provided with similar semantics.

    Return type: | iterator

class `sortedcontainers.``KeysView`

  A KeysView object is a dynamic view of the dictionary’s keys, which means that when the dictionary’s keys change, the view reflects those changes.

  `KeysView` implements the KeysView, Set, and Sequence Abstract Base Class types.

  `len`(keysview)

    Return the number of entries in the dictionary.

    Return type: | `int`

  `iter`(keysview)

    Return an iterator over the keys in the dictionary. Keys are iterated over in their sorted order.

    Iterating views while adding or deleting entries in the dictionary may raise a `RuntimeError` or fail to iterate over all entries.

    Return type: | iterator

  `reversed`(keysview)

    Return a reversed iterator over the keys in the dictionary.

    Iterating views while adding or deleting entries in the dictionary may raise a `RuntimeError` or fail to iterate over all entries.

    Return type: | iterator

  `x in keysview`

    Return `True` iff x is one of the underlying dictionary’s keys.

    Return type: | `bool`

  `keysview[i]`

    Return the key at position i.

    Return type: | value

  `keysview & other`

    Return the intersection of the keys and the other object as a new set.

    Return type: | `SortedSet`

  `keysview | other`

    Return the union of the keys and the other object as a new set.

    Return type: | `SortedSet`

  `keysview - other`

    Return the difference between the keys and the other object (all keys that aren’t in other) as a new set.

    Rtype: | `SortedSet`

  `keysview ^ other`

    Return the symmetric difference (all elements either in the keys or other, but not in both) of the keys and the other object as a new set.

    Rtype: | `SortedSet`

  `keysview.``count`(key)

    Return the number of occurrences of key in the set.

    Return type: | `int`

  `keysview.``index`(key[, start[, stop]])

    Return the smallest k such that

    System Message: WARNING/2 (`keysview[k] == x`)

    latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.17 (TeX Live 2016/Debian) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2016/03/31> patch level 3 Babel <3.9r> and hyphenation patterns for 3 language(s) loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2014/09/29 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty ! LaTeX Error: File `utf8x.def’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: def) Enter file name: ! Emergency stop. <read *> l.158 \endinput ^^M No pages of output. Transcript written on math.log.
    and

    System Message: WARNING/2 (`i <= k < j`)

    latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.17 (TeX Live 2016/Debian) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2016/03/31> patch level 3 Babel <3.9r> and hyphenation patterns for 3 language(s) loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2014/09/29 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty ! LaTeX Error: File `utf8x.def’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: def) Enter file name: ! Emergency stop. <read *> l.158 \endinput ^^M No pages of output. Transcript written on math.log.
    . Raises `KeyError` if key is not present. stop defaults to the end of the set. start defaults to the beginning. Negative indexes are supported, as for slice indices.

    Return type: | `int`

class `sortedcontainers.``ValuesView`

  A ValuesView object is a dynamic view of the dictionary’s values, which means that when the dictionary’s values change, the view reflects those changes.

  `ValuesView` implements the ValuesView and Sequence Abstract Base Class types.

  `len`(valuesview)

    Return the number of entries in the dictionary.

    Return type: | `int`

  `iter`(valuesview)

    Return an iterator over the values in the dictionary. Values are iterated over in sorted order of the keys.

    Iterating views while adding or deleting entries in the dictionary may raise a `RuntimeError` or fail to iterate over all entries.

    Return type: | iterator

  `reversed`(valuesview)

    Return a reversed iterator over the values in the dictionary. Values are iterated over in reversed sorted order of the keys.

    Iterating views while adding or deleting entries in the dictionary may raise a `RuntimeError` or fail to iterate over all entries.

    Return type: | iterator

  `x in valuesview`

    Return `True` iff x is one of the underlying dictionary’s values.

    Return type: | `bool`

  `valuesview[i]`

    Return the value at position i.

    Return type: | value

  `valuesview.``count`(value)

    Return the number of occurrences of value in the set.

    Return type: | `int`

  `valuesview.``index`(value)

    Return the smallest k such that

    System Message: WARNING/2 (`valuesview[k] == x`)

    latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.17 (TeX Live 2016/Debian) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2016/03/31> patch level 3 Babel <3.9r> and hyphenation patterns for 3 language(s) loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2014/09/29 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty ! LaTeX Error: File `utf8x.def’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: def) Enter file name: ! Emergency stop. <read *> l.158 \endinput ^^M No pages of output. Transcript written on math.log.
    . Raises `ValueError` if value is not present.

    Return type: | `int`

class `sortedcontainers.``ItemsView`

  An ItemsView object is a dynamic view of the dictionary’s `(key, value)` pairs, which means that when the dictionary changes, the view reflects those changes.

  `ItemsView` implements the ItemsView, Set, and Sequence Abstract Base Class types.

  `len`(itemsview)

    Return the number of entries in the dictionary.

    Return type: | `int`

  `iter`(itemsview)

    Return an iterator over the items in the dictionary. Items are iterated over in sorted order of the keys.

    Iterating views while adding or deleting entries in the dictionary may raise a `RuntimeError` or fail to iterate over all entries.

    Return type: | iterator

  `reversed`(itemsview)

    Return a reversed iterator over the items in the dictionary.

    Iterating views while adding or deleting entries in the dictionary may raise a `RuntimeError` or fail to iterate over all entries.

    Return type: | iterator

  `x in itemsview`

    Return `True` iff x is one of the underlying dictionary’s items.

    Return type: | `bool`

  `itemsview[i]`

    Return the `(key, value)` pair at position i.

    Return type: | item

  `itemsview & other`

    Return the intersection of the items and the other object as a new set.

    Return type: | `SortedSet`

  `itemsview | other`

    Return the union of the items and the other object as a new set.

    Return type: | `SortedSet`

  `itemsview - other`

    Return the difference between the items and the other object (all items that aren’t in other) as a new set.

    Rtype: | `SortedSet`

  `itemsview ^ other`

    Return the symmetric difference (all elements either in the items or other, but not in both) of the items and the other object as a new set.

    Rtype: | `SortedSet`

  `itemsview.``count`(item)

    Return the number of occurrences of item in the set.

    Return type: | `int`

  `itemsview.``index`(item[, start[, stop]])

    Return the smallest k such that

    System Message: WARNING/2 (`itemsview[k] == x`)

    latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.17 (TeX Live 2016/Debian) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2016/03/31> patch level 3 Babel <3.9r> and hyphenation patterns for 3 language(s) loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2014/09/29 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty ! LaTeX Error: File `utf8x.def’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: def) Enter file name: ! Emergency stop. <read *> l.158 \endinput ^^M No pages of output. Transcript written on math.log.
    and

    System Message: WARNING/2 (`i <= k < j`)

    latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.17 (TeX Live 2016/Debian) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2016/03/31> patch level 3 Babel <3.9r> and hyphenation patterns for 3 language(s) loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2014/09/29 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty ! LaTeX Error: File `utf8x.def’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: def) Enter file name: ! Emergency stop. <read *> l.158 \endinput ^^M No pages of output. Transcript written on math.log.
    . Raises `KeyError` if item is not present. stop defaults to the end of the set. start defaults to the beginning. Negative indexes are supported, as for slice indices.

    Return type: | `int`