473,704 Members | 4,514 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Why are there no ordered dictionaries?

This is probably a FAQ, but I dare to ask it nevertheless since I
haven't found a satisfying answer yet: Why isn't there an "ordered
dictionary" class at least in the standard list? Time and again I am
missing that feature. Maybe there is something wrong with my programming
style, but I rather think it is generally useful.

I fully agree with the following posting where somebody complains why so
very basic and useful things are not part of the standard library:
http://groups.google.com/group/comp....52d2f771a49857

Are there plans to get it into the standard lib sometime?

-- Christoph
Nov 22 '05
210 10472

Fredrik Lundh wrote:
bo****@gmail.co m wrote:
I am writing a web applications(si mple forms) which has a number of
fields. Each field naturally has a name and a number of
attributes(form atting etc.), like this :

d = {'a':{...}, 'b':{....}}

This dict would be passed to the Kid template system which would lay it
out into a HTML form. For quick and dirty forms, I don't want to code
each field individually in the HTML template but just from top to
bottom(or left to right for a table) with a for loop.

However, I still want to group certain fields together. This is my need
of an ordered dict.


huh? if you want a list, use a list.

d = [('a', {...}), ('b', {....})]

Didn't I say that for quick and dirty form(usually first draft), I want
a list ? But the same template, it would(may) be further enhanced by
graphic designers in which case, I need direct access to the field
names, thus the dict property.

In this way, I don't have to change the python code just because I
change the presentation in the template.

Nov 22 '05 #11
> You asked "why not" rather than "has anyone done this anyway"; if
you asked the latter of the Python Cookbook, you might find something
like this:

<URL:http://aspn.activestat e.com/ASPN/Cookbook/Python/Recipe/107747>

A little old, and pre-dates subclassable native types, but quite
serviceable.


Here's a more recent and tested one, by yours truly (and Michael Foord):

An Ordered Dictionary
http://www.voidspace.org.uk/python/odict.html

--
Nicola Larosa - ni*******@m-tekNico.net

How wonderful the world would be if his behaviour and attitude was the
default among rich people - using his money with a vision to improve the
world, instead of getting 8 sportcars and a larger penis.
-- barkholt on Slashdot, October 2005, referring to Mark Shuttleworth
Nov 22 '05 #12
> You asked "why not" rather than "has anyone done this anyway"; if
you asked the latter of the Python Cookbook, you might find something
like this:

<URL:http://aspn.activestat e.com/ASPN/Cookbook/Python/Recipe/107747>

A little old, and pre-dates subclassable native types, but quite
serviceable.


Here's a more recent and tested one, by yours truly (and Michael Foord):

An Ordered Dictionary
http://www.voidspace.org.uk/python/odict.html

--
Nicola Larosa - ni*******@m-tekNico.net

How wonderful the world would be if his behaviour and attitude was the
default among rich people - using his money with a vision to improve the
world, instead of getting 8 sportcars and a larger penis.
-- barkholt on Slashdot, October 2005, referring to Mark Shuttleworth
Nov 22 '05 #13
> What answers have you received that have not been satisfactory?

I googled a little bit and haven't found many answers at all. Some were
in the posting I mentioned: Stuff should go into the standard lib only
when it is mature and "right" enough. However, we are already at Python
2.4 and there is still no ordered dictionary, though there is a lot of
other specialized stuff.
Some possible answers: The native dict is very fast, partly because
the implementation doesn't need to ensure any particular ordering.
Ok, but that's not an argument against providing ordered dictionaries as
well.
Ordering the keys isn't the normal case, and can be done easily when
needed.
That depends. Maybe I do not want the keys to be sorted alphabetically,
but according to some criteria which cannot be derived from the keys
themselves.
You asked "why not" rather than "has anyone done this anyway"; if
you asked the latter of the Python Cookbook, you might find something
like this.
Yes, I also found that others have done it more than once, and I know
that it's not so difficult to do. There are at least two recipes in the
mentioned cookbook and there is odict in pythonutils. The question was
why is it not available in the *standard* lib.
In what cases do you find yourself needing a dict that preserves its
key order? Can you present a use case that would be improved by an
ordered dict?
There are too many different situations and it would be too much to
explain them here, usually in the case mentioned above where the keys
are not sorted alphabetically. I often solve them by using two data
structures, a list or tuple, plus a dictionary. For instance, the list
could contain the names of database fields which shall be output in a
certain order, and the dictionary values could contain human readable
description of the database fields for headers or something. Instead of
maintaining both data structures I feel it would be more natural to use
only one ordered dictionary.
For my part, I consider it a virtue of Python that the standard
library doesn't change rapidly. It allows many competing
implementations to be shaken out before everyone starts depending on
any one of them.


Ok, but this can be used as an argument to not add anything to the
standard lib any more. There are already enough competing
implementations . Also, the implementation details are not so important,
there must be only agreement on the interface and behavior which should
not be so difficult in this case.

I simply wanted to ask why it is not available in the standard lib,
since I simply don't know

