From: Nathan Myers (ncm-yahoospam_at_[hidden])
Date: 2001-12-29 15:59:06
"joel de guzman" wrote:
> From: "Nathan Myers" :
> >
> > A bit set implementation (sparse or otherwise) wouldn't be useful in my
> > application. It will be easy to add general set operations to extent_set
> > if anybody finds them valuable; in my application the greater efficiency
> > of the more-restricted interface matters, and the preconditions matter not
> > at all.
>
> The sparse bit set implemented as range-runs is a superset of
> the extent set. Internally it's almost alike. I haven't checked but
> performance wise, the extent set shouldn't be much faster than
> the range-run in the average case especially if you are not inserting
> or removing overlapping ranges anyway. I haven't done some profiling
> though and perhaps I am wrong.
Now that I have had an opportunity to read Joel's code, I can comment
further. BTW, it was not where he said, but here instead:
http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/spirit/spirit/boost/spirit/impl/chset.ipp
Joel's implementation special-cases char, signed char, and unsigned char,
and uses a bitmap representation for them. For others, it uses a sorted
vector of ranges, rather than a map indexed on the first element. As a
result, insert and erase operations involve block moves, but memory usage
is tight, where in extent_set<> everything involves tree operations.
Joel's uses reference counting, with copy-on-write to enable efficient
copy/assignment.
The important differences are more subtle. Joel's interface emphasizes
construction, copying, combining and membership tests; extent_set<>
emphasizes inserting and erasing ranges, and scanning the ranges present.
These differences are appropriate to their usage domains; Joel's for
representing character class membership, extent_set<> for resource
allocation. Joel's is a higher-level structure that could easily use
extent_set<> in its implementation, given a few more operators.
Along another dimension, Joel's uses native operators (e.g. less than)
where mine is parameterized on these operations like std::map<> itself.
I don't think we should let similarities in implementation details
distract us from what a component is for, and how well it serves that
purpose. Joel's design is highly evolved to be useful to aid parsing.
My extent_set<> is more primitive, in the zoological sense, and
lower-level, and potentially more generally applicable as it matures.
Nathan Myers
ncm at cantrip dot org