Ordered dictionary in python: sortedcontainers
In C++ we have:
- map which is a ordered map. Detail about the order can be found here.
- unordered_map which is an unordered map.
In java, we have tree map which is similar to C++’s map.
In python, we don’t have such a data structure until we meet with
SortedDict
Using sortedDict as an example to explore the time complexity of basic operations.
From here we can see the most operation has O(log n ) complexity
setitem
__setitem__(key, value)[source]
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
__delitem__(key)[source]
Remove item from sorted dict identified by key.
sd.__delitem__(key) <==> del sd[key]
Runtime complexity: O(log(n)) — approximate.
pop
pop(key, default=<not-given>)[source]
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.
Compare with C++ map complexity
C++ complexity is shown here.
