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 
Christoph Zwerschke <ci**@online.de > wrote:
... * C++ has a Map template in the STL which is ordered (a "Sorted
Associative Container").
Ordered *by comparisons on keys*, NOT by order of insertion -- an
utterly and completely different idea.
So ordered dictionaries don't seem to be such an exotic idea.
Ordered *by order of key insertion*: Java, PHP
Ordered *by other criteria*: LISP, C++
Unordered: Python, Perl, Ruby, Smalltalk, Awk, Tcl
by classification of the languages you've listed.
I can't help but I still find it unambiguous and intuitive enough to
consider it "the one" standard implementation for ordered dictionaries.
Then you should be very careful not to call C++'s implementation
"ordered", because that makes it VERY HARD to argue that "the one"
thingy;-).
Nevertheless, since sorting by keys (or any function of the keys and
values, including one depending on an external table, which was claimed
to be otherwise in other parts of this thread) is so trivial, while
recovering insertion order is impossible without some auxiliary data
structure ``on the side'', I agree that a dictionary subclass that's
ordered based on insertion timing would have more added value than one
where the 'ordering' is based on any function of keys and values.
Alex
On Tue, 22 Nov 2005 22:06:12 +0100, Christoph Zwerschke <ci**@online.de > wrote: 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.
If you define the semantics like feeding overlapping keys in a tuple
sequence to dict, then later duplicate keys just replace prior ones
by same rules as d[k]=v1; d[k]=v2. I think that makes sense in this
context, and can be defined unambigously.
Regards,
Bengt Richter
Tom Anderson <tw**@urchin.ea rth.li> wrote:
... 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.
However, since Christoph himself just misclassified C++'s std::map as
"ordered" (it would be "sorted" in this new terminology he's now
introducing), it seems obvious that the terminological confusion is
rife. Many requests and offers in the past for "ordered dictionaries"
(e.g. on this group) were also "sorted", NOT "ordered", in this new
terminology.
Maybe it would therefore be clearer to have the name of the new
container reflect this, with a specific mention of *insertion* order...
rather than just call it "ordered" and risk probable confusion.
Alex
Alex Martelli wrote: However, since Christoph himself just misclassified C++'s std::map as
"ordered" (it would be "sorted" in this new terminology he's now
introducing), it seems obvious that the terminological confusion is
rife. Many requests and offers in the past for "ordered dictionaries"
(e.g. on this group) were also "sorted", NOT "ordered", in this new
terminology.
Maybe it would therefore be clearer to have the name of the new
container reflect this, with a specific mention of *insertion* order...
rather than just call it "ordered" and risk probable confusion.
Um,
what would be the definition of "sorted" and "ordered", before we can
go on ?
On 22 Nov 2005 19:15:42 -0800, "bo****@gmail.c om" <bo****@gmail.c om> wrote:
Alex Martelli wrote: However, since Christoph himself just misclassified C++'s std::map as
"ordered" (it would be "sorted" in this new terminology he's now
introducing), it seems obvious that the terminological confusion is
rife. Many requests and offers in the past for "ordered dictionaries"
(e.g. on this group) were also "sorted", NOT "ordered", in this new
terminology.
Maybe it would therefore be clearer to have the name of the new
container reflect this, with a specific mention of *insertion* order...
rather than just call it "ordered" and risk probable confusion.
Um,
what would be the definition of "sorted" and "ordered", before we can
go on ?
For me the implication of "sorted" is that there is a sorting algorithm
that can be used to create an ordering from a prior state of order,
whereas "ordered" could be the result of arbitrary permutation, e.g.,
manual shuffling, etc. Of course either way, a result can be said
to have a particular defined order, but "sorted" gets ordered
by sorting, and "ordered" _may_ get its order by any means.
Regards,
Bengt Richter
Bengt Richter wrote: For me the implication of "sorted" is that there is a sorting algorithm
that can be used to create an ordering from a prior state of order,
whereas "ordered" could be the result of arbitrary permutation, e.g.,
manual shuffling, etc. Of course either way, a result can be said
to have a particular defined order, but "sorted" gets ordered
by sorting, and "ordered" _may_ get its order by any means.
But Alex seems to think that based on another external table should be
classified as "sorted" whereas I would consider it as "manual
shuffling", thus "ordered".
I may be wrong it interpreting him though, which is why I want to
clarify. > Alex Martelli <al***@mail.com cast.net> writes: > Ordered
*by order of key insertion*: Java, PHP > Ordered *by other
criteria*: LISP, C++ Java supports both ordered by key insertion
(LinkedHashMap) as well as ordered by key comparison (TreeMap).
Ganesan
--
Ganesan Rajagopal (rganesan at debian.org) | GPG Key:
1024D/5D8C12EA Web: http://employees.org/~rganesan | http://rganesan.blogspot.com bo****@gmail.co m <bo****@gmail.c om> wrote: Bengt Richter wrote: For me the implication of "sorted" is that there is a sorting algorithm
that can be used to create an ordering from a prior state of order,
whereas "ordered" could be the result of arbitrary permutation, e.g.,
manual shuffling, etc. Of course either way, a result can be said
to have a particular defined order, but "sorted" gets ordered
by sorting, and "ordered" _may_ get its order by any means.
But Alex seems to think that based on another external table should be
classified as "sorted" whereas I would consider it as "manual
shuffling", thus "ordered".
I may be wrong it interpreting him though, which is why I want to
clarify.
What you can obtain (or anyway easily simulate in terms of effects on a
loop) through an explicit call to the 'sorted' built-in, possibly with a
suitable 'key=' parameter, I would call "sorted" -- exactly because, as
Bengt put it, there IS a sorting algorithm which, etc, etc (if there
wasn't, you couldn't implement it through the 'sorted' built-in!).
So, any ordering that can be reconstructed from the key,value data held
in a dict (looking up some combinations of those in an external table is
nothing special in these terms) falls under this category. But, a dict
does not record anything about what was set or changed or deleted when;
any ordering which requires access to such information thus deserves to
be placed in a totally separate category.
Alex
Alex Martelli wrote: What you can obtain (or anyway easily simulate in terms of effects on a
loop) through an explicit call to the 'sorted' built-in, possibly with a
suitable 'key=' parameter, I would call "sorted" -- exactly because, as
Bengt put it, there IS a sorting algorithm which, etc, etc (if there
wasn't, you couldn't implement it through the 'sorted' built-in!).
So, any ordering that can be reconstructed from the key,value data held
in a dict (looking up some combinations of those in an external table is
nothing special in these terms) falls under this category. But, a dict
does not record anything about what was set or changed or deleted when;
any ordering which requires access to such information thus deserves to
be placed in a totally separate category.
But I can also record these changes in a seperate table which then
becomes a "sorted" case ? This thread has been closed and replies have been disabled. Please start a new discussion. |
