An ordered dict implementation in Python using a second hash map to store the order information.

ordered_dicts_python.py

#!/usr/bin/env python
import random
import operator
import time
from collections import OrderedDict
import unittest

class ordered_dict(dict):
    def __init__(self):
        self.order = {}
        self.count = 0

    def __getitem__(self, key):
        return dict.__getitem__(self, key)

    def __setitem__(self, key, value):
        dict.__setitem__(self, key, value)
        self.order[(key, value)] = self.count
        self.count += 1

    def __delitem__(self, key):
        del self.order[(key, dict.__getitem__(self, key))]
        dict.__delitem__(self, key)

    def iteritems(self):
        """ Preseves ordering, albeit inneficiently """
        order_items = self.order.items()
        order_items.sort(key=operator.itemgetter(1))
        for order_item in order_items:
            yield order_item[0]

start = None
def tic():
    global start
    start = time.time()

def toc(msg):
    global start
    print "%s took: %ss" % (msg, time.time() - start)
    start = time.time()

def test_ordereddict(d, x):
    tic()
    for i in x:
        d[i] = i
    toc("adding items")

    for i in xrange(1, len(x), 3):
        del d[i]
    toc("removing 1/3rd of items")

    for item in d.iteritems():
        pass

    toc("iterating over items in order")
#    return ordered_items

class Test(unittest.TestCase):
    def test(self):
        n = 10**6
        d = ordered_dict()
        x = range(n)
        random.shuffle(x)

        print "Testing ordered_dict"
        test_ordereddict(ordered_dict(), x)

        print "Testing OrderedDict"
        test_ordereddict(OrderedDict(), x)

        # This takes a long time
#        self.assertEqual(ret1, ret2)

if __name__ == '__main__':
    unittest.main()