Ordered Dictionaries? Trees?

jepler epler jepler.lnk at lnk.ispi.net
Mon Sep 4 22:02:39 EDT 2000


On Mon, 04 Sep 2000 13:31:16 -0700, Stephen Hansen
 <stephen at cerebralmaelstrom.com> wrote:
>I need a Dictionary who's order is perdictable and/or settable; e.g.
>FIFO/LILO... For instance, if I do: dict['A'] = 1, dict['C'] = 2, dict['B'] = 3,
>then dict.keys() would return ('A','C','B'), always. :)

Something like (untested and incomplete)

class OrderedDict:
	def __init__(self):
		self.data = []
		self.names = []

	def __setitem__(self, item, value):
		if item in self.names:
			self.data[self.names.index(item)] = value	
		else:
			self.names.append(item)
			self.data.append(names)

	def __getitem__(self, item):
		if item in self.names:
			return self.data[self.names.index(item)]
		else:
			raise KeyError, item

	def keys(self):
		return self.names[:]
	def values(self):
		return self.data[:]
	def items(self):
		return map(tuple, self.names, self.data)

>
>What's the best way to do this,
>that isn't tooooooo terribly slow? Speed isn't urgent, but hey, i'd rather
>it not become a negative later on as things expand.

Remember: encapsulate behavior in a class; if performance becomes a problem,
rewrite the class as a C extension.  Performance of the above code is likely
not too great, since 'item in list' and 'list.index(item)' are linear in the
number of items.  Instead, you might make 'names' be a native dict, with keys
equal to the keys of your ordered dictionary, and values equal to the index
of the key.  But in that case, deleting a key can be an expensive operation.

Jeff



More information about the Python-list mailing list