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

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

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

Raymond Hettinger 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

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

In data 15 giugno 2008 alle ore 07:43:32, Raymond Hettinger 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

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, 2008-06-15 at 00:12 -0700, Raymond Hettinger wrote:

From: "Cesare Di Mauro"

...

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

On Sun, 15 Jun 2008 07:39:05 pm Armin Ronacher wrote:

Steven D'Aprano 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

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

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.

On Sat, Jun 14, 2008 at 4:57 PM, André Malo 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/)

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

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

* Guido van Rossum wrote:

On Sat, Jun 14, 2008 at 4:57 PM, André Malo 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 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

BJörn Lindqvist 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 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

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

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.

At 02:34 PM 6/15/2008 +0000, Antoine Pitrou wrote:

Phillip J. Eby 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.

From: "Armin Ronacher"

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

Armin Ronacher 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

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.