OrderedDict¶
An OrderedDict is just a dict having an order of items.
When iterating through an OrderedDict, the order is the FIFO. The first item added to the dict will be the first you'll get during iteration.
Naive OrderedDict¶
It seems not hard? A list holding the keys will finish the work. At least, it looks so.
Poor Man OrderedDict
class UnderneathAllPoorManOrderedDict(dict):
def __init__(self, mapping={}):
self._key_list = []
super().__init__(self)
self.update(mapping)
def __setitem__(self, key, value):
if key not in self:
self._key_list.append(key)
super().__setitem__(key, value)
def __iter__(self):
for k in self._key_list:
yield k
def __delitem__(self, key):
self.pop(key)
def __reversed__(self):
for k in self._key_list[::-1]:
yield k
def pop(self, key):
self._key_list.remove(key)
return super().pop(key)
def keys(self):
return self.__iter__()
def items(self):
for k in self._key_list:
yield (k, self[k])
Run
ua_ordered_dict = UnderneathAllPoorManOrderedDict()
ua_ordered_dict['b'] = 1
ua_ordered_dict['c'] = 3
ua_ordered_dict['a'] = 2
del ua_ordered_dict['c']
for k in ua_ordered_dict:
print(k)
Output
b
c
a
Run
for k in reversed(ua_ordered_dict):
print(k)
Output
a
c
b
Run
del ua_ordered_dict['c']
for k in ua_ordered_dict:
print(k)
Output
b
a
We use a _key_list to store all the keys. However, performance will be a big issue.
In the real OrderedDict, Link is used to store all the keys in order.