Below is the source code of the collections
module in Python 2.7. I feel confused by the way the OrderedDict
initializes its __root
variable. Why does it use try
and except
, is it necessary? Why can't it just use
self.__root = root = [] # sentinel node
root[:] = [root, root, None]
self.__map = {}
self.__update(*args, **kwds)
to initialize self.__root
?
thanks a lot ...
class OrderedDict(dict):
'Dictionary that remembers insertion order'
# An inherited dict maps keys to values.
# The inherited dict provides __getitem__, __len__, __contains__, and get.
# The remaining methods are order-aware.
# Big-O running times for all methods are the same as regular dictionaries.
# The internal self.__map dict maps keys to links in a doubly linked list.
# The circular doubly linked list starts and ends with a sentinel element.
# The sentinel element never gets deleted (this simplifies the algorithm).
# Each link is stored as a list of length three: [PREV, NEXT, KEY].
def __init__(self, *args, **kwds):
'''Initialize an ordered dictionary. The signature is the same as
regular dictionaries, but keyword arguments are not recommended because
their insertion order is arbitrary.
'''
if len(args) > 1:
raise TypeError('expected at most 1 arguments, got %d' % len(args))
try:
self.__root
except AttributeError:
self.__root = root = [] # sentinel node
root[:] = [root, root, None]
self.__map = {}
self.__update(*args, **kwds)
An OrderedDict is a dictionary subclass that remembers the order in which its contents are added. import collections print 'Regular dictionary:' d = {} d['a'] = 'A' d['b'] = 'B' d['c'] = 'C' d['d'] = 'D' d['e'] = 'E' for k, v in d. items(): print k, v print '\nOrderedDict:' d = collections.
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.
No it won't become redundant in Python 3.7 because OrderedDict is not just a dict that retains insertion order, it also offers an order dependent method, OrderedDict. move_to_end() , and supports reversed() iteration*.
OrderedDict is over 80% slower than the standard Python dictionary (8.6/4.7≈1.83).
I found a discussion here (worth noting that Raymond Hettinger is a python core developer).
Essentially it seems to be a precaution for cases where users call __init__
a second time (instead of update
) like this:
In [1]: from collections import OrderedDict
In [2]: od = OrderedDict([(1,2), (3,4)])
In [3]: od
Out[3]: OrderedDict([(1, 2), (3, 4)])
In [4]: od.__init__([(5,6), (7,8)])
In [5]: od
Out[5]: OrderedDict([(1, 2), (3, 4), (5, 6), (7, 8)])
While very uncommon this is mainly important for consistency with dict.__init__
which can also be called a second time instead of dict.update
:
In [6]: d = {1:2, 3:4}
In [7]: d.__init__([(5,6), (7,8)])
In [8]: d
Out[8]: {1: 2, 3: 4, 5: 6, 7: 8} # warning: don't rely on this order!
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