From: tseaver at palladion.com (Tres Seaver)
Date: Mon, 12 Apr 1999 08:20:20 -0500
Subject: OrderedDict.py
References: <Pine.GSO.3.96.990409180912.20801E-100000@crusoe.crusoe.net>
Message-ID: <3711F314.FC15B844@palladion.com>
Content-Length: 1238
X-UID: 194                                                  

evil Japh wrote:
> 
> Is there a need for a module which allows for ordered processing of an
> dictionary?
> 
> I have one written, and it works fine I think.  Basically, it allows for a
> dictionary to be treated like a list, but have the data structure of
> dictionary.  Key-value pairs retain the order you entered them in.  Unless
> you specifically change them.  I'm currently working on more methods, to
> allow it to be sliced like an array.

Your approach sounds like a sequence of (key, value) tuples.  It can't really be
used as a general-purpose dictionary, because searching for an arbitrary element
using the key is going to be linear in the number of elements, whereas the
native Python dictionary is (normal-case) constant-time for the same lookup.

Perhaps you are maintaining the ordered keys in a separate sequence on the
side?  This construct is more useful, but again has scalability problems: 
removing items from the list is harder, and more expensive, and you store the
keys twice (if keys are objects, this is only storing refernces twice).


-- 
=========================================================
Tres Seaver         tseaver at palladion.com    713-523-6582
Palladion Software  http://www.palladion.com




