Mr.SpOOn: > Is there another convenient structure or shall I use lists and define > the operations I need?
<musings> As Python becomes accepted for more and more "serious" projects some more data structures can eventually be added to the collections module: - SortedSet, SortedDict: can be based on red-black trees. Require items to be sortable (them being hashable isn't required, but it's probably more safe that they are immutable). - Odict: a dict ordered according to insertion order. - Bidict: a unordered dict that allows O(1) retrieval on both keys and values (that are both unique). - Graph: a directed unsorted data structure like mine may be acceptable too. - Bitset: dynamically re-sizable and efficient in space and time, easy to implement in C. - Chain: simulates a double linked list, but its implementation can be similar to the current Deque but allowing not completely filled blocks in the middle too. (I haven't named it just List because there's a name clash with the list()). - I use all those data structures in Python programs, plus some more, like interval map, trie (and a dawg), persistent dict and persistent list, kd-tree, BK-tree, Fibonacci Heap, a rank & select, a disjoint- set, and maybe more. But those are uncommon enough to be left out of a standard library. - A problem with the Chain data structure is how to represent iterators in Python. I think this is a big problem, that I don't know how to solve yet. A possible solution is to make them owned by the Chain itself, but this makes the code slow down linearly in accord to the number of the iterators. If someone has a solution I'm all ears. </musings> Bye, bearophile -- http://mail.python.org/mailman/listinfo/python-list
