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  10547 
Carsten Haese wrote: That could easily be fixed by making the sequence a "managed property"
whose setter raises a ValueError if you try to set it to something
that's not a permutation of what it was.
Ok, a managed attribute would be an option. You would allow people to do
what they want with the sequence, and then fix the dictionary
accordingly (if items were deleted from the sequence, they are deleted
from the dictionary, it items were added which are not in the directory,
a ValueError is raised etc.).
But probably it is still better to hide the sequence and instead of
letting people do list operations like sort() on the odict.sequence, let
them do these operations on odict directly. d1[0] + d1[2] ==> OrderedDict( (1, 11), (3, 13) )
What do you think you're doing here?
Sorry, what I meant was
d1[0:0] + d1[2:2] ==> OrderedDict( (1, 11), (3, 13) )
Ordered dictionaries could allow slicing and concatenation.
-- Christoph
> d1[0:0] + d1[2:2] ==> OrderedDict( (1, 11), (3, 13) )
Oops, sorry, that was nonsense again. I meant
d1[0:1] + d1[1:2] ==> OrderedDict( (1, 11), (3, 13) ) Ordered dictionaries could allow slicing and concatenation.
Some operations such as concatenation need of course special
considerations, since the keys must stay unique. A concatenation of
ordered dicts with overlapping keys should probably give an IndexError.
-- Christoph
On Tue, 22 Nov 2005 21:24:29 +0100, Christoph Zwerschke <ci**@online.de > wrote: Carsten Haese wrote:
That could easily be fixed by making the sequence a "managed property"
whose setter raises a ValueError if you try to set it to something
that's not a permutation of what it was.
Ok, a managed attribute would be an option. You would allow people to do
what they want with the sequence, and then fix the dictionary
accordingly (if items were deleted from the sequence, they are deleted
from the dictionary, it items were added which are not in the directory,
a ValueError is raised etc.).
But probably it is still better to hide the sequence and instead of
letting people do list operations like sort() on the odict.sequence, let
them do these operations on odict directly.
d1[0] + d1[2] ==> OrderedDict( (1, 11), (3, 13) )
What do you think you're doing here?
Sorry, what I meant was
d1[0:0] + d1[2:2] ==> OrderedDict( (1, 11), (3, 13) )
Ordered dictionaries could allow slicing and concatenation.
Those are zero-length slices in normal notation. ITYM [0:1] and [2:3]?
Note that you'd have to define addition as possible replacement,
if all the keys happened to match. Or pure concat if none matched,
and variations mixing both ways.
But with the current version you can already write that as
OrderedDict(d1. items()[0:1]+d2.items()[2:3])
you just want the sugar? d1+d2 would be like using [:] in the above line
Not a biggie to do.
Regards,
Bengt Richter
On Tue, 22 Nov 2005 20:15:18 +0100, Christoph Zwerschke <ci**@online.de > wrote: def __init__(self, init_val = ()):
dict.__init__(s elf, init_val)
self.sequence = [x[0] for x in init_val]
Fuzzyman wrote:
But that doesn't allow you to create an ordered dict from another
ordered dict.
Right; I did not want to present a full implementation, just the
relevant part. Of course, a real implementation should also allow to
build an ordered dict from another ordered dict or an ordinary dict. (In
the latter case, maybe the keys should be automatically sorted.) But one
or two case disctinctions would not make things mentionable slower.
Since the OrderedDict constructor takes a sequence of tuples as a legitimate
argument, you can always create an ordered dict from an unordered by getting
unordered_dict. items() and sorting or ordering them any way you want and calling
the OrderedDict constructor. Ditto for ordered dicts, since they give your their
ordered items with the items() method as a start. I guess one could pass a
key=fun keyword arg to the OrderedDict constuctor to imply a pre-construction sort.
Regards,
Bengt Richter
On 22 Nov 2005 11:18:19 -0800, "Kay Schluehr" <ka**********@g mx.net> wrote: Bengt Richter wrote: On Mon, 21 Nov 2005 01:27:22 +0100, Christoph Zwerschke <ci**@online.de > wrote: Note that is isn't hard to snap a few pieces together to make an ordered
dict to your own specs. But IMO it belongs in pyPI or such, not in the system
library. At least until it gets a lot of mileage -- and MMV ;-)
It's also not very hard to write a hex2ascii converter. That's the
reason why 20 incompatible versions of it ( coded in C ) exists in my
department ;)
Bicycle shed effect, I guess ;-)
Kay
PS. Here is some attempt of my own to implement an odict, following the
discussion here.
The implementation highlights just the model and is incomplete:
This is essentially the tack I took in modifying odict.py, except I
added optional caching of sorted items, and other minor differences.
class odict(dict):
def __init__(self, create_order = True):
dict.__init__(s elf)
self.create_ord er = create_order
self.__cnt = 0
def __setitem__(sel f, key, value):
val = dict.get(self,k ey)
if val and self.create_ord er:
dict.__setitem_ _(self, key, (val[0], value))
else:
self.__cnt+=1
dict.__setitem_ _(self, key, (self.__cnt, value))
def __getitem__(sel f, key):
return dict.__getitem_ _(self, key)[1]
def values(self):
return list(zip(*sorte d(dict.values(s elf)))[1])
maybe more directly
return [v for i,v in sorted(dict.val ues(self))]
def keys(self):
ks = [(dict.get(self, k)[0],k) for k in dict.keys(self)]
return list(zip(*sorte d(ks))[1])
or (untested)
def keys(self):
return [k for k,v in sorted(dict.ite ms(self), key=operator.it emgetter(1))]
def items(self):
return [(k,v[1]) for k,v in sorted(dict.ite ms(self), key=operator.it emgetter(1))] od = odict()
od["a"] = 0
od["b"] = 8
od.keys()["a", "b"]
od = odict(create_or der = False)
od["a"] = 1
od["b"] = 2
od["a"] = 3
od.keys()
["b", "a"]
Regards,
Bengt Richter
Bengt Richter wrote: On 22 Nov 2005 03:07:47 -0800, "bo****@gmail.c om" <bo****@gmail.c om> wrote:
Bengt Richter wrote: Ok, so if not in the standard library, what is the problem? Can't find what
you want with google and PyPI etc.? Or haven't really settled on what your
_requirements_ are? That seems to be the primary problem people who complain
with "why no sprollificator mode?" questions. They don't know what they really
mean when it comes down to a DYFR (Define Your Felicitous Requirements) challenge.
So DYFR ;-)Beat me. I am not the one asking the question.
Sorry, I thought you wanted an ordered dict too.
I want/need(well I am told I don't need) to loop over a dict in certain
order but I don't want or need a standard one as I don't think there is
ONE implementation of it. My original post was a response to the
question "why do one want ordered dict", in the tone of "there is no
way one wants it".
>> > parsing or not parsing is not the point, and parsing/converting is
>> > still "create a new view" of an existing data structure.
>>
So you'd like the mechanics to be automated and hidden? Then you need to
DYFR for using the black box you want. Methods, semantics.
Lose you. don't know what you want to say.
I like solving problems. I just get frustrated when people don't focus on getting
the problem defined, which IME is 2/3 of the way to a solution. I don't mind,
in fact enjoy, rambling musings, but if someone seems actually to want a solution
for something, I like to try to realize it concretely.
I tried to define the problem, and how I solve it(if it helps to convey
the message), but was told you don't have the problem in the first
place.
On Tue, 22 Nov 2005, Carsten Haese wrote: On Tue, 2005-11-22 at 14:37, Christoph Zwerschke wrote:
In Foord/Larosa's odict, the keys are exposed as a public member which
also seems to be a bad idea ("If you alter the sequence list so that it
no longer reflects the contents of the dictionary, you have broken your
OrderedDict").
That could easily be fixed by making the sequence a "managed property"
whose setter raises a ValueError if you try to set it to something
that's not a permutation of what it was.
I'm not a managed property expert (although there's a lovely studio in
Bayswater you might be interested in), but how does this stop you doing:
my_odict.sequen ce[0] = Shrubbery()
Which would break the odict good and hard.
tom
--
When I see a man on a bicycle I have hope for the human race. --
H. G. Wells
On Tue, 22 Nov 2005 20:37:40 +0100, Christoph Zwerschke <ci**@online.de > wrote: One implementation detail that I think needs further consideration is in
which way to expose the keys and to mix in list methods for ordered
dictionaries .
In http://aspn.activestate.com/ASPN/Coo.../Recipe/107747
the keys are exposed via the keys() method which is bad. It should be a
copy only, like for ordinary dicts (one comment also mentions that).
In Foord/Larosa's odict, the keys are exposed as a public member which
also seems to be a bad idea ("If you alter the sequence list so that it
no longer reflects the contents of the dictionary, you have broken your
OrderedDict" ).
I think it would be probably the best to hide the keys list from the
public, but to provide list methods for reordering them (sorting,
slicing etc.).
For instance:
d1 = OrderedDict( (1, 11), (2, 12), 3, 13) )
d1[1:] ==> OrderedDict( (2, 12), 3, 13) )
d1[0] + d1[2] ==> OrderedDict( (1, 11), (3, 13) )
d1.reverse() ==> OrderedDict( (3, 13), (2, 12), 1, 11) )
d1.insert(1, (4, 14))
==> OrderedDict( (1, 11), (4, 14), (2, 12), 3, 13) )
etc.
But no other way to directly manipulate the keys should be provided.
from odictb import OrderedDict
d1 = OrderedDict([(1, 11), (2, 12), (3, 13)])
d1
{1: 11, 2: 12, 3: 13} d1[1:]
{2: 12, 3: 13} d1[0:1] + d1[2:3]
{1: 11, 3: 13} d1.reverse()
d1
{3: 13, 2: 12, 1: 11} d1.insert(1, (4,14))
d1
{3: 13, 4: 14, 2: 12, 1: 11} d1.items()
[(3, 13), (4, 14), (2, 12), (1, 11)] d1.keys()
[3, 4, 2, 1] d1.values()
[13, 14, 12, 11] d1[1:2]
{4: 14} d1[-1:]
{1: 11}
Que mas?
Regards,
Bengt Richter
On Tue, 22 Nov 2005, Christoph Zwerschke wrote: One implementation detail that I think needs further consideration is in
which way to expose the keys and to mix in list methods for ordered
dictionaries.
In Foord/Larosa's odict, the keys are exposed as a public member which
also seems to be a bad idea ("If you alter the sequence list so that it
no longer reflects the contents of the dictionary, you have broken your
OrderedDict").
I think it would be probably the best to hide the keys list from the public,
but to provide list methods for reordering them (sorting, slicing etc.).
I'm not too keen on this - there is conceptually a list here, even if it's
one with unusual constraints, so there should be a list i can manipulate
in code, and which should of course be bound by those constraints.
I think the way to do it is to have a sequence property (which could be a
managed attribute to prevent outright clobberation) which walks like a
list, quacks like a list, but is in fact a mission-specific list subtype
whose mutator methods zealously enforce the invariants guaranteeing the
odict's integrity.
I haven't actually tried to write such a beast, so i don't know if this is
either of possible and straightforward .
tom
--
When I see a man on a bicycle I have hope for the human race. --
H. G. Wells
On Tue, 22 Nov 2005, Christoph Zwerschke wrote: Fuzzyman schrieb:
Of course ours is ordered *and* orderable ! You can explicitly alter
the sequence attribute to change the ordering.
What I actually wanted to say is that there may be a confusion between a
"sorted dictionary" (one where the keys are automatically sorted) and an
"ordered dictionary" (where the keys are not automatically ordered, but
have a certain order that is preserved). Those who suggested that the
"sorted" function would be helpful probably thought of a "sorted
dictionary" rather than an "ordered dictionary."
Exactly.
Python could also do with a sorted dict, like binary tree or something,
but that's another story.
tom
--
When I see a man on a bicycle I have hope for the human race. --
H. G. Wells This thread has been closed and replies have been disabled. Please start a new discussion. |
