Boost logo

Boost :

From: Michael S. Tsirkin (mtsirkin_at_[hidden])
Date: 2000-07-06 00:43:16

Does there exist a library for union/find type of problem?

I have written a simple library that uses a forest of
splay trees to solve this in O(NlogN), with low memory overhead.

[This is not optimal in terms of speed, AFAIK , but memory overhead
would have to be higher]

The forest of splay trees class migth have other uses
(e.g. as a replacement to "map": it has lower memory overhead
per node as compared to the standard RB tree implementation-
-does not need the "color" bit- while providing amortized
O(ln N) time for operations, as opposed to O(ln N) for one
operation in an RB tree - as usual speed/ memory tradeoff).

It might also be useful for teaching teh data structures course :)

My implementation is templated to allow keeping different
types of data in the nodes, and uses STL-like iterators for access,
to simplify the usage.

I would like to know:
- Does someone have another implementation , that I can compare
  with in terms of memory/speed?
- Is someone interested in my implementation of this library?
  If yes, I think I could publish the library to teh public domain.
Thank you,

This message content is not part of Intel's views or affairs
Michael S. Tsirkin
    >   Four things are to be strengthened: Torah,and good deeds,
    >   prayer and one's good manners (Berachoth)

Boost list run by bdawes at, gregod at, cpdaniel at, john at