This seems like the right thread to tell you I'm working on a new data type for Redis, that is, ordered sets: http://pastie.org/664270
Any feedback is really welcomed, for instance, do you know of better data structures to do the work? I'm using a red black tree and an hash table. The pastie above documents the specification more or less. Thanks
Why not use a hashtable with a linked list running through it (basically the python ordered dictionary class without the mapping). I believe ruby 1.9 uses these for its default hash type.
insert in order inside a linked list is O(N), or I missed something? Maybe they are using some more advanced kind of linked list where it's possible to run a binary search (like skip lists or alike).
Sorry this assumes that you wanted consistent ordering, not necessarily that you want to be able to create arbitrary ordering for it. So you'd have insert ordering.
Any feedback is really welcomed, for instance, do you know of better data structures to do the work? I'm using a red black tree and an hash table. The pastie above documents the specification more or less. Thanks