On Sep 13, 1:27 am, Mark Summerfield <[EMAIL PROTECTED]> wrote: > On 13 Sep, 00:03, Paul Rubin <http://[EMAIL PROTECTED]> wrote: > > > Mark Summerfield <[EMAIL PROTECTED]> writes: > > > I feel that Python lacks one useful data structure: an ordered > > > dictionary. > > > Do other Python programmers feel this lack? Is this worth a PEP? > > > Yes. It should use a functional data structure. > > Could you elaborate? > > Here's my impression of the postings so far: there are 3 categories of > response: > > (A) There is no need for such a thing. > > (B) It is useful, but so easy to implement that it needn't be in the > library. > > (C) It is worth having an ordered data structure of some kind. > > Regarding (A) and (B): I remember Python before it had the sets > module. "There's no need for sets, you can do them with dicts". > Thankfully sets are in the language and I for one use them > extensively. > > For (C) what I had in mind was: > > An API that is identical to a dict, with the few additional methods/ > behaviours listed below: > - If an item is inserted it is put in the right place (because the > underlying data structure, b*tree, skiplist or whatever is > intrinsically ordered by < on the key) > - Extra methods > key_at(index : int) -> key > item_at(index : int) -> (key, value) > value_at(index : int) -> value > set_value_at(index : int, value) # no return value necessary but > maybe key if convenient > od[x:y:z] -> list of values ordered by key # can read a slice but > not assign a slice > and maybe > keys_for(fromindex : int, uptobutexcludingindex : int) -> ordered > list of keys > > I've given examples of the use cases I envisage (and that I use in > both Python with my own ordered dict and in C++ with the map class) in > a previous posting, and I've shown the API I envisage above. I know > that some people might prefer ordering by value or the option of case- > insensitive ordering, but both these can be achieved using the API > above, e.g., > od[value.lower()] = value # case-insensitive ordering of list of > values > And as for duplicates there are two approaches I use: (1) make each > string unique as I showed in my previous post, or (2) use a value that > itself is a list, dict or set. > (As for those who have suggested an ordered data structure that isn't > a dict, I don't see a conflict, I'd be happy to see more data > structures in the collections module.) > > Is what I've suggested sufficient (and sufficiently general) for the > standard library?
Is the index the insertion order? The only use I have an ordered dictionary is to quickly determine that a sequence value is the first duplicate found (the structure can have millions of numbers) and then play back (so they don't have to be re-calculated) the sequence from the first duplicate to the end. So I would get the index when I find the duplicate and then iterate data[index:] to get the sequence in insertion order? > If it is not, what should be done, or is there some > other approach and API that would better provide the functionality > envisaged? -- http://mail.python.org/mailman/listinfo/python-list
