search for: sparsebitmapel

...or that is sparse by only > +/// storing the elements that have non-zero bits set. In order to make this I'd like to suggest the name SparseBitVector for this class, to correspond with the name of the existing BitVector class, which has a similar interface, but isn't sparse. > + SparseBitmapElement(unsigned Idx) { This misses an explicit keyword. > + if (Bitmap.Elements.empty()) > + { > + AtEnd = true; > + return; > + } Here and a few other places miss reformatting. > + template <int ElementSize> > + class Sp...

The attached patch adds a SparseBitmap implementation, which more or less works the same way as GCC's sparse bitmap. That is, we only store non-zero bits (broken up into elements of some bit size), and store the elements in a linked list. We keep track of the last accessed part of the linked list, so in-order tests/sets/resets are all constant time, rather than linear time. Set operations

...e non-zero bits set. In order to make this > > I'd like to suggest the name SparseBitVector for this class, to > correspond with the name of the existing BitVector class, which has > a similar interface, but isn't sparse. Sure, i have no problem with that. > > > + SparseBitmapElement(unsigned Idx) { > > This misses an explicit keyword. > Fixed! > > + if (Bitmap.Elements.empty()) > > + { > > + AtEnd = true; > > + return; > > + } > > Here and a few other places miss reformatting. Fi...

...9;m happy to give it a default value of 128. Interesting. Out of curiosity, do you happen to know roughly the sizes and sparsities where using 256-bit elements was faster? Looking at the implementation a little more, I see ElementList is a list of pointers to elements: + typedef std::list<SparseBitmapElement<ElementSize> *> ElementList; The extra pointer indirection is unfortunate; It'd be nice to have just a list of elements. I guess std::list's push_back always makes an element copy, which might not be ideal, though that could be weighed against the extra operator new call that...

...a sparse bitmap that is more memory intensive but much faster at random bit testing, and it was a win here as well, but not worth the memory cost :) > > Looking at the implementation a little more, I see ElementList is a list > of pointers to elements: > > + typedef std::list<SparseBitmapElement<ElementSize> *> ElementList; > > The extra pointer indirection is unfortunate; It'd be nice to have just > a list of elements. I guess std::list's push_back always makes an > element copy, which might not be ideal, though that could be weighed > against the extr...