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

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.