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

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

-- Christoph

[Christoph Zwerschke]

bo****@gmail.co m wrote:

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]

Christoph Zwerschke wrote:

bo****@gmail.co m wrote:

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?

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.

[bonono]

Christoph Zwerschke wrote:

bo****@gmail.co m wrote:

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?

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]

bo****@gmail.co m <bo****@gmail.c om> wrote:
...

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_field s = ['foo', 'bar', 'baz']

def process_preferr ed_fields():
global preferred_field s
temp = {}
for i, field in enumerate(prefe rred_fields):
temp[field] = '%s%s' % (chr(0), chr(i))
preferred_field s = temp
process_preferr ed_fields()
del process_preferr ed_fields

def sort_key(akey, preferred_field s=preferred_fie lds):
return preferred_field s.get(akey, akey)
del preferred_field s

## ...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_field s entry in instances of that
custom type... having such instances compare with each other based on
the index within preferred_field s of the key they're wrapping, etc etc).
Alex

[Alex Martelli]

bo****@gmail.co m <bo****@gmail.c om> wrote:
...

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_field s = ['foo', 'bar', 'baz']

def process_preferr ed_fields():
global preferred_field s
temp = {}
for i, field in enumerate(prefe rred_fields):
temp[field] = '%s%s' % (chr(0), chr(i))
preferred_field s = temp
process_preferr ed_fields()
del process_preferr ed_fields

def sort_key(akey, preferred_field s=preferred_fie lds):
return preferred_field s.get(akey, akey)
del preferred_field s

## ...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_field s entry in instances of that
custom type... having such instances compare with each other based on
the index within preferred_field s of the key they're wrapping, etc etc).
Alex

[Alex Martelli]

Christoph Zwerschke <ci**@online.de > wrote:
...

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]

Christoph Zwerschke <ci**@online.de > wrote:
...

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

[Mike Meyer]

Christoph Zwerschke <ci**@online.de > writes:

Ben Finney wrote:

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

And how would an ordered dictionary help in this case?

<mike
--
Mike Meyer <mw*@mired.or g> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.

[Mike Meyer]

Christoph Zwerschke <ci**@online.de > writes:

Ben Finney wrote:

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

And how would an ordered dictionary help in this case?

<mike
--
Mike Meyer <mw*@mired.or g> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.

[bonono]

Alex Martelli wrote:

bo****@gmail.co m <bo****@gmail.c om> wrote:
...

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_field s = ['foo', 'bar', 'baz']

def process_preferr ed_fields():
global preferred_field s
temp = {}
for i, field in enumerate(prefe rred_fields):
temp[field] = '%s%s' % (chr(0), chr(i))
preferred_field s = temp
process_preferr ed_fields()
del process_preferr ed_fields

def sort_key(akey, preferred_field s=preferred_fie lds):
return preferred_field s.get(akey, akey)
del preferred_field s

## ...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_field s entry in instances of that
custom type... having such instances compare with each other based on
the index within preferred_field s of the key they're wrapping, etc etc).

Thanks. For me, I don't need such complex thing, it is just like :

d = somedict_from_d b()
prefer=['f','a',b']

def my_order(d):
for x in prefer:
if x in d: yield x
s = frozenset(prefe r)
for x in d:
if x not in s: yield x