- has it not been demanded loud enough?
- is it really not needed (if you need it it shows you are doing
something wrong)?
- because nobody presented a satisfying implementation yet?
- are there hidden difficulties or controversial issues?

-- Christoph
Nov 22 '05 #14
> What answers have you received that have not been satisfactory?

I googled a little bit and haven't found many answers at all. Some were
in the posting I mentioned: Stuff should go into the standard lib only
when it is mature and "right" enough. However, we are already at Python
2.4 and there is still no ordered dictionary, though there is a lot of
other specialized stuff.
Some possible answers: The native dict is very fast, partly because
the implementation doesn't need to ensure any particular ordering.
Ok, but that's not an argument against providing ordered dictionaries as
well.
Ordering the keys isn't the normal case, and can be done easily when
needed.
That depends. Maybe I do not want the keys to be sorted alphabetically,
but according to some criteria which cannot be derived from the keys
themselves.
You asked "why not" rather than "has anyone done this anyway"; if
you asked the latter of the Python Cookbook, you might find something
like this.
Yes, I also found that others have done it more than once, and I know
that it's not so difficult to do. There are at least two recipes in the
mentioned cookbook and there is odict in pythonutils. The question was
why is it not available in the *standard* lib.
In what cases do you find yourself needing a dict that preserves its
key order? Can you present a use case that would be improved by an
ordered dict?
There are too many different situations and it would be too much to
explain them here, usually in the case mentioned above where the keys
are not sorted alphabetically. I often solve them by using two data
structures, a list or tuple, plus a dictionary. For instance, the list
could contain the names of database fields which shall be output in a
certain order, and the dictionary values could contain human readable
description of the database fields for headers or something. Instead of
maintaining both data structures I feel it would be more natural to use
only one ordered dictionary.
For my part, I consider it a virtue of Python that the standard
library doesn't change rapidly. It allows many competing
implementations to be shaken out before everyone starts depending on
any one of them.


Ok, but this can be used as an argument to not add anything to the
standard lib any more. There are already enough competing
implementations . Also, the implementation details are not so important,
there must be only agreement on the interface and behavior which should
not be so difficult in this case.

I simply wanted to ask why it is not available in the standard lib,
since I simply don't know

- has it not been demanded loud enough?
- is it really not needed (if you need it it shows you are doing
something wrong)?
- because nobody presented a satisfying implementation yet?
- are there hidden difficulties or controversial issues?

-- Christoph
Nov 22 '05 #15
bo****@gmail.co m schrieb:
By ordered dict, one usually wants order that is arbitary which cannot
be derived from the content, say insertion order(most ordered dict I
saw use this order).
I am writing a web applications(si mple forms) which has a number of
fields. Each field naturally has a name and a number of
attributes(form atting etc.), like this :
d = {'a':{...}, 'b':{....}}


Things like that are also my typical use case. The keys usually contain
things like database fields or html form fields, the values contain the
corresponding description, formatting, data type or data itself etc.

The example above is a bit misleading, because using 'a', 'b' as keys
can give the impression that you just have to sort() the keys to have
what you want. So let's make it more realistic:

d = { 'pid': ('Employee ID', 'int'),
'name': ('Employee name', 'varchar'),
'sal': ('Salary', 'float') }

Now if I want these things to be presented in this order, I need to run
through a separate list ('pid', 'name', 'sal') that holds the order.

Ok, you could simply use a list instead of a dictionary:

d = ( ('pid', 'Employee ID', 'int'),
('name', 'Employee name', 'varchar'),
('sal', 'Salary', 'float') )

This works as long as you *only* have to go through the list
sequentially. But maybe you want to print the name with its description
at some other place as well. Now how do you access its description
'Employee name' so easily?

-- Christoph
Nov 22 '05 #16
bo****@gmail.co m schrieb:
By ordered dict, one usually wants order that is arbitary which cannot
be derived from the content, say insertion order(most ordered dict I
saw use this order).
I am writing a web applications(si mple forms) which has a number of
fields. Each field naturally has a name and a number of
attributes(form atting etc.), like this :
d = {'a':{...}, 'b':{....}}


Things like that are also my typical use case. The keys usually contain
things like database fields or html form fields, the values contain the
corresponding description, formatting, data type or data itself etc.

The example above is a bit misleading, because using 'a', 'b' as keys
can give the impression that you just have to sort() the keys to have
what you want. So let's make it more realistic:

d = { 'pid': ('Employee ID', 'int'),
'name': ('Employee name', 'varchar'),
'sal': ('Salary', 'float') }

Now if I want these things to be presented in this order, I need to run
through a separate list ('pid', 'name', 'sal') that holds the order.

Ok, you could simply use a list instead of a dictionary:

d = ( ('pid', 'Employee ID', 'int'),
('name', 'Employee name', 'varchar'),
('sal', 'Salary', 'float') )

This works as long as you *only* have to go through the list
sequentially. But maybe you want to print the name with its description
at some other place as well. Now how do you access its description
'Employee name' so easily?

