Why are there no ordered dictionaries?

[Christoph Zwerschke]

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.lang.python/msg/e652d2f771a49857

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

-- Christoph

 

[Ben Finney]

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?

What answers have you received that have not been satisfactory?

Some possible answers: The native dict is very fast, partly because
the implementation doesn't need to ensure any particular ordering.
Ordering the keys isn't the normal case, and can be done easily when
needed.

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.activestate.com/ASPN/Cookbook/Python/Recipe/107747>

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

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.

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?

I fully agree with the following posting where somebody complains
why so very basic and useful things are not part of the standard
library:

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.

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

Where to find an answer:

<URL:http://www.python.org/peps/pep-0000.html>

Where to change that answer:

<URL:http://www.python.org/peps/pep-0001.html>

 

[przemek drochomirecki]

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.lang.python/msg/e652d2f771a49857

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

-- Christoph

i am not sure what is the purpose of having ordered dictionaries built in
python, could u provide any examples?

i use a contruction:
for x in sorted(d.keys())

cheers,

przemek

 

[bonono]

i am not sure what is the purpose of having ordered dictionaries built in
python, could u provide any examples?

i use a contruction:
for x in sorted(d.keys())

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(simple forms) which has a number of
fields. Each field naturally has a name and a number of
attributes(formatting 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. Or course, I can pass a list along with the dict
and loop over the list and retrieve value from the dict, but that would
mean another things to pass along. And given the constraint of Kid
where everything must be one-liner(expression, no block of code), it
makes thing a bit harder.

 

[Fredrik Lundh]

I am writing a web applications(simple forms) which has a number of
fields. Each field naturally has a name and a number of
attributes(formatting 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', {....})]

</F>

 

[bonono]

I am writing a web applications(simple forms) which has a number of
fields. Each field naturally has a name and a number of
attributes(formatting 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.

 

[Nicola Larosa]

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.activestate.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 - (e-mail address removed)

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

 

[Christoph Zwerschke]

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

 

[Christoph Zwerschke]

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(simple forms) which has a number of
fields. Each field naturally has a name and a number of
attributes(formatting 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

 

[Ben Finney]

[restored my attribution line so we know who said what]

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.

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.

 

[Fredrik Lundh]

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>

 

[bonono]

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...

Using the same logic, we don't need types other than string in a DBMS
as we can always convert a string field into some other types when it
is needed.

Of course there are more than one way to skin a cat(well it may be
against the general idiom of python) but in some situation certain way
is preferred.

 

[Christoph Zwerschke]

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
...
but you can easily generate an index when you need it:
index = dict(d)

That's exactly the kind of things I find myself doing too often and what
I was talking about: You are using *two* pretty redundant data
structures, a dictionary and a list/tuple to describe the same thing.
Ok, you can use a trick to automatically create the dictionary from the
tuple, but still it feels somewhat "unnatural" for me. A "ordered
dictionary" would be the more "natural" data structure here.

I also wanted to mention the uglyness in the definition (nested tuples),
but then I understood that even an ordered dictionary would not
eliminate that uglyness, since the curly braces are part of the Python
syntax and cannot be used for creating ordered dictionaries anyway. I
would have to define the ordered dictionary in the very same ugly way:

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

(Unless the Python syntax would be extend to use double curly braces or
something for ordered dictionaries - but I understand that this is not
an option.)

-- Christoph

 

[bonono]

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

What does sorted() have anythng to do with orders like insertion order,
or some arbitary order that instead of a,b,c,d,e, I want it as e, c, b,
d, a ?

Personally, I have needs for ordered dict but I don't think it should
be in standard library though, as different situation called for
different behaviour for "ordered" and skewing my code to a standard lib
way is no good.

What I think is better is like the itertools recipe of giving example
of how one can make their own based on the needs.

 

[Christoph Zwerschke]

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.

I have indicated an example, discussed in more detail in another subthread.

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?

At least it shows I'm not the only one who thinks ordered dictionaries
may be sometimes nice to have.

Loud demands don't count for much. PEPs with popular working
implementations do.

Sorry, I did not mean "loud enough" but "often enough". The same what
you are calling "popular."

I'm not sure what you mean by "satisfying".

You can take your own definition: "sufficiently shaken out", "working",
"popular", and "succifiently beneficial" and "proven (to the BDFL's
criteria)".

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

The 'sorted' function does not help in the case I have indicated, where
"I do not want the keys to be sorted alphabetically, but according to
some criteria which cannot be derived from the keys themselves."

-- Christoph

 

[Christoph Zwerschke]

Personally, I have needs for ordered dict but I don't think it should
be in standard library though, as different situation called for
different behaviour for "ordered" and skewing my code to a standard lib
way is no good.

I have started the thread in the first place because I believed it is
pretty unabmiguous what an "ordered dictionary" is and how it should
behave. That's why I asked myself why something that straigthforward has
not been added to the standard lib yet. Maybe I'm wrong; I must admit
that I haven't meditated about it very much.

Do you have an example for different options of behavior?

-- Christoph

 

[bonono]

I have started the thread in the first place because I believed it is
pretty unabmiguous what an "ordered dictionary" is and how it should
behave. That's why I asked myself why something that straigthforward has
not been added to the standard lib yet. Maybe I'm wrong; I must admit
that I haven't meditated about it very much.

Do you have an example for different options of behavior?

As mentioned, most ordered dict I saw is "insertion order" based. I
assume that is the need of their creators. But that is not my need, so
there are at least two behaviour. What I need is a "preferred order".
Say if I have designed a web form(correspond to a database table), I
just want say 3 fields that goes before anything else in the
presentation. The rest I don't care as the DBA may create more fields
later which I don't want to then update my code yet again.

 

[Alex Martelli]

there are at least two behaviour. What I need is a "preferred order".
Say if I have designed a web form(correspond to a database table), I
just want say 3 fields that goes before anything else in the
presentation. The rest I don't care as the DBA may create more fields
later which I don't want to then update my code yet again.

preferred_fields = ['foo', 'bar', 'baz']

def process_preferred_fields():
global preferred_fields
temp = {}
for i, field in enumerate(preferred_fields):
temp[field] = '%s%s' % (chr(0), chr(i))
preferred_fields = temp
process_preferred_fields()
del process_preferred_fields

def sort_key(akey, preferred_fields=preferred_fields):
return preferred_fields.get(akey, akey)
del preferred_fields

## ...build dictionary d...

# now output d...:
for k in sorted(d, key=sort_key):
print k, d[k]

Season to taste if you want non-preferred fields emitted other than
alphabetically, or if you want to wrap this stuff into a class, etc.
(Note: untested code, so typos &c are quite possible). This assumes
that no 'real' key is a non-string, and no 'real' key starts with
chr(0), but it's quite easy to tweak for slightly different specs (at
worst by defining a custom type designed to always compare less than any
real key, and wrapping the preferred_fields entry in instances of that
custom type... having such instances compare with each other based on
the index within preferred_fields of the key they're wrapping, etc etc).


Alex

 

[Alex Martelli]

I have started the thread in the first place because I believed it is
pretty unabmiguous what an "ordered dictionary" is and how it should

I think you're wrong here. People in the past who have requested or
implemented stuff they called 'ordered dicts' in the past had in mind
drastically different things, based on some combination of insertion
orders, keys, and _values_. So, ambiguity is definitely present in the
phrase 'ordered dictionary', because there are so many different
criteria whereby the 'ordering' could take place.

Note the plural in 'insertion orderS': some people care about the FIRST
time a key was added to a dict, some about the LAST time it was added,
some about the latest time it was 'first inserted' (added and wasn't
already there) as long as it's never been deleted since that occasion --
and these are just a few of the multifarious orders based on the time of
insertions and deletions of keys. The number of variations is
staggering, e.g., consider

x['a'] = 1
x['b'] = 2
x['a'] = 1

in some applications you'd want to have 'b' come before 'a' because the
last time of addition was earlier for 'b' -- but in others you might
want 'a' first because the latest addition wasn't really one, since it
didn't really change anything (because the value inserted was the same
as the one already there -- it would be different, for those other apps,
if the RHS of the third assignment was 0 rather than 1...).

To get 'ordered dicts' into Python, you have to identify ONE unambiguous
definition which has a large-enough number of use-cases, possibly
customizable through some reasonably SIMPLE combination of flags and a
callable or two, like the 'sorted' built-in has a 'reversed' flag and
'key' and 'cmp' optional callables. Expect a lot of flak from those who
have been pining for an 'ordered dict' which does NOT match your one
unambiguous definition...;-)

If the field of use cases for 'ordered dicts' is just too fragmented,
it's quite possible that it's best not to have any single kind built-in,
even though, could all different use cases be combined (which by
hypothesis is unfeasible), "critical mass" would be reached...


Alex

 

[Alex Martelli]

The 'sorted' function does not help in the case I have indicated, where
"I do not want the keys to be sorted alphabetically, but according to
some criteria which cannot be derived from the keys themselves."

Ah, but WHAT 'some criteria'? There's the rub! First insertion, last
insertion, last insertion that wasn't subsequently deleted, last
insertion that didn't change the corresponding value, or...???


Alex