# Sorted Dict

Sorted Containers is an Apache2 licensed Python sorted collections library, written in pure-Python, and fast as C-extensions. The introduction is the best way to get started.

Sorted dict implementations:

- `SortedDict`
- `SortedKeysView`
- `SortedItemsView`
- `SortedValuesView`

# SortedDict

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

  Bases: `dict`

  Sorted dict is a sorted mutable mapping.

  Sorted dict keys are maintained in sorted order. The design of sorted dict is simple: sorted dict inherits from dict to store items and maintains a sorted list of keys.

  Sorted dict keys must be hashable and comparable. The hash and total ordering of keys must not change while they are stored in the sorted dict.

  Mutable mapping methods:

  - `SortedDict.__getitem__()` (inherited from dict)
  - `SortedDict.__setitem__()`
  - `SortedDict.__delitem__()`
  - `SortedDict.__iter__()`
  - `SortedDict.__len__()` (inherited from dict)

  Methods for adding items:

  - `SortedDict.setdefault()`
  - `SortedDict.update()`

  Methods for removing items:

  - `SortedDict.clear()`
  - `SortedDict.pop()`
  - `SortedDict.popitem()`

  Methods for looking up items:

  - `SortedDict.__contains__()` (inherited from dict)
  - `SortedDict.get()` (inherited from dict)
  - `SortedDict.peekitem()`

  Methods for views:

  - `SortedDict.keys()`
  - `SortedDict.items()`
  - `SortedDict.values()`

  Methods for miscellany:

  - `SortedDict.copy()`
  - `SortedDict.fromkeys()`
  - `SortedDict.__reversed__()`
  - `SortedDict.__eq__()` (inherited from dict)
  - `SortedDict.__ne__()` (inherited from dict)
  - `SortedDict.__repr__()`
  - `SortedDict._check()`

  Sorted list methods available (applies to keys):

  - `SortedList.bisect_left()`
  - `SortedList.bisect_right()`
  - `SortedList.count()`
  - `SortedList.index()`
  - `SortedList.irange()`
  - `SortedList.islice()`
  - `SortedList._reset()`

  Additional sorted list methods available, if key-function used:

  - `SortedKeyList.bisect_key_left()`
  - `SortedKeyList.bisect_key_right()`
  - `SortedKeyList.irange_key()`

  Sorted dicts may only be compared for equality and inequality.

  `__init__`(*args, **kwargs)

    Initialize sorted dict instance.

    Optional key-function argument defines a callable that, like the key argument to the built-in sorted function, extracts a comparison key from each dictionary key. If no function is specified, the default compares the dictionary keys directly. The key-function argument must be provided as a positional argument and must come before all other arguments.

    Optional iterable argument provides an initial sequence of pairs to initialize the sorted dict. Each pair in the sequence defines the key and corresponding value. If a key is seen more than once, the last value associated with it is stored in the new sorted dict.

    Optional mapping argument provides an initial mapping of items to initialize the sorted dict.

    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 stored in the sorted dict.

    Sorted dict keys must be hashable, per the requirement for Python’s dictionaries. Keys (or the result of the key-function) must also be comparable, per the requirement for sorted lists.

        >>> d = {'alpha': 1, 'beta': 2}
        >>> SortedDict([('alpha', 1), ('beta', 2)]) == d
        True
        >>> SortedDict({'alpha': 1, 'beta': 2}) == d
        True
        >>> SortedDict(alpha=1, beta=2) == d
        True

  `key`

    Function used to extract comparison key from keys.

    Sorted dict compares keys directly when the key function is none.

  `__getitem__`()

    x.__getitem__(y) <==> x[y]

  `__setitem__`(key, value)

    Store item in sorted dict with key and corresponding value.

    `sd.__setitem__(key, value)` <==> `sd[key] = value`

    Runtime complexity: O(log(n)) – approximate.

        >>> sd = SortedDict()
        >>> sd['c'] = 3
        >>> sd['a'] = 1
        >>> sd['b'] = 2
        >>> sd
        SortedDict({'a': 1, 'b': 2, 'c': 3})

    Parameters:

    - key – key for item
    - value – value for item

  `__delitem__`(key)

    Remove item from sorted dict identified by key.

    `sd.__delitem__(key)` <==> `del sd[key]`

    Runtime complexity: O(log(n)) – approximate.

        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
        >>> del sd['b']
        >>> sd
        SortedDict({'a': 1, 'c': 3})
        >>> del sd['z']
        Traceback (most recent call last):
          ...
        KeyError: 'z'

    Parameters: | key – key for item lookup
    Raises: | KeyError – if key not found

  `__iter__`()

    Return an iterator over the keys of the sorted dict.

    `sd.__iter__()` <==> `iter(sd)`

    Iterating the sorted dict while adding or deleting items may raise a `RuntimeError` or fail to iterate over all keys.

  `__len__`()

    Return len(self).

  `setdefault`(key, default=None)

    Return value for item identified by key in sorted dict.

    If key is in the sorted dict then return its value. If key is not in the sorted dict then insert key with value default and return default.

    Optional argument default defaults to none.

    Runtime complexity: O(log(n)) – approximate.

        >>> sd = SortedDict()
        >>> sd.setdefault('a', 1)
        1
        >>> sd.setdefault('a', 10)
        1
        >>> sd
        SortedDict({'a': 1})

    Parameters:

    - key – key for item
    - default – value for item (default None)

    Returns: | value for item identified by key

  `update`(*args, **kwargs)

    Update sorted dict with items from args and kwargs.

    Overwrites existing items.

    Optional arguments args and kwargs may be a mapping, an iterable of pairs or keyword arguments. See `SortedDict.__init__()` for details.

    Parameters:

    - args – mapping or iterable of pairs
    - kwargs – keyword arguments mapping

  `clear`()

    Remove all items from sorted dict.

    Runtime complexity: O(n)

  `pop`(key, default=<not-given>)

    Remove and return value for item identified by key.

    If the key is not found then return default if given. If default is not given then raise `KeyError`.

    Runtime complexity: O(log(n)) – approximate.

        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
        >>> sd.pop('c')
        3
        >>> sd.pop('z', 26)
        26
        >>> sd.pop('y')
        Traceback (most recent call last):
          ...
        KeyError: 'y'

    Parameters:

    - key – key for item
    - default – default value if key not found (optional)

    Returns: | value for item
    Raises: | KeyError – if key not found and default not given

  `popitem`(index=-1)

    Remove and return `(key, value)` pair at index from sorted dict.

    Optional argument index defaults to -1, the last item in the sorted dict. Specify `index=0` for the first item in the sorted dict.

    If the sorted dict is empty, raises `KeyError`.

    If the index is out of range, raises `IndexError`.

    Runtime complexity: O(log(n))

        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
        >>> sd.popitem()
        ('c', 3)
        >>> sd.popitem(0)
        ('a', 1)
        >>> sd.popitem(100)
        Traceback (most recent call last):
          ...
        IndexError: list index out of range

    Parameters: | index (int) – index of item (default -1)
    Returns: | key and value pair

    Raises:

    - KeyError – if sorted dict is empty
    - IndexError – if index out of range

  `__contains__`()

    True if the dictionary has the specified key, else False.

  `get`()

    Return the value for key if key is in the dictionary, else default.

  `peekitem`(index=-1)

    Return `(key, value)` pair at index in sorted dict.

    Optional argument index defaults to -1, the last item in the sorted dict. Specify `index=0` for the first item in the sorted dict.

    Unlike `SortedDict.popitem()`, the sorted dict is not modified.

    If the index is out of range, raises `IndexError`.

    Runtime complexity: O(log(n))

        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
        >>> sd.peekitem()
        ('c', 3)
        >>> sd.peekitem(0)
        ('a', 1)
        >>> sd.peekitem(100)
        Traceback (most recent call last):
          ...
        IndexError: list index out of range

    Parameters: | index (int) – index of item (default -1)
    Returns: | key and value pair
    Raises: | IndexError – if index out of range

  `keys`()

    Return new sorted keys view of the sorted dict’s keys.

    See `SortedKeysView` for details.

    Returns: | new sorted keys view

  `items`()

    Return new sorted items view of the sorted dict’s items.

    See `SortedItemsView` for details.

    Returns: | new sorted items view

  `values`()

    Return new sorted values view of the sorted dict’s values.

    See `SortedValuesView` for details.

    Returns: | new sorted values view

  `copy`()

    Return a shallow copy of the sorted dict.

    Runtime complexity: O(n)

    Returns: | new sorted dict

  classmethod `fromkeys`(iterable, value=None)

    Return a new sorted dict initailized from iterable and value.

    Items in the sorted dict have keys from iterable and values equal to value.

    Runtime complexity: O(n*log(n))

    Returns: | new sorted dict

  `__reversed__`()

    Return a reverse iterator over the keys of the sorted dict.

    `sd.__reversed__()` <==> `reversed(sd)`

    Iterating the sorted dict while adding or deleting items may raise a `RuntimeError` or fail to iterate over all keys.

  `__eq__`()

    Return self==value.

  `__ne__`()

    Return self!=value.

  `__repr__`()

    Return string representation of sorted dict.

    `sd.__repr__()` <==> `repr(sd)`

    Returns: | string representation

  `_check`()

    Check invariants of sorted dict.

    Runtime complexity: O(n)

  Sorted list methods (applies to keys):

  - `SortedList.bisect_left()`
  - `SortedList.bisect_right()`
  - `SortedList.count()`
  - `SortedList.index()`
  - `SortedList.irange()`
  - `SortedList.islice()`
  - `SortedList._reset()`

  Additional sorted list methods, if key-function used:

  - `SortedKeyList.bisect_key_left()`
  - `SortedKeyList.bisect_key_right()`
  - `SortedKeyList.irange_key()`