-- Christoph
Nov 22 '05 #17
[restored my attribution line so we know who said what]

Christoph Zwerschke <ci**@online.de > wrote:
Ben Finney wrote:
In what cases do you find yourself needing a dict that preserves
its key order? Can you present a use case that would be improved
by an ordered dict?
There are too many different situations and it would be too much to
explain them here, usually in the case mentioned above where the
keys are not sorted alphabetically.


Without an example, it's hard to know what you want to do and whether
an ordered dictionary is the best way to do it.
For my part, I consider it a virtue of Python that the standard
library doesn't change rapidly. It allows many competing
implementations to be shaken out before everyone starts depending
on any one of them.


Ok, but this can be used as an argument to not add anything to the
standard lib any more.


I hope not. Rather, it's an argument not to add something to the
standard library until it's proven (to the BDFL's criteria) that it's
better in than out.
There are already enough competing
implementations .
Have they been sufficiently shaken out to show a clearly superior
version? Is any version sufficiently beneficial to write a PEP for its
inclusion in the standard library?
I simply wanted to ask why it is not available in the standard lib,
since I simply don't know

- has it not been demanded loud enough?
Loud demands don't count for much. PEPs with popular working
implementations do.
- is it really not needed (if you need it it shows you are doing
something wrong)?
You dismissed a request for your use cases with handwaving. How can we
know?
- because nobody presented a satisfying implementation yet?
I'm not sure what you mean by "satisfying ".
- are there hidden difficulties or controversial issues?


Another possibility: ordered dictionaries are not needed when Python
2.4 has the 'sorted' builtin.

--
\ "Those who will not reason, are bigots, those who cannot, are |
`\ fools, and those who dare not, are slaves." -- "Lord" George |
_o__) Gordon Noel Byron |
Ben Finney
Nov 22 '05 #18
[restored my attribution line so we know who said what]

Christoph Zwerschke <ci**@online.de > wrote:
Ben Finney wrote:
In what cases do you find yourself needing a dict that preserves
its key order? Can you present a use case that would be improved
by an ordered dict?
There are too many different situations and it would be too much to
explain them here, usually in the case mentioned above where the
keys are not sorted alphabetically.


Without an example, it's hard to know what you want to do and whether
an ordered dictionary is the best way to do it.
For my part, I consider it a virtue of Python that the standard
library doesn't change rapidly. It allows many competing
implementations to be shaken out before everyone starts depending
on any one of them.


Ok, but this can be used as an argument to not add anything to the
standard lib any more.


I hope not. Rather, it's an argument not to add something to the
standard library until it's proven (to the BDFL's criteria) that it's
better in than out.
There are already enough competing
implementations .
Have they been sufficiently shaken out to show a clearly superior
version? Is any version sufficiently beneficial to write a PEP for its
inclusion in the standard library?
I simply wanted to ask why it is not available in the standard lib,
since I simply don't know

- has it not been demanded loud enough?
Loud demands don't count for much. PEPs with popular working
implementations do.
- is it really not needed (if you need it it shows you are doing
something wrong)?
You dismissed a request for your use cases with handwaving. How can we
know?
- because nobody presented a satisfying implementation yet?
I'm not sure what you mean by "satisfying ".
- are there hidden difficulties or controversial issues?


Another possibility: ordered dictionaries are not needed when Python
2.4 has the 'sorted' builtin.

--
\ "Those who will not reason, are bigots, those who cannot, are |
`\ fools, and those who dare not, are slaves." -- "Lord" George |
_o__) Gordon Noel Byron |
Ben Finney
Nov 22 '05 #19
Christoph Zwerschke wrote:
The example above is a bit misleading, because using 'a', 'b' as keys
can give the impression that you just have to sort() the keys to have
what you want. So let's make it more realistic:

d = { 'pid': ('Employee ID', 'int'),
'name': ('Employee name', 'varchar'),
'sal': ('Salary', 'float') }

Now if I want these things to be presented in this order, I need to run
through a separate list ('pid', 'name', 'sal') that holds the order.

Ok, you could simply use a list instead of a dictionary:

d = ( ('pid', 'Employee ID', 'int'),
('name', 'Employee name', 'varchar'),
('sal', 'Salary', 'float') )
if you restructure the list somewhat

d = (
('pid', ('Employee ID', 'int')),
('name', ('Employee name', 'varchar')),
('sal', ('Salary', 'float'))
)

you can still loop over the list

for key, (name, type) in d:
print key, name, type # e.g. generate form entry
This works as long as you *only* have to go through the list
sequentially. But maybe you want to print the name with its description
at some other place as well. Now how do you access its description
'Employee name' so easily?


but you can easily generate an index when you need it:

index = dict(d)

name, type = index["pid"]
print name

the index should take less than a microsecond to create, and since it
points to the members of the original dict, it doesn't use much memory
either...

</F>

Nov 22 '05 #20

This thread has been closed and replies have been disabled. Please start a new discussion.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.