Python Programming/Sorted Container Types
Sorted Container Types
Python does not provide modules like C++'s set and map data types as part of its standard library. This is a concious decision on the part of Guido, 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. Several implementations are described here.
- Python SortedContainers Module - Pure-Python implementation that is fast-as-C implementations. Implements sorted list, dict, and set data types. Testing includes 100% code coverage and hours of stress. Documentation includes full API reference, performance comparison, and contributing/development guidelines.
- Python rbtree Module - Provides a fast, C-implementation for dict and set data types. Based on a red-black tree implementation.
- Python treap Module - Provides a sorted dict data type. Uses a treap for implementation and improves performance using Cython.
- Python bintrees Module - 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.
- Python banyan Module - Provides a fast, C-implementation for dict and set data types.
- Python skiplistcollections Module - Pure-Python implementation based on skip-lists providing a limited API for dict and set data types.
- Python blist Module - Provides sorted list, dict and set data types based on the "blist" data type, a B-tree implementation. Implemented in Python and C.