Ordering python sets

[bearophileHUGS at lycos.com]

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