How do you retrieve items from a dictionary in the order that they're inserted?

Question

Is it possible to retrieve items from a Python dictionary in the order that they were inserted?

Answer 1

You can't do this with the base dict class -- it's ordered by hash. You could build your own dictionary that is really a list of key,value pairs or somesuch, which would be ordered.

Answer 2

The standard python dict isn't able to do this.

There is a proposal (PEP 372) to add an "ordered dictionary" (that keeps track of the order of insertion) to the collections module in the standard library. It includes links to various implementations of ordered dictionaries (see also these two recipes in the Python Cookbook).

You might want to stick with the reference implementation in the PEP if you want your code to be compatible with the "official" version (if the proposal is eventually accepted).

Answer 3

The other answers are correct; it's not possible, but you could write this yourself. However, in case you're unsure how to actually implement something like this, here's a complete and working implementation that subclasses dict which I've just written and tested. (Note that the order of values passed to the constructor is undefined but will come before values passed later, and you could always just not allow ordered dicts to be initialized with values.)

class ordered_dict(dict):
    def __init__(self, *args, **kwargs):
        dict.__init__(self, *args, **kwargs)
        self._order = self.keys()

    def __setitem__(self, key, value):
        dict.__setitem__(self, key, value)
        if key in self._order:
            self._order.remove(key)
        self._order.append(key)

    def __delitem__(self, key):
        dict.__delitem__(self, key)
        self._order.remove(key)

    def order(self):
        return self._order[:]

    def ordered_items(self):
        return [(key,self[key]) for key in self._order]


od = ordered_dict()
od["hello"] = "world"
od["goodbye"] = "cruel world"
print od.order()            # prints ['hello', 'goodbye']

del od["hello"]
od["monty"] = "python"
print od.order()            # prints ['goodbye', 'monty']

od["hello"] = "kitty"
print od.order()            # prints ['goodbye', 'monty', 'hello']

print od.ordered_items()
# prints [('goodbye','cruel world'), ('monty','python'), ('hello','kitty')]

Answer 4

if you don't need the dict functionality, and only need to return tuples in the order you've inserted them, wouldn't a queue work better?

Answer 5

I've used StableDict before with good success.

http://pypi.python.org/pypi/StableDict/0.2

Answer 6

Or, just make the key a tuple with time.now() as the first field in the tuple.

Then you can retrieve the keys with dictname.keys(), sort, and voila!

Gerry

Answer 7

It's not possible unless you store the keys in a separate list for referencing later.

Answer 8

Or use any of the implementations for the PEP-372 described here, like the odict module from the pythonutils.

I successfully used the pocoo.org implementation, it is as easy as replacing your

my_dict={}
my_dict["foo"]="bar"

with

my_dict=odict.odict()
my_dict["foo"]="bar"

and require just this file