indexed.IndexedOrderedDict: a dictionary that is indexed by insertion order
Introduction
indexed.IndexedOrderedDict (alias indexed.Dict) is fully compatible
with collections.OrderedDict 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") == 1Features
- 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(). Including:
- Initialization, setting, getting and deleting items
- Iterating forwards and in reverse
d.clear()d.popitem(last=True)d.move_to_end(key, last=True)d.keys(),d.values(),d.items()d.pop(key[, default])d.setdefault(key, default=None)- String representation
- Pickling
- Copying
- Creating from keys
- Comparing order sensitively with other ordered dictionaries or order insensitively with other mappings
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.