On Fri, 27 Jul 2012 15:40:35 +0200 Richard Guenther <richard.guent...@gmail.com> wrote: > Also it looks less efficient than sbitmap in the case when > your main operation is adding to the set and querying the set randomly.
How so? Adding/deleting a member to a sparseset is an O(1) operation, as is querying whether something is/isn't a member of a sparseset. Or are you talking about slower by some small constant factor? > It's space overhead is really huge - for smaller universes a smaller > SPARSESET_ELT_TYPE would be nice, templates to the rescue! I > wonder in which cases a unsigned HOST_WIDEST_FAST_INT sized > universe is even useful (but a short instead of an int is probably too > small ...) Yes, space overhead it large, but the extra space overhead allows sparseset to have O(1) operations for most set functions and O(N) for iterating over the members of the set. Obviously, you don't want to use this as in general set usage, but where speed is critical, it has its uses. Peter
