Fast Resettable Flag Vector

http://upcoder.com/9/fast-resettable-flag-vector/

by crispweed • 12 years ago

7 2 12 years ago

TillE• 12 years ago

The "threshold" counter is a clever idea for optimizing a very specific situation, but it's extremely odd that there's no mention of std::bitset in this article. That won't give you an O(1) reset time, but it'll be a whole lot faster than a vector of bools.

Specifically, vector<bool>::clear() is not at all equivalent to bitset::reset()

pbnjay• 12 years ago

I agree a bitset is probably a better use here, but this may be a case where the requirements or actual usage numbers tilt the design this way?

I'm guessing if the size of the vector is very large, and the set bits are very sparse, then this threshold counter idea would be faster. But that would beg the question of why a bitset and tracked offsets (similar to the other idea mentioned in the article) wouldn't be fast either. Especially considering the caching effects of the bitset.

Fast Resettable Flag Vector

Related Stories