indexed 1.3.0

A dictionary that is indexed by insertion order.

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.