Antoon Pardon <[EMAIL PROTECTED]> wrote: > On 2007-09-27, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > >> Is this a practical use case? When are sequential visits of all >> elements in order frequently suspended to make insertions and >> deletions, with a need for efficient lookup by key? > > Does it need to be a sequential visit of *all* elements? > > Suppose you have a mapping of start times to tasks. You can then want > to iterate over all tasks that need to be started between noon en 4 pm > next monday. If you have a hashtable you still will need to sort all > the keys even if you will visit only 10%. If you have a tree you can > just visit the specified keys. > It still depends on the exact pattern of use. If you have an implementation which tracks additions and deletions and sorts them into the list when required (as we came up with earlier) then this is much more efficient that re-sorting the whole list every time. Sorting a large sorted list with a few unsorted elements on the end is comparable to inserting the elements individually into a tree, and you still have the hashtable benefits on accessing elements to help level the playing field.
For me though, the most convincing use-case for a sorted dictionary is one that I don't think has been mentioned yet: There are situations when you want to use a dictionary with existing library code that doesn't care about the random key ordering, but you have additional requirements which the original code didn't know about. For example, in the sorteddict code I added an implementation for the __repr__ method and an associated doctest. Unlike iteration over sorteddict itself, I didn't bother to make __repr__ stable, so in that particular doctest it only tests the repr of a sorteddict with a single element. If that was fixed to make the repr stable it would be a real benefit for writing any doctests which want to produce a dictionary as a result. Another example would be if you had a library which serialised a dictionary to xml. There is nothing wrong with the library if it doesn't care about order, but if you have some other reason why you want the xml to be stable (e.g. because you store it in a version control system and want to compare revisions) then a sorteddict would allow you to impose that behaviour on the library from outside. Contrary to my earlier insistence that sorteddict is only really useful if you can have a key parameter, both of these examples simply want an arbitrary but defined order of iteration for dictionary keys. A much simpler sorteddict that has been discussed earlier would be sufficient. -- http://mail.python.org/mailman/listinfo/python-list
