# Python Programming/Sorted Container Types

Python does not provide modules for *sorted* set and dictionary data
types as part of its standard library. This is a concious decision on
the part of Guido van Rossum, et al. to preserve \"one obvious way to do
it.\" Instead, Python delegates this task to third-party libraries that
are available on the Python Package Index. These libraries use various
techniques to maintain list, dict, and set types in sorted order.
Maintaining order using a specialized data structure can avoid very slow
behavior (quadratic run-time) in the naive approach of editing and
constantly re-sorting.

Third-party modules supporting sorted containers:

-   SortedContainers - Pure-Python implementation that is fast-as-C
    implementations. Implements sorted list, dict, and set. Testing
    includes 100% code coverage and hours of stress. Documentation
    includes full API reference, performance
    comparison,
    and contributing/development guidelines. License: Apache2.
-   rbtree - Provides a fast, C-implementation for sorted dict and set
    data types. Based on a red-black tree implementation.
-   treap - Provides a sorted dict data type. Uses a treap for
    implementation and improves performance using Cython.
-   bintrees - Provides several tree-based implementations for dict and
    set data types. Fastest implementations are based on AVL and
    Red-Black trees. Implemented in C. Extends the conventional API to
    provide set operations for dict data types.
-   banyan - Provides a fast, C-implementation for dict and set data
    types.
-   skiplistcollections - Pure-Python implementation based on skip-lists
    providing a limited API for dict and set data types.
-   blist - Provides sorted list, dict and set data types based on the
    \"blist\" data type, a B-tree implementation. Implemented in Python
    and C.

## External links

-   SortedContainers,
    pypi.python.org
-   rbtree, pypi.python.org
-   treap, pypi.python.org
-   bintrees, pypi.python.org
-   Banyan, pypi.python.org
-   skiplistcollections,
    pypi.python.org
-   blist, pypi.python.org

