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  10577 
Bengt Richter wrote: I think the concept has converged to a replace-or-append-by-key ordering
of key:value items with methods approximately like a dict. We're now
into usability aspects such as syntactic sugar vs essential primitives,
and default behaviour vs selectable modes, ISTM.
Yes, and we would be good if we do not stop the discussion at this point
with nothing, but really create such a sophisticated implementation.
Whether it will become popular or go to the standard lib some day is a
completely different question.
E.g., it might be nice to have a mode that assumes d[key] is
d.items()[k][1] when key is an integer, and otherwise uses dict lookup, for cases where
the use case is just string dict keys.
I also thought about that and I think PHP has that feature, but it's
probably better to withstand the temptation to do that. It could lead to
an awful confusion if the keys are integers.
-- Christoph
>>* C++ has a Map template in the STL which is ordered (a "Sorted Associative Container").
Alex Martelli wrote:
Ordered *by comparisons on keys*, NOT by order of insertion -- an
utterly and completely different idea.
Shame on me. I talked so much about the difference between "ordered" and
"sorted" and now I wrote such a confusing sentence. You're right, C++
Maps are not an example for "ordered dictionaries", but for "sorted
dictionaries".
-- Christoph
Duncan Booth schrieb: In Javascript Object properties (often used as an associative array) are
defined as unordered although as IE seems to always store them in the order
of original insertion it wouldn't surprise me if there are a lot of
websites depending on that behaviour.
You're right with both. The ECMA language definition says object
properties are an unordered collection, but MSIE and probably other
browsers keep the order in which they were created. Of course one should
not rely on that.
-- Christoph
On Wed, 2005-11-23 at 15:17, Christoph Zwerschke wrote: Bengt Richter wrote: > I think the concept has converged to a replace-or-append-by-key ordering
> of key:value items with methods approximately like a dict. We're now
> into usability aspects such as syntactic sugar vs essential primitives,
> and default behaviour vs selectable modes, ISTM.
Yes, and we would be good if we do not stop the discussion at this point
with nothing, but really create such a sophisticated implementation.
Whether it will become popular or go to the standard lib some day is a
completely different question.
> E.g., it might be nice to have a mode that assumes d[key] is
d.items()[k][1] when > key is an integer, and otherwise uses dict lookup, for cases where
the use > case is just string dict keys.
I also thought about that and I think PHP has that feature, but it's
probably better to withstand the temptation to do that. It could lead to
an awful confusion if the keys are integers.
Thus quoth the Zen of Python:
"Explicit is better than implicit."
"In the face of ambiguity, refuse the temptation to guess."
With those in mind, since an odict behaves mostly like a dictionary, []
should always refer to keys. An odict implementation that wants to allow
access by numeric index should provide explicitly named methods for that
purpose.
-Carsten
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.
I'm sorry again. Please don't conclude that others are as uneducated as
I am (I haven't studied computer science but mathematics). Speaking
about "ordered" and "sorted" in the context of collections is not a new
terminology I am introducing, but seems to be pretty common in computer
science (see, e.g. http://www.gamespp.com/java/dataStru...avaPart6.html).
Perhaps Pythonists are not used to that terminology, since they use the
term "list" for an "ordered collection". An ordered dictionary is a
dictionary whose keys are a (unique) list. Sometimes it is also called a
"sequence" (therefore in the odict implementation, the keys attribute
has this name). A unique list, in turn, can also be called an "ordered
set", so you can also understand an ordered dictionary as a dictionary
whose keys are an ordered set. I think all of this is pretty logical ;-)
-- Christoph
Ganesan Rajagopal wrote: the definition of "sorted" and "ordered", before we can > go on ? Sorted
would be ordered by key comparison. Iterating over such a container will
give you the keys in sorted order. Java calls this a SortedMap. See
http://java.sun.com/j2se/1.4.2/docs/...SortedMap.html C++ STL
map container is also a Sorted Associative container. See
http://www.sgi.com/tech/stl/Map.html Ganesan
Exactly, that's "sorted." "Ordered" means the same there is some order
between the existing elements, but there is no magic (i.e. a general
comparison function) for ordering new elements. Thus, if you add an
element to an ordered collection, it simply gets appended (is considered
as the greatest of all elements) by convention, whereas if you add an
element to a sorted collection, it will be inserted into the correct
place by using the comparison function.
-- Christoph
Alex Martelli schrieb: I detest and abhor almost-sequences which can't be sliced (I consider
that a defect of collections.deq ue). If the ordered dictionary records
by its sequencing the time order of key insertion, being able to ask for
"the last 5 keys entered" or "the first 3 keys entered" seem to me to be
perfectly natural use cases, and most naturally accomplished by slicing
of course, d[-5:] and d[:3] respectively.
I agree. A use case was requested: Say your dictionary holds form
fields, and you know the last field is always a hidden field you wont to
ignore in your output, or your dictionary holds attributes of a
database, and you don't want to print the first attribute which is
always some kind of uninteresting OID, then you would write
"for field in d[1:]" or "for field in d[:-1]".
(Otherwise, you would have to write "for field in d.keys()[1:]" etc.)
-- Christoph
Bengt Richter wrote: >>> 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?
Eso es exactamente lo que yo queria haber!
-- Chris
>> 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.).
Tom Anderson wrote:
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.
Think of it similar as the case of an ordinary dictionary: There is
conceptually a set here (the set of keys), but you cannot manipulate it
directly, but only through the according dictionary methods.
For an ordedred dictionary, there is conceptually a list (or more
specifically a unique list). Again you should not manipulate it
directly, but only through methods of the ordered dictionary.
This sounds at first more complicated, but is in reality more easy.
For instance, if I want to put the last two keys of an ordered dict d at
the beginning, I would do it as d = d[:-2] + d[-2:].
With the list attribute (called "sequence" in odict, you would have to
write: d.sequence = d.sequence[:-2] + d.sequence[-2:]. This is not only
longer to write down, but you also have to know that the name of the
attribute is "sequence". Python's strength is that you don't have to
keep many details in mind because it has a small "basic vocabulary" and
orthogonal use. I prefer the ordered dictionary does not introduce new
concepts or attributes if everything can be done intuitively with the
existing Python methods and operators.
-- Christoph
Fuzzyman wrote: So what do you want returned when you ask for d1[1] ? The member keyed
by 1, or the item in position 1 ?
In case of conflict, the ordered dictionary should behave like a
dictionary, not like a list. So d1[1] should be the member keyed by 1,
not the item in position 1. Only in case there is no member keyed by 1,
the item in position 1 could be returned, but I think that would be too
adventurous a hattrick and can lead to big confusion. Better to raise a
KeyError in that case.
But no other way to directly manipulate the keys should be provided.
Why - don't trust yourself with it ?
No, because I think it is not needed if list operations like insert are
directly possible on your dictionary.
But maybe methods such as setkeys() and setvalues() would be nice to
have in addition.
Instead of writing d.sequence = new_sequence, I would write
d.setkeys(new_s equence). But I'm not sure what to do if new_sequence is
not a permutation of the old one. Raise a KeyError? Or even swallow
this? For instance
d = OrderedDict((1, 11), (2,12))
d.setkeys((2, 1)) ==> d = OrderedDict((2, 11), (1, 12))
d.setkeys((3, 4)) ==> d = OrderedDict((3, 11), (4, 12)) (or KeyError?)
d.setvalues((12 , 11)) ==> d = OrderedDict((1, 12), (2, 11))
d.setvalues((13 , 14)) ==> d = OrderedDict((1, 13), (2, 14)) (always ok)
(Or maybe better set_keys in analogy to has_key?)
I hesitate making keys and values managed properties, because this would
conflict with them being methods in ordinary dicts. Ordered dicts should
resemble ordinary dicts as closely as possible. And giving it a
different name like "sequence" I find confusing and unintuitive.
A resort could be the following: If keys() is given a sequence as
argument, then use this as the new sequence of keys, and similar with
values(). This way, no new methods need to be introduced.
-- Christoph This thread has been closed and replies have been disabled. Please start a new discussion. |
