1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
indexed.IndexedOrderedDict: a dictionary that is indexed by insertion order
===========================================================================
.. image:: https://github.com/niklasf/indexed.py/actions/workflows/test.yml/badge.svg
:target: https://github.com/niklasf/indexed.py/actions/workflows/test.yml
:alt: Test
.. image:: https://badge.fury.io/py/indexed.svg
:target: https://pypi.python.org/pypi/indexed
:alt: PyPI package
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.
.. code-block:: python
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) [#a]_ O(1) O(n) [#a]_
----------------- ---------- ------------------ -------- ----------------------
del d[key] **O(1)** O(n) O(n) O(n)
----------------- ---------- ------------------ -------- ----------------------
d.keys()[i] O(n) [#k]_ O(n) [#k]_ **O(1)** **O(1)**
----------------- ---------- ------------------ -------- ----------------------
d.values()[i] O(n) [#v]_ O(n) [#v]_ **O(1)** O(n)
----------------- ---------- ------------------ -------- ----------------------
d.items()[i] O(n) [#v]_ O(n) [#v]_ **O(1)** O(n)
----------------- ---------- ------------------ -------- ----------------------
d.keys().index(x) O(n) [#v]_ O(n) [#v]_ O(n) O(n)
================= ========== ================== ======== ======================
.. [#a] These are amortized_ worst case runtimes.
.. [#k] 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))``.
.. [#v] 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.
.. _amortized: http://en.wikipedia.org/wiki/Amortized_analysis
|