# SortedKeysView

class `sortedcontainers.``SortedKeysView`(mapping)

  Bases: `collections.abc.KeysView`, `collections.abc.Sequence`

  Sorted keys view is a dynamic view of the sorted dict’s keys.

  When the sorted dict’s keys change, the view reflects those changes.

  The keys view implements the set and sequence abstract base classes.

  `__getitem__`(index)

    Lookup key at index in sorted keys views.

    `skv.__getitem__(index)` <==> `skv[index]`

    Supports slicing.

    Runtime complexity: O(log(n)) – approximate.

        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
        >>> skv = sd.keys()
        >>> skv[0]
        'a'
        >>> skv[-1]
        'c'
        >>> skv[:]
        ['a', 'b', 'c']
        >>> skv[100]
        Traceback (most recent call last):
          ...
        IndexError: list index out of range

    Parameters: | index – integer or slice for indexing
    Returns: | key or list of keys
    Raises: | IndexError – if index out of range

  `__delitem__`(index)

    Remove item at index from sorted dict.

    `view.__delitem__(index)` <==> `del view[index]`

    Supports slicing.

    Runtime complexity: O(log(n)) – approximate.

        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
        >>> view = sd.keys()
        >>> del view[0]
        >>> sd
        SortedDict({'b': 2, 'c': 3})
        >>> del view[-1]
        >>> sd
        SortedDict({'b': 2})
        >>> del view[:]
        >>> sd
        SortedDict({})

    Parameters: | index – integer or slice for indexing
    Raises: | IndexError – if index out of range

# SortedItemsView

class `sortedcontainers.``SortedItemsView`(mapping)

  Bases: `collections.abc.ItemsView`, `collections.abc.Sequence`

  Sorted items view is a dynamic view of the sorted dict’s items.

  When the sorted dict’s items change, the view reflects those changes.

  The items view implements the set and sequence abstract base classes.

  `__getitem__`(index)

    Lookup item at index in sorted items view.

    `siv.__getitem__(index)` <==> `siv[index]`

    Supports slicing.

    Runtime complexity: O(log(n)) – approximate.

        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
        >>> siv = sd.items()
        >>> siv[0]
        ('a', 1)
        >>> siv[-1]
        ('c', 3)
        >>> siv[:]
        [('a', 1), ('b', 2), ('c', 3)]
        >>> siv[100]
        Traceback (most recent call last):
          ...
        IndexError: list index out of range

    Parameters: | index – integer or slice for indexing
    Returns: | item or list of items
    Raises: | IndexError – if index out of range

# SortedValuesView

class `sortedcontainers.``SortedValuesView`(mapping)

  Bases: `collections.abc.ValuesView`, `collections.abc.Sequence`

  Sorted values view is a dynamic view of the sorted dict’s values.

  When the sorted dict’s values change, the view reflects those changes.

  The values view implements the sequence abstract base class.

  `__getitem__`(index)

    Lookup value at index in sorted values view.

    `siv.__getitem__(index)` <==> `siv[index]`

    Supports slicing.

    Runtime complexity: O(log(n)) – approximate.

        >>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
        >>> svv = sd.values()
        >>> svv[0]
        1
        >>> svv[-1]
        3
        >>> svv[:]
        [1, 2, 3]
        >>> svv[100]
        Traceback (most recent call last):
          ...
        IndexError: list index out of range

    Parameters: | index – integer or slice for indexing
    Returns: | value or list of values
    Raises: | IndexError – if index out of range