Hi, I noticed lately that quite a few projects are implementing their own subclasses of `dict` that retain the order of the key/value pairs. However half of the implementations I came across are not implementing the whole dict interface which leads to weird bugs, also the performance of a Python implementation is not that great. To fight that problem I want to proposed a new class in "collections" called odict which is a dict that keeps the items sorted, similar to a PHP array. The interface would be fully compatible with dict and implemented as dict subclass. Updates to existing keys does not change the order of a key but new keys are inserted at the end. Additionally it would support slicing where a list of key, value tuples is returned and sort/reverse/index methods that work like their list equivalents. Index based lookup could work via odict.byindex(). An implementation of that exists as part of the ordereddict implementation which however goes beyond that and is pretty much a fork of the python dict[1]. Some reasons why ordered dicts are a useful feature: - in XML/HTML processing it's often desired to keep the attributes of an tag ordered during processing. So that input ordering is the same as the output ordering. - Form data transmitted via HTTP is usually ordered by the position of the input/textarea/select field in the HTML document. That information is currently lost in most Python web applications / frameworks. - Eaiser transition of code from Ruby/PHP which have sorted associative arrays / hashmaps. - Having an ordered dict in the standard library would allow other libraries support them. For example a PHP serializer could return odicts rather then dicts which drops the ordering information. XML libraries such as etree could add support for it when creating elements or return attribute dicts. Regards, Armin [1]: http://www.xs4all.nl/~anthon/Python/ordereddict/
Armin Ronacher wrote:
Hi,
I noticed lately that quite a few projects are implementing their own subclasses of `dict` that retain the order of the key/value pairs. However half of the implementations I came across are not implementing the whole dict interface which leads to weird bugs, also the performance of a Python implementation is not that great.
I'm +1 - but this proposal has been made many times before and people always argue about what features are needed or desirable. :-( Michael Foord
To fight that problem I want to proposed a new class in "collections" called odict which is a dict that keeps the items sorted, similar to a PHP array.
The interface would be fully compatible with dict and implemented as dict subclass. Updates to existing keys does not change the order of a key but new keys are inserted at the end.
Additionally it would support slicing where a list of key, value tuples is returned and sort/reverse/index methods that work like their list equivalents. Index based lookup could work via odict.byindex().
An implementation of that exists as part of the ordereddict implementation which however goes beyond that and is pretty much a fork of the python dict[1].
Some reasons why ordered dicts are a useful feature:
- in XML/HTML processing it's often desired to keep the attributes of an tag ordered during processing. So that input ordering is the same as the output ordering.
- Form data transmitted via HTTP is usually ordered by the position of the input/textarea/select field in the HTML document. That information is currently lost in most Python web applications / frameworks.
- Eaiser transition of code from Ruby/PHP which have sorted associative arrays / hashmaps.
- Having an ordered dict in the standard library would allow other libraries support them. For example a PHP serializer could return odicts rather then dicts which drops the ordering information. XML libraries such as etree could add support for it when creating elements or return attribute dicts.
Regards, Armin
[1]: http://www.xs4all.nl/~anthon/Python/ordereddict/
_______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/fuzzyman%40voidspace.org.u...
-- http://www.ironpythoninaction.com/ http://www.theotherdelia.co.uk/ http://www.voidspace.org.uk/ http://www.ironpython.info/ http://www.resolverhacks.net/
Michael Foord wrote:
Armin Ronacher wrote:
Hi,
I noticed lately that quite a few projects are implementing their own subclasses of `dict` that retain the order of the key/value pairs. However half of the implementations I came across are not implementing the whole dict interface which leads to weird bugs, also the performance of a Python implementation is not that great.
I'm +1 - but this proposal has been made many times before and people always argue about what features are needed or desirable. :-(
There's been a lot of controversy/confusion about ordered dicts. One of the sources of confusion is that people mean different things when they use the term "ordered dict": In some cases, the term is used to mean a dictionary that remembers the order of insertions, and in other cases it is used to mean a sorted dict, i.e. an associative data structure in which the entries are kept sorted. (And I'm not sure that those are the only two possibilities.) I would be more in favor of the idea if we could come up with a less ambiguous naming scheme. -- Talin
2008/6/14 Talin <talin@acm.org>:
There's been a lot of controversy/confusion about ordered dicts. One of the sources of confusion is that people mean different things when they use the term "ordered dict": In some cases, the term is used to mean a dictionary that remembers the order of insertions, and in other cases it is used to mean a sorted dict, i.e. an associative data structure in which the entries are kept sorted. (And I'm not sure that those are the only two possibilities.)
Have the comparison function passed in as a parameter then, if it's None, then have it maintain the order of insertion? Something like: def __init__(self, cmpfunc = None): self.dict = dict() def __getattr__(self, key): try: return self.key -- Cheers, Hasan Diwan <hasan.diwan@gmail.com>
Have the comparison function passed in as a parameter then, if it's None, then have it maintain the order of insertion?
No. This would contribute to the confusion, not resolve it. If it's called "ordered dictionary", it shouldn't do sorting at all. If it does sorting, it should be called "sorted dictionary", and mandate a comparison function (which might default to cmp). Regards, Martin
Hasan Diwan <hasan.diwan <at> gmail.com> writes:
2008/6/14 Talin <talin <at> acm.org>:
There's been a lot of controversy/confusion about ordered dicts. One of the sources of confusion is that people mean different things when they use the term "ordered dict": In some cases, the term is used to mean a dictionary that remembers the order of insertions, and in other cases it is used to mean a sorted dict, i.e. an associative data structure in which the entries are kept sorted. (And I'm not sure that those are the only two possibilities.)
Have the comparison function passed in as a parameter then, if it's None, then have it maintain the order of insertion? Something like: def __init__(self, cmpfunc = None): self.dict = dict()
I think that would be contraproductive and would make the constructor incompatible with the normal dict constructor which accepts keyword arguments too. Also that dict is just in order, but not sorted by something. You could still do something like this: d = odict() d['Pinguin'] = 'telly' d['Parrot'] = 'cage' d['Mouse'] = 'Napoleon' d.sort(key=lambda x: x[1].lower()) That of course would not sort items inserted after the sort call. Regards, Armin
Talin wrote:
Michael Foord wrote:
Armin Ronacher wrote:
Hi,
I noticed lately that quite a few projects are implementing their own subclasses of `dict` that retain the order of the key/value pairs. However half of the implementations I came across are not implementing the whole dict interface which leads to weird bugs, also the performance of a Python implementation is not that great.
I'm +1 - but this proposal has been made many times before and people always argue about what features are needed or desirable. :-(
There's been a lot of controversy/confusion about ordered dicts. One of the sources of confusion is that people mean different things when they use the term "ordered dict": In some cases, the term is used to mean a dictionary that remembers the order of insertions, and in other cases it is used to mean a sorted dict, i.e. an associative data structure in which the entries are kept sorted. (And I'm not sure that those are the only two possibilities.)
I would be more in favor of the idea if we could come up with a less ambiguous naming scheme.
I think Armin's proposal addresses this nicely by the analogy to lists: the ordered dict is in key insertion order by default, but you can invoke odict.sort() to sort it instead. Given the synergy with the Py3k metaclass enhancements, I believe this would be a good thing to have. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia --------------------------------------------------------------- http://www.boredomandlaziness.org
From: "Talin" <talin@acm.org>
There's been a lot of controversy/confusion about ordered dicts.
I think that is why all earlier proposals all died.
One of the sources of confusion is that people mean different things when they use the term "ordered dict": In some cases, the term is used to mean a dictionary that remembers the order of insertions, and in other cases it is used to mean a sorted dict, i.e. an associative data structure in which the entries are kept sorted. (And I'm not sure that those are the only two possibilities.)
For an insertion order dictionary, there was also a question about how to handle duplicate keys. Given odict([(k1,v1), (k2,v2), (k1,v3)]), what should the odict.items() return? [(k1,v3), (k2,v2)] [(k2,v2), (k1,v3)] The first maintains the original sort order and is consistent with the usual idea that d[k]=v simply replaces the value but does not alter the hash table. It is a bit weird though because v3 appears earlier than v2 which was inserted earlier. It's especially weird for keys that are equal but not identical: d[0]=v1 d[0.0]=v3. Do you want 0.0 to remain associated with v3 or should the items list contain a pair that was not in the original insertion list, (0, v3)? The second one is a bit weird because a key "loses its place" whenever the value is updated. IIRC, previous discussions showed an interest in odicts but that there were a lot of questions of the specific semantics of the API. This would no doubt be compounded by attempts to emulate dict views. Regardless, there should probably be a PEP and alternate pure python versions should be posted on ASPN so people can try them out. post Raymond
Raymond Hettinger <python <at> rcn.com> writes:
For an insertion order dictionary, there was also a question about how to handle duplicate keys.
Given odict([(k1,v1), (k2,v2), (k1,v3)]), what should the odict.items() return?
[(k1,v3), (k2,v2)] [(k2,v2), (k1,v3)] All the ordered dict implementations I saw behave like this:
>>> odict([(1, 'foo'), (2, 'bar'), (1, 'baz')]).items() [(1, 'baz'), (2, 'bar')] And that makes sense because it's consistent with the dict interface. But I guess that is a pretty small issue and most of the time you are not dealing with double keys when using an ordered dict.
IIRC, previous discussions showed an interest in odicts but that there were a lot of questions of the specific semantics of the API. No doubt there. But
This would no doubt be compounded by attempts to emulate dict views. Regardless, there should probably be a PEP and alternate pure python versions should be posted on ASPN so people can try them out. That's true, but by now there are countless of ordered dict implementations with a mostly-compatible interface and applications and libraries are using them already.
I have an example implementation here that incorporates the ideas from ordereddict, Django's OrderedDict and Babel's odict: http://dev.pocoo.org/hg/sandbox/raw-file/tip/odict.py Regards, Armin
Armin Ronacher wrote:
That's true, but by now there are countless of ordered dict implementations with a mostly-compatible interface and applications and libraries are using them already.
Even worse, most of them are slow, i.e. show a wrong algorithmic complexity ...
I have an example implementation here that incorporates the ideas from ordereddict, Django's OrderedDict and Babel's odict:
... like your implementation. It is not too hard to get the delitem O(log n) compared to your O(n), see here: http://codespeak.net/svn/user/arigo/hack/pyfuse/OrderedDict.py So many people are implementing this kind of data type but do not really care about making as fast as it could be ... IMHO yet another reason to ship a usable implementation with Python. Kind regards, Alexander
... like your implementation. It is not too hard to get the delitem O(log n) compared to your O(n), see here:
http://codespeak.net/svn/user/arigo/hack/pyfuse/OrderedDict.py
So many people are implementing this kind of data type but do not really care about making as fast as it could be ... IMHO yet another reason to ship a usable implementation with Python.
If you use a linked list instead of Python list, you can even do deletion in O(1). Of course, memory consumption will be higher. Regards, Martin
Hi, Alexander Schremmer <2008a <at> usenet.alexanderweb.de> writes:
Even worse, most of them are slow, i.e. show a wrong algorithmic complexity ... I already said that in the initial post.
I have an example implementation here that incorporates the ideas from ordereddict, Django's OrderedDict and Babel's odict:
... like your implementation. It is not too hard to get the delitem O(log n) compared to your O(n), see here: That implementation is intended as example implementation for a possible API not one you should actually use.
Regards, Armin
In data 15 giugno 2008 alle ore 07:43:32, Raymond Hettinger <python@rcn.com> ha scritto:
For an insertion order dictionary, there was also a question about how to handle duplicate keys.
Given odict([(k1,v1), (k2,v2), (k1,v3)]), what should the odict.items() return?
[(k1,v3), (k2,v2)] [(k2,v2), (k1,v3)]
The first maintains the original sort order and is consistent with the usual idea that d[k]=v simply replaces the value but does not alter the hash table. It is a bit weird though because v3 appears earlier than v2 which was inserted earlier. It's especially weird for keys that are equal but not identical: d[0]=v1 d[0.0]=v3. Do you want 0.0 to remain associated with v3 or should the items list contain a pair that was not in the original insertion list, (0, v3)?
The second one is a bit weird because a key "loses its place" whenever the value is updated.
IIRC, previous discussions showed an interest in odicts but that there were a lot of questions of the specific semantics of the API. This would no doubt be compounded by attempts to emulate dict views. Regardless, there should probably be a PEP and alternate pure python versions should be posted on ASPN so people can try them out. post
Raymond
The same problem happens with dictionary updates: d = {} d[k1] = v1 d[k2] = v2 d[k1] = v3 The last instruction just replaces the existing entry, so I'm +0 for the first result. Cesare
From: "Cesare Di Mauro" <cesare@pronto.it>
The same problem happens with dictionary updates:
d = {} d[k1] = v1 d[k2] = v2 d[k1] = v3
The last instruction just replaces the existing entry, so I'm +0 for the first result.
There's a difference. With dicts, the third insertion *replaces* the value while leaving data structure unmolested. Also, the key doesn't update (an equal but identical key doesn't get substituted). With an odict that preserves insertion order, you're talking about *deleting* the old entry and *appending* the new one, complete with both the new key and new value. If that is the desired behavior, then it becomes impossible to update the value of an odict entry while leaving its insertion order unchanged. What a bummer. An alternative behavior is to replace the value, leaving the key in its original position. But then, you've messed-up the expectation that v2 occurs before v3 eventhough v3 was inserted later. This is especially weird because you keep k1 which was inserted earlier, not k3 which is equivalent but not necessarily identical. Neither behavior is de facto, TheRightWay(tm). Each has its uses. Each has its oddities. Each will have its fans who find that particular way to be the best and most intuitive. One other issue arises if you choose the approach where updating a value triggers re-ordering -- the the dict view concept no longer translates very well. With regular dicts, you can update values while iterating. Losing that would be a bummer too. I don't favor one over the other. Am just pointing-out that the proposal is a little more complex than simply wishing for an ordered verion of a dictionary and expecting that that wish is self-defining in a way the matches everyone's intuition, use cases, and expectations. Raymond
Raymond Hettinger wrote:
I don't favor one over the other. Am just pointing-out that the proposal is a little more complex than simply wishing for an ordered verion of a dictionary and expecting that that wish is self-defining in a way the matches everyone's intuition, use cases, and expectations.
If you have an odict with first-insertion ordering, it's fairly trivial to convert it to a dictionary with last-insertion ordering: class odictlastinsertion(odict): def __setitem__(self, k, v): self.pop(k, None) self[k] = v As you note, going the other way would be rather difficult, suggesting that the version ordered by the first key insertion is the more fundamental structure. A PEP would definitely be needed to thrash out those kind of issues and decisions though Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia --------------------------------------------------------------- http://www.boredomandlaziness.org
On Sun, Jun 15, 2008 at 1:03 AM, Nick Coghlan <ncoghlan@gmail.com> wrote:
Raymond Hettinger wrote:
I don't favor one over the other. Am just pointing-out that the proposal is a little more complex than simply wishing for an ordered verion of a dictionary and expecting that that wish is self-defining in a way the matches everyone's intuition, use cases, and expectations.
If you have an odict with first-insertion ordering, it's fairly trivial to convert it to a dictionary with last-insertion ordering:
class odictlastinsertion(odict): def __setitem__(self, k, v): self.pop(k, None) self[k] = v
As you note, going the other way would be rather difficult, suggesting that the version ordered by the first key insertion is the more fundamental structure.
A PEP would definitely be needed to thrash out those kind of issues and decisions though
Right. Though on this particular issue, my gut instinct tells me that first-insertion-order is more useful (matching your assertion above). -- --Guido van Rossum (home page: http://www.python.org/~guido/)
On Sun, 2008-06-15 at 00:12 -0700, Raymond Hettinger wrote:
From: "Cesare Di Mauro" <cesare@pronto.it>
The same problem happens with dictionary updates:
d = {} d[k1] = v1 d[k2] = v2 d[k1] = v3
The last instruction just replaces the existing entry, so I'm +0 for the first result.
There's a difference. With dicts, the third insertion *replaces* the value while leaving data structure unmolested. Also, the key doesn't update (an equal but identical key doesn't get substituted).
With an odict that preserves insertion order, you're talking about *deleting* the old entry and *appending* the new one, complete with both the new key and new value. If that is the desired behavior, then it becomes impossible to update the value of an odict entry while leaving its insertion order unchanged. What a bummer.
An alternative behavior is to replace the value, leaving the key in its original position. But then, you've messed-up the expectation that v2 occurs before v3 eventhough v3 was inserted later. This is especially weird because you keep k1 which was inserted earlier, not k3 which is equivalent but not necessarily identical.
An other behavior making sense would be to append a new position for the key. With your example above: d.index(k1) = [0, 2] d.index(k2) = [1, ] Deletion of a key would have to be explicit (and delete all associated indexes). An other way to think of such a structure would be as a list, for which each item would also have an associated key. I think someone mentioned the link with a list during this thread, but here I am not referring to implementation, but the feature of a container-like class that would allow to access elements either by position (index), and that would be a one-to-one association, or key, and that would be a one-to-possibly-many association.
Neither behavior is de facto, TheRightWay(tm). Each has its uses. Each has its oddities. Each will have its fans who find that particular way to be the best and most intuitive.
One other issue arises if you choose the approach where updating a value triggers re-ordering -- the the dict view concept no longer translates very well. With regular dicts, you can update values while iterating. Losing that would be a bummer too.
I don't favor one over the other. Am just pointing-out that the proposal is a little more complex than simply wishing for an ordered verion of a dictionary and expecting that that wish is self-defining in a way the matches everyone's intuition, use cases, and expectations.
Raymond
_______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/lgautier%40gmail.com
On Sun, 15 Jun 2008 06:42:32 pm laurent wrote:
An other way to think of such a structure would be as a list, for which each item would also have an associated key. I think someone mentioned the link with a list during this thread, but here I am not referring to implementation, but the feature of a container-like class that would allow to access elements either by position (index), and that would be a one-to-one association, or key, and that would be a one-to-possibly-many association.
I think the quickest way to kill this proposal again will be to start overloading it with more and more complicated behaviour. Python dicts are one-to-one (ignoring edge cases like dict[1] vs dict[1.0]). If you want one-to-many, you can subclass dict and get that behaviour. I think that an ordered dict in the standard library should follow the same philosophy: define the simplest, most fundamental behaviour which is an ordered dictionary, and then let people sub-class it to make more complicated types. So I vote -1 on one-to-many associations, and +1 to one-to-one like regular dicts. As for a API to access items by position rather than by key, I'm neutral on it. You can always get the nth key by extracting the keys into a list. Provided it doesn't become a point of contention, then I'm +0 on giving the ordered dict index-based methods in addition to the key-based methods, but if it becomes a sticking point and puts the whole concept in jeopardy, then I vote -1 on the index-based API. This applies also to slicing. -- Steven
On Sun, 15 Jun 2008 05:12:38 pm Raymond Hettinger wrote:
With an odict that preserves insertion order, you're talking about *deleting* the old entry and *appending* the new one, complete with both the new key and new value.
I certainly don't consider updating an ordered dictionary entry as a deletion followed by an append. In fact, I'd be very surprised, and dismayed, if that was the default behaviour. Conceptually, I would expect the following behaviour:
od = odict() od[1] = 'spam' # insert a new key od[2] = 'parrot' # insert a new key od[1] = 'ham' # modify existing key od.items() [(1, 'ham'), (2, 'parrot')]
If I wanted the alternative behaviour, I could easily get it:
od = odict() od[1] = 'spam' # insert a new key od[2] = 'parrot' # insert a new key od.pop(1, None); od[1] = 'ham' # remove and re-insert a key od.items() [(2, 'parrot'), (1, 'ham')]
Earlier, Raymond also asked what to do about keys with equal but not identical keys. Since I consider setting the value to be an update rather than a deletion plus re-insertion, then the behaviour is obvious.
od = odict([(1, 'norwegian blue'), (2, 'parrot')]) od[1.0] = 'norwegian red' od.items() [(1, 'norwegian red'), (2, 'parrot')]
This is close to the behaviour of regular dicts, and to do differently would be very surprising to me. Again, anyone who wants the alternative behaviour can get it easily, with a pop and a set. +1 for an ordered dictionary. As for a sorted dictionary, I don't care much, so +0. You can always sort the keys when you need them. -- Steven
Steven D'Aprano <steve <at> pearwood.info> writes:
Conceptually, I would expect the following behaviour:
od = odict() od[1] = 'spam' # insert a new key od[2] = 'parrot' # insert a new key od[1] = 'ham' # modify existing key od.items() [(1, 'ham'), (2, 'parrot')] That behavior is different to any ordered-dict implementation out there ;-)
Regards, Armin
On Sun, 15 Jun 2008 07:39:05 pm Armin Ronacher wrote:
Steven D'Aprano <steve <at> pearwood.info> writes:
Conceptually, I would expect the following behaviour:
od = odict() od[1] = 'spam' # insert a new key od[2] = 'parrot' # insert a new key od[1] = 'ham' # modify existing key od.items()
[(1, 'ham'), (2, 'parrot')]
That behavior is different to any ordered-dict implementation out there ;-)
I beg to differ. It's the same behaviour as in this implementation: http://dev.pocoo.org/hg/sandbox/raw-file/tip/odict.py which I understand was written by you. -- Steven
Sorry to pipe in so late, but this is actually the default behaviour of my C implementation (which I call KIO (Key Insertion Order), there is an option to change this to KVIO (Key (or) Value Insertion Order), which moves the pair to the end. Anthon Armin Ronacher wrote:
Steven D'Aprano <steve <at> pearwood.info> writes:
Conceptually, I would expect the following behaviour:
od = odict() od[1] = 'spam' # insert a new key od[2] = 'parrot' # insert a new key od[1] = 'ham' # modify existing key od.items() [(1, 'ham'), (2, 'parrot')] That behavior is different to any ordered-dict implementation out there ;-)
Regards, Armin
_______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/anthon%40mnt.org
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Jun 15, 2008, at 1:43 AM, Raymond Hettinger wrote:
For an insertion order dictionary, there was also a question about how to handle duplicate keys.
Given odict([(k1,v1), (k2,v2), (k1,v3)]), what should the odict.items() return?
[(k1,v3), (k2,v2)] [(k2,v2), (k1,v3)]
The first maintains the original sort order and is consistent with the usual idea that d[k]=v simply replaces the value but does not alter the hash table. It is a bit weird though because v3 appears earlier than v2 which was inserted earlier. It's especially weird for keys that are equal but not identical: d[0]=v1 d[0.0]=v3. Do you want 0.0 to remain associated with v3 or should the items list contain a pair that was not in the original insertion list, (0, v3)?
The second one is a bit weird because a key "loses its place" whenever the value is updated.
Heh, neither of these would work for the email package's own flavor of "ordered" dictionary. Its .items() will return all three key/val pairs, but it's __getitem__ interface would only return the first two, and there are additional interfaces exposed for .get_all() (which is like .get() but returns a list of values matching the given key). Okay, so email couldn't use whatever stdlib odict gets added, but I think that just shows that this may not be as fundamental a data structure as we think it is. I'd much rather see a package on the cheeseshop gain overwhelming popularity, practically forcing us to include it in the stdlib. - -Barry -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (Darwin) iQCVAwUBSFUEpHEjvBPtnXfVAQIj9QQAtuvlC5YtcSBsddztqD8kwokSrvKz7Nef oM0JpxjVBQ7oT0F9MnWEvu9Rf8aTVdXsR/zWTf0yw1jt4HtM50Yu4RGqyjghFJ/Z +Gz+hAqyCerJE6Y9AlW4UdJbQ47wD/Sp1AbMafHCubbt3Sp1AxKmr1tN84WAFefw 8rkP6LbpP64= =dwAi -----END PGP SIGNATURE-----
On Sun, Jun 15, 2008 at 6:01 AM, Barry Warsaw <barry@python.org> wrote:
On Jun 15, 2008, at 1:43 AM, Raymond Hettinger wrote:
The second one is a bit weird because a key "loses its place" whenever the value is updated.
Heh, neither of these would work for the email package's own flavor of "ordered" dictionary. Its .items() will return all three key/val pairs, but it's __getitem__ interface would only return the first two, and there are additional interfaces exposed for .get_all() (which is like .get() but returns a list of values matching the given key).
Okay, so email couldn't use whatever stdlib odict gets added, but I think that just shows that this may not be as fundamental a data structure as we think it is. I'd much rather see a package on the cheeseshop gain overwhelming popularity, practically forcing us to include it in the stdlib.
+1 on this comment, -0 on adding an ordered dict to 2.6/3.0. An ordered (or sorted) dict seems to be more of a gut reaction. They have some data in a dict, they realize they want it ordered/sorted for some purpose, so the first thing they check is if the dict already provides it. It doesn't, but putting together a combination of a dict and a list is often a fair bit of work - nevermind if you want O(1) removal - so we hear about it in the mean time. But my point is that we we need to focus on finding real use cases and exploring how best to solve them. Otherwise we might as well throw in my OrderedSet[1] as-is, despite that it's got no comments and no ratings. Even I don't seem to use it. Everybody has an opinion on the colour of this bikeshed. [1] http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/528878 -- Adam Olsen, aka Rhamphoryncus
But my point is that we we need to focus on finding real use cases and exploring how best to solve them. Otherwise we might as well throw in my OrderedSet[1] as-is, despite that it's got no comments and no ratings. Even I don't seem to use it.
I'm mostly lurking on these threads, so as to be semi-prepared when new versions come out.. in fifty years, since we *just* migrated from 2.3 to 2.4 on our product, so. :) Anyways, we've had an OrderedDictionary sort of implementation in our library for eons. The product is commercial and a mix between a desktop application and a web one, with an application server and cross-platform availability... so there's a slightly bizarre and wide range of uses that we've found for putting ordered dictionaries to. If some various use-cases and our reasoning helps, here it is. If not, ignore :) - One is that the system is modular, with various parts able to be activated or deactivated in configuration. The order of module load is important, as we've never quite bothered to put in automatic dependency checking -- that's just overboard for us. Further, the modules can't really be referred to each other via "import" or in code, but instead need to go through a layer of indirection through a name-- so-- the system maintains an ordered dict of modules, a la sys.modules, with the order determining load when it goes through to initialize itself. - There's several more places with a similar pattern; a mapping between "Component Name" and "Module" for generic systems. A processing host which is meant to be able to load and run any kind of service or task. - There's several places where a user is configuring a slightly complex set of actions-- he gives these actions a name, which is shown to the user, and then we have the configuration options itself we use if that is chosen. Its just natural/easy to store that in an ordered dict after we pull it out of the DB, as we want its order to be whatever the user chooses in their setup, and the key->value association is clear. - In a modular application with a generic outer interface(meaning the main app can't even fathom what all it might be asked to load), there's things like a "Windows" menu item that's easily stored internally as a mapping between window names and the window object itself, so the menu can be readily re-generated at will and the window found to switch to. - In fact, we use a lot of OrderedDictionaries as a part of that UI to data/configuration mapping, come to think of it. We know the order of "fields" that someone can search on in the database in advance, and have them written into the searchUI code as an ordered dict because it just works nicely. The keys() become a drop-down list, the value a structure identifying to the central server what field it is they're searching on. - Fiiinally (sorta), we find passing ordered dictionaries to our Genshi web templating layer very lovely for making easy-designable web templates for the web client. We even let customers edit them sometimes! Basically, after looking at all of these, my impressions of an "ordered dictionary" for the various use cases we use are: - The ordered dictionary is used almost exclusively in situations where we are getting the order implicitly from some other source. Be it a SQL query (with its own ORDER BY statements), a configuration option, the order of lines in a file, an auto-sequenced table, or hard-coded data.... Thus, we've always found "insertion order" to be important. - Much to my surprise, we actually aren't ever using an ordered dictionary in a situation where the value ends up being modified after the dictionary is loaded. - The only time we use dictionaries where we are updating them after the fact and their order is -expected- to change is when we are using a *sorted* dictionary. - As such, I'd be quite surprised if I was updating the value of an ordered dictionary and it were to change its order. Meaning:
d = odict() d["hello"] = 1 d["there"] = 2 d["hello"] = 3 d.keys() ['hello', 'there']
And not: ['there', 'hello'] An ordered dictionary that does not simply preserve initial insertion order strikes me as a *sorted* dictionary-- sorting on insertion time. I'd expect a sorted dictionary to shift itself around as appropriate. I'd not expect an ordered dictionary to change the order without some explicit action. To me, "ordered dictionary" is in fact a *preordered* dictionary. The order is defined before the data in, and the dictionary's job is to just preserve it. Anyways. No idea if that'll help the discussion, but a couple people kept talking about use cases :) --Stephen P.S. Our implementation, incidentally, is essentially the same as one mentioned above though its subclassing from UserDict (historical reasons for now). We just track the keys in _keys, and if someone's setting something in the dictionary not in keys, we append. It seemed the most natural/obvious way to do it.
Talin wrote:
In some cases, the term is used to mean a dictionary that remembers the order of insertions, and in other cases it is used to mean a sorted dict,
I would be more in favor of the idea if we could come up with a less ambiguous naming scheme.
Perhaps "indexed list" or maybe "keyed list" would be a better term for the first variety. And "sorted dict" seems like a good enough term for the other one. -- Greg
Hi, Armin Ronacher <armin.ronacher <at> active-4.com> writes:
To fight that problem I want to proposed a new class in "collections" called odict which is a dict that keeps the items sorted, similar to a PHP array.
I'm also +1 on this. I've used the implementation you mentioned in a compiler project of mine and found it to be quite useful. It is hard for me to mention any other uses but there definitely are many occasions where people need them and either go for (key, value)-tuples or use some lib which does only provide this single data type. I am pretty optimistic that the addition will find its usecases, once it is in the stdlib. regards, Marek
* Armin Ronacher wrote:
Some reasons why ordered dicts are a useful feature:
- in XML/HTML processing it's often desired to keep the attributes of an tag ordered during processing. So that input ordering is the same as the output ordering.
- Form data transmitted via HTTP is usually ordered by the position of the input/textarea/select field in the HTML document. That information is currently lost in most Python web applications / frameworks.
- Eaiser transition of code from Ruby/PHP which have sorted associative arrays / hashmaps.
- Having an ordered dict in the standard library would allow other libraries support them. For example a PHP serializer could return odicts rather then dicts which drops the ordering information. XML libraries such as etree could add support for it when creating elements or return attribute dicts.
I find this collection of cases pretty weak as an argument for implementing that in the stdlib. A lot of special purpose types would fit into such reasoning, but do you want to have all of them maintained here? nd -- Da fällt mir ein, wieso gibt es eigentlich in Unicode kein "i" mit einem Herzchen als Tüpfelchen? Das wär sooo süüss! -- Björn Höhrmann in darw
On Sat, Jun 14, 2008 at 4:57 PM, André Malo <nd@perlig.de> wrote:
* Armin Ronacher wrote:
Some reasons why ordered dicts are a useful feature:
- in XML/HTML processing it's often desired to keep the attributes of an tag ordered during processing. So that input ordering is the same as the output ordering.
- Form data transmitted via HTTP is usually ordered by the position of the input/textarea/select field in the HTML document. That information is currently lost in most Python web applications / frameworks.
- Eaiser transition of code from Ruby/PHP which have sorted associative arrays / hashmaps.
- Having an ordered dict in the standard library would allow other libraries support them. For example a PHP serializer could return odicts rather then dicts which drops the ordering information. XML libraries such as etree could add support for it when creating elements or return attribute dicts.
I find this collection of cases pretty weak as an argument for implementing that in the stdlib. A lot of special purpose types would fit into such reasoning, but do you want to have all of them maintained here?
No, but an ordered dict happens to be a *very* common thing to need, for a variety of reasons. So I'm +0.5 on adding this to the collections module. However someone needs to contribute working code. It would also be useful to verify that it actually fulfills the needs of some actual use case. Perhaps looking at how Django uses its version would be helpful. -- --Guido van Rossum (home page: http://www.python.org/~guido/)
Guido van Rossum <guido <at> python.org> writes:
On Sat, Jun 14, 2008 at 4:57 PM, André Malo <nd <at> perlig.de> wrote:
I find this collection of cases pretty weak as an argument for implementing that in the stdlib. A lot of special purpose types would fit into such reasoning, but do you want to have all of them maintained here?
No, but an ordered dict happens to be a *very* common thing to need, for a variety of reasons. So I'm +0.5 on adding this to the collections module. However someone needs to contribute working code. It would also be useful to verify that it actually fulfills the needs of some actual use case. Perhaps looking at how Django uses its version would be helpful.
I compared multiple ordered dicts now (including Babel, Django and the C-implementation I mentioned earlier) and implemented a python version of the ordered dict as reference implementation: http://dev.pocoo.org/hg/sandbox/raw-file/tip/odict.py Regards, Armin
I compared multiple ordered dicts now (including Babel, Django and the C-implementation I mentioned earlier) and implemented a python version of the ordered dict as reference implementation:
I find the slicing API surprising. IMO, if you do support slicing, then a) the start and end indices should be the same ones that you also use in regular indexing. b) the result should be of the same kind as the thing being sliced, i.e. an odict. So I would rather expect
d['c':'spam'] odict.odict([('c', 'd'), ('foo', 'bar')])
The slicing operation that you provide should be spelled as d.items()[1:3], or, if you don't want to pay the cost of creating the full items list, then add a method such as d.slice_by_index(1,3). What's the use case for this operation, anyway? Regards, Martin
Martin v. Löwis <martin <at> v.loewis.de> writes:
I compared multiple ordered dicts now (including Babel, Django and the C-implementation I mentioned earlier) and implemented a python version of the ordered dict as reference implementation:
I find the slicing API surprising. IMO, if you do support slicing, then a) the start and end indices should be the same ones that you also use in regular indexing. b) the result should be of the same kind as the thing being sliced, i.e. an odict.
So I would rather expect
d['c':'spam'] odict.odict([('c', 'd'), ('foo', 'bar')])
The slicing operation that you provide should be spelled as d.items()[1:3], or, if you don't want to pay the cost of creating the full items list, then add a method such as d.slice_by_index(1,3). What's the use case for this operation, anyway?
The use case in my particular case is a ordered dict for messages of a .po file I want to display page-wise in an application. However I agree that it's not useful most of the time so dropping it makes sense. If an application really needs slicing it can still subclass it and implement that. Furthermore with dict-views in Python 3 it would be possible to implement an efficient slicing operation on the dict view returned. Regards, Armin
* Guido van Rossum wrote:
On Sat, Jun 14, 2008 at 4:57 PM, André Malo <nd@perlig.de> wrote:
* Armin Ronacher wrote:
Some reasons why ordered dicts are a useful feature:
- in XML/HTML processing it's often desired to keep the attributes of an tag ordered during processing. So that input ordering is the same as the output ordering.
- Form data transmitted via HTTP is usually ordered by the position of the input/textarea/select field in the HTML document. That information is currently lost in most Python web applications / frameworks.
- Eaiser transition of code from Ruby/PHP which have sorted associative arrays / hashmaps.
- Having an ordered dict in the standard library would allow other libraries support them. For example a PHP serializer could return odicts rather then dicts which drops the ordering information. XML libraries such as etree could add support for it when creating elements or return attribute dicts.
I find this collection of cases pretty weak as an argument for implementing that in the stdlib. A lot of special purpose types would fit into such reasoning, but do you want to have all of them maintained here?
No, but an ordered dict happens to be a *very* common thing to need, for a variety of reasons. So I'm +0.5 on adding this to the collections module. However someone needs to contribute working code. It would also be useful to verify that it actually fulfills the needs of some actual use case. Perhaps looking at how Django uses its version would be helpful.
FWIW, I'm working a lot in the contexts described above and I never needed ordered dicts so far (what do I have to do in order to need them?). I've found myself implementing, for example, mutlivaluedicts instead, several times. nd -- Real programmers confuse Christmas and Halloween because DEC 25 = OCT 31. -- Unknown (found in ssl_engine_mutex.c)
On Jun 14, 2008, at 8:26 PM, Guido van Rossum wrote:
No, but an ordered dict happens to be a *very* common thing to need, for a variety of reasons. So I'm +0.5 on adding this to the collections module. However someone needs to contribute working code.
Here's an LRU cache that I've used a few times over the years: http://allmydata.org/trac/pyutil/browser/pyutil/pyutil/cache.py This is just like a dict ordered by insertion, except: 1. That it removes the oldest entry if it grows beyond a limit. 2. That it moves an entry to the head of the queue when has_key() is called on that item. So, it would be easy to change those two behaviors in order to use this implementation. There are actually three implementations in that file: one that is asymptotically O(1) for all operations (using a double-linked list woven into the values of the dict), and one that uses a Python list to hold the order, so it is faster for small enough dicts. The third implementation is an implementation that someone else wrote that I included just for comparison purposes -- the comparison showed that each of mine was better. Regards, Zooko
On Jun 15, 2008, at 12:20 PM, zooko wrote:
So, it would be easy to change those two behaviors in order to use this implementation. There are actually three implementations in that file: one that is asymptotically O(1) for all operations (using a double-linked list woven into the values of the dict), and one that uses a Python list to hold the order, so it is faster for small enough dicts.
P.S. I didn't mean to fall for the common misunderstanding that hash table operations are O(1). What I should have written is that my ordered dict technique *adds* only O(1) time to the time of the dict on which it is built. As to the question of how important or common this data structure is, I have to admit that while I implemented this one and used it several times (always exclusively for LRU caching), I currently don't use it for anything. Nowadays I try to avoid doing transparent caching (such as LRU caches are often used for) in favor of explicit management of the resource. Regards, Zooko
On Sat, Jun 14, 2008 at 11:39 PM, Armin Ronacher <armin.ronacher@active-4.com> wrote:
Some reasons why ordered dicts are a useful feature:
And for metaclasses or for LRU caches or for removing duplicates in a list while maintaining order. I think that the name ordereddict would be more readable though, and match the existing defaultdict class in the collections module. -- mvh Björn
BJörn Lindqvist <bjourne <at> gmail.com> writes:
I think that the name ordereddict would be more readable though, and match the existing defaultdict class in the collections module. While I agree that "ordered" makes more sense, it's pretty stupid to type with two 'd's right after another.
Regards, Armin
On 14-Jun-08, at 8:39 PM, Armin Ronacher wrote:
... I noticed lately that quite a few projects are implementing their own subclasses of `dict` that retain the order of the key/value pairs. ... I'm +1 on this one too, as there are at least a couple of times in recent memory when I would have found this useful.
And, as far as questions about the definition of an ordered dictionary, is there any good reason not to simply treat the dict as a list? Something like (with the obvious bits left out): class odict(dict): def __init__(self, *args): self._order = [] def __setitem__(self, key, val): if key not in self: self._order.append(key) def __iter__(self): return self._order def items(self): return ([item, self[item] for item in self._order]) def sort(self): self._order.sort() ... and so on ... That way all the order-related functions are well defined, so it would be hard claim that it doesn't do the "right thing" without claiming that lists don't do the "right thing".
On Sun, 15 Jun 2008 02:59:51 pm David Wolever wrote:
And, as far as questions about the definition of an ordered dictionary, is there any good reason not to simply treat the dict as a list? Something like (with the obvious bits left out):
Yes. (1) If you implement the ordered dict as a list of key/value pairs, then you get order for free, but searching is slow, and so is deletion. If we wanted O(N) searches, we'd just use a list of tuples :) (2) If you implement it as a hash table plus a list of keys in insertion order, then searching the dict is fast, but deletions are slow. Also you double (?) the amount of memory needed for the keys. On the other hand... a tree-based implementation would require more work, and many more decisions (what kind of tree?), would lose the O(1) behaviour of the hash table, and may end up using just as much memory. So I wouldn't discount your suggestion. -- Steven
On Jun 14, 4:39 pm, Armin Ronacher <armin.ronac...@active-4.com> wrote:
- in XML/HTML processing it's often desired to keep the attributes of an tag ordered during processing. So that input ordering is the same as the output ordering.
Munging XML is a niche.
- Form data transmitted via HTTP is usually ordered by the position of the input/textarea/select field in the HTML document. That information is currently lost in most Python web applications / frameworks.
If you don't like the fact that your web application framework loses the order of its key:value pairs relative to the page, then you should bring it up with the developers. Ordered dicts, dicts that remember the chronological order of their insertion, don't sound generally useful. In contrast, sorted dicts sound appealing, but I can't think of any use cases where sorted(mydict.keys()) fails to be effective; it seems to me the main advantage of a sorted dict is that you don't have to remember to sort the keys every time you want to use them.
Additionally it would support slicing where a list of key, value tuples is returned and sort/reverse/index methods that work like their list equivalents. Index based lookup could work via odict.byindex().
Slicing tuples, lists, and strings return objects of the same type, so slicing a sorted dict should return a sorted dict. A sorted dict is the same data structure as a Berkeley DB table. Why not use the term 'table' instead of 'sorteddict'? Unless I am missing something big, the implementation of new key insert for sorteddict looks inefficient - on average you have to move half of your elements over one space. A B tree or B+ tree (or other tree) would be a more efficient algorithm. -1 for ordered dict +1 for sorted dict David
dbpokorny@gmail.com wrote:
-1 for ordered dict +1 for sorted dict
Build the ordered dict, then sort it in-place afterwards, just like a list (alternatively, build a normal dict then feed sorted(orig.items()) to the ordered dict constructor). The point of an ordered dict is that unlike a normal dict, the order the keys are returned is well defined at the interface level, rather than arbitrary and implementation-defined. David Wolever's example of a normal dict() with an associated key list is an excellent way of thinking about the proposed semantics. Having a fast ordered dict in the standard library also opens up the possibility of eventually using such a thing for keyword arguments at some point in the future. How nice would it be to be able to just write: t = namedtuple(a=1, b=2, c=3) instead of: c = namedtuple("a b c") t = c(a=1, b=2, c=3) Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia --------------------------------------------------------------- http://www.boredomandlaziness.org
dbpokorny <at> gmail.com <dbpokorny <at> gmail.com> writes:
If you don't like the fact that your web application framework loses the order of its key:value pairs relative to the page, then you should bring it up with the developers.
Who will then point up that to retain that order while providing you with a dict-like API, they need to write some kind of ordered dict implementation. Then you'll complain that their implementation is sub-optimal and isn't 100% compatible with the original dict API, and post on python-dev to ask that a standard odict implementation is considered for the stdlib.
Ordered dicts, dicts that remember the chronological order of their insertion, don't sound generally useful.
They are generally useful in any case where you want to handle key-value pairs while not confusing a human operator by messing up the original order. Think e.g. configuration files. A common complaint against ConfigParser is that writing a configuration file does not preserve the order of the original file, which is harmless for the computer but very annoying for the human being who maintains that file. As for sorted dicts with general O(log(n)) behaviour, you could try to combine the blist type (http://pypi.python.org/pypi/blist/) with the standard bisect module and see what that gives.
At 02:19 PM 6/15/2008 +0000, Antoine Pitrou wrote:
Ordered dicts, dicts that remember the chronological order of their insertion, don't sound generally useful.
They are generally useful in any case where you want to handle key-value pairs while not confusing a human operator by messing up the original order. Think e.g. configuration files. A common complaint against ConfigParser is that writing a configuration file does not preserve the order of the original file, which is harmless for the computer but very annoying for the human being who maintains that file.
You don't need an ordered dictionary for that; you need a save routine that stream-edits the old file contents. That way, you don't lose comments and spacing either. As for the other uses for ordered dictionaries, I find it simplest to just use a list of key,value pairs, and only transform it to a dictionary or dictionary-like structure as needed, using tools like the cgi module, the email package, or wsgiref.headers.
Phillip J. Eby <pje <at> telecommunity.com> writes:
As for the other uses for ordered dictionaries, I find it simplest to just use a list of key,value pairs, and only transform it to a dictionary or dictionary-like structure as needed, using tools like the cgi module, the email package, or wsgiref.headers.
What you are saying is that there are already generally useful container types in the stdlib, but isn't it a good argument in favor of ripping them out of domain-specific packages and provide them as generic classes in the collections module? Someone never using cgi or wsgiref wouldn't know that some of the code there can be useful for other purposes.
At 02:34 PM 6/15/2008 +0000, Antoine Pitrou wrote:
Phillip J. Eby <pje <at> telecommunity.com> writes:
As for the other uses for ordered dictionaries, I find it simplest to just use a list of key,value pairs, and only transform it to a dictionary or dictionary-like structure as needed, using tools like the cgi module, the email package, or wsgiref.headers.
What you are saying is that there are already generally useful container types in the stdlib, but isn't it a good argument in favor of ripping them out of domain-specific packages and provide them as generic classes in the collections module?
Someone never using cgi or wsgiref wouldn't know that some of the code there can be useful for other purposes.
I didn't say I used them for other purposes, or that they were generally useful. Rather, they're specifically useful for the things they're useful for. More often than not, the use case calls for not merely ordering, but ordering of *values*, with multiple values for each key. But the precise API desired for manipulating such structures tends to be highly app-specific (like email, CGI form values, HTTP headers, etc.), so it's actually IMO an argument *against* a general odict type.
There are far more responses for that topic than I imagined so I would love to write a PEP about that topic, incorporating the ideas/questions and suggestions discussed here. Regards, Armin
From: "Armin Ronacher" <armin.ronacher@active-4.com>
There are far more responses for that topic than I imagined so I would love to write a PEP about that topic, incorporating the ideas/questions and suggestions discussed here.
Instead of going straight to a PEP, I recommend opening a new wiki page on the topic, letting people post sample pure python implementations, pros/cons of various APIs, showing sample use cases, and analyzing the O(n) behavior of various implementation strategies. As a reference point, the collections.namedtuple() recipe was much simpler but took over six months to mature. Its development process started by combining the best of all previously posted attempts at the same thing, then it was exercised heavily in real apps, then it was posted on ASPN and underwent significant improvements based on feedback from a number of expert developers. Then, it was proposed on python-dev and improved again based on feedback received there. Upon writing the docs and creating examples, more refinements ensued. Upon applying it to the standard library, more was learned. After the alpha, we started getting user feedback and it got refined even further. Raymond
2008/6/15 Raymond Hettinger <python@rcn.com>:
From: "Armin Ronacher" <armin.ronacher@active-4.com>
There are far more responses for that topic than I imagined so I would love to write a PEP about that topic, incorporating the ideas/questions and suggestions discussed here.
Instead of going straight to a PEP, I recommend opening a new wiki page on the topic, letting people post sample pure python implementations, pros/cons of various APIs, showing sample use cases, and analyzing the O(n) behavior of various implementation strategies.
That sounds reasonable. I'm +1 in principle, but would like to see the details thrashed out. BTW, as a meta-question, where is this proposal targeted for? I'd assume 2.6/3.0 are closed now, as we're hitting betas - so are we looking at 2.7/3.1? (Just a quick sanity check on the timing...) Paul.
Armin Ronacher <armin.ronacher <at> active-4.com> writes:
There are far more responses for that topic than I imagined so I would love to write a PEP about that topic, incorporating the ideas/questions and suggestions discussed here.
There is now a PEP for the ordered dict: - PEP: http://www.python.org/dev/peps/pep-0372/ - Thread on comp.lang.python: http://thread.gmane.org/gmane.comp.python.general/577894 Regards, Armin
Armin Ronacher wrote:
Armin Ronacher <armin.ronacher <at> active-4.com> writes:
There are far more responses for that topic than I imagined so I would love to write a PEP about that topic, incorporating the ideas/questions and suggestions discussed here.
There is now a PEP for the ordered dict:
- PEP: http://www.python.org/dev/peps/pep-0372/ - Thread on comp.lang.python: http://thread.gmane.org/gmane.comp.python.general/577894
Another use case: in 2.6, RawConfigParser accepts a dict_type argument that allows an application to set the type of dictionary used internally. The motivation for this addition was expressly to allow users to provide an ordered dictionary [1]. Cheers, Nick. [1] http://bugs.python.org/issue1371075 -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia --------------------------------------------------------------- http://www.boredomandlaziness.org
Armin Ronacher wrote:
- in XML/HTML processing it's often desired to keep the attributes of an tag ordered during processing. So that input ordering is the same as the output ordering.
- [...] XML libraries such as etree could add support for it when creating elements or return attribute dicts.
I hope that what you call "etree" here (I assume you mean ElementTree) would stay compatible to lxml.etree in that case. Meaning: adding or replacing an attribute removes a possibly existing entry and appends the new value at the end. Stefan
It is possible to get both ordered dict and sorted dict semantics in the same type if you replace (key, value) pairs for dictionary entries with (key,value,order) triples. The third component is a value that indicates the place of the entry relative to the other entries. To get an ordered dict, __setitem__ assigns 1+ max(order) to the new entry's order. To get a sorted dict, order = key. To get a dict sorted by some key function, order = keyfunc(key), etc... David
dbpokorny@gmail.com writes:
It is possible to get both ordered dict and sorted dict semantics in the same type if you replace (key, value) pairs for dictionary entries with (key,value,order) triples.
Roundup uses something like this concept for its value choice menus. I don't actually think it's used, though, except as a way to allow admin user input that inserts an item at a position.
participants (28)
-
"Martin v. Löwis" -
Adam Olsen -
Alexander Schremmer -
André Malo -
Anthon van der Neut -
Antoine Pitrou -
Armin Ronacher -
Barry Warsaw -
BJörn Lindqvist -
Cesare Di Mauro -
David Wolever -
dbpokorny＠gmail.com -
Greg Ewing -
Guido van Rossum -
Hasan Diwan -
laurent -
Marek Kubica -
Michael Foord -
Nick Coghlan -
Paul Moore -
Phillip J. Eby -
Raymond Hettinger -
Stefan Behnel -
Stephen Hansen -
Stephen J. Turnbull -
Steven D'Aprano -
Talin -
zooko