Why are there no ordered dictionaries?
cito at online.de
Tue Nov 22 09:40:33 CET 2005
Alex Martelli schrieb:
> Perl hashes now keep track of 'order of keys'? That's new to me, they
> sure didn't back when I used Perl!
Maybe I shouldn't have talked about Perl when I'm an ignoramus about
that language... You're right, Perl has unordered arrays. That was new
to me since I associate the term "array" always with "ordered" and I
just remembered that PHP's assoc arrays are similar to Perl's but in
fact, and the examples I have read did not mention about that problem.
> What about PHP?
You can conclude that PHP's assoc arrays are ordered from the fact that
the language provides a ksort() function to order the keys. And I think
PHP's insertion order is the one I mentioned in my last post.
Anyway, it would be interesting to examine this in detail and how this
is implemented in other languages.
> "first insertion (since the last deletion if any)" is ONE unambiguous
> definition, but surely not "_the_ ONE" with emphasis on ``the''.
> I see nothing _ambiguous_ (nor _unnatural_) in being interested in the
> *last* insertion, for example; indeed if phrased as "upon insertion, put
> the key at the end of the sequence" (whether it was already elsewhere in
> the sequence of not), with no need for conditionals regarding previous
> existence, it might appear more "conceptually compact".
But it would not satisfy the concept of "keys of a dictionary" which are
BTW, there are some boundary conditions that should be fulfilled for the
insertion order, most obviously:
If you define an ordered dict that way:
d = odict()
d['a'] = 1
d['b'] = 2
d['c'] = 3
The keys should then be orderes as ('a', 'b', 'c').
> Anyway -- subclassing dict to implement your definition is reasonably
> easy, and we could put the resulting package on the Cheese Shop. I hope
> python.org keeps good enough statistics to be able to tell us, a couple
> months later, how many people downloaded said package, vs how many
> people downloaded a complete Python distro; of course, that ratio is
> biased (in favour of the package) by the fact that many people already
> have a complete distro available, while initially nobody would have the
> package, but if we measure when things settle, after letting a month of
> two or 'transient' pass, that effect might be lessened.
That would be also biased (in favour of Python) by the fact that
probably very little people would look for and use the package in the
cheese shop if they were looking for ordered dicts. I for example would
probably use ordered dicts if they were part of the standard lib, but
not if I have to install it as an obscure separate package. So I don't
think that will give us a real clue how many people would like ordered
dicts in the standard lib.
But anyway, if I find some time, I will research a little bit more about
the issue and create such a package, because it seems to me that the
existing packages and recipes are not really satisfying and you're right
it seems to be reasonably easy. It's on my todo list now...
More information about the Python-list