3 ms·
I read Pugh's original paper in the late 90's and thought skip lists were a heck of lot simpler than red-black trees. Ended up using them all over Second Life's
by CoryOndrejka 17y ago
I read Pugh's original paper in the late 90's and thought skip lists were a heck of lot simpler than red-black trees. Ended up using them all over Second Life's original code base. By 2004 or so we switched the code over the STL and the LLSkipList class was retired to the dark depths of the CVS/SVN repository.
- tptacek 17y agoMaybe simpler, but better? Probably not so much. I wanted red-blacks on a project that couldn't use STL, and found that porting STLPort's <map> red-black to C-with-void*'s was pretty straightforward. Didn't even have to write and debug a red-black tree: <map> is bulletproof.
- eru 17y agoYou can even let the type system guarantee the red-black-tree laws. That's even better than idiot-proof. (http://www.cs.kent.ac.uk/people/staff/smk/redblack/rb.html http://www.cs.kent.ac.uk/people/staff/smk/redblack/rb.html has an implementation in Haskell.) Shouldn't trees be a nightmare to maintain without a GC? (Are you modifying in-place?)
- CoryOndrejka 17y agoIn hindsight that would have made a lot of sense :-) at the time we had looked at STL, but getting it to work across Debian and Win2k (which is what SL was running on at the time) looked like a PITA. Didn't even think about porting STL, especially since skiplists were so simple to implement.