Menu
OrderedDict is a collection that preserves order of items (in which they were inserted). I do not think this can be achieved with hashtables (which regular dict uses I think) so are balanced trees used to implement it?
I assume there are many depends like Python 2/3 and CPython/IPython/others.
757
Both implementations of OrderedDict involve using a doubly linked list to capture the order of items. Despite having linear time for some operations, the linked list implementation in OrderedDict is highly optimized to preserve the fast times of the corresponding dictionary methods.
The OrderedDict is a subclass of dict object in Python. The only difference between OrderedDict and dict is that, in OrderedDict, it maintains the orders of keys as inserted. In the dict, the ordering may or may not be happen. The OrderedDict is a standard library class, which is located in the collections module.
This means, when iterating over an OrderedDict, the elements are returned in the same order in which the keys (of the key-value pair) were inserted into the data structure. Under the hood, OrderedDict is implemented with the help of the doubly-linked list data structure.
OrderedDict is over 80% slower than the standard Python dictionary (8.6/4.7≈1.83).
You can read the implementation in CPython's source code: Lib/collections/__init__.py as OrderedDict is implemented in Python.
It uses a doubly linked list to maintain the order of the elements in the dictionary.
192
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
