PEP 372 -- Adding an ordered directory to collections

"Martin v. Löwis" martin at
Wed Jun 18 00:42:56 CEST 2008

> Well, this has become something of a rant, 

Indeed - and I was only asking about .byindex(n) :-)

I don't know why that method is included in the PEP. Speculating
myself, I assume that the PEP author wants it to be O(1). As
bearophile explains, that's not possible/not a good idea.

As for releasing the odict - that will likely have mostly the
same cost as releasing a regular dictionary, except that you
might have to look at each key twice (once in the regular dict,
once in the structure preserving the order). It might be
that the odict uses a linked-list style approach, which indeed
would nto be so good from a allocation/deallocation overhead
point of view. With the approach bearophile suggests (i.e.
each slot in the dict has a reference to the predecessor and
successor key also), a pure Python implementation would normally
allocate additional memory per key, whereas a pure C implementation
wouldn't (adding the space for the prev/next pointer right into
the slot's struct definition.


More information about the Python-list mailing list