Introduction
indexed.IndexedOrderedDict (alias indexed.Dict) is feature compatible
with collections.OrderedDict as of Python 3.11 and can be used as
a drop in replacement.
The main difference is that key, value and item views support accessing
elements by their index.
d = indexed.IndexedOrderedDict() d["first-key"] = "first-value" d["second-key"] = "second-value" d["third-key"] = "third-value" values = d.values() assert values[2] == "third-value" assert d.keys().index("second-key") == 1
Features
- Access keys, values and items by index, e.g.,
d.keys()[5]. - Find the index of a key, e.g.,
d.keys().index("key"). - Sort keys in place, e.g.,
d.sort().
Excluding those additions the API is the same as the API of
collections.OrderedDict().
Installing
pip install indexed
Performance
Performance is practically on the same order of magnitude as the built in
collections.OrderedDict, with exceptions in bold:
| d | collections.OrderedDict |
indexed.IndexedOrderedDict |
||
|---|---|---|---|---|
| Operation | Avergage | Worst case | Average | Worst case |
| d.copy() | O(n) | O(n) | O(n) | O(n) |
| d[key] | O(1) | O(n) | O(1) | O(n) |
| d[key] = value | O(1) | O(n) [1] | O(1) | O(n) [1] |
| del d[key] | O(1) | O(n) | O(n) | O(n) |
| d.keys()[i] | O(n) [2] | O(n) [2] | O(1) | O(1) |
| d.values()[i] | O(n) [3] | O(n) [3] | O(1) | O(n) |
| d.items()[i] | O(n) [3] | O(n) [3] | O(1) | O(n) |
| d.keys().index(x) | O(n) [3] | O(n) [3] | O(n) | O(n) |
| [1] | (1, 2) These are amortized worst case runtimes. |
| [2] | (1, 2) This does not work in Python 3 because colections.KeysView is not
indexable. One of the theoretically best work arounds is
next(itertools.islice(d.keys(), i, i + 1)). |
| [3] | (1, 2, 3, 4, 5, 6) Assuming the theoretically best possible workaround. |
License
This library is derived from CPython's collections.OrderedDict
and licensed under the PSFL.
See the LICENSE file for the full license text.