David Abrahams wrote:
Phil Endecott wrote:
Further investigation with other workloads suggests that this bitset really works very well, and I note that it would be possible to write a specialisation of std::set<char> using it. This is probably worth pursuing.
Assuming you're willing to play fast-and-loose with the big-O of iterator increment (I am).
It's still O(1) - its execution time is bounded - so there's nothing to worry about even if you did care. Sketch of iterator-increment code: // the bit-set: uint64_t bits[4]; unsigned char inc_iterator(unsigned char c) { // Find the next set bit in bits after c. // libc defines ffs and fls to find the first and last set bit in a word. // At least ffs should be a single instruction on many machines (e.g. // the bsfl instruction on x86). // gcc has __builtin_ffs that should generate this. It also has // __builtin_ffsll for 64-bit words. Here I'm using flsll; if that // doesn't exist you can reverse the order of the bits - except that // you'll still want the other one for decrementing, hmmm. // Note that they return the bit number plus 1, or 0 if none is set. // The lowest interesting bit: int l = c+1; // Find any next bit in the same word as l: uint64_t w = bits[l>>6]>>(l&63); if (w) return flsll(w)-1+l; // Look at the remaining words: switch (l>>6) { case 0: w = bits[1]; if (w) return flsll(w)+63; // fall through case 1: w = bits[2]; if (w) return flsll(w)+127; // fall through case 2: w = bits[3]; if (w) return flsll(w)+191; // fall through } return end(); } Phil.