Python:Extend the 'dict' class

Question

I have to solve this exercise:

Python's dictionaries do not preserve the order of inserted data nor store the data sorted by the key. Write an extension for the dict class whose instances will keep the data sorted by their key value. Note that the order must be preserved also when new elements are added.

How do I extend dict? Do I need to have access to the source code for the dict type?

Answer 1

If you use python 2.7+, then see collections.OrderedDict.
Otherwise, backport (copy the source) or see Recipe 576693: Ordered Dictionary for Py2.4 (Python) .

But if you really need to extend the dict, then start with UserDict, source for which you can find in /lib/UserDict.py of your python distribution (Lib/collections/__init__.py with Python 3).

Answer 2

You can either subclass dict or UserDict, since van already talked about UserDict, lets look at dict.

Type help(dict) into an interpreter and you see a big list of methods. You will need to override all the methods that modify the dict as well as the methods that iterate over the dict.

Methods that modify the dict include __delitem__,__setitem__,clear etc.

Methods that iterate the dict include __iter__,keys,values,items etc.

This should get you started

>>> class odict(dict):
...     def __init__(self, *args, **kw):
...         super(odict,self).__init__(*args, **kw)
...         self.itemlist = super(odict,self).keys()
...     def __setitem__(self, key, value):
...          # TODO: what should happen to the order if
...          #       the key is already in the dict       
...         self.itemlist.append(key)
...         super(odict,self).__setitem__(key, value)
...     def __iter__(self):
...         return iter(self.itemlist)
...     def keys(self):
...         return self.itemlist
...     def values(self):
...         return [self[key] for key in self]  
...     def itervalues(self):
...         return (self[key] for key in self)
... 
>>> od = odict(a=1,b=2)
>>> print od
{'a': 1, 'b': 2}
>>> od['d']=4
>>> od['c']=3
>>> print od   # look at the `__str__` and `__repr__` methods 
{'a': 1, 'c': 3, 'b': 2, 'd': 4}
>>> print od.keys()
['a', 'b', 'd', 'c']
>>> print od.values()
[1, 2, 4, 3]

Answer 3

Good news: the problem is not difficult at all.

In order to poke around and see the entrails of a class you can use

>>> dir(dict)
['__class__', '__cmp__', '__contains__', '__delattr__', '__delitem__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__', '__init__', '__iter__', '__le__', '__len__', '__lt__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', 'clear', 'copy', 'fromkeys', 'get', 'has_key', 'items', 'iteritems', 'iterkeys', 'itervalues', 'keys', 'pop', 'popitem', 'setdefault', 'update', 'values']

and help(dict), which has a very complete interactive documentation, but of course you also have access to the even more complete online documentation.

Once you have a grasp of what dict does behind the scenes, you should learn about inheritance in Python.

If you get stuck _{visit this site to get some ideas, but} don't copy/paste, your teacher will not see it kindly.

Answer 4

The implementation of dict will not help you with the task. What you want is a class that has the same interface as dict, but a different implementation. That will require to implement methods like __getitem__, __setitem__, etc. If you Google for "ordereddict", you will find a lot of examples.