Python Class Methods – Implementing Ordered Dictionary

“It is the time you have wasted for your rose that makes your rose so important.” ― Antoine de Saint-Exupéry, The Little Prince


  • 2. Implementing an Ordered Dictionary
  • 3. Improving String Representation
  • 6. Delegated Implementations

1. Introduction

The python class system supports a number of special methods which allows class implementations to mimic built-in python objects objects. These special methods are invoked by the python run-time system in a way similar to the built-in classes. For example, the method __len__()
can be defined by a user class which will be invoked when the client code attempts to find the length of the object using len(obj)

In this article, we take a look at implementing an ordered dictionary – a dictionary which remembers the order in which the items (key – value pairs) were inserted and allows you to iterate on the items in the same order. We do this by storing the items in an array as well as in a dict
. We also illustrate the use of some of the python special class methods to mimic the behavior of dict
as closely as possible.

Note: The python standard library includes a module collections.OrderedDict
which is a much more complete implementation of the concepts discussed here, and should be used in all real code. The article and code presented here is intended as a learning aid rather than a complete implementation.

2. Implementing an Ordered Dictionary

Here is a basic class for implementing an ordered dictionary. It starts withan inner class for representing a key-value pair. The class stores the (key, value) pairs in an array, and also maintains a dict
for fast lookup of the keys. The array serves to store the order in which the items were inserted. We want our ordered_dict
to work as much as possible like a standard dict

class ordered_dict:
    class _item:
        def __init__(self, key, value):
            self.k = key
            self.v = value

    def __init__(self):
        self.d = {}
        self.a = []

    def _find(self, key):
        for i in self.a:
            if i.k == key: return i
        return None

    def __setitem__(self, key, value):
        if key in self.d:
            item = self._find(key)
            item.v = value
            self.d[key] = value
            self.a.append(ordered_dict._item(key, value))

    def __getitem__(self, key):
        return self.d[key]

Let us see how to use this class.

d = ordered_dict()
d['jim'] = 4
d['cat'] = 'fink'
d['dog'] = 'dink'
d['joe'] = 1
print d

3. Improving String Representation

We don’t like the string representation of the class – it is a default representation of an object in python. Let us improve it to look just like dict
. We do that by defining the __str__()

class ordered_dict:
    def __str__(self):
        s = ''
        for i in self.a:
            if s: s += ', '
            if isinstance(i.v, (int, long, float)):
                v = str(i.v)
                v = "'" + str(i.v) + "'"
            s += "'" + str(i.k) + "'" + ': ' + v
        return '{' + s + '}'

Now we get a nice representation similar to dict

print d
# {'jim': 4, 'cat': 'fink', 'dog': 'dink', 'joe': 1}

4. Adding Iteration

The main purpose of our ordered dict class is to be able to fetch items in the same order as inserted. For this, we need to add iteration to our class. We do this by defining an inner class (called _iter
) which handles the iteration using the array member.

class ordered_dict:
    class _iter:
        def __init__(self, arr):
            self.a = arr
            self.c = 0;

        def next(self):
            i = self.c
            if i >= len(self.a):
                raise StopIteration
            self.c += 1
            return self.a[i].k
    def __iter__(self):
        return ordered_dict._iter(self.a)

By comparison, here is what happens with an ordinary dict
. As you can see, dict
returns items in no particular order.

c = {}
c['jim'] = 4
c['cat'] = 'fink'
c['dog'] = 'dink'
c['joe'] = 1
print c

for i in c:
    print ' ', i
# prints
{'joe': 1, 'jim': 4, 'dog': 'dink', 'cat': 'fink'}

5. Deleting an Item

Deleting an item needs to be handled specially. Since the items are being maintained in an array as well as an internal dict
, we need to delete the item from both.

class ordered_dict:
    def __delitem__(self, key):
        del self.d[key]
        # above stmt raises exception if no key so following code not executed
        a = []
        for i in self.a:
            if i.k != key: a.append(i)
        self.a = a

Checking if it works:

d = ordered_dict()
d['jim'] = 4
d['cat'] = 'fink'
d['dog'] = 'dink'
d['joe'] = 1
print d
del d['joe']
print d
# prints
{'jim': 4, 'cat': 'fink', 'dog': 'dink', 'joe': 1}
{'jim': 4, 'cat': 'fink', 'dog': 'dink'}

6. Delegated Implementations

Let us look into implementing methods for handling len(obj)
and key in obj
check. These are done using __len__()
and __contains__()
respectively, and is quite simple – just delegate to the underlying dict.

class ordered_dict:
    def __contains__(self, key):
        return dict.__contains__(self.d, key)

    def __iter__(self):
        return ordered_dict._iter(self.a)

    def __len__(self):
        return len(self.d)

And of course, verify that it works as normal.

d = ordered_dict()
d['jim'] = 4
d['cat'] = 'fink'
d['dog'] = 'dink'
d['joe'] = 1
print d, 'has', len(d), 'items.'
print 'does d have "joe"?', 'joe' in d
print 'does d have "jack"?', 'jack' in d


In this article, we learnt some special methods in python and how to use these to enhance your class to behave in an idiomatic way in python.

Novixys Software Dev Blog稿源:Novixys Software Dev Blog (源链) | 关于 | 阅读提示

本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 综合编程 » Python Class Methods – Implementing Ordered Dictionary

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